INTRODUCTION Solving quantum many-body problems, such as finding ground states of quantum systems, has far-reaching consequences for physics, materials science, and chemistry. Classical computers have facilitated many profound advances in science and technology, but they often struggle to solve such problems. Scalable, fault-tolerant quantum computers will be able to solve a broad array of quantum problems but are unlikely to be available for years to come. Meanwhile, how can we best exploit our powerful classical computers to advance our understanding of complex quantum systems? Recently, classical machine learning (ML) techniques have been adapted to investigate problems in quantum many-body physics. So far, these approaches are mostly heuristic, reflecting the general paucity of rigorous theory in ML. Although they have been shown to be effective in some intermediate-size experiments, these methods are generally not backed by convincing theoretical arguments to ensure good performance. RATIONALE A central question is whether classical ML algorithms can provably outperform non-ML algorithms in challenging quantum many-body problems. We provide a concrete answer by devising and analyzing classical ML algorithms for predicting the properties of ground states of quantum systems. We prove that these ML algorithms can efficiently and accurately predict ground-state properties of gapped local Hamiltonians, after learning from data obtained by measuring other ground states in the same quantum phase of matter. Furthermore, under a widely accepted complexity-theoretic conjecture, we prove that no efficient classical algorithm that does not learn from data can achieve the same prediction guarantee. By generalizing from experimental data, ML algorithms can solve quantum many-body problems that could not be solved efficiently without access to experimental data. RESULTS We consider a family of gapped local quantum Hamiltonians, where the Hamiltonian H ( x ) depends smoothly on m parameters (denoted by x ). The ML algorithm learns from a set of training data consisting of sampled values of x , each accompanied by a classical representation of the ground state of H ( x ). These training data could be obtained from either classical simulations or quantum experiments. During the prediction phase, the ML algorithm predicts a classical representation of ground states for Hamiltonians different from those in the training data; ground-state properties can then be estimated using the predicted classical representation. Specifically, our classical ML algorithm predicts expectation values of products of local observables in the ground state, with a small error when averaged over the value of x . The run time of the algorithm and the amount of training data required both scale polynomially in m and linearly in the size of the quantum system. Our proof of this result builds on recent developments in quantum information theory, computational learning theory, and condensed matter theory. Furthermore, under the widely accepted conjecture that nondeterministic polynomial-time (NP)–complete problems cannot be solved in randomized polynomial time, we prove that no polynomial-time classical algorithm that does not learn from data can match the prediction performance achieved by the ML algorithm. In a related contribution using similar proof techniques, we show that classical ML algorithms can efficiently learn how to classify quantum phases of matter. In this scenario, the training data consist of classical representations of quantum states, where each state carries a label indicating whether it belongs to phase A or phase B . The ML algorithm then predicts the phase label for quantum states that were not encountered during training. The classical ML algorithm not only classifies phases accurately, but also constructs an explicit classifying function. Numerical experiments verify that our proposed ML algorithms work well in a variety of scenarios, including Rydberg atom systems, two-dimensional random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases. CONCLUSION We have rigorously established that classical ML algorithms, informed by data collected in physical experiments, can effectively address some quantum many-body problems. These rigorous results boost our hopes that classical ML trained on experimental data can solve practical problems in chemistry and materials science that would be too hard to solve using classical processing alone. Our arguments build on the concept of a succinct classical representation of quantum states derived from randomized Pauli measurements. Although some quantum devices lack the local control needed to perform such measurements, we expect that other classical representations could be exploited by classical ML with similarly powerful results. How can we make use of accessible measurement data to predict properties reliably? Answering such questions will expand the reach of near-term quantum platforms. Classical algorithms for quantum many-body problems. Classical ML algorithms learn from training data, obtained from either classical simulations or quantum experiments. Then, the ML algorithm produces a classical representation for the ground state of a physical system that was not encountered during training. Classical algorithms that do not learn from data may require substantially longer computation time to achieve the same task.
more »
« less
Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
We 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 point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.
more »
« less
- NSF-PAR ID:
- 10216638
- Date Published:
- Journal Name:
- STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
- Page Range / eLocation ID:
- 378 to 386
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Quantum systems evolving unitarily and subject to quantum measurements exhibit various types of non-equilibrium phase transitions, arising from the competition between unitary evolution and measurements. Dissipative phase transitions in steady states of time-independent Liouvillians and measurement induced phase transitions at the level of quantum trajectories are two primary examples of such transitions. Investigating a many-body spin system subject to periodic resetting measurements, we argue that many-body dissipative Floquet dynamics provides a natural framework to analyze both types of transitions. We show that a dissipative phase transition between a ferromagnetic ordered phase and a paramagnetic disordered phase emerges for long-range systems as a function of measurement probabilities. A measurement induced transition of the entanglement entropy between volume law scaling and sub-volume law scaling is also present, and is distinct from the ordering transition. The two phases correspond to an error-correcting and a quantum-Zeno regimes, respectively. The ferromagnetic phase is lost for short range interactions, while the volume law phase of the entanglement is enhanced. An analysis of multifractal properties of wave function in Hilbert space provides a common perspective on both types of transitions in the system. Our findings are immediately relevant to trapped ion experiments, for which we detail a blueprint proposal based on currently available platforms.more » « less
-
Servedio, Rocco (Ed.)We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-case to average-case reductions and two protocols. We also show a novel protocol. 1. We prove that secret-key cryptography exists if O˜(n‾√)-approximate SVP is hard for 2εn-time algorithms. I.e., we extend to our setting (Micciancio and Regev's improved version of) Ajtai's celebrated polynomial-time worst-case to average-case reduction from O˜(n)-approximate SVP to SIS. 2. We prove that public-key cryptography exists if O˜(n)-approximate SVP is hard for 2εn-time algorithms. This extends to our setting Regev's celebrated polynomial-time worst-case to average-case reduction from O˜(n1.5)-approximate SVP to LWE. In fact, Regev's reduction is quantum, but ours is classical, generalizing Peikert's polynomial-time classical reduction from O˜(n2)-approximate SVP. 3. We show a 2εn-time coAM protocol for O(1)-approximate CVP, generalizing the celebrated polynomial-time protocol for O(n/logn‾‾‾‾‾‾‾√)-CVP due to Goldreich and Goldwasser. These results show complexity-theoretic barriers to extending the recent line of fine-grained hardness results for CVP and SVP to larger approximation factors. (This result also extends to arbitrary norms.) 4. We show a 2εn-time co-non-deterministic protocol for O(logn‾‾‾‾‾√)-approximate SVP, generalizing the (also celebrated!) polynomial-time protocol for O(n‾√)-CVP due to Aharonov and Regev. 5. We give a novel coMA protocol for O(1)-approximate CVP with a 2εn-time verifier. All of the results described above are special cases of more general theorems that achieve time-approximation factor tradeoffs.more » « less
-
BACKGROUND Landau’s Fermi liquid theory provides the bedrock on which our understanding of metals has developed over the past 65 years. Its basic premise is that the electrons transporting a current can be treated as “quasiparticles”—electron-like particles whose effective mass has been modified, typically through interactions with the atomic lattice and/or other electrons. For a long time, it seemed as though Landau’s theory could account for all the many-body interactions that exist inside a metal, even in the so-called heavy fermion systems whose quasiparticle mass can be up to three orders of magnitude heavier than the electron’s mass. Fermi liquid theory also lay the foundation for the first successful microscopic theory of superconductivity. In the past few decades, a number of new metallic systems have been discovered that violate this paradigm. The violation is most evident in the way that the electrical resistivity changes with temperature or magnetic field. In normal metals in which electrons are the charge carriers, the resistivity increases with increasing temperature but saturates, both at low temperatures (because the quantized lattice vibrations are frozen out) and at high temperatures (because the electron mean free path dips below the smallest scattering pathway defined by the lattice spacing). In “strange metals,” by contrast, no saturation occurs, implying that the quasiparticle description breaks down and electrons are no longer the primary charge carriers. When the particle picture breaks down, no local entity carries the current. ADVANCES A new classification of metallicity is not a purely academic exercise, however, as strange metals tend to be the high-temperature phase of some of the best superconductors available. Understanding high-temperature superconductivity stands as a grand challenge because its resolution is fundamentally rooted in the physics of strong interactions, a regime where electrons no longer move independently. Precisely what new emergent phenomena one obtains from the interactions that drive the electron dynamics above the temperature where they superconduct is one of the most urgent problems in physics, attracting the attention of condensed matter physicists as well as string theorists. One thing is clear in this regime: The particle picture breaks down. As particles and locality are typically related, the strange metal raises the distinct possibility that its resolution must abandon the basic building blocks of quantum theory. We review the experimental and theoretical studies that have shaped our current understanding of the emergent strongly interacting physics realized in a host of strange metals, with a special focus on their poster-child: the copper oxide high-temperature superconductors. Experiments are highlighted that attempt to link the phenomenon of nonsaturating resistivity to parameter-free universal physics. A key experimental observation in such materials is that removing a single electron affects the spectrum at all energy scales, not just the low-energy sector as in a Fermi liquid. It is observations of this sort that reinforce the breakdown of the single-particle concept. On the theoretical side, the modern accounts that borrow from the conjecture that strongly interacting physics is really about gravity are discussed extensively, as they have been the most successful thus far in describing the range of physics displayed by strange metals. The foray into gravity models is not just a pipe dream because in such constructions, no particle interpretation is given to the charge density. As the breakdown of the independent-particle picture is central to the strange metal, the gravity constructions are a natural tool to make progress on this problem. Possible experimental tests of this conjecture are also outlined. OUTLOOK As more strange metals emerge and their physical properties come under the scrutiny of the vast array of experimental probes now at our disposal, their mysteries will be revealed and their commonalities and differences cataloged. In so doing, we should be able to understand the universality of strange metal physics. At the same time, the anomalous nature of their superconducting state will become apparent, offering us hope that a new paradigm of pairing of non-quasiparticles will also be formalized. The correlation between the strength of the linear-in-temperature resistivity in cuprate strange metals and their corresponding superfluid density, as revealed here, certainly hints at a fundamental link between the nature of strange metallicity and superconductivity in the cuprates. And as the gravity-inspired theories mature and overcome the challenge of projecting their powerful mathematical machinery onto the appropriate crystallographic lattice, so too will we hope to build with confidence a complete theory of strange metals as they emerge from the horizon of a black hole. Curved spacetime with a black hole in its interior and the strange metal arising on the boundary. This picture is based on the string theory gauge-gravity duality conjecture by J. Maldacena, which states that some strongly interacting quantum mechanical systems can be studied by replacing them with classical gravity in a spacetime in one higher dimension. The conjecture was made possible by thinking about some of the fundamental components of string theory, namely D-branes (the horseshoe-shaped object terminating on a flat surface in the interior of the spacetime). A key surprise of this conjecture is that aspects of condensed matter systems in which the electrons interact strongly—such as strange metals—can be studied using gravity.more » « less
-
more » « less
We advance the characterization of complexity in quantum many-body systems by examining
W W W W
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1145/3357713.3384322
