Ben Reichardt
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
CV: pdf

Current & recent teaching EE 520 Intro. to quantum information processing (2016) EE 512 Stochastic processes (2014)
EE 599 Quantum algorithms (2012) CS 798 Adv. topics in quantum fault tolerance (2010)
QIC 710 Intro. to quantum information processing (2010) EE 441 Linear algebra (2013)
EE 364 Probability theory (2015) CS 360 Intro. to the theory of computation (2011)


Publications
Quantum Algorithms
Fault-tolerant Computing
Geometry
Cryptography

Quantum Algorithms   [Show/hide abstracts]
Span programs and quantum algorithms for st-connectivity and claw detection
    A. Belovs, B. Reichardt.   arXiv:1203.2603 [quant-ph], 2012. European Symp. on Algorithms (ESA) 2012, LNCS vol. 7501, pp. 193-204. 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. A 82(4):040302, 2010 paper arXiv: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 N1/2+o(1) on a quantum computer
    A. Ambainis, A. Childs, B. Reichardt, R. Špalek, S. Zhang.   FOCS'07 special issue of SIAM J. Computing 39(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.

Faster quantum algorithm for evaluating game trees
    B. Reichardt.   Proc. SODA 2011, quant-ph/0907.1623. slides

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.
Fault-Tolerant Quantum Computing   [Show/hide abstracts]
Fault-tolerant quantum computation with few qubits
    R. Chao, B. Reichardt.   arXiv:1705.05365 [quant-ph], 2017.

Reliable qubits are difficult to engineer, but standard fault-tolerance schemes use seven or more physical qubits to encode each logical qubit, with still more qubits required for error correction. The large overhead makes it hard to experiment with fault-tolerance schemes with multiple encoded qubits.
The 15-qubit Hamming code protects seven encoded qubits to distance three. We give fault-tolerant procedures for applying arbitrary Clifford operations on these encoded qubits, using only two extra qubits, 17 total. In particular, individual encoded qubits within the code block can be targeted. Fault-tolerant universal computation is possible with four extra qubits, 19 total. The procedures could enable testing more sophisticated protected circuits in small-scale quantum devices.
Our main technique is to use gadgets to protect gates against correlated faults. We also take advantage of special code symmetries, and use pieceable fault tolerance.

Quantum error correction with only two extra qubits
    R. Chao, B. Reichardt.   arXiv:1705.02329 [quant-ph], 2017.

Noise rates in quantum computing experiments have dropped dramatically, but reliable qubits remain precious. Fault-tolerance schemes with minimal qubit overhead are therefore essential. We introduce fault-tolerant error-correction procedures that use only two ancilla qubits. The procedures are based on adding "flags" to catch the faults that can lead to correlated errors on the data. They work for various distance-three codes.
In particular, our scheme allows one to test the [[5,1,3]] code, the smallest error-correcting code, using only seven qubits total. Our techniques also apply to the [[7,1,3]] and [[15,7,3]] Hamming codes, thus allowing to protect seven encoded qubits on a device with only 17 physical qubits.

