Perimeter Institute Quantum Discussions

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm.
Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest.

Joint work with Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar

We reconsider the black hole firewall puzzle, emphasizing that quantum error-correction, computational complexity, and pseudorandomness are crucial concepts for understanding the black hole interior. We assume that the Hawking radiation emitted by an old black hole is pseudorandom, meaning that it cannot be distinguished from a perfectly thermal state by any efficient quantum computation acting on the radiation alone. We then infer the existence of a subspace of the radiation system which we interpret as an encoding of the black hole interior. This encoded interior is entangled with the late outgoing Hawking quanta emitted by the old black hole, and is inaccessible to computationally bounded observers who are outside the black hole. Specifically, efficient operations acting on the radiation, those with quantum computational complexity polynomial in the entropy of the remaining black hole, commute with a complete set of logical operators acting on the encoded interior, up to corrections which are exponentially small in the entropy. Thus, under our pseudorandomness assumption, the black hole interior is well protected from exterior observers as long as the remaining black hole is macroscopic. On the other hand, if the radiation is not pseudorandom, an exterior observer may be able to create a firewall by applying a polynomial-time quantum computation to the radiation.

Given a vector in a representation, can it be distinguished from zero by an invariant polynomial? This classical question in invariant theory relates to a diverse set of problems in mathematics and computer science. In quantum information, it captures the quantum marginal problem and recent bounds on tensor ranks. We will see that the general question can be usefully thought of as an optimization problem and discuss how this perspective leads to efficient algorithms for solving it.

Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n-qubit group, one often resorts to t-designs. Unitary t-designs mimic the Haar-measure up to t-th moments. It is known that Clifford operations can implement at most 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. We find that it suffices to inject O(t^4 log^2(t) log(1/ε)) many non-Clifford gates into a polynomial-depth random Clifford circuit to obtain an ε-approximate t-design. Strikingly, the number of non-Clifford gates required is independent of the system size – asymptotically, the density of non-Clifford gates is allowed to tend to zero. We also derive novel bounds on the convergence time of random Clifford circuits to the t-th moment of the uniform distribution on the Clifford group. Our proofs exploit a recently developed variant of Schur-Weyl duality for the Clifford group, as well as bounds on restricted spectral gaps of averaging operators. Joint work with J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, and D. Gross.

Given the large push by academia and industry (e.g., IBM and Google), quantum computers with hundred(s) of qubits are at the brink of existence with the promise of outperforming any classical computer. Demonstration of computational advantages of noisy near-term quantum computers over classical computers is an imperative near-term goal. The foremost candidate task for showing this is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. This is exactly the task that recently Google experimentally performed on 53-qubits.

Stockmeyer's theorem implies that efficient sampling allows for estimation of probability amplitudes. Therefore, hardness of probability estimation implies hardness of sampling. We prove that estimating probabilities to within small errors is #P-hard on average (i.e. for random circuits), and put the results in the context of previous works.

Some ingredients that are developed to make this proof possible are construction of the Cayley path as a rational function valued unitary path that interpolate between two arbitrary unitaries, an extension of Berlekamp-Welch algorithm that efficiently and exactly interpolates rational functions, and construction of probability distributions over unitaries that are arbitrarily close to the Haar measure.

Basic statistical properties of quantum many-body systems in thermal equilibrium can be obtained from their partition function. In this talk, I will present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this temperature. This shows that the transition in the phase of a quantum system is also accompanied by a transition in the computational hardness of estimating its statistical properties. The key to this result is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. I will also discuss the relation between these complex zeros and another signature of the thermal phase transition, namely, the exponential decay of correlations. I will show that in a system of n particles above the phase transition point, where the complex zeros are far from the real axis, the correlation between two observables whose distance is at least log(n) decays exponentially. This is based on joint work with Aram Harrow and Saeed Mehraban.

Schur-Weyl duality is a ubiquitous tool in quantum information. At its heart is the statement that the space of operators that commute with the tensor powers of all unitaries is spanned by the permutations of the tensor factors. In this work, we describe a similar duality theory for tensor powers of Clifford unitaries. The Clifford group is a central object in many subfields of quantum information, most prominently in the theory of fault-tolerance. The duality theory has a simple and clean description in terms of finite geometries. We demonstrate its effectiveness in several applications: (1) We resolve an open problem in quantum property testing by showing that "stabilizerness" is efficiently testable: There is a protocol that, given access to six copies of an unknown state, can determine whether it is a stabilizer state, or whether it is far away from the set of stabilizer states. We give a related membership test for the Clifford group. (2) We find that tensor powers of stabilizer states have an increased symmetry group. We provide corresponding de Finetti theorems, showing that the reductions of arbitrary states with this symmetry are well-approximated by mixtures of stabilizer tensor powers (in some cases, exponentially well). (3) We show that the distance of a pure state to the set of stabilizers can be lower-bounded in terms of the sum-negativity of its Wigner function. This gives a new quantitative meaning to the sum-negativity (and the related mana) -- a measure relevant to fault-tolerant quantum computation. The result constitutes a robust generalization of the discrete Hudson theorem. (4) We show that complex projective designs of arbitrary order can be obtained from a finite number (independent of the number of qudits) of Clifford orbits. To prove this result, we give explicit formulas for arbitrary moments of random stabilizer states. (5) Lastly, we comment on the structure of the irreducible representations of the Clifford group.

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),

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