Perimeter Institute Quantum Discussions

To build a fully functioning quantum computer, it is necessary to encode quantum information to protect it from noise. Topological codes, such as the color code, naturally protect against local errors and represent our best hope for storing quantum information. Moreover, a quantum computer must also be capable of processing this information. Since the color code has many computationally valuable transversal logical gates, it is a promising candidate for a future quantum computer architecture.

In the talk, I will provide an overview of the color code. First, I will establish a connection between the color code and a well-studied model - the toric code. Then, I will explain how one can implement a universal gate set with the subsystem and the stabilizer color codes in three dimensions using techniques of code switching and gauge fixing. Next, I will discuss the problem of decoding the color code. Finally, I will explain how one can find the optimal error correction threshold by analyzing phase transitions in certain statistical-mechanical models.

The talk is based on http://arxiv.org/abs/1410.0069, http://arxiv.org/abs/1503.02065 and recent works with M. Beverland, F. Brandao, N. Delfosse, J. Preskill and K. Svore.

I will answer the question in the title. I will also describe a new quantum algorithm for Boolean formula evaluation and an improved analysis of an existing quantum algorithm for st-connectivity. Joint work with Stacey Jeffery. 

Information theory establishes the fundamental limits on data transmission, storage, and processing. Quantum information theory unites information theoretic ideas with an accurate quantum-mechanical description of reality to give a more accurate and complete theory with new and more powerful possibilities for information processing. The goal of both classical and quantum information theory is to quantify the optimal rates of interconversion of different resources. These rates are usually characterized in terms of entropies. However, nonadditivity of many entropic formulas often makes finding answers to information theoretic questions intractable. In a few auspicious cases, such as the classical capacity of a classical channel, the capacity region of a multiple access channel and the entanglement assisted capacity of a quantum channel, additivity allows a full characterization of optimal rates. Here we present a new mathematical property of entropic formulas, uniform additivity, that is both easily evaluated and rich enough to capture all known quantum additive formulas. We give a complete characterization of uniformly additive functions using the linear programming approach to entropy inequalities. In addition to all known quantum formulas, we find a new and intriguing additive quantity: the completely coherent information. We also uncover a remarkable coincidence---the classical and quantum uniformly additive functions are identical; the tractable answers in classical and quantum information theory are formally equivalent.

A central question in quantum computation is to identify which problems can be solved faster on a quantum computer. A Holy Grail of the field would be to have a theory of quantum speed-ups that delineates the physical mechanisms sustaining quantum speed-ups and helps in the design of new quantum algorithms. In this talk, we present such a toy theory for the study of a class of quantum algorithms for algebraic problems, including Shor’s celebrated factoring algorithm. Our theory is an extension of Gottesman’s stabilizer formalism based on elements of group and hypergroup theory. Using our methods, we develop classical simulation algorithms for Clifford-like circuits containing quantum Fourier transforms as well as new quantum algorithms for hidden symmetries and hyper-symmertry problems. During the talk, we will discuss the role of resources such as entanglement, interference and contextuality within our formalism and connect quantum speed-ups therein to the presence of precise algebraic structures.

Based on the following works:

[1] https://arxiv.org/abs/1210.3637
[2] https://arxiv.org/abs/1409.3208
[3] https://arxiv.org/abs/1409.4800
[4] https://arxiv.org/abs/1509.05806

Non-abelian anyons have drawn much interest due to their suspected existence in two-dimensional condensed matter systems and for their potential applications in quantum computation. In particular, a quantum computation can in principle be realized by braiding and fusing certain non-abelian anyons. These operations are expected to be intrinsically robust due to their topological nature. Provided the system is kept at a
temperature T lower than the spectral gap, the density of thermal excitations is suppressed by an exponential Boltzman factor. In contrast to the topological protection however, this thermal protection is not scalable: thermal excitations do appear at constant density for any non-zero temperature and so their presence is unavoidable as the size of the computation increases. Thermally activated anyons can corrupt the encoded
data by braiding or fusing with the computational anyons.

In the present work, we generalize a fault-tolerant scheme introduced by Harrington for the toric-code to the setting of non-cyclic modular anyons. We prove that the quantum information encoded in the fusion space of a non-abelian anyon system can be preserved for arbitrarily long times with poly-log overhead. In particular, our model accounts for noise processes which lead to the creation of anyon pairs from the vacuum, anyon diffusion, anyon fusion as well as errors in topological charge measurements.
Related Arxiv #: arXiv:1607.02159

