Quantum Information

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.

The gauge color code is a quantum error-correcting code with local syndrome measurements that, remarkably, admits a universal transversal gate set without the need for resource-intensive magic state distillation. A result of recent interest, proposed by Bombin, shows that the subsystem structure of the gauge color code admits an error-correction protocol that achieves tolerance to noisy measurements without the need for repeated measurements, so called single-shot error correction. Here, we demonstrate the promise of single-shot error correction by designing a two-part decoder and investigate its performance. We simulate fault-tolerant error correction with the gauge color code by repeatedly applying our proposed error-correction protocol to deal with errors that occur continuously to the underlying physical qubits of the code over the duration that quantum information is stored. We estimate a sustainable error rate, i.e. the threshold for the long time limit, of ~0.31% for a phenomenological noise model using a simple decoding algorithm.

In this talk I address the problem of simultaneously inferring unknown quantum states and unknown quantum measurements from empirical data. This task goes beyond state tomography because we are not assuming anything about the measurement devices. I am going to talk about the time and sample complexity of the inference of states and measurements, and I am going to talk about the robustness of the minimal Hilbert space dimension. Moreover, I will describe a simple heuristic algorithm (alternating optimization) to fit states and measurements to empirical data. For this algorithm the dataset does not need to be quantum. Hence, the proposed algorithm enables us to interpret general datasets from a quantum perspective. By analyzing movie ratings, we demonstrate the power of quantum models in the context of item recommendation which is a key discipline in machine learning. We observe that quantum models can compete with state-of-the-art algorithms for item recommendation. Based on joint work with Aram Harrow. Relevant preprints: arXiv:1412.7437 and arXiv:1510.02800.

The accumulated intuition from the last decades of research on quantum entanglement is that this phenomenon is highly non-robust, and very hard to maintain in the presence of de-cohering noise at non-zero temperatures. In recent years however, and motivated, in part, by a quest for a quantum analog of the PCP theorem researches have tried to establish, at least in theory, whether or not we can preserve quantum entanglement at "constant" temperatures that are independent of system size. This would imply that any quantum state with energy at most, say 0.05 of the total available energy of the Hamiltonian, would be highly-entangled.

A conjecture formalizing this notion was defined by Freedman and Hastings : called NLTS - it stipulates the existence of locally-defined quantum systems that retain long-range entanglement even at high temperatures. Such a conjecture does not only present a necessary condition for quantum PCP, but also poses a fundamental question on the nature of entanglement itself. To this date, no such systems were found, and moreover, it became evident that even embedding local Hamiltonians on robust, albeit "non-physical" topologies, namely expanders, does not guarantee entanglement robustness.

In this study, refute the intuition that entanglement is inherently fragile: we show that locally-defined quantum systems can, in fact, retain long-range entanglement at high temperatures.  To do this, we construct an explicit family of 7-local Hamiltonians, and prove that for such local Hamiltonians ANY low-energy state is hard to even approximately simulate by low-depth quantum circuits of depth o(log(n)). In particular, this resolves the NLTS conjecture in the affirmative, and suggests the existence of quantum systems whose low-energy states are not only highly-entangled but also "usefully"-entangled, in the computational-theoretic sense. 

I will introduce the unitarity, a parameter quantifying the coherence of a channel and show that it is useful for two reasons. First, it can be efficiently estimated via a variant of randomized benchmarking. Second, it captures useful information about the channel, such as the optimal fidelity achievable with unitary corrections and an improved bound on the diamond distance.

I’ll present new approaches to the problems of quantum control and quantum tomography wherein no classical simulation is required. The experiment itself performs the simulation (in situ) and, in a sense, guides itself to the correct solution. The algorithm is iterative and makes use of ideas from stochastic optimization theory.