The power of quantum systems on a line

Abstract

We study the computational strength of quantum particles (each of finite dimensionality) arranged on a line. First, we prove that it is possible to perform universal adiabatic quantum computation using a one-dimensional quantum system (with 9 states per particle). This might have practical implications for experimentalists interested in constructing an adiabatic quantum computer. Building on the same construction, but with some additional technical effort and 12 states per particle, we show that the problem of approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete; QMA is a quantum analogue of NP. This is in striking contrast to the fact that the analogous classical problem, namely, one-dimensional MAX-2-SAT with nearest neighbor constraints, is in P. The proof of the QMA-completeness result requires an additional idea beyond the usual techniques in the area: Not all illegal configurations can be ruled out by local checks, so instead we rule out such illegal configurations because they would, in the future, evolve into a state which can be seen locally to be illegal. Our construction implies (assuming the quantum Church-Turing thesis and that quantum computers cannot efficiently solve QMA-complete problems) that there are one-dimensional systems which take an exponential time to relax to their ground states at any temperature, making them candidates for being one-dimensional spin glasses.

21 pages. v2 has numerous corrections and clarifications, and most importantly a new author, merged from arXiv:0705.4067. v3 is the published version, with additional clarifications, publisher's version available at http://www.springerlink.com

References in corpus (13)

• The density-matrix renormalization group
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• An Area Law for One Dimensional Quantum Systems
• Robustness of adiabatic quantum computation
• The Dynamics of 1D Quantum Spin Systems Can Be Approximated Efficiently
• Error correcting codes for adiabatic quantum computation
• Hamiltonian Quantum Cellular Automata in 1D
• A universally programmable Quantum Cellular Automaton
• The Computational Power of Symmetric Hamiltonians
• The ground state of a class of noncritical 1D quantum spin systems can be approximated efficiently
• Local Hamiltonians in Quantum Computation
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• The Complexity of Quantum Systems on a One-dimensional Chain

Cited by in corpus (139)

