Sign outOpen workspaceSign in

SlotLayer 0

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.

Takes

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)=∑α=1mCα(z)C(z) = \sum_{\alpha=1}^{m} C_\alpha(z) over nn bits and mm clauses; given, for adiabatic evolution, as the final Hamiltonian HPH_P of an interpolation whose starting point HBH_B has an easily-constructed ground state. Neither method is told how the operator was built, or by which encoding.

Returns

A bit string zz 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.

This one, drawn

Search a cost Hamiltonian for the assignment it minimisesAlternate a cost unitary with a mixer, p timesInterpolate slowly to the problem HamiltonianAlternate a cost unitary with a mixer, p times — click the name to read about itAlternate a cost unitary with a mixer, p timesInterpolate slowly to the problem Hamiltonian — click the name to read about itInterpolate slowly to the problem HamiltonianCost Hamiltonian, diagonal in the computational basis — you start hereAssignment, with the objective value it achieves — you finish here

Drag to pan. Pinch, or hold ctrl and scroll, to zoom. Arrow keys pan, plus and minus zoom, zero resets the view.

From Cost Hamiltonian, diagonal in the computational basis to Assignment, with the objective value it achieves

A circle is an object you are holding. Each line between the two ends is one recorded way through this slot; where a way is built from smaller slots, those are its own lines. Circles are named on hover, and each one is a link.

Nothing drawn here has a recorded way through it that this figure leaves shut. See it on the map

Why this is a layer

Both routes here read the same object — an operator diagonal in the computational basis whose lowest state is the problem's answer — and hand back the same kind of thing: a bit string, not an energy. What separates them is what that string is guaranteed to be, and the boundary is drawn by the authors of one route against the other, in their own paper: "We are focused on finding a good approximate solution to an optimization problem whereas the Quantum Adiabatic Algorithm, QAA, is designed to find the optimal solution and will do so if the run time is long enough." The two constructions sit close enough that one is literally a Trotterization of the other, in the same paragraph: "A Trotterized approximation to the evolution consists of an alternation of the operators U(C, γ) and U(B, β)." So the choice a reader makes here is not between two different objects — it is between a guarantee bought with more circuit depth (adiabatic evolution, at a cost its own authors state they cannot bound in general) and a guarantee given up for a fixed, shallow circuit (QAOA, at a ratio its authors can state exactly, for one problem, at one depth).

Ways to do this

2 methods recorded

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

  • Interpolate slowly to the problem Hamiltonian

    Build a time-dependent Hamiltonian H(t) that starts at an initial Hamiltonian whose ground state is trivial to prepare and ends at the final Hamiltonian encoding the problem, interpolate between them over a time T, and let the state track the instantaneous ground state along the whole path. The adiabatic theorem proves this works whenever the gap above the ground state never closes and T is long enough — and the same paper states, in the same breath, that outside a few symmetric special cases it cannot say how long that is.

Routes that skip this layer

No recorded route avoids this step.

This is a step inside

Nothing in this graph needs this as a step, so it is where a reading starts.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.