Source-linked AI summary
The power of quantum systems on a line
Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe
TL;DR
The paper asks how much computational power can be realized by finite-dimensional quantum particles arranged on a line. It constructs one-dimensional Hamiltonians supporting universal adiabatic computation and proves 12-state ground-state-energy approximation QMA-complete, with conditional implications for exponentially slow relaxation.
Problem
The paper addresses whether one-dimensional quantum systems, often viewed as classically tractable, can nevertheless support universal computation and computationally hard ground-state-energy problems.
Method
The authors build a one-dimensional circuit-to-Hamiltonian construction using local propagation rules, with additional checks to exclude incorrectly initialized, rejecting, or illegal history states.
Results
The construction enables universal adiabatic quantum computation with 9-state particles and makes 1-DIM 12-STATE HAMILTONIAN QMA-complete.
Takeaways & Limitations
Under the stated complexity assumptions, some one-dimensional quantum systems take exponentially long to relax to their ground state or low-temperature thermal equilibrium, making them candidates for one-dimensional spin glasses.
Takeaways & Limitations
The adiabatic construction has a highly degenerate ground state, and reducing the particle dimension further remains an open problem.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper asks how computationally powerful quantum particles arranged on a line can be, against the backdrop of simpler classical one-dimensional systems. It proves universal adiabatic computation with 9 states per particle and QMA-completeness for 12-state one-dimensional Hamiltonians, with implications for slow relaxation.
- One-dimensional classical nearest-neighbor satisfiability is solvable in polynomial time, unlike its higher-dimensional counterpart, which is NP-complete.
- The paper investigates whether quantum particles on a line can support universal computation and whether their ground-state energies are computationally difficult to approximate.
- 1.1 Results related to adiabatic computation: Universal adiabatic quantum computation is possible with one-dimensional 9-state Hamiltonians.
- 1.2 Results related to QMA-completeness: 1-DIM 12-STATE HAMILTONIAN is QMA-complete, establishing a sharp contrast with the classical one-dimensional problem.
- 1.2 Results related to QMA-completeness: The construction encodes an additional time dimension through history-state superpositions, explaining why one-dimensional quantum Hamiltonians resemble higher-dimensional classical constraint problems.
- 1.3 Implications of our results: Subject to the quantum Church–Turing thesis and quantum hardness of QMA, some constructed systems require exponentially long relaxation to their ground or low-temperature equilibrium states.
2 The basic construction
The basic construction simulates a quantum circuit on a one-dimensional line by moving a block of qubits through nearest-neighbor gate cycles. Local transition rules implement the computation, requiring 12 states for the QMA construction and 9 after simplifying the adiabatic version.
- A single active site acts like a Turing-machine head, moving along the line and applying local transition rules to manipulate encoded qubits.
- The construction maps a circuit to a line of 12-state particles organized into blocks, with each block representing one circuit round.
- Because constant-dimensional sites cannot count arbitrary distances, the construction moves the full qubit set one position at a time and detects new rounds at block boundaries.
- The 12 site states include data subsystems, flags, and active sites that serve as local computational pointers and markers.
- The transition rules are locally reversible and, for valid configurations, determine exactly one forward and one backward step except at the endpoints.
- For adiabatic computation, merging selected state types reduces the construction from 12 to 9 states per particle.
3 Universality of adiabatic evolution in one dimension
The construction simulates any quantum circuit through adiabatic evolution on a one-dimensional line of 9-state particles. Its Hamiltonians encode the computation's history state, while an invariant subspace and inverse-polynomial spectral gap establish universality.
- Circuit-to-line construction: A circuit on n qubits is transformed into a one-dimensional 9-state system whose transition rules generate K + 1 configurations.The construction uses nR 9-state particles and K = n(2n+3)R + n−1 evolution steps.
- Hamiltonian construction: The final Hamiltonian is built by translating each transition rule into a nearest-neighbor 2-local Hamiltonian.Each transition from |α⟩ to |β⟩ is represented using the corresponding gate U on encoded qubits.
- Initial and final Hamiltonians: The initial Hamiltonian penalizes configurations lacking the required |0⟩ state at the first position, making the initial configuration its ground state.Although its ground space is highly degenerate overall, |γ(0)⟩ is the only satisfying state within the relevant invariant subspace.
- Spectral-gap analysis: The subspace spanned by the computation-history states remains invariant throughout the adiabatic interpolation.This reduces the spectral-gap analysis to the invariant subspace K0.
- Spectral-gap analysis: The spectral gap is at least 1/[2(K + 1)^2], an inverse polynomial in the circuit parameters, proving Theorem 1.2.The history state is a zero eigenstate of the final Hamiltonian in the chosen basis.
4 1D QMA
The construction strengthens one-dimensional Hamiltonians so that local propagation, initialization, acceptance, and penalty terms distinguish legal computation histories from illegal configurations. A key technical step is ruling out some illegal configurations indirectly through their future evolution, yielding inverse-polynomial energy lower bounds for bad invariant subspaces.
- Hamiltonian construction: The propagation Hamiltonian alone is insufficient because incorrectly initialized or rejecting history states, and uniform superpositions containing illegal configurations, can still have zero propagation energy.Additional initialization, final, and penalty terms are therefore required.
- Hamiltonian construction: Hinit penalizes ancillas not initialized to |0⟩, while Hfinal penalizes histories whose output qubit is |0⟩ when the checking circuit rejects.The gate flag sweeps through the first and final blocks to enforce these conditions.
- Hamiltonian construction: Local penalty rules forbid specified adjacent arrangements, including active-site conflicts and arrangements missing forward or backward transition rules.The resulting Hpenalty sums penalties over forbidden neighboring pairs, with adjustments at block boundaries.
- Classifying configurations: Configurations satisfying groups 1–6 are either legal or fall into three exceptions involving qubit strings at an endpoint, incorrect lengths, or block misalignment.Groups 5 and 6 also ensure that exactly one active site remains.
- Indirect detection: The three exceptions cannot be excluded by local checks alone, so the proof uses invariant subspaces preserved by both Hpenalty and Hprop.This couples direct local penalties with the future evolution of configurations.
- Energy separation: Ω(1/K3) is the minimum eigenvalue of Hprop + Hpenalty on every type-2 or type-3 invariant subspace, where K is the number of circuit steps.For type-3 spaces, a nonzero fraction of configurations becomes locally checkably illegal under the transition rules.
5 Discussion and Open Problems
The construction establishes one-dimensional 12-state Hamiltonians for universal adiabatic computation and QMA-complete problems, while extending the result to QCMA under an efficiently constructible ground-state promise. Open questions concern reducing particle dimension and understanding promise and spectral gaps.
- 1-dimensional 12-state Hamiltonians support both universal adiabatic quantum computation and QMA-complete problems.
- The corresponding Hamiltonian problem is also QCMA-complete when the ground state is promised to be efficiently constructible.The reduction preserves witnesses after amplification, and the adiabatic algorithm can construct the corresponding Hamiltonian witness efficiently.
- Reducing the particle dimension to qubits remains open because existing perturbation-theory gadgets do not work in one dimension, although the approach yields a constant-width two-dimensional strip.Interacting qubit pairs require a graph of degree at least 3, or 4 for some gadgets.
- Reaching 2-state particles may require new techniques, since removing explicit time references alone is unlikely to eliminate the additional states used for control instructions.An intermediate transition between 2 and 12 states is also possible.
- The promise gap is polynomially small relative to energy per term but can be amplified to a constant, while making it a constant fraction of total energy remains open.Amplification uses t copies of the ground state to increase the gap from ∆ to t∆.
- For adiabatic computation, universality is shown with a spectral gap polynomially small relative to energy per term; constant-gap behavior remains unresolved for the QMA-completeness problem.If the spectral gap is sufficiently large relative to energy per term, the ground state has a matrix product state representation and the problem is in NP.