Interpolate slowly to the problem Hamiltonian

What it fills

• Search a cost Hamiltonian for the assignment it minimises

  A cost function over discrete assignments, rewritten as an operator diagonal in the computational basis, is searched for the assignment at or near its minimum — by alternating short unitaries at a fixed, chosen depth, or by interpolating continuously toward the operator's own ground state. Both routes read the same operator; what they promise about the assignment they hand back is where they differ.

When it applies

The Hamiltonian is built directly from the instance: $H(t) = H_{C_1}(t) + \cdots + H_{C_M}(t)$, "where each $H_{C_a}$ depends only on clause $C_a$ and acts only on the bits in $C_a$" (§1). The initial Hamiltonian's ground state must be one "that is easy to construct" (Abstract), and the interpolation must stay slow enough over the whole path: the adiabatic theorem's guarantee needs the gap $E_1(s) - E_0(s)$ "strictly greater than zero for all $0 \le s \le 1$" (§2.1). The paper states this is the typical case rather than something proved for every instance: "typically $g_{\min}$ is not zero" (§2.6).

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  an n-bit satisfiability formula C_1 AND C_2 AND ... AND C_M          (Eq. 1.1)
       H_B, built per-bit and weighted by each bit's clause degree          (Eq. 2.22)
       H_P, whose ground state encodes the satisfying assignment

H(t) = (1 - t/T) * H_B + (t/T) * H_P     for t in [0, T]                    (Eq. 2.23)
     # equivalently H~(s) = (1-s)*H_B + s*H_P,  s = t/T in [0,1]             (Eq. 2.24)

prepare |psi(0)> = ground state of H(0) = H_B          # easy, by construction
evolve |psi(t)> under  i * d/dt |psi(t)> = H(t) |psi(t)>,  t: 0 -> T        (Eq. 2.1)

g_min = min over s in [0,1] of ( E_1(s) - E_0(s) )                          (Eq. 2.7)
# adiabatic theorem: if the gap is > 0 for every s in [0,1], then for
# T much greater than E / g_min^2, |psi(T)> is close to the ground state of H_P
#   (E is the largest matrix element of dH~/ds between the two lowest
#    instantaneous eigenstates, over the whole path -- Eq. 2.9)

measure |psi(T)> in the computational basis -> the assignment z

# "The time required depends on the minimum energy difference between the two
#  lowest states of the interpolating Hamiltonian. We are unable to estimate
#  this gap in general." -- for three special symmetric cases the paper proves T
#  is polynomial in n; those cases are also classically easy, so the authors call
#  them only "a small bit of evidence" the method may run fast on harder cases

Cost, as the source states it

"The time required depends on the minimum energy difference between the two lowest states of the interpolating Hamiltonian. We are unable to estimate this gap in general" (Abstract). Where the gap can be bounded, the theorem gives $T \gg E/g_{\min}^2$ (§2.1, rendered from Eqs. 2.8–2.9 for legibility); the paper proves this for "special symmetric cases of the satisfiability problem", every one of which is "easily seen to be classically solvable in polynomial time" by other means, offered only as "a small bit of evidence" about harder cases (§6). Realised as a gate-model circuit, cost tracks $T$ directly: "the number of factors in the product is proportional to $T^2$ times a polynomial in $n$" (§5) — so wherever $T$ is unbounded, so is this.

Implementations

