The power of quantum systems on a line

DOI10.1007/s00220-008-0710-3zbMath1180.68162arXiv0705.4077OpenAlexW2072381205MaRDI QIDQ842451

Julia Kempe, Daniel Gottesman, Sandy Irani, Dorit Aharonov

Publication date: 25 September 2009

Published in: Communications in Mathematical Physics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0705.4077

zbMATH Keywords

quantum computation

Mathematics Subject Classification ID

Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Two-dimensional local Hamiltonian problem with area laws is \textsf{QMA}-complete ⋮ The power of quantum systems on a line ⋮ Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. ⋮ Undecidability of the Spectral Gap ⋮ Universal qudit Hamiltonians ⋮ The complexity of translationally invariant spin chains with low local dimension ⋮ Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes ⋮ The complexity of translationally invariant low-dimensional spin lattices in 3D ⋮ Classifying data using near-term quantum devices ⋮ Ground states of unfrustrated spin Hamiltonians satisfy an area law ⋮ Universal quantum computation by scattering in the Fermi–Hubbard model ⋮ Epsilon-net method for optimizations over separable states ⋮ On complexity of the quantum Ising model ⋮ ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS ⋮ The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\) ⋮ Product-state approximations to quantum states ⋮ Perturbation gadgets: arbitrary energy scales from a single strong interaction ⋮ Exponential decay of correlations implies area law ⋮ Colloquium: Area laws for the entanglement entropy ⋮ Translationally invariant universal quantum Hamiltonians in 1D ⋮ Ground state entanglement in one-dimensional translationally invariant quantum systems ⋮ Gapped and gapless phases of frustration-free spin-12 chains

Uses Software

• MAX-2-SAT

Cites Work

• Unnamed Item
• Unnamed Item
• The power of quantum systems on a line
• NP is as easy as detecting unique solutions
• Quantum stochastic optimization
• Improved gap estimates for simulating quantum circuits by adiabatic evolution
• Relationship between d-Dimensional Quantal Spin Systems and (d+1)-Dimensional Ising Systems: Equivalence, Critical Exponents and Systematic Approximants of the Partition Function and Spin Correlations
• The density-matrix renormalization group
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation
• Fast universal quantum computation with railroad-switch local Hamiltonians
• The Complexity of the Local Hamiltonian Problem

This page was built for publication: The power of quantum systems on a line