Search for: All records

Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences. To learn the Gibbs state of local Hamiltonians at any inverse temperature β, the state-of-the-art provable algorithms fall short of the optimal sample and computational complexity, in sharp contrast with the locality and simplicity in the classical cases. In this work, we present a learning algorithm that learns each local term of a n-qubit D-dimensional Hamiltonian to an additive error ϵ with sample complexity $$\tilde{O}\left(\frac{e^{\mathrm{poly}(\beta)}}{\beta^2\epsilon^2}\right)\log(n)$$. The protocol uses parallelizable local quantum measurements that act within bounded regions of the lattice and near-linear-time classical post-processing. Thus, our complexity is near optimal with respect to n, ϵ and is polynomially tight with respect to β. We also give a learning algorithm for Hamiltonians with bounded interaction degree with sample and time complexities of similar scaling on n but worse on β, ϵ. At the heart of our algorithm is the interplay between locality, the Kubo-Martin-Schwinger condition, and the operator Fourier transform at arbitrary temperatures. 

QAC0 is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by Moore as a quantum counterpart of AC0, along with the conjecture that QAC0 circuits cannot compute PARITY. In this work, we make progress on this long-standing conjecture: we show that any depth-𝑑 QAC0 circuit requires 𝑛^{1+3^{−𝑑}} ancillae to compute a function with approximate degree Θ(𝑛), which includes PARITY, MAJORITY and MOD_𝑘. We further establish superlinear lower bounds on quantum state synthesis and quantum channel synthesis. This is the first lower bound on the super-linear sized QAC0. Regarding PARITY, we show that any further improvement on the size of ancillae to 𝑛^{1+exp(−𝑜(𝑑))} would imply that PARITY ∉ QAC0. These lower bounds are derived by giving low-degree approximations to QAC0 circuits. We show that a depth-𝑑 QAC0 circuit with 𝑎 ancillae, when applied to low-degree operators, has a degree (𝑛 + 𝑎)^{1−3^{−𝑑}} polynomial approximation in the spectral norm. This implies that the class QLC0, corresponding to linear size QAC0 circuits, has an approximate degree 𝑜(𝑛). This is a quantum generalization of the result that LC0 circuits have an approximate degree 𝑜(𝑛) by Bun, Kothari, and Thaler. Our result also implies that QLC0 ≠ NC1. 

We define a map from an arbitrary quantum circuit to a local Hamiltonian whose ground state encodes the quantum computation. All previous maps relied on the Feynman-Kitaev construction, which introduces an ancillary ‘clock register’ to track the computational steps. Our construction, on the other hand, relies on injective tensor networks with associated parent Hamiltonians, avoiding the introduction of a clock register. This comes at the cost of the ground state containing only a noisy version of the quantum computation, with independent stochastic noise. We can remedy this—making our construction robust—by using quantum fault tolerance. In addition to the stochastic noise, we show that any state with energy density exponentially small in the circuit depth encodes a noisy version of the quantum computation with adversarial noise. We also show that any ‘combinatorial state’ with energy density polynomially small in depth encodes the quantum computation with adversarial noise. This serves as evidence that any state with energy density polynomially small in depth has a similar property. As an application, we show that contracting injective tensor networks to additive error is BQP-hard. We also discuss the implication of our construction to the quantum PCP conjecture, combining with an observation that QMA verification can be done in logarithmic depth. 

Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit shallow quantum circuit 𝑈 (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of 𝑈. We also provide a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit state |𝜓⟩ = 𝑈|0^𝑛⟩ prepared by a shallow quantum circuit 𝑈 (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of |𝜓⟩. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate. 

We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, alternate learning models to tomography and learning classical functions encoded as quantum states. We highlight how these results are paving the way for a highly successful theory with a range of exciting open questions. To this end, we distill 25 open questions from these results. 

The NLTS (No Low-Energy Trivial State) conjecture of Freedman and Hastings posits that there exist families of Hamiltonians with all low energy states of non-trivial complexity (with complexity measured by the quantum circuit depth preparing the state). We prove this conjecture by showing that a particular family of constant-rate and linear-distance qLDPC codes correspond to NLTS local Hamiltonians, although we believe this to be true for all current constructions of good qLDPC codes. 

We prove concentration bounds for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from \cite{DMRF22}; (ii) injective matrix product states; (iii) output states of dense Hamiltonian evolution, i.e. states of the form e ι H ( p ) ⋯ e ι H ( 1 ) | ψ 0 ⟩ for any n -qubit product state | ψ 0 ⟩ , where each H ( i ) can be any local commuting Hamiltonian satisfying a norm constraint, including dense Hamiltonians with interactions between any qubits. Our proofs use polynomial approximations to show that these states are close to local operators. This implies that the distribution of the Hamming weight of a computational basis measurement (and of other related observables) concentrates.An example of (iii) are the states produced by the quantum approximate optimisation algorithm (QAOA). Using our concentration results for these states, we show that for a random spin model, the QAOA can only succeed with negligible probability even at super-constant level p = o ( log ⁡ log ⁡ n ) , assuming a strengthened version of the so-called overlap gap property. This gives the first limitations on the QAOA on dense instances at super-constant level, improving upon the recent result [BGMZ22]. 

The NLTS (No Low-Energy Trivial State) conjecture [M. H. Freedman and M. B. Hastings, Quantum Inf. Comput. 14, 144 (2014)] posits that there exist families of Hamiltonians with all low energy states of high complexity (with complexity measured by the quantum circuit depth preparing the state). Here, we prove a weaker version called the combinatorial no low error trivial states (NLETS), where a quantum circuit lower bound is shown against states that violate a (small) constant fraction of local terms. This generalizes the prior NLETS results [L. Eldar and A. W. Harrow, in 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2017), pp. 427–438] and [Nirkhe et al., in 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), edited by Chatzigiannakis et al. (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018), Vol. 107, pp. 1–11]. Our construction is obtained by combining tensor networks with expander codes [M. Sipser and D. Spielman, IEEE Trans. Inf. Theory 42, 1710 (1996)]. The Hamiltonian is the parent Hamiltonian of a perturbed tensor network, inspired by the “uncle Hamiltonian” of Fernández-González et al. [Commun. Math. Phys. 333, 299 (2015)]. Thus, we deviate from the quantum Calderbank-Shor-Steane (CSS) code Hamiltonians considered in most prior works. 

Ground-state entanglement governs various properties of quantum many-body systems at low temperatures and is the key to understanding gapped quantum phases of matter. Here we identify a structural property of entanglement in the ground state of gapped local Hamiltonians. This property is captured using a quantum information quantity known as the entanglement spread, which measures the difference between Rényi entanglement entropies. Our main result shows that gapped ground states possess limited entanglement spread across any partition of the system, exhibiting an area-law scaling. Our result applies to systems with interactions described by any graph, but we obtain an improved bound for the special case of lattices. These interaction graphs include cases where entanglement entropy is known not to satisfy an area law. We achieve our results first by connecting the ground-state entanglement to the communication complexity of testing bipartite entangled states and then devising a communication scheme for testing ground states using recently developed quantum algorithms for Hamiltonian simulation.