Many-body ground state preparation is an important subroutine used in the simulation of physical systems. In this paper, we introduce a flexible and efficient framework for obtaining a state preparation circuit for a large class of many-body ground states. We introduce polynomial-time classical algorithms that take reduced density matrices over O ( 1 ) -sized balls as inputs, and output a circuit that prepares the global state. We introduce algorithms applicable to (i) short-range entangled states (e.g., states prepared by shallow quantum circuits in any number of dimensions, and more generally, invertible states) and (ii) long-range entangled ground states (e.g., the toric code on a disk). Both algorithms can provably find a circuit whose depth is asymptotically optimal. Our approach uses a variant of the quantum Markov chain condition that remains robust against constant-depth circuits. The robustness of this condition makes our method applicable to a large class of states, whilst ensuring a classically tractable optimization landscape.
Many-body ground state preparation is an important subroutine used in the simulation of physical systems. In this paper, we introduce a flexible and efficient framework for obtaining a state preparation circuit for a large class of many-body ground states. We introduce polynomial-time classical algorithms that take reduced density matrices over O ( 1 ) -sized balls as inputs, and output a circuit that prepares the global state. We introduce algorithms applicable to (i) short-range entangled states (e.g., states prepared by shallow quantum circuits in any number of dimensions, and more generally, invertible states) and (ii) long-range entangled ground states (e.g., the toric code on a disk). Both algorithms can provably find a circuit whose depth is asymptotically optimal. Our approach uses a variant of the quantum Markov chain condition that remains robust against constant-depth circuits. The robustness of this condition makes our method applicable to a large class of states, whilst ensuring a classically tractable optimization landscape.
Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.
We give a polynomial time algorithm that, given copies of an unknown quantum state ∣ψ⟩=U∣0n⟩ that is prepared by an unknown constant depth circuit U on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares ∣ψ⟩. The algorithm extends to the case when the depth of U is polylog(n), with a quasi-polynomial run-time. The key new idea is a simple and general procedure that efficiently reconstructs the global state ∣ψ⟩ from its local reduced density matrices. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
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. Published by the American Physical Society 2024
Quantum state preparation is an important subroutine for quantum computing. We show that any n-qubit quantum state can be prepared with a Θ(n)-depth circuit using only single- and two-qubit gates, although with a cost of an exponential amount of ancillary qubits. On the other hand, for sparse quantum states with d⩾2 nonzero entries, we can reduce the circuit depth to Θ(log(nd)) with O(ndlogd) ancillary qubits. The algorithm for sparse states is exponentially faster than best-known results and the number of ancillary qubits is nearly optimal and only increases polynomially with the system size. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories, and find cases with exponential reductions of the circuit depth for all these three tasks. In particular, using our algorithm, we find a family of linear system solving problems enjoying exponential speedups, even compared to the best-known quantum and classical dequantization algorithms.
Long-range entanglement is an important quantum resource, particularly for topological orders and quantum error correction. In reality, preparing long-range entangled states requires a deep unitary circuit, which poses significant experimental challenges. A promising avenue is offered by replacing some quantum resources with local operations and classical communication (LOCC). With these classical components, one can communicate outcomes of midcircuit measurements in distant subsystems, substantially reducing circuit depth in many important cases. However, to prepare general long-range entangled states, finding LOCC-assisted circuits of a short depth remains an open question. Here, to address this challenge, we propose a quantum-classical hybrid algorithm to find optimal LOCC protocols for preparing ground states of given Hamiltonians. In our algorithm, we introduce an efficient way to estimate parameter gradients and use such gradients for variational optimization. Theoretically, we establish the conditions for the absence of barren plateaus, ensuring trainability at a large system size. Numerically, the algorithm accurately solves the ground state of long-range entangled models, such as the perturbed Greenberger-Horne-Zeilinger state and surface code. Our results demonstrate the advantage of our method over conventional unitary variational circuits: the practical advantage in the accuracy of estimated ground-state energy and the theoretical advantage in creating long-range entanglement.
Preparing matrix product states (MPSs) on quantum computers is an essential routine in the simulation of many-body physics. However, widely used schemes based on staircase circuits are often too deep to execute on current hardware. Here, we demonstrate that MPSs with short-range correlations can be prepared with shallow circuits by leveraging heuristics from approximate quantum compiling (AQC). We achieve this with ADAPT-AQC, an adaptive-ansatz preparation algorithm, and introduce a generalized initialization procedure for the existing AQC-Tensor algorithm. We first compare these methods for the task of preparing a molecular electronic structure ground state. We then use them to prepare an antiferromagnetic (AFM) ground state of the 50-site Heisenberg XXZ spin chain near the AFM-XY phase boundary. Through the execution of circuits with up to 59 depth and 1251 gates, we perform a global quench and observe the relaxation of magnetic ordering in a parameter regime previously inaccessible due to deep ground-state preparation circuits. Our results demonstrate how the integration of quantum and classical resources can push the boundary of what can be studied on quantum computers.