Perimeter Institute Quantum Discussions

It is believed that active quantum error correction will be an essential ingredient to build a scalable quantum computer. The currently favored scheme is the surface code due to its high decoding threshold and efficient decoding algorithm. However, it suffers from large overheads which are even more severe when parity check measurements are subject to errors and have to be repeated. Furthermore, the number of encoded qubits in the surface code does not grow with system size, leading to a sub-optimal use of the physical qubits.

Finally, the decoding algorithm, while efficient, has non-trivial complexity and it is not clear whether it can be implemented in hardware that can keep up with the classical processing.

We present a class of low-density-parity check (LDPC) quantum codes which fix all three of the concerns mentioned above. They were first proposed in [1] and called 4D hyperbolic codes, as their definition is based on four-dimensional, curved geometries. They have the remarkable property that the number of encoded qubits grows linearly with system size, while their distance grows polynomially with system size, i.e. d~n a with 0.1 < a < 0.3. This is remarkable since it was previously conjectured that such codes could not exist [1]. Their structure allows for decoders which can deal with erroneous syndrome measurements, a property called single-shot error correction [2] as well as local decoding schemes [3].

Although [1] analyzed the encoding rate and distance of this code family abstractly, it is a non-trivial task to actually construct them. There is no known efficient deterministic procedure for obtaining small examples. Only single examples of reasonable size had been obtained previously [4]. These previous examples were part of different code families, so that it was not possible to determine a threshold. We succeeded to construct several small examples by utilizing a combination of randomized search and algebraic tools. We analyze the performance of these codes under several different local decoding procedures via Monte Carlo simulations. The decoders all share the property that they can be executed in parallel in O(1) time. Under the phenomenological noise model and including syndrome errors we obtain a threshold of ~5% which to our knowledge is the highest threshold among all local decoding schemes.

[1] A. Lubotzky, A. Guth, Journal Of Mathematical Physics 55, 082202 (2014).
[2] H. Bombin, Physical Review X 5 (3), 031043 (2015).
[3] M. Hastings, QIC 14, 1187 (2014).
[4] V. Londe, A. Leverrier, arXiv:1712.08578 (2017).

 

 

The area law for entanglement provides one of the most important connections between information theory and quantum many-body physics. It is not only related to the universality of quantum phases, but also to efficient numerical simulations in the ground state (i.e., the lowest energy state).  Various numerical observations have led to a strong belief that the area law is true for every non-critical phase in short-range interacting systems [1]. The so-called area-law conjecture states that the entanglement entropy is proportional to the surface region of subsystem if the ground state is non-critical (or gapped). 

However, the area law for long-range interacting systems is still elusive as the long-range interaction results in correlation patterns similar to the ones in critical phases. Here, we show that for generic non-critical one-dimensional ground states, the area law robustly holds without any corrections even under long-range interactions [2]. Our result guarantees an efficient description of ground states by the matrix-product state in experimentally relevant long-range systems, which justifies the density-matrix renormalization algorithm. In the present talk, I will give an overview of the results, and show ideas of the proof if the time allows. 

 

[1] J. Eisert, M. Cramer, and M. B. Plenio, ``Colloquium: Area laws for the entanglement entropy,'' Rev. Mod. Phys. 82, 277–306 (2010).

