Electrical Engineering Dept. EEB 528
University of Southern California (USC)
3740 McClintock Ave
Los Angeles, CA 90089-2565
(213)740-7229 ben.reichardt at usc

Span programs and quantum algorithms for st-connectivity and claw detection
A. Belovs, B. Reichardt. arXiv:1203.2603 [quant-ph], 2012. To appear in ESA 2012. slides

We introduce a span program that decides st-connectivity, and generalize the span program to develop quantum algorithms for several graph problems. First, we give an algorithm for st-connectivity that uses O(n d^{1/2}) quantum queries to the n x n adjacency matrix to decide if vertices s and t are connected, under the promise that they either are connected by a path of length at most d, or are disconnected. We also show that if T is a path, a star with two subdivided legs, or a subdivision of a claw, its presence as a subgraph in the input graph G can be detected with O(n) quantum queries to the adjacency matrix. Under the promise that G either contains T as a subgraph or does not contain T as a minor, we give O(n)-query quantum algorithms for detecting T either a triangle or a subdivision of a star. All these algorithms can be implemented time efficiently and, except for the triangle-detection algorithm, in logarithmic space. One of the main techniques is to modify the st-connectivity span program to drop along the way "breadcrumbs," which must be retrieved before the path from s is allowed to enter t.

Quantum query complexity of state conversion
T. Lee, R. Mittal, B. Reichardt, R. Spalek, M. Szegedy. Proc. FOCS 2011, arXiv:1011.3020 [quant-ph].

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm.

In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem.

Reflections for quantum query complexity: The general adversary bound is tight for every boolean function
B. Reichardt. Proc. SODA 2011, arXiv:1005.1601 [quant-ph]. slides

We show that any boolean function can be evaluated optimally by a bounded-error quantum query algorithm that alternates a certain fixed, input-independent reflection with coherent queries to the input bits (a second reflection). Originally introduced for the unstructured search problem, this two-reflections paradigm is therefore a universal feature of quantum algorithms.
Our proof goes via the general adversary bound, a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. By a quantum algorithm for evaluating span programs, this lower bound is known to be tight up to a sub-logarithmic factor. The extra factor comes from converting a continuous-time query algorithm into a discrete-query algorithm. We give a direct and simplified quantum algorithm based on the dual SDP, with a query complexity that matches the general adversary bound.
Therefore, the general adversary lower bound is tight; it is in fact an SDP for quantum query complexity. This implies that the bounded-error quantum query complexity of the composition f(g, ..., g) of two boolean functions f and g matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. It further shows that span programs are equivalent to quantum query algorithms.