• Area laws for the entanglement entropy - a review
• Adiabatic Quantum Computing
• Quantum Metropolis Sampling
• PEPS as ground states: degeneracy and topology
• Solving strongly correlated electron models on a quantum computer
• Undecidability of the Spectral Gap (short version)
• Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
• Heisenberg-limited ground state energy estimation for early fault-tolerant quantum computers
• Near-optimal ground state preparation
• Genuine quantum correlations in quantum many-body systems: a review of recent progress
• Hamiltonian complexity
• Exponential Decay of Correlations Implies Area Law
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices
• Quantum Hamiltonian Complexity
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Violation of area-law scaling for the entanglement entropy in spin 1/2 chains
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Universal Quantum Hamiltonians
• Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation
• Exploring out-of-equilibrium quantum magnetism and thermalization in a spin-3 many-body dipolar lattice system
• Entanglement spectroscopy on a quantum computer
• Preparing thermal states of quantum systems by dimension reduction
• Scaling of variational quantum circuit depth for condensed matter systems
• Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes
• Entanglement vs. gap for one-dimensional spin systems
• Single-ancilla ground state preparation via Lindbladians
• Hamiltonian Quantum Cellular Automata in 1D
• Interacting boson problems are QMA-hard
• Quantum measurement occurrence is undecidable
• Ground State Entanglement in One Dimensional Translationally Invariant Quantum Systems
• Spectral Gap Amplification
• Spin State Transfer in Laterally Coupled Quantum Dot Chains with Disorders
• An energetic perspective on rapid quenches in quantum annealing
• Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
• Engineered thermalization and cooling of quantum many-body systems
• Unfrustrated Qudit Chains and their Ground States
• Quantum many-body systems in thermal equilibrium
• Matrix Product State and mean field solutions for one-dimensional systems can be found efficiently
• Computational Difficulty of Computing the Density of States
• Undecidability of the Spectral Gap in One Dimension
• The Quantum PCP Conjecture
• Quantum computation, quantum state engineering, and quantum phase transitions driven by dissipation
• Product-state Approximations to Quantum Ground States
• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Local tests of global entanglement and a counterexample to the generalized area law
• Critical exponents of one-dimensional quantum critical models by means of MERA tensor network
• Solving frustration-free spin systems
• Ground states of unfrustrated spin Hamiltonians satisfy an area law
• Space-Time Circuit-to-Hamiltonian Construction and Its Applications
• Universal 2-local Hamiltonian Quantum Computing
• Scalable effective temperature reduction for quantum annealers via nested quantum annealing correction
• Computable Rényi mutual information: Area laws and correlations
• When a local Hamiltonian must be frustration-free
• The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
• A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians
• The Complexity of Translationally-Invariant Spin Chains with Low Local Dimension
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Approximation algorithms for QMA-complete problems
• An Efficient Algorithm for approximating 1D Ground States
• The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
• Thermal States as Convex Combinations of Matrix Product States
• The quantum marginal problem for symmetric states: applications to variational optimization, nonlocality and self-testing
• Condensed Matter Applications of Entanglement Theory
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Isometric tensor network optimization for extensive Hamiltonians is free of barren plateaus
• Importance of the spectral gap in estimating ground-state energies
• The Bose-Hubbard model is QMA-complete
• Analysis and limitations of modified circuit-to-Hamiltonian constructions
• Improved Bounds for Eigenpath Traversal
• Local Hamiltonians in Quantum Computation
• A comparative study of universal quantum computing models: towards a physical unification
• Dynamics of an itinerant spin-3 atomic dipolar gas in an optical lattice
• Universal quantum walks and adiabatic algorithms by 1D Hamiltonians
• Computing energy density in one dimension
• A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
• The Local Hamiltonian problem on a line with eight states is QMA-complete
• A polynomial-time algorithm for the ground state of one-dimensional gapped Hamiltonians
• The Complexity of Translationally-Invariant Low-Dimensional Spin Lattices in 3D
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• The Complexity of Quantum Systems on a One-dimensional Chain
• Accuracy guarantees and quantum advantage in analogue open quantum simulation with and without noise
• Undecidability of the Spectral Gap (full version)
• Non-Identity Check Remains QMA-Complete for Short Circuits
• Sign problem in the Bethe approximation
• Early Fault-Tolerant Quantum Algorithms in Practice: Application to Ground-State Energy Estimation
• QCMA hardness of ground space connectivity for commuting Hamiltonians
• Quantum interactive proofs using quantum energy teleportation
• Certificates of quantum many-body properties assisted by machine learning
• Quantum Complexity: restrictions on algorithms and architectures
• Absence of barren plateaus and scaling of gradients in the energy optimization of isometric tensor network states
• The Complexity of Translationally Invariant Problems beyond Ground State Energies
• Hamiltonian quantum computer in one dimension
• On complexity of the quantum Ising model
• Double-bracket quantum algorithms for quantum imaginary-time evolution
• Sparse random Hamiltonians are quantumly easy
• Is there a physically universal cellular automaton or Hamiltonian?
• Cavity approach to variational quantum mechanics
• Universal Quantum Computation by Scattering in the Fermi-Hubbard Model
• The commuting local Hamiltonian on locally-expanding graphs is in NP
• Two-dimensional local Hamiltonian problem with area laws is QMA-complete
• The Local Consistency Problem for Stoquastic and 1-D Quantum Systems
• Detailed Analysis of Circuit-to-Hamiltonian Mappings
• Polynomial Time Quantum Gibbs Sampling for Fermi-Hubbard Model at any Temperature
• Translationally-Invariant Universal Quantum Hamiltonians in 1D
• Markovian Matrix Product Density Operators : Efficient computation of global entropy
• Fully-programmable universal quantum simulator with a one-dimensional quantum processor
• Classifying Data with Local Hamiltonians
• The Detectability Lemma and Quantum Gap Amplification
• Perturbation Gadgets: Arbitrary Energy Scales from a Single Strong Interaction
• Approximation, Proof Systems, and Correlations in a Quantum World
• Complexity of stoquastic frustration-free Hamiltonians
• Bounds on Autonomous Quantum Error Correction
• Oracle complexity classes and local measurements on physical Hamiltonians
• Properties of thermal quantum states: locality of temperature, decay of correlations, and more
• A PromiseBQP-complete String Rewriting Problem
• A measurement driven analog of adiabatic quantum computation for frustration-free Hamiltonians
• Universal Hamiltonians for Exponentially Long Simulation
• StoqMA vs. MA: the power of error reduction
• Universal Hamiltonian simulators in one and two dimensions
• Trotterless Simulation of Open Quantum Systems for NISQ Quantum Devices
• Statistical mechanics of classical and quantum computational complexity
• Undecidability in Spacetime Geometry via the AdS/CFT Correspondence
• Spin Systems and Computational Complexity
• Predictive complexity of quantum subsystems
• A journey into localization, integrability and thermalization
• Low overhead universality and quantum supremacy using only $Z$-control
• Sample complexity of matrix product states at finite temperature
• Entanglement and ground states of gapped Hamiltonians
• Noise-resilient and resource-efficient hybrid algorithm for robust quantum gap estimation
• Undecidability of the spectral gap in rotationally symmetric Hamiltonians
• Improving adiabatic quantum factorization via chopped random-basis optimization
• On polynomially many queries to NP or QMA oracles
• Gapped and gapless phases of frustration-free spin-1/2 chains
• Testing quantum expanders is co-QMA-complete
• Diffusion in quantum state preparation: From passive cooling to system-bath engineering
• On the physical limit of quantum computing
• Two remarks on the local Hamiltonian problem