[2] T. Kuwahara and K. Saito, ``Area law of non-critical ground states in 1d long-range interacting systems,'' arXiv preprint arXiv:1908.11547 (2019),

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating player can try to bias the output bit towards a preferred value. A weak coin-flipping protocol has a bias ϵ if neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically ϵ=1/2, Mochon showed in 2007 [arXiv:0711.4114] that quantumly weak coin flipping can be achieved with arbitrarily small bias, i.e. ϵ(k)=1/(4k+2) for arbitrarily large k, and he proposed an explicit protocol approaching bias 1/6. So far, the best known explicit protocol is the one by Arora, Roland and Weis, with ϵ(2)=1/10 (corresponding to k=2) [STOC'19, p. 205-216]. In the current work, we present the construction of protocols approaching arbitrarily close to zero bias, i.e. ϵ(k) for arbitrarily large k. We connect the algebraic properties of Mochon's assignments---at the heart of his proof of existence---with the geometric properties of the unitaries whose existence he proved. It is this connection that allows us to find these unitaries analytically.

The quantum Fisher information (QFI) measures the amount of information that a quantum state carries about an unknown parameter. Given a quantum channel, its entanglement-assisted QFI is the maximum QFI of the output state assuming an input state over the system and an arbitrarily large ancilla. Consider N identical copies of a quantum channel, the channel QFI grows either linearly or quadratically with N asymptotically. Here we obtain a simple criterion that determines whether the scaling is linear or quadratic. In both cases, we found a quantum error correction protocol achieving the channel QFI asymptotically and an SDP to solve the optimal code.

Motivated by puzzles in quantum gravity AdS/CFT, Lenny Susskind posed the following question: supposing one had the technological ability to distinguish a macroscopic superposition of two given states |v> and |w> from incoherent mixture of those states, would one also have the technological ability to map |v> to |w> and vice versa?  More precisely, how does the quantum circuit complexity of the one task relate to the quantum circuit complexity of the other?  Here we resolve Susskind's question -- showing that the two complexities are essentially identical, even for approximate versions of these tasks, with the one caveat that a unitary transformation that maps |v> to |w> and |w> to -|v> need not imply any distinguishing ability.  Informally, "if you had the ability to prove Schrödinger's cat was in superposition, you'd necessarily also have the ability to bring a dead cat back to life."  I'll also discuss the optimality of this little result and some of its implications.

 

Paper (with Yosi Atia) in preparation

This talk is a progress report on ongoing research. I will explain what resource theories have to do with real algebraic geometry, and then present a preliminary result in real algebraic geometry which can be interpreted as a theorem on asymptotic and catalytic resource orderings.

It reproves the known criterion for asymptotic and catalytic majorization in terms of Rényi entropies, and generalizes it to any resource theory which satisfies a mild boundedness hypothesis. I will sketch the case of matrix majorization as an example.

 

We show that a generic many-body Hamiltonian can be uniquely reconstructed from a single pair of initial-final states under the unitary time evolution. Interesting it is, this method is not practical due to its high complexity. We then propose a practical method for Hamiltonian reconstruction from multiple pairs of initial-final states. The stability of this method is mathematically proved and numerically verified.

This work is joint with Liujun Zou and Timothy Hsieh.

Results from the first digital quantum simulation of an SU(2) gauge theory are presented. This was done by analytically constructing gauge-invariant states and implementing a Trotterized time evolution operator for that basis on superconducting hardware. By using error mitigation techniques, electric energy measurements could be reliably extracted following one Trotter-Suzuki time step. This work is a small but important step toward determining what field-theoretic calculations will be possible using near-term devices.

In quantum spin systems, the existence of a spectral gap above the ground state has strong implications for the low-energy physics. We survey recent results establishing spectral gaps in various frustration-free spin systems by verifying finite-size criteria. The talk is based on collaborations with Abdul-Rahman, Lucia, Mozgunov, Nachtergaele, Sandvik, Yang, Young, and Wang.

Connections between 2D gapped quantum phases and the anyon fusion theory have been proven in various ways under different settings. In this work, we introduce a new framework connecting them by only assuming a conjectured form of entanglement area law for 2D gapped systems. We show that one can systematically define topological charges and fusion rules from the area law alone, in a well-defined way. We then derive the fusion rules of charges satisfy all the axioms required in the algebraic theory of anyons. Moreover, even though we make no assumption about the exact value of the constant sub-leading term of the entanglement entropy, this term is shown to be equal to the logarithm of the total quantum dimension of the anyon theory we defined. 

 Holographic quantum error correcting codes (HQECC) have been proposed as toy models for the AdS/CFT correspondence, and exhibit many of the features of the duality. HQECC give a mapping of states and observables. However, they do not map local bulk Hamiltonians to local Hamiltonians on the boundary. In this work, we combine HQECC with Hamiltonian simulation theory to construct a bulk-boundary mapping between local Hamiltonians, whilst retaining all the features of the HQECC duality. This allows us to construct a duality between models, encompassing the relationship between bulk and boundary energy scales and time dynamics.

It also allows us to construct a map in the reverse direction: from local boundary Hamiltonians to the corresponding local Hamiltonian in the bulk. Under this boundary-to- bulk mapping, the bulk geometry emerges as an approximate, low-energy, effective theory living in the code-space of an (approximate) HQECC on the boundary. At higher energy scales, this emergent bulk geometry is modified in a way that matches the toy models of black holes proposed previously for HQECC. Moreover, the duality on the level of dynamics shows how these toy-model black holes can form dynamically.

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms.
This is joint work with Fernando Brandao (Caltech) and Daniel Stilck Franca (QMATH, Copenhagen).