Span programs and quantum query algorithms
B. Reichardt. ECCC TR10-110, 2010.

Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower bound is tight for every boolean function.
The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs imply an "effective" spectral gap around zero. We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor.
The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f(g, ..., g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms.
We give a second procedure for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.

Least span program witness size equals the general adversary lower bound on quantum query complexity
B. Reichardt. ECCC TR10-075, 2010.

Span programs form a linear-algebraic model of computation, with span program ``size" used in proving classical lower bounds. Quantum query complexity is a coherent generalization, for quantum algorithms, of classical decision-tree complexity. It is bounded below by a semi-definite program (SDP) known as the general adversary bound. We connect these classical and quantum models by proving that for any boolean function, the optimal ``witness size" of a span program for that function coincides exactly with the general adversary bound.

Estimating Turaev-Viro three-manifold invariants is universal for quantum computation
G. Alagic, S. Jordan, R. Koenig, B. Reichardt.
Phys. Rev. A82(4):040302, 2010 paperarXiv:1003.0923 [quant-ph], 2010.

The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-dimensional topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a relation between the task of distinguishing nonhomeomorphic 3-manifolds and the power of a general quantum computer.

Any NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer
A. Ambainis, A. Childs, B. Reichardt, R. Špalek, S. Zhang.
FOCS'07 special issue of SIAM J. Computing39(6):2513-2530, 2010, quant-ph/0703015. slides

For every NAND formula of size N, there is a bounded-error
N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that
evaluates this formula on a black-box input. Balanced, or ``approximately
balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is
optimal. It follows that the (2-o(1))-th power of the quantum query
complexity is a lower bound on the formula size, almost solving in the
positive an open problem posed by Laplante, Lee and Szegedy.

We give an O(sqrt n log n)-query quantum algorithm for evaluating size-n AND-OR formulas. Its running time is poly-logarithmically greater after efficient preprocessing. Unlike previous approaches, the algorithm is based on a quantum walk on a graph that is not a tree. Instead, the algorithm is based on a hybrid of direct-sum span program composition, which generates tree-like graphs, and a novel tensor-product span program composition method, which generates graphs with vertices corresponding to minimal zero-certificates.
For comparison, by the general adversary bound, the quantum query complexity for evaluating a size-n read-once AND-OR formula is at least Omega(sqrt n), and at most O(sqrt{n} log n / log log n). However, this algorithm is not necessarily time efficient; the number of elementary quantum gates applied between input queries could be much larger. Ambainis et al. have given a quantum algorithm that uses sqrt{n} 2^{O(sqrt{log n})} queries, with a poly-logarithmically greater running time.

Span-program-based quantum algorithm for evaluating unbalanced formulas
B. Reichardt.
TQC 2011, quant-ph/0907.1622, 2009. slides

The formula-evaluation problem is defined recursively. A formula's evaluation is the evaluation of a gate, the inputs of which are themselves independent formulas. Despite this pure recursive structure, the problem is combinatorially difficult for classical computers.
A quantum algorithm is given to evaluate formulas over any finite boolean gate set. Provided that the complexities of the input subformulas to any gate differ by at most a constant factor, the algorithm has optimal query complexity. After efficient preprocessing, it is nearly time optimal. The algorithm is derived using the span program framework. It corresponds to the composition of the individual span programs for each gate in the formula. Thus the algorithm's structure reflects the formula's recursive structure.

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
B. Reichardt.
Proc. FOCS 2009, Extended abstract, Full version: quant-ph/0904.2759, 2009.
slides

The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor.
In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantum algorithm for evaluating span programs with only a logarithmic query overhead on the witness size.

Span-program-based quantum algorithm for evaluating formulas
B. Reichardt, R. Špalek.
quant-ph/0710.2630,
2007, Proc. STOC'08.
slides

We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates
(e.g., NAND, 3-majority). The algorithm is optimal on read-once formulas for which each gate's inputs are balanced in a certain sense.
The main new tool is a correspondence between a classical linear-algebraic model of computation, "span programs," and weighted bipartite
graphs. A span program's evaluation corresponds to an eigenvalue-zero eigenvector of the associated graph. A quantum computer can therefore
evaluate the span program by applying spectral estimation to the graph.
For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization of
randomized alpha-beta pruning is known to be suboptimal. In contrast, our algorithm generalizes the optimal quantum AND-OR formula
evaluation algorithm and is optimal for evaluating the balanced ternary majority formula.

The quantum adiabatic optimization algorithm and local minima. Correction
B. Reichardt. STOC 2004.

Universal fault-tolerant quantum computation with only transversal gates and error correction
A. Paetnick, B. Reichardt.
Physical Review Letters111:090505, 2013,
arXiv:1304.3709 [quant-ph].

Transversal implementations of encoded unitary gates are highly desirable for fault-tolerant quantum computation. Though transversal gates alone cannot be computationally universal, they can be combined with specially distilled resource states in order to achieve universality. We show that "triorthogonal" stabilizer codes, introduced for state distillation by Bravyi and Haah [Phys. Rev. A 86, 052329 (2012)], admit transversal implementation of the controlled-controlled-Z gate. We then construct a universal set of fault-tolerant gates without state distillation by using only transversal controlled-controlled-Z, transversal Hadamard, and fault-tolerant error correction. We also adapt the distillation procedure of Bravyi and Haah to Toffoli gates, improving on existing Toffoli distillation schemes.

Systematic distillation of composite Fibonacci anyons using one mobile quasiparticle
B. Reichardt.
Quantum Information & Computation12:876-892, 2012,
arXiv:1206.0330 [quant-ph].

A topological quantum computer should allow intrinsically fault-tolerant quantum computation, but there remains uncertainty about how such a computer can be implemented. It is known that topological quantum computation can be implemented with limited quasiparticle braiding capabilities, in fact using only a single mobile quasiparticle, if the system can be properly initialized by measurements. It is also known that measurements alone suffice without any braiding, provided that the measurement devices can be dynamically created and modified. We study a model in which both measurement and braiding capabilities are limited. Given the ability to pull nontrivial Fibonacci anyon pairs from the vacuum with a certain success probability, we show how to simulate universal quantum computation by braiding one quasiparticle and with only one measurement, to read out the result. The difficulty lies in initializing the system. We give a systematic construction of a family of braid sequences that initialize to arbitrary accuracy nontrivial composite anyons. Instead of using the Solovay-Kitaev theorem, the sequences are based on a quantum algorithm for convergent search.

Fault-tolerant ancilla preparation and noise threshold lower bounds for the 23-qubit Golay code
A. Paetznick, B. Reichardt.
Quantum Information & Computation12:1034-1080, 2012, arXiv:1106.2190 [quant-ph].

In fault-tolerant quantum computing schemes, the overhead is often dominated by the cost of preparing codewords reliably. This cost generally increases quadratically with the block size of the underlying quantum error-correcting code. In consequence, large codes that are otherwise very efficient have found limited fault-tolerance applications. Fault-tolerant preparation circuits therefore are an important target for optimization.
We study the Golay code, a 23-qubit quantum error-correcting code that protects the logical qubit to a distance of seven. In simulations, even using a naive ancilla preparation procedure, the Golay code is competitive with other codes both in terms of overhead and the tolerable noise threshold. We provide two simplified circuits for fault-tolerant preparation of Golay code-encoded ancillas. The new circuits minimize error propagation, reducing the overhead by roughly a factor of four compared to standard encoding circuits. By adapting the malignant set counting technique to depolarizing noise, we further prove a threshold above 1.32 x 10^{-3} noise per gate.

Quantum computation with Turaev-Viro codes
R. Koenig, G. Kuperberg, B. Reichardt.
Annals of Physics 325(12):2707-2749, 2010,
arXiv:1002.2816 [quant-ph]

The Turaev-Viro invariant for a closed 3-manifold is defined as the contraction of a certain tensor network. The tensors correspond to tetrahedra in a triangulation of the manifold, with values determined by a fixed spherical category. For a manifold with boundary, the tensor network has free indices that can be associated to qudits, and its contraction gives the coefficients of a quantum error-correcting code. The code has local stabilizers determined by Levin and Wen. For example, applied to the genus-one handlebody using the Z_2 category, this construction yields the well-known toric code.
For other categories, such as the Fibonacci category, the construction realizes a non-abelian anyon model over a discrete lattice. By studying braid group representations acting on equivalence classes of colored ribbon graphs embedded in a punctured sphere, we identify the anyons, and give a simple recipe for mapping fusion basis states of the doubled category to ribbon graphs. We explain how suitable initial states can be prepared efficiently, how to implement braids, by successively changing the triangulation using a fixed five-qudit local unitary gate, and how to measure the topological charge. Combined with known universality results for anyonic systems, this provides a large family of schemes for quantum computation based on local deformations of stabilizer codes. These schemes may serve as a starting point for developing fault-tolerance schemes using continuous stabilizer measurements and active error-correction.

Error-detection-based quantum fault-tolerance threshold
B. Reichardt. Algorithmica55(3):517-556, 2009. paper

A major hurdle in building a quantum computer is overcoming noise, since quantum superpositions are fragile. Developed over the last couple of years, schemes for achieving fault tolerance based on error detection, rather than error correction, appear to tolerate as much as 3–6% noise per gate—an order of magnitude higher than previous procedures. However, proof techniques could not show that these promising fault-tolerance schemes tolerated any noise at all; the distribution of errors in the quantum state has correlations that conceivably could grow out of control.
With an analysis based on decomposing complicated probability distributions into mixtures of simpler ones, we rigorously prove the existence of constant tolerable noise rates (“noise thresholds”) for error-detection-based schemes. Numerical calculations indicate that the actual noise threshold this method yields is lower-bounded by 0.1% noise per gate.

Exact entanglement renormalization for string-net models
R. Koenig, B. Reichardt, G. Vidal.
Physical Review B79:195123, 2009, 6 pages, paper,
arXiv:0806.4583 [cond-mat.str-el]

We construct an explicit renormalization group (RG) transformation for Levin and Wen's string-net models on a hexagonal lattice. The transformation leaves invariant the ground-state "fixed-point" wave function of the string-net condensed phase. Our construction also produces an exact representation of the wave function in terms of the multi-scale entanglement renormalization ansatz (MERA). This sets the stage for efficient numerical simulations of string-net models using MERA algorithms. It also provides an explicit quantum circuit to prepare the string-net ground-state wave function using a quantum computer.

Quantum universality by state distillation
B. Reichardt. Quantum Inf. Comput.9:1030-1052, 2009. arXiv:quant-ph/0608085, slides

Quantum universality can be achieved using stabilizer operations and repeated preparation of certain ancilla states. Which ancilla states suffice for universality? We extend the range of single-qubit mixed states which are known to give universality, by using a simple parity-checking operation. Additionally, we display a two-qubit mixed state which is not a mixture of stabilizer states, but for which every postselected stabilizer reduction from two qubits to one outputs a mixture of stabilizer states. The main application of these techniques is to quantum fault tolerance. Our results imply that recent fault-tolerance threshold upper bounds based on the Gottesman-Knill theorem are tight.

Error-detection-based quantum fault tolerance against discrete Pauli noise
B. Reichardt. Ph.D. thesis, University
of California, 2006. quant-ph/0612004

A quantum computer -- i.e., a computer capable of manipulating data in
quantum superposition -- would find applications including factoring,
quantum simulation and tests of basic quantum theory. Since quantum
superpositions are fragile, the major hurdle in building such a computer
is overcoming noise.
Developed over the last couple of years, new schemes for achieving fault
tolerance based on error detection, rather than error correction, appear
to tolerate as much as 3-6% noise per gate -- an order of magnitude better
than previous procedures. But proof techniques could not show that these
promising fault-tolerance schemes tolerated any noise at all.
With an analysis based on decomposing complicated probability
distributions into mixtures of simpler ones, we rigorously prove the
existence of constant tolerable noise rates ("noise thresholds") for
error-detection-based schemes. Numerical calculations indicate that the
actual noise threshold this method yields is lower-bounded by 0.1% noise
per gate.

Postselection threshold against biased noise.
B. Reichardt.
Foundations of Computer Science (FOCS), 2006. quant-ph/0608018, slides

Quantum error correction of systematic errors using a quantum search framework
B. Reichardt, L. Grover. Phys. Rev. A72:042326, 2005. paper, quant-ph/0506242

Composite pulses are a quantum control technique for canceling out systematic control errors. We present a different composite pulse sequence inspired by quantum search. Our technique can correct a wider variety of systematic errors—including, for example, nonlinear over-rotational errors—than previous techniques. Concatenation of the pulse sequence can reduce a systematic error to an arbitrarily small level.

Quantum universality from magic states distillation applied to CSS codes.
B. Reichardt.
Quantum Inf. Proc.4(3):251-264, 2005 paperquant-ph/0411036, 2004. slides

Proof of the Double Bubble Conjecture in R^{n}.
B. Reichardt. Journal of Geometric Analysis18(1):172-191, 2008, paper, math.MG/0705.1601. slides

The least-area hypersurface enclosing and separating two given volumes in R^{n} is the standard double bubble.

Proof of the double bubble conjecture in R^{4} and certain higher dimensional cases. B. Reichardt, C. Heilmann, Y. Lai, A. Spielman. Pacific Journal of Mathematics208(2):347-366, 2003. paper

We prove that the standard double bubble is the minimizing double bubble in R^{4} and in certain higher dimensional cases, extending the recent work in R^{3} of Hutchings, Morgan, Ritoré and Ros.

Classical command of quantum systems
B. Reichardt, F. Unger, U. Vazirani.
Nature496:456-460, 2013. paper
Long version: A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games, arXiv:1209.0448 [quant-ph], 2012.

Quantum computation and cryptography both involve scenarios in which a user interacts with an imperfectly modelled or "untrusted" system. It is therefore of fundamental and practical interest to devise tests that reveal whether the system is behaving as instructed. In 1969, Clauser, Horne, Shimony and Holt proposed an experimental test that can be passed by a quantum-mechanical system but not by a system restricted to classical physics. Here we extend this test to enable the characterization of a large quantum system. We describe a scheme that can be used to determine the initial state and to classically command the system to evolve according to desired dynamics. The bipartite system is treated as two black boxes, with no assumptions about their inner workings except that they obey quantum physics. The scheme works even if the system is explicitly designed to undermine it; any misbehaviour is detected. Among its applications, our scheme makes it possible to test whether a claimed quantum computer is truly quantum. It also advances towards a goal of quantum cryptography: namely, the use of "untrusted" devices to establish a shared random key, with security based on the validity of quantum physics.

On parallel composition of zero-knowledge proofs with black-box quantum simulators
R. Jain, A. Kolla, G. Midrijanis, B. Reichardt.
Quantum Information and Computation9:513-532, 2009,
quant-ph/0607211.

Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator S, then L in BQP. Our result also applies to any language having a three-round quantum interactive proof (QIP), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator.
These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990).
Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when L notin BQP would imply an impossibly-good quantum search algorithm.

All-paths differential cryptanalysis of ideal Feistel and ideal Skipjack ciphers
B. Reichardt.
Manuscript.

Markov truncated differential cryptanalysis of Skipjack
B. Reichardt, D. Wagner.
SAC 2002, LNCS 2595. paper, slides.

A classical leash for a quantum tiger: Classical command of quantum systems via rigidity of CHSH games DIQIP-QCS Meeting, ICFO, Castelldefels, Spain 6/11/12

Quantum algorithms based on span programs: The general adversary bound is nearly tight for quantum query complexity CIFAR Quantum Information Processing Meeting 5/25/09

Quantum algorithms based on span programs: The general adversary bound is nearly tight for quantum query complexity UNM Center for Advanced Studies Seminar 4/16/09

Improved magic states distillation for quantum universality Quantum computing seminar, UC Berkeley 9/28/04

Recent schemes for increasing the fault-tolerance threshold Banff International Research Station Workshop on Quantum Computation and Information Theory 9/25/04