• QuTiP's `mesolve`-based adiabatic-sweep tutorial (Lecture 8)

  QuTiP's own tutorial repository (qutip/qutip-tutorials) ships a notebook titled "Lecture 8 - Adiabatic sweep" (by J. R. Johansson), at tutorials-v5/lectures/Lecture-8-Adiabatic-quantum-computing.md, which states the same $H_0 \to H_1$ interpolation this record's theory describes and warns, in its own words, that "if the Hamiltonian is transformed from $H_0$ to $H_1$ too quickly, the system will get excited from the ground state [and] the adiabatic computing algorithm fails." No paper accompanies the notebook, so it is recorded here as a code artefact rather than a literature source.

  Builds $H_0 = \sum_n -0.5 \times 2.5\,\sigma_z^{(n)}$ on $N = 6$ spins, whose ground state is the trivially-prepared computational basis state `psi0`, and `H1` as a chain of nearest-neighbour couplings with independently random $J_x$, $J_y$, $J_z$ per bond (not diagonal in the computational basis, so this demonstrates the general adiabatic-sweep mechanism rather than interpolating toward a combinatorial-optimization cost operator built from clauses, as this record's own SAT example does). It packages the linear schedule pairing `H0` with a weight that decays from 1 to 0 and `H1` with a weight that grows from 0 to 1 as a `QobjEvo`, then calls `mesolve(h_t, psi0, taulist, [], e_ops=process_rho, args=args)`. Passing an empty list as the fourth (`c_ops`) argument keeps the evolution unitary: `mesolve`'s own docstring states "In the absence of collapse operators the system is evolved according to the unitary evolution of the Hamiltonian" and "When no collapse operator are given ... it will defer to sesolve." At every timestep the callback `process_rho` diagonalises the instantaneous Hamiltonian with `H.eigenstates(eigvals=M)` and records the overlap of the evolving state with each of the $M = 20$ lowest eigenstates -- the same instantaneous-eigenbasis tracking this record's Eq. 2.6-2.7 describe -- then plots it as an energy-spectrum figure with occupation probability encoded in line width, rather than returning a computed $g_{\min}$ number.

  None external: `h`, `Jx`, `Jy`, `Jz` are drawn fresh on every run from `np.random.rand`, so the instance is synthetic and re-randomised each execution rather than loaded from a fixed dataset or file.

  qutip/qutip-tutorials, tutorials-v5/lectures/Lecture-8-Adiabatic-quantum-computing.md (jupytext-linked to the notebook of the same name), at commit 97d7d09baaa926c6604bb75e4f139c7bea74ee5e. Calls `qutip.QobjEvo` and `qutip.mesolve`, and `Qobj.eigenstates`. Checked against qutip/qutip's current default branch: `QobjEvo` is defined in qutip/core/cy/qobjevo.pyx, re-exported to qutip.core's own top level by qutip/core/__init__.py's `from .cy.qobjevo import *`, and re-exported again to qutip's own top level by qutip/__init__.py's `from .core import *` -- matching the tutorial's own `from qutip import (QobjEvo, ...)` import; `mesolve` is defined in qutip/solver/mesolve.py.

  No specific numeric result is recorded here: the instance is randomised on every run, and the markdown source carries no saved output cells, so no fixed `taumax`, fidelity, or gap value is stated anywhere in it -- only the code that produces the spectrum and occupation-probability plot. The evolution itself runs on QuTiP's own in-process ODE integrator (`mesolve` deferring to `sesolve`); no external quantum hardware or third-party simulator backend is invoked.

• qore's `ASP` (Adiabatic State Preparation) class, applied to open-pit-mine scheduling

  • Quantum Computation by Adiabatic Evolution

  qore (HaoTy/qore on GitHub, BSD-3-Clause) is a small, one-day-pushed (March 2022) project whose setup.py names its author as "Q Ore Team" and describes it as "Q Ore leverages quantum power to speedup open pit mining algorithms", linking to `https://github.com/cs210/IBM-QC-Open-Pit-Mining/` -- `cs210` is Stanford's CS210 course organization on GitHub, whose own org profile names it "CS210 Software Project Experience" and gives its location as "Stanford, CA", though the linked `cs210/IBM-QC-Open-Pit-Mining` repository itself no longer exists (404) and no sponsorship relationship is stated anywhere fetched this session. It ships qore/algorithms/asp.py, whose module docstring reads "The Adiabatic State Preparation algorithm. See https://arxiv.org/pdf/quant-ph/0001106.pdf", the same paper this record cites, and the identical sentence is repeated as the docstring of the class `ASP(MinimumEigensolver)` it defines.

  `ASP._set_default_initial_operator` builds the initial Hamiltonian $H_B = \sum_i X_i$ and `_set_default_initial_state` builds its ground state $|-\rangle^{\otimes n}$ via `(Minus ^ self.num_qubits).to_circuit()`. `_construct_circuit` then Trotterizes the interpolation across `nsteps` steps using the midpoint rule $\xi_i = (0.5 + i)/\text{nsteps}$, appending per step one `circuit.hamiltonian(operator, xi*evol_time/nsteps, qubits)` gate for the caller-supplied problem Hamiltonian and one `circuit.hamiltonian(initial_operator, (1-xi)*evol_time/nsteps, qubits)` gate for $H_B$ -- a per-step split-operator realisation of $H(t) = (1 - t/T)H_B + (t/T)H_P$, this record's own Eq. 2.23. The problem operator is whatever `operator` is passed into `compute_minimum_eigenvalue(operator, aux_operators)`, docstringed there as "The problem Hamiltonian `H_P`."

  scripts/run_asp.py supplies $H_P$ from qore.model.mine.Mine, whose `gen_Hp` method is docstringed "Generate the profit Hamiltonian $H_{p} = \sum_{i} w(i)(1-Z_{i})/2$" and is built from a block-value grid written directly in the script -- a hard-coded 2-row-by-3-column array of values (including one infeasible block marked `inf`), overwritten before use by a second 3-row-by-5-column array in the same script -- not loaded from any external dataset. `run_asp.py` calls `qmine.solve(asp, False, False)`, so `Mine.solve`'s `penalty` argument is `False`; inside `solve`, the operator handed to `algorithm.compute_minimum_eigenvalue` is `self.gen_Hamiltonian(penalty)`, and with `penalty = False` that method's `if penalty:` branch -- the one that would return `-Hp + penalty*Hs` -- is skipped, so it instead returns `self.gen_projected_Hamiltonian()`. That method does not add a weighted `Hs` term to `Hp` at all: it uses `Hs` only to build a 0/1 diagonal projector onto the computational-basis states where `Hs`'s smoothness constraint evaluates to zero (`state_fn = (-self.Hs @ (Plus^n)).reduce().eval().to_dict_fn()`, keeping the indices where the resulting amplitude is near zero), then returns `(p_op @ -self.Hp @ p_op).reduce().to_matrix_op()`, a projection of `Hp` onto that hard-constraint subspace rather than a penalty-weighted sum of the two. `Hp` and `Hs` are still passed separately as `aux_operators` alongside this projected operator (`algorithm.compute_minimum_eigenvalue(self.gen_Hamiltonian(penalty), [self.Hp, self.Hs])`); for `algorithm = ASP(...)`, it is this projected operator that becomes `self._operator` and is what `_construct_circuit` interpolates toward as $H_P$.

  HaoTy/qore, commit 2d866615bb05c5b8a5d6f6c7a2c1ca1008e7851b: qore/algorithms/asp.py (class `ASP`, methods `_construct_circuit`, `_set_default_initial_operator`, `_set_default_initial_state`, `compute_minimum_eigenvalue`) and qore/model/mine.py (class `Mine`, methods `gen_Hp`, `gen_Hamiltonian`, `gen_projected_Hamiltonian`, `solve`), driven by scripts/run_asp.py. The code targets the pre-1.0 Qiskit API pinned in setup.py (`qiskit>=0.25`) -- `qiskit.opflow`, `qiskit.algorithms.MinimumEigensolver`, `qiskit.providers.aer.QasmSimulator` -- modules current Qiskit has since removed or relocated (a search of today's Qiskit/qiskit repository for a `QuantumCircuit.hamiltonian` method the way this code calls it finds none), so this entry reports the repository's own code as written, not a claim that it runs against a current Qiskit install.

  run_asp.py constructs `ASP(evol_time=10, nsteps=20, quantum_instance=QasmSimulator())` and calls `qmine.solve(asp, False, False)`, printing the returned `MiningProblemResult`. This record did not execute the script, so no specific bitstring or profit value from that run is stated here -- only that the script targets Qiskit's `QasmSimulator`, a classical statevector/qasm simulator backend, not any named quantum hardware.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Alternate a cost unitary with a mixer, p times

  Read the objective as a sum of clause terms and turn each term into a small diagonal unitary; alternate p rounds of that cost unitary with a transverse-field mixer, starting from the uniform superposition, and measure. The circuit depth is fixed by p before anything is optimised, and the paper proves exactly one number about what comes back — for p = 1 on 3-regular graphs, a cut at least 0.6924 of the optimal one — stated as an approximation ratio, not a running time and not a comparison with any classical algorithm.

In the Atlas

• Quantum adiabatic evolution

  An optimization pattern that slowly deforms an easy ground state into the ground state of a problem Hamiltonian.

Sources

• Quantum Computation by Adiabatic Evolution↗Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser · 2000theory yes · simulation ? · hardware ?