Raussendorf introduced a powerful model of fault tolerant measurement based quantum computation, which can be understood as a layering (or “foliation”) of a multiplicity of Kitaev’s toric code.  I will discuss our generalisation of Raussendorf’s construction to an arbitrary CSS code.  We call this a Foliated Quantum Code.  Decoding this foliated construction is not necessarily straightforward, so I will discuss an example in which we foliate a family of finite-rate quantum turbo codes, and present the results of numerical simulations of the decoder performance.

If I have time, I will discuss some ongoing work (with Gavin Brennan) on relational time applied to topological quantum field theories, in particular, how anyonic systems with essentially trivial dynamics can still exhibit correlations that track “time".

In this talk I will introduce recent research into quantum clocks of finite dimension, with the focus on their accuracy, as determined by their dimension, coherence, and power consumption.

I will present arguments to bound the synchronization time of any quantum clock as a function of its dimension. In addition, quantum coherence appears to be necessary to saturate these bounds, as the synchronization time of incoherent clocks is seen to have a worse bound. In addition, I will review simple proposals for autonomous clocks built out of thermal machines, and demonstrate that the power consumption of thermal clocks determines the limit of their accuracy. Finally, I will introduce an example of a finite quantum clock that is able to control any quantum operation up to a calculable accuracy, and discuss whether it represents a best case scenario for quantum clocks.

We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity. Our results are given in the language of quantum interactive proof systems. Specifically, we show that any language in BQP has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover. Here, soundness is unconditional---i.e it holds even for computationally unbounded provers. Compared to prior work achieving similar results, our technique does not require the encoding of the input or of the computation; instead, we rely on encryption of the input (together with a method to perform computations on encrypted inputs), and show that the random choice between three types of input (defining a "computational run", versus two types of "test runs") suffice. As a proof technique, we use a reduction to an entanglement-based protocol; this enables a relatively simple analysis for a situation that has previously remained ambiguous in the literature.

We study restrictions on locality-preserving unitary logical gates for topological quantum codes in two spatial dimensions.  A locality-preserving operation is one which maps local operators to local operators --- for example, a  constant-depth quantum circuit of geometrically local gates, or evolution for a constant time governed by a geometrically-local bounded-strength Hamiltonian. Locality-preserving logical gates of topological codes are intrinsically fault tolerant because spatially localized errors remain localized, and hence sufficiently dilute errors remain correctable. By invoking general properties of two-dimensional topological field theories, we find that the locality-preserving logical gates are severely limited for codes which admit non-abelian anyons; in particular, there are no locality-preserving logical gates on the torus or the sphere with M punctures if the braiding of anyons is computationally universal. Furthermore, for Ising anyons on the M-punctured sphere, locality-preserving gates must be elements of the logical Pauli group. We derive these results by relating logical gates of a topological code to automorphisms of the Verlinde algebra of the corresponding anyon model, and by requiring the logical gates to be compatible with basis changes in the logical Hilbert space arising from local F-moves and the mapping class group. 

This is joint work with Oliver Buerschaper, Robert Koenig, Fernando Pastawski and Sumit Sijher.

Quantum adiabatic optimization (QAO) slowly varies an initial Hamiltonian with an easy-to-prepare ground-state to a final Hamiltonian whose ground-state encodes the solution to some optimization problem. Currently, little is known about the performance of QAO relative to classical optimization algorithms as we still lack strong analytic tools for analyzing its performance. In this talk, I will unify the problem of bounding the runtime of one such class of Hamiltonians -- so-called stoquastic Hamiltonians -- with questions about functions on graphs, heat diffusion, and classical sub-stochastic processes. I will introduce new tools for bounding the spectral gap of stoquastic Hamiltonians and, by exploiting heat diffusion, show that one of these techniques also provides an optimal and previously unknown gap bound for particular classes of graphs. Using this intuition and combining heat diffusion with classical sub-stochastic processes, I will offer a classical adiabatic algorithm that exhibits behavior typically considered "quantum", such as tunneling.

I will review a recent proposal for a top-down approach to AdS/CFT by A. Schwarz, which has the advantage of requiring few assumptions or extraneous knowledge, and may be of benefit to information theorists interested by the connections with tensor networks.  I will also discuss ways to extend this approach from the Euclidean formalism to a real-time picture, and potential relationships with MERA.

Scalable anyonic topological quantum computation requires the error-correction of non-abelian anyon systems. In contrast to abelian topological codes such as the toric code, the design, modelling, and simulation of error-correction protocols for non-abelian anyon codes is still in its infancy. Using a phenomenological noise model, we adapt abelian topological decoding protocols to the non-abelian setting and simulate their behaviour. We also show how to simulate error-correction in universal anyon models by exploiting the special structure of typical noise patterns.