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).

An Ising or QUBO operator, diagonal in the computational basis, whose extremal eigenvector encodes the problem's solution — given, for QAOA, as a sum of clause terms $C(z) = \sum_{\alpha=1}^{m} C_\alpha(z)$ over $n$ bits and $m$ clauses; given, for adiabatic evolution, as the final Hamiltonian $H_P$ of an interpolation whose starting point $H_B$ has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding.

1. Cost Hamiltonian, diagonal in the computational basis → Assignment, with the objective value it achievesinterpolate H(t) between H_B and H_P, tracking the instantaneous ground state

   The Hamiltonian is built directly from the problem: for an $n$-bit instance $C_1 \wedge \cdots \wedge C_M$, $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, Eq. 1.2), and "the Hamiltonian that governs the system's evolution is constructed directly from the clauses of the formula" (§6). For the satisfiability construction the two endpoints are $H_B$, built per-bit and weighted by each bit's clause degree so that "its ground state is easy to construct" (§2.4, Eq. 2.22), and $H_P$, whose ground state "encodes the satisfying assignment" (Abstract). The path is $H(t) = (1-t/T)H_B + (t/T)H_P$ (Eq. 2.23), equivalently $\tilde H(s) = (1-s)H_B + sH_P$ for $s = t/T \in [0,1]$ (Eq. 2.24). Starting at the ground state of $H(0) = H_B$ and evolving under $i\frac{d}{dt}|\psi(t)\rangle = H(t)|\psi(t)\rangle$ (Eq. 2.1), the adiabatic theorem says that "if the gap between the two lowest levels, $E_1(s) - E_0(s)$, is strictly greater than zero for all $0 \le s \le 1$", then the overlap with the target ground state approaches 1 as $T \to \infty$ (Eq. 2.6). Writing $g_{\min} = \min_{0 \le s \le 1}[E_1(s) - E_0(s)]$ (Eq. 2.7), "a closer look at the adiabatic theorem tells us that taking $T \gg E/g_{\min}^2$" — where $E$ is the largest matrix element of $d\tilde H/ds$ between the two lowest instantaneous eigenstates over the whole path (rendered here from Eq. 2.9 for legibility) — can make the final overlap "arbitrarily close to 1" (Eq. 2.10). assumption: the guarantee needs $g_{\min}$ nonzero over the whole interval, and the paper is explicit that this is the typical case rather than a proved one — "typically $g_{\min}$ is not zero" (§2.6) — so a degenerate or closing gap sits outside what Eq. (2.6) certifies. Measuring $|\psi(T)\rangle$ in the computational basis returns the assignment. assumption: how large $T$ needs to be is not bounded in general — "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; restated at §1, "we are unable to estimate the required running time $T$ in general", and at §6, "though we are unable to determine, in general, the required running time"). Three special symmetric cases are proved polynomial, and the paper's own reading of that result is modest: "even though these cases are easily seen to be classically solvable in polynomial time, our algorithm operates in an entirely different way from the classical one, and these examples may provide a small bit of evidence that our algorithm may run quickly on other, more interesting cases" (§6). Realised as a gate-model circuit, "the number of factors in the product is proportional to $T^2$ times a polynomial in $n$" (§5), so a bound on circuit cost is exactly as available as a bound on $T$ itself — which is to say, not available in general.

   assumption

A bit string $z$ read off the computational basis — the assignment — together with the objective value it achieves, or, for the adiabatic route, the stated promise that this string is (with fidelity approaching 1, for a long enough evolution time) the true minimiser. Neither route returns an energy with an error bar; both return a string.

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

"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.

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

  About

  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.

  Methods

  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.

  Data

  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.

  Code

  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.

  Results

  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

    Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser · 2000

  About

  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.

  Methods

  `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`."

  Data

  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$.

  Code

  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.

  Results

  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.

• Quantum adiabatic evolution · Qiskit

  From the repository — run, not written up from a paper · native

  About

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

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Two-qubit interpolation checked by construction · schedule, parity, and final-energy invariants recorded

• Quantum adiabatic evolution

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