Extensive quantum error correction is necessary in order to perform a useful computation on a noisy quantum computer. Moreover, quantum error correction must be implemented based on imperfect parity check measurements that may return incorrect outcomes or inject additional faults into the qubits. To achieve fault-tolerant error correction, Shor proposed to repeat the sequence of parity check measurements until the same outcome is observed sufficiently many times. Then, one can use this information to perform error correction. A basic implementation of this fault tolerance strategy requires$\Omega (r d^{2})$parity check measurements for a distance-$d$code defined by$r$parity checks. For some specific highly structured quantum codes, Bombin has shown that single-shot fault-tolerant quantum error correction is possible using only$r$measurements. In this work, we consider a phenomenological noise model for parity check measurements assuming that each bit of a codeword and the measurement outcome suffer from independent bit flips with some error rate$p$. For this model, we demonstrate that fault-tolerant quantum error correction can be achieved using$O(d \log (d))$measurements for any code with distance$d \geq \Omega (n^\alpha)$for some constant$\alpha > 0$. Moreover, we prove the existence of a sub-single-shot fault-tolerant quantum error correction scheme using fewer than$r$measurements. In some cases, the number of parity check measurements required for fault-tolerant quantum error correction is exponentially smaller than the number of parity checks defining the code. The short measurement sequences constructed generally have high weight and our phenomenological noise model is not realistic in this regime. Our error correction strategy could find applications to small codes and LDPC codes if one can manage to keep the weight of the measured parity checks low.

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 $\leq ε$ in $n^{O(1/ε^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.

Span programs form a linear-algebraic model of computation that is studied to prove classical lower bounds. Quantum query complexity is a coherent generalization for quantum algorithms of decision-tree complexity. It is characterized by a semidefinite program 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 equals the general adversary bound. Therefore, span program witness size and quantum query complexity are equivalent measures. In particular, quantum algorithms can be designed based on span programs.

Can a classical experimentalist command an untrusted quantum system to realize arbitrary quantum dynamics, aborting if it misbehaves? If so, then we could realize the dream of device-independent quantum cryptography: using untrusted quantum devices to establish a shared random key, with security based on the correctness of quantum mechanics. It would also allow for testing whether a claimed quantum computer is truly quantum. We prove a rigidity theorem for the famous Clauser-Horne-Shimony-Holt (CHSH) game, first formulated to provide a means of experimentally testing the violation of the Bell inequalities. The theorem shows that the only way for the two non-communicating quantum players to win many games played in sequence is if their shared quantum state is close to the tensor product of EPR states (Bell states) and their measurements are the optimal CHSH measurements on successive qubits. This theorem may be viewed as analogous to classical multi-linearity testing, in the sense that the outcome of local checks gives a characterization of a global object.

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.

We give an O(√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.

We show that any boolean function can be evaluated optimally by a quantum query algorithm that alternates a certain fixed, input-independent reflection with a second reflection that coherently queries the input string. Originally introduced for solving the unstructured search problem, this two-reflections structure 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 bounded-error 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 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 efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It further shows that span programs are equivalent to quantum query algorithms.

Consider the problem of evaluating an AND-OR formula on an N-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

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. The first result is motivated by a quantum algorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantum algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula-evaluation problem. We extend the analysis of the quantum algorithm for evaluating span programs. The previous analysis shows that a corresponding bipartite graph has a large spectral gap, but only works when applied to the composition of constant-size span programs. We show generally that properties of eigenvalue-zero eigenvectors in fact imply an "effective" spectral gap around zero. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more quantum algorithms.

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.

For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) 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.

The highest current estimates for the amount of noise a quantum computer can tolerate are based on fault-tolerance schemes relying heavily on postselecting on no detected errors. However, there has been no proof that these schemes give even a positive tolerable noise threshold. A technique to prove a positive threshold, for probabilistic noise models, is presented. The main idea is to maintain strong control over the distribution of errors in the quantum state at all times. This distribution has correlations which conceivably could grow out of control with postselection. But in fact, the error distribution can be written as a mixture of nearby distributions each satisfying strong independence properties, so there are no correlations for postselection to amplify

The quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two Hamiltonians. The quantum wave function can sometimes tunnel through significant obstacles. However it can also sometimes get stuck in local minima, even for fairly simple problems. An initial Hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing Markov transition rule. We study a physical system -- the Ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular SAT problem. We prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. Indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. Applying the adiabatic theorem therefore takes exponential time, even for this simple problem.