Universal fault-tolerant quantum computation with only transversal gates and error correction
    A. Paetznick, B. Reichardt.   Physical Review Letters 111: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 & Computation 12: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 & Computation 12: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.   Algorithmica 55(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 B 79: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
Fault-tolerance threshold for a distance-three quantum code.
    B. Reichardt.   ICALP 2006, LNCS 4051. quant-ph/0509203, slides
Quantum error correction of systematic errors using a quantum search framework
    B. Reichardt, L. Grover.   Phys. Rev. A 72: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 paper quant-ph/0411036, 2004. slides
Improved ancilla preparation scheme increases fault-tolerant threshold
    B. Reichardt.   quant-ph/0406025, 2004.

Geometry   [Show/hide abstracts]
Proof of the Double Bubble Conjecture in Rn.
    B. Reichardt.   Journal of Geometric Analysis 18(1):172-191, 2008, paper, math.MG/0705.1601. slides

The least-area hypersurface enclosing and separating two given volumes in Rn is the standard double bubble.

Proof of the double bubble conjecture in R4 and certain higher dimensional cases.
    B. Reichardt, C. Heilmann, Y. Lai, A. Spielman.   Pacific Journal of Mathematics 208(2):347-366, 2003. paper

We prove that the standard double bubble is the minimizing double bubble in R4 and in certain higher dimensional cases, extending the recent work in R3 of Hutchings, Morgan, Ritoré and Ros.


Cryptography   [Show/hide abstracts]
Overlapping qubits
    R. Chao, B. Reichardt, C. Sutherland, T. Vidick.   arXiv:1701.01062 [quant-ph], 2017.

An ideal system of n qubits has 2^n dimensions. This exponential grants power, but also hinders characterizing the system's state and dynamics. We study a new problem: the qubits in a physical system might not be independent. They can "overlap," in the sense that an operation on one qubit slightly affects the others.
We show that allowing for slight overlaps, n qubits can fit in just polynomially many dimensions. (Defined in a natural way, all pairwise overlaps can be <=eps in n^O(1/eps^2) dimensions.) Thus, even before considering issues like noise, a real system of n qubits might inherently lack any potential for exponential power.
On the other hand, we also provide an efficient test to certify exponential dimensionality. Unfortunately, the test is sensitive to noise. It is important to devise more robust tests on the arrangements of qubits in quantum devices.

Test for a large amount of entanglement, using few measurements
    R. Chao, B. Reichardt, C. Sutherland, T. Vidick.   arXiv:1610.00771 [quant-ph], 2016.

Bell-inequality violations establish that two systems share some quantum entanglement. We give a simple test to certify that two systems share an asymptotically large amount of entanglement, n EPR states. The test is efficient: unlike earlier tests that play many games, in sequence or in parallel, our test requires only one or two CHSH games. One system is directed to play a CHSH game on a random specified qubit i, and the other is told to play games on qubits {i,j}, without knowing which index is i.
The test is robust: a success probability within delta of optimal guarantees distance O(n^{5/2} sqrt{delta}) from n EPR states. However, the test does not tolerate constant delta; it breaks down for delta = Omega~(1/sqrt{n}). We give an adversarial strategy that succeeds within delta of the optimum probability using only O~(delta^{-2}) EPR states.

Classical command of quantum systems
    B. Reichardt, F. Unger, U. Vazirani.   Nature 496: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 Computation 9: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.


Selected talks
Title and VenueSlides/Video
2017Overlapping qubits
Innovations in Theoretical CS (ITCS) 1/11/17		video
Tests for small quantum devices
QuICS seminar, UMD 4/12/17
Fault-tolerant quantum computation with few qubits
IQI seminar, Caltech 5/30/17		slides
2015Classical command of quantum systems
UC Riverside 1/26/15
Overlapping qubits
Quantum Hamiltonian Complexity Reunion workshop
Simons Inst., UC Berkeley, 5/4/15		slides
Fault tolerance tutorial
Canadian Summer School on Quantum Information (CSSQI), U. Toronto, 8/12/15		slides
2014Quantum error correction tutorial
1. Codes and stabilizer algebra
2. Fault-tolerance schemes & threshold theorems
3. Surface code

QUTE-Europe Summer School, Smolenice, Slovakia 8/22-8/24/14		slides 1
slides 2
slides 3
Classical command of quantum systems
Microsoft Research QuArC Workshop on Quantum Algorithms & Devices
Redmond, WA 7/16/14
2013Classical command of quantum systems
QCrypt 2013, Waterloo 8/7/13		slides, video
Classical command of quantum systems
CIFAR Quantum Information Processing Meeting, Edmonton 2/19/13		slides
Tests for quantum entanglement and dynamics
Heilbronn Quantum Algorithms Day, University of Bristol 4/25/13		slides
A classical leash for a quantum system
Workshop on Quantum Hamiltonian Complexity, UC Berkeley 2/19/13		slides
Classical command of quantum systems
MHI EE Research Festival, USC 2/6/13		slides
Classical command of quantum systems
Quantum Information Processing (QIP) 2013, Tsinghua University, Beijing 1/21/13		slides
A classical leash for a quantum system:
Command of quantum systems via rigidity of CHSH games
Innovations in Theoretical Computer Science (ITCS) 2013, UC Berkeley 1/11/13		slides
2012A classical leash for a quantum tiger: Key distribution with minimal assumptions
IQI Seminar, Caltech 10/17/12
The adversary bound, span programs, learning graphs and quantum algorithms
QIS Workshop in Computer & Natural Sciences, U. Maryland 9/28/12		slides
Quantum algorithm for deciding st-connectivity
DIQIP-QCS Meeting, ICFO, Castelldefels, Spain 6/11/12
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		slides
A classical leash for a quantum tiger:
Classical command of quantum systems via rigidity of sequential CHSH games
USC Quantum Information & Condensed Matter Seminar, USC 4/27/12
Quantum algorithm for deciding st-connectivity
Recent Progress in Quantum Algorithms, U. Waterloo & Perimeter Institute 4/11/12		slides, video
2011Key distribution with minimal assumptions
UC Berkeley 11/7/11
Query complexity of converting states
Workshop on Quantum Computer Science, Montreal 10/7/11		notes
Self-testing for sequential CHSH games
Dagstuhl seminar on Quantum Cryptanalysis, Wadern, Germany 9/23/11		notes
Span-program-based quantum algorithm for evaluating unbalanced formulas
TQC 2011, Madrid 5/25/11		slides
Optimal algorithms for quantum computers based on a norm
Sandia National Labs, Albuquerque, NM 5/16/11
How to compose quantum algorithms
HRL Labs, Malibu 5/12/11
Quantum computers: Algorithms and implementations
USC, Los Angeles 3/21/11
The query complexity of generating quantum states
UC Berkeley 2/25/11
Faster Quantum Algorithm for Evaluating Game Trees
SODA 2011, San Francisco 1/23/11		slides
Reflections for quantum query algorithms
SODA 2011, San Francisco 1/23/11		slides
Quantum query complexity
QIP 2011 invited tutorial, Singapore 1/9/11		slides
2010A semi-definite program for quantum query complexity
2nd Barriers in Computational Complexity Workshop, Princeton 8/28/10		video, slides & notes
Span programs and optimal quantum query algorithms
APS March Meeting 2010, Portland 3/15/10
Equivalent quantum computer models, for algorithms and implementations
NIST 2/17/10
Span programs and quantum algorithms
QIP 2010 invited talk 1/19/10		video
2009Span programs & quantum algorithms
HRL Labs 12/10/09
Faster quantum algorithm for evaluating game trees
Caltech 11/17/09
Span programs & quantum algorithms
MIT 11/09/09
Span programs and quantum query complexity:
The general adversary bound is nearly tight for every boolean function
FOCS 09 10/27/09		video
Span programs and quantum query algorithms
Institute for Advanced Study, Princeton 9/29/09		video
Span programs and quantum query algorithms
KITP, Santa Barbara 9/18/09		video
Span programs and quantum query complexity
Waterloo Combinatorics & Optimization Dept. Tutte seminar 8/14/09
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		slides
Semi-definite programs for span programs
UC Berkeley quantum lunch seminar 3/6/09
2008Exact entanglement renormalization for string-net models
IQC colloquium 10/6/08
Span-program-based quantum algorithm for formula evaluation
STOC 2008, Victoria, BC
Making quantum computers fault tolerant
USC EE 4/9/08
Making quantum computers fault tolerant
UC Davis math colloqium 3/17/08		slides
Research directions in quantum computing
UC Berkeley BNNI 3/14/08
Making quantum computers fault tolerant
UC Berkeley BNNI 3/13/08
Formula evaluation using a quantum computer, and Factories for quantum fault tolerance
University of Waterloo 2/11/08
Span-program-based quantum algorithm for evaluating formulas
UC Berkeley 2/1/08
Span-program-based quantum algorithm for formula evaluation
QIP 2008 invited talk		slides
2007Span program-based quantum algorithm for evaluating formulas
NEC/Rutgers Quantum Computation Group seminar 10/25/07
Quantum algorithm for evaluating span programs
WQACT 2008, Singapore
Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
FOCS 2007		slides
Quantum algorithms for formula evaluation
AQIS 2007 invited talk, Kyoto, Japan		slides
Proof of the Double Bubble Conjecture in Rn
Mathfest 2007, San Jose		slides
...
Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer
NEC Labs 7/07		slides
Error-detection-based quantum fault tolerance
Perimeter Institute FTQC 2 Workshop, Waterloo 6/07
Error-detection-based quantum fault tolerance against discrete Pauli noise
USC EE 5/31/07
Universality by distillation
QIP 2007, Brisbane, Australia		slides
2006Postselection threshold against biased noise
FOCS 2006, Berkeley		slides
A probabilistic mixing lemma and quantum fault tolerance
UC Berkeley Theory Lunch 9/13/06
Fault-tolerance threshold for a distance-three quantum code
ICALP 2006, Venice, Italy 7/10/06		slides
Quantum fault tolerance against probabilistic Pauli noise
UC Berkeley Theory seminar dissertation talk 5/15/06
Techniques for fault-tolerant quantum error correction
UC Berkeley quantum seminar 3/14/06
Techniques for fault-tolerant quantum error correction
NIST Boulder Workshop on Trapped Ion Quantum Computing 2006		slides
Rigorous fault-tolerance thresholds
QIP 2006 invited talk, Paris		slides
...
2005Fault-tolerance threshold for a distance-three quantum code
CIAR QIP program meeting invited talk 12/8/05		slides
Threshold for the distance three Steane quantum code
Caltech 10/05		slides
Quantum universality from magic states distillation applied to CSS codes
IQC, University of Waterloo 6/21/05		slides
Quantum algorithms, complexity, and robustness
DARPA Quantum Information Science and Technology (QuIST) program review,
St Augustine, FL 4/05
Improved "magic states" distillation for quantum universality
Toronto Quantum Information Seminar 2/4/05		slides
Fault-tolerant universality from fault-tolerant stabilizer operations and noisy ancillas
ARDA program review invited talk, Bell Labs 1/20/05		slides
2004Recent schemes for increasing the fault-tolerance threshold
Bay Area Theory Symposium, Berkeley 12/10/04		slides
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		notes
2002Markov truncated differential cryptanalysis of Skipjack
Selected Areas in Cryptography (SAC) 2002, St. John's, Newfoundland 8/15/02		slides