Source-linked AI summary
Quantum Speedup by Quantum Annealing
Daniel Nagaj, Rolando D. Somma, Maria Kieferova
TL;DR
The glued-trees oracle problem lacked a known efficient annealing solution using simple stoquastic Hamiltonians, despite a quantum-walk approach and a classical oracle lower bound. The paper gives an annealing schedule that prepares a state encoding the EXIT in polynomial time with arbitrarily high probability.
Problem
An efficient quantum annealing solution using simple stoquastic Hamiltonians was not known for the glued-trees oracle problem, for which classical methods cannot solve the task with poly(n) oracle calls.
Source: pp. 1–2Method
The paper anneals an oracle Hamiltonian path involving H0, A, and H1 at an inverse-polynomial rate to transform the ENTRANCE-encoding state toward the EXIT-encoding state.
Source: pp. 2–3Results
The schedule prepares a state encoding the solution in polynomial time with arbitrarily high probability, whereas classical methods cannot solve the problem with poly(n) oracle calls.
Source: pp. 1–2Takeaways & Limitations
The result places limits on classical simulation of quantum annealing even when the Hamiltonians do not have the sign problem.
Source: p. 1The result relies on oracle evolutions under A, H0, and H1; the passage notes that general Hamiltonians do not satisfy the assumptions.
Source: pp. 2, 4
Abstract
from arXiv · showhide
We study the glued-trees problem of Childs et. al. in the adiabatic model of quantum computing and provide an annealing schedule to solve an oracular problem exponentially faster than classically possible. The Hamiltonians involved in the quantum annealing do not suffer from the so-called sign problem. Unlike the typical scenario, our schedule is efficient even though the minimum energy gap of the Hamiltonians is exponentially small in the problem size. We discuss generalizations based on initial-state randomization to avoid some slowdowns in adiabatic quantum computing due to small gaps.
I. SUPPLEMENTARY ONLINE MATERIAL
The spectral analysis rescales the Hamiltonian and uses an eigenstate ansatz to derive eigenvalue conditions. A symmetry then restricts the analysis to half the parameter range, where the chosen α produces an efficient annealing method.
1. SUPPLEMENTARY ONLINE MATERIAL
- The analysis rescales H(s) by s(1−s) to study H′(s) = α′H0−A+β′H1, with α′ = α/s and β′ = α/(1−s).The rescaled Hamiltonian is introduced for the spectral analysis.Source: §I · p. 5
- An eigenstate ansatz and the eigenvalue and normalization conditions determine the unknown parameters and yield a quantization condition for p.The ansatz coefficients are a, b, c, and d; p may be real or imaginary.Source: §I · p. 5
- The symmetry α′ ↔ β′ reduces the analysis to 0 < s ≤ 1/2, and choosing α = 1/8 produces an efficient annealing method.The solution behavior depends on whether α is above or below 1/2.Source: §I · p. 5
1. Hyperbolic solutions
The hyperbolic solutions characterize the low-energy branches and their finite-size behavior. They show a level crossing in the large-n limit and an exponentially small finite-n gap near the crossing.
1. Hyperbolic solutions
- In the large-n limit, the two lowest eigenvalues cross at s×, swapping which branch is the ground state and which is first excited.The eigenvalues are exchanged for s ≥ s×.Source: §1 · p. 6
- The finite-size correction yields an exponentially small gap of order 2^-n/2 near s×.The correction is obtained by a second-order Taylor approximation; away from s×, corrections are smaller for s < α.Source: §1 · p. 6
- For s ≤ s×, the lowest eigenvalue for finite n is characterized by the hyperbolic solution, while the lowest and first-excited branches swap for s ≥ s×.The section introduces these branch descriptions on either side of the crossing.Source: §1 · p. 6
- The corresponding eigenstate |φ̄q(s)⟩ becomes independent of s as n → ∞.The passage identifies it as the eigenstate corresponding to the branch valid on both sides of the crossing.Source: §1 · p. 6
2. Goniometric solutions
The goniometric solutions use real p and finite-size corrections to characterize excited states and estimate spectral gaps. The analysis identifies a minimum-gap location in the upper parameter region.
2. Goniometric solutions
- For 0 ≤ s ≤ α, the analysis uses goniometric eigenvectors and finite-size corrections to estimate spectral gaps.The corrections are obtained by expanding p around kπ/(n + 1).Source: §2 · p. 6
- For α ≤ s ≤ 1/2, the gap between the first and second excited states takes its minimum at s = 1/2.At s = 1/2, α′ = β′ = 2α.Source: §2 · p. 6
- At α = 1/8 and s = 1/2, p = π/(n + 1) satisfies the stated condition and corresponds to the second excited state.The passage also gives x(1/2) = −2.82 for an approximation to another solution.Source: §2 · p. 7
- The finite-size correction parameter μ is O(1/(n + 1)^3).The passage places this bound in its discussion of the spectral gap between the first and second excited states.Source: §2 · p. 7