Fault-tolerant quantum computing

Remarkably, quantum systems with finite coherence times can be used to perform arbitrarily long and difficult quantum computations if the decoherence rate is less than some constant threshold. This accuracy threshold is a combinatorial property that does not depend on the size of the computation and exists even when the quantum noise process is adversarial or non-Markovian. Understanding the extent to which the accuracy threshold can be increased under physically realistic assumptions is one of the great open problems in the theory of quantum computation.

In particular, we are interested in (1) the influence of geometry on the accuracy threshold and (2) the behavior of the accuracy threshold for engineered systems, where constant and linear factors matter. Ultimately, we hope to integrate these concepts into a complete system architecture for a trapped-ion quantum computer.

Monte-Carlo simulation is one approach for studying classical and quantum fault-tolerance. We have developed simulation software based on this and other methods that applies to quantum circuits with and without local layouts. Our largest simulations take place on a 32 node Beowulf cluster.

An essential idea of fault-tolerance can be seen in a simple example. The 3 bit redundancy code copies each bit to three bits. Computation on the encoded bit triples proceeds as you would expect. Single bit flip errors are corrected by three fan-outs and three majority voting gates. Hence, the output of a circuit protected in this way decodes incorrectly only if two or more gates have experience soft failures. If we now encode one bit in nine copies and apply voters recursively, we can correct three arbitrary faults. Continuing in this way, we are lead to the concept of the threshold.

QC with free Clifford operations

Teleportation and measurement-based one-way quantum computing provides an alternative way to realize scalable quantum computers, rather than the standard unitary operation-based scheme. We are seeking novel teleportation schemes as well as one-way quantum computing models where free Clifford group operations are assumed. We are particularly interested in the converse statement of the Gottesman-Knill theorem with hope to identify the boundary between what is classical and what is quantum.

Applications of the Schur Basis to Quantum Algorithms

Many of the most successful quantum algorithms are designed around symmetries, for which group representation theory provides the mathematical foundation. These algorithms traditionally have achieved their speedups with the quantum Fourier transform (QFT), but this is not the only method known to exploit group symmetries. One concept which has been productive in mathematics, chemistry, physics, and recently quantum information theory, is known as Schur (or Schur-Weyl) duality. Early in this project we gave an efficient quantum circuit, which we call the Schur transform by analogy to the QFT, for transforming quantum data between two different forms: the standard computational basis and the Schur basis [1]. This allows quantum computers to efficiently compute using the Schur symmetries of quantum information. While this already has applications to quantum communication, one of our main goals is to find algorithmic uses of the transform. We are also looking at ways of using Schur symmetry in a purely mathematical sense to construct quantum algorithms, so that Schur duality would be used in the analysis of the algorithm but its implementation would not explicitly use the Schur transform [2].

During our search for possible new quantum algorithms based on the Schur transform, we studied properties of particular entangled states corresponding to graphs, and how they were transformed under symmetries such as those employed in quantum algorithms. Such entangled states can be used as resources to speed up quantum computations, in a manner which is vital to implementing quantum algorithms such that they can be robust against local gate failures.

We have recently discovered that such use of entanglement, to “teleport gates,” is not just a nice way to provide fault tolerance, but indeed, a necessary ingredient for fault tolerance, using any presently known quantum code [3]. This result answers a long-standing question: does a standard (“stabilizer”) quantum code exist, on which universal quantum computation can be accomplished without decoding the quantum data? The answer is “no,” and the reason has to do with fundamental properties of quantum codes, and allowable automorphisms on the groups involved.