skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure
Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. We prove this by constructing strong forms of pseudoentanglement in a public-key setting, where the circuits used to prepare the states are public knowledge. In particular, we construct two families of quantum circuits which produce volume-law vs near area-law entangled states, but nonetheless the classical descriptions of the circuits are indistinguishable under the Learning with Errors (LWE) assumption. Indistinguishability of the circuits then allows us to translate our construction to Hamiltonians. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.  more » « less
Award ID(s):
2044923 2016245
PAR ID:
10554455
Author(s) / Creator(s):
; ; ; ; ; ;
Editor(s):
Santhanam, Rahul
Publisher / Repository:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Date Published:
Volume:
300
ISSN:
1868-8969
ISBN:
978-3-95977-331-7
Page Range / eLocation ID:
300-300
Subject(s) / Keyword(s):
Quantum computing Quantum complexity theory entanglement Theory of computation → Quantum computation theory Theory of computation → Pseudorandomness and derandomization
Format(s):
Medium: X Size: 23 pages; 827450 bytes Other: application/pdf
Size(s):
23 pages 827450 bytes
Right(s):
Creative Commons Attribution 4.0 International license; info:eu-repo/semantics/openAccess
Sponsoring Org:
National Science Foundation
More Like this
  1. 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. 
    more » « less
  2. Adaptive quantum circuits, which combine local unitary gates, midcircuit measurements, and feedforward operations, have recently emerged as a promising avenue for efficient state preparation, particularly on near-term quantum devices limited to shallow-depth circuits. Matrix product states (MPS) comprise a significant class of many-body entangled states, efficiently describing the ground states of one-dimensional gapped local Hamiltonians and finding applications in a number of recent quantum algorithms. Recently, it has been shown that the Affleck-Kennedy-Lieb-Tasaki state—a paradigmatic example of an MPS—can be exactly prepared with an adaptive quantum circuit of constant depth, an impossible feat with local unitary gates alone due to its nonzero correlation length [Smith , PRX Quantum 4, 020315 (2023)]. In this work, we broaden the scope of this approach and demonstrate that a diverse class of MPS can be exactly prepared using constant-depth adaptive quantum circuits, outperforming theoretically optimal preparation with unitary circuits. We show that this class includes short- and long-ranged entangled MPS, symmetry-protected topological (SPT) and symmetry-broken states, MPS with finite Abelian, non-Abelian, and continuous symmetries, resource states for MBQC, and families of states with tunable correlation length. Moreover, we illustrate the utility of our framework for designing constant-depth sampling protocols, such as for random MPS or for generating MPS in a particular SPT phase. We present sufficient conditions for particular MPS to be preparable in constant time, with global on-site symmetry playing a pivotal role. Altogether, this work demonstrates the immense promise of adaptive quantum circuits for efficiently preparing many-body entangled states and provides explicit algorithms that outperform known protocols to prepare an essential class of states. 
    more » « less
  3. We introduce and prove the “root theorem”, which establishes a condition for families of operators to annihilate all root states associated with zero modes of a given positive semi-definite k-body Hamiltonian chosen from a large class. This class is motivated by fractional quantum Hall and related problems, and features generally long-ranged, one-dimensional, dipole-conserving terms. Our theorem streamlines analysis of zero-modes in contexts where “generalized” or “entangled” Pauli principles apply. One major application of the theorem is to parent Hamiltonians for mixed Landau-level wave functions, such as unprojected composite fermion or parton-like states that were recently discussed in the literature, where it is difficult to rigorously establish a complete set of zero modes with traditional polynomial techniques. As a simple application, we show that a modified V1 pseudo-potential, obtained via retention of only half the terms, stabilizes the ν=1/2 Tao–Thouless state as the unique densest ground state. 
    more » « less
  4. We generalize the area-law violating models of Fredkin and Motzkin spin chains into two dimensions by building quantum six- and nineteen-vertex models with correlated interactions. The Hamiltonian is frustration free, and its projectors generate ergodic dynamics within the subspace of height configuration that are non negative. The ground state is a volume- and color-weighted superposition of classical bi-color vertex configurations with non-negative heights in the bulk and zero height on the boundary. The entanglement entropy between subsystems has a phase transition as the q q -deformation parameter is tuned, which is shown to be robust in the presence of an external field acting on the color degree of freedom. The ground state undergoes a quantum phase transition between area- and volume-law entanglement phases with a critical point where entanglement entropy scales as a function L\log L L log L of the linear system size L L . Intermediate power law scalings between L\log L L log L and L^2 L 2 can be achieved with an inhomogeneous deformation parameter that approaches 1 at different rates in the thermodynamic limit. For the q>1 q > 1 phase, we construct a variational wave function that establishes an upper bound on the spectral gap that scales as q^{-L^3/8} q − L 3 / 8 . 
    more » « less
  5. Adaptive quantum circuits—where a quantum many-body state is controlled using measurements and conditional unitary operations—are a powerful paradigm for state preparation and quantum error-correction tasks. They can support two types of nonequilibrium quantum phase transitions: measurement-induced transitions between volume- and area-law-entangled steady states and control-induced transitions where the system falls into an absorbing state or, more generally, an orbit visiting several absorbing states. Within this context, nonlocal conditional operations can alter the critical properties of the two transitions and the topology of the phase diagram. Here, we consider the scenario where the measurements are , in order to engineer efficient control onto dynamical trajectories. Motivated by Rydberg-atom arrays, we consider a locally constrained model with global sublattice magnetization measurements and local correction operations to steer the system’s dynamics onto a many-body orbit with finite recurrence time. The model has a well-defined classical limit, which we leverage to aid our analysis of the control transition. As a function of the density of local correction operations, we find control and entanglement transitions with continuously varying critical exponents. For sufficiently high densities of local correction operations, we find that both transitions acquire a dynamical critical exponent z < 1 , reminiscent of criticality in long-range power-law interacting systems. At low correction densities, we find that the criticality reverts to a short-range nature with z 1 . In the long-range regime, the control and entanglement transitions are indistinguishable to within the resolution of our finite-size numerics, while in the short-range regime we find evidence that the transitions become distinct. We conjecture that the effective long-range criticality mediated by collective measurements is essential in driving the two transitions together. Published by the American Physical Society2025 
    more » « less