Quantum Annealing’s Ideal Form Is the Gate Model in Disguise

Marin Ivezic July 13, 2026

21 minutes read

Introduction

In February 2007, at the Computer History Museum in Mountain View, a Canadian startup called D-Wave demonstrated what it billed as the world’s first commercially viable quantum computer. Sixteen qubits. A Sudoku puzzle solved live, by a processor that was actually sitting in Burnaby, British Columbia. The machine ran quantum annealing, and the announcement split its audiences: many physicists questioned whether the box was doing anything usefully quantum at all, while my clients asked a blunter question. I had been assessing quantum risk since 2000, when a European government engaged my firm to evaluate what quantum computers would eventually mean for national cryptographic infrastructure, and by that spring the question landing in my inbox was simple. Is this the machine that starts the countdown for RSA?

My working answer was no, and about the box itself I was right: Orion could not run Shor’s algorithm through any control D-Wave exposed, and no descendant of it has run Shor’s since. But my reasoning was wrong in a way that still delights me. I had argued from taxonomy: no gates, therefore not that kind of computer, therefore not on the road to breaking cryptography. The taxonomy turned out to be false. Three years earlier, Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev had proved, in “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation” (a result I will call the AVKLLR proof, after the initials of its six authors), that the gate-free, settle-to-the-bottom model of computing is, in its idealized form, exactly as powerful as the circuit model. The theorem did not make Orion a universal computer. It said something stranger: a computer with no gates at all could be one.

To my thinking it remains the most eye-opening result I have met in this field, and the proof outshines the theorem. It builds an energy valley whose floor holds an entire computation, every timestep at once, a movie frozen at the bottom of a canyon. I have wanted to walk readers through that construction for years, and this article finally does it, ending with the fine print that explains why the AVKLLR proof, for all its power, still does not put your RSA keys at the mercy of an annealer.

Walk into a quantum computing lab today and you will find one of two very different species of machine. (Not the only two in existence; measurement-based designs and analog simulators are out there too. But these two dominate the market, and this story.)

The first species, built by IBM, Google, Quantinuum, IonQ, and most of the industry across the major hardware modalities, is the gate-model (or “circuit-model,” or “universal”) quantum computer. It works the way the textbooks describe: qubits are prepared, then a long sequence of discrete operations called gates is applied to them, one after another, like a musician playing sheet music note by note. Each gate is physically a calibrated control operation (a microwave or laser pulse on most platforms), and the program is the score: which gates, on which qubits, in which order. Shor’s algorithm, Grover’s algorithm, and the simulation of molecules all live in this language. The character of the machine is digital through and through: a discrete alphabet of operations, composed in time.

The second species, commercialized almost single-handedly by D-Wave, is the quantum annealer. It has no gates and no score. You encode your problem into a terrain of energies, arranged so that the configuration you are looking for is the lowest-energy configuration, the deepest valley. Then you let physics do what physics does: start the system in an easy, well-understood state, and slowly morph the terrain from the easy one into the one encoding your problem. Morph it slowly enough and the system stays settled in the deepest valley of the shifting terrain. Read out the qubits and, if all went well, you are holding the answer. The character of this machine is analog: one continuous physical evolution, with no steps at all.

Even the name comes from outside computing. A blacksmith anneals metal by heating it and letting it cool slowly, so the atoms have time to find their orderly, low-energy crystal arrangement instead of freezing mid-chaos into defects and internal stress. Cool too fast and you lock the imperfections in; cool slowly and the material finds its own perfection. Quantum annealing borrows the idea, name and all, with one addition classical metallurgy lacks: a quantum system can tunnel straight through a thin energy barrier instead of having to climb over it.

Put the two species side by side and they seem to belong to different technological universes. One executes instructions; the other obeys thermodynamic instinct. One is a processor; the other is, in spirit, a lump of programmable matter cooling down. It seems obvious that such machines must be good at different things, that each must own some territory the other cannot touch.

They don’t. And that is a theorem.

It is, precisely, the AVKLLR proof: anything one idealized species can do efficiently, the other can do efficiently too, each simulating the other with polynomial overhead. The two tribes, in the idealized limit, are one.

The proof rests on a construction with a distinguished pedigree. Richard Feynman sketched it in 1985, Alexei Kitaev sharpened it into a complexity-theoretic tool in the late 1990s, and the AVKLLR authors completed the equivalence at FOCS 2004. Understanding it rewires your intuition about what computation and energy have to do with each other, which is reason enough for the tour.

What “equally powerful” actually claims

“Equally powerful” is both a stronger and a weaker claim than it sounds, so pin it down before admiring it.

In complexity theory, the dividing line that matters runs between feasible and hopeless. Does the cost of solving a problem grow polynomially with its size (like $$n^2$$ or $$n^3$$: expensive, but payable), or exponentially (like $$2^n$$: a wall no engineering will ever climb)? The set of problems a quantum computer can solve with polynomial resources has a name: BQP (decision problems, bounded error probability, for the sticklers).

The AVKLLR proof says the gate model and the idealized adiabatic model of quantum computation have exactly the same computational power: the same BQP. If a gate circuit solves a problem in time $$T$$, there exists an adiabatic process that solves it in time polynomial in $$T$$, and vice versa. Translating between the models costs something, but the cost never explodes. That is the entire ballgame: were the translation cost exponential, a problem could be feasible on one machine and hopeless on the other, and the models would be “equivalent” only in a uselessly abstract sense. Because the overhead is polynomial, the boundary between feasible and hopeless sits in the same place for both machines. One honesty clause belongs here: in the original construction the polynomial is of high degree, so read this as a complexity classification, not an engineering recipe. An $$n^{100}$$ algorithm is “feasible” only to a theorist.

Note what the AVKLLR proof does not say. It does not say the machines run at the same speed, and it does not say every physical annealer is secretly a universal computer. We will return to that fine print, because most of the public confusion lives there. The proof’s actual content: neither species can reach any problem that lies, even in principle, beyond the other’s reach.

One direction of the proof is routine. The other is the gem.

A circuit can fake a slow melt

Simulating an adiabatic computer on a gate-model machine is standard technology. An adiabatic computation is a continuous evolution under a slowly changing Hamiltonian $$H(s)$$, the mathematical object that encodes the energy terrain, interpolating from an easy start to the problem:

$$$
H(s) = (1-s)\,H_{\mathrm{start}} + s\,H_{\mathrm{problem}}, \qquad s: 0 \to 1.
$$$

A gate machine cannot do anything continuous, but it does not need to: it chops the smooth evolution into many tiny discrete time steps and applies each one as a gate. This is Trotterization, and it leans on the fact that evolution under a Hamiltonian built from pieces can be approximated piecewise,

$$$
e^{-i(A+B)\,\delta} \;\approx\; e^{-iA\,\delta}\, e^{-iB\,\delta}
$$$

for small time slices $$\delta$$, with errors that shrink as the slicing gets finer. The number of steps needed grows only polynomially in the problem size and the accuracy demanded. None of this is proof-technology alone: digitized adiabatic evolution has been run on real gate hardware, and QAOA, one of the most-studied near-term algorithms, is a close relative. Its alternating layers are what a coarsely Trotterized anneal looks like, though its optimized schedules need not approximate any smooth sweep.

So gates can imitate melting. The astonishing direction runs the other way: a machine whose only move is settling to its lowest energy must reproduce a computation made of billions of precise steps in a specific order. Where, in an energy terrain, does sequence live?

Turning a movie into a mountain range

Someone hands you a quantum circuit: $$n$$ qubits in a known starting state $$|\psi_{\mathrm{in}}\rangle$$ (take it to be all zeros; any fancier preparation folds into the circuit’s first gates) and a sequence of gates $$U_1, U_2, \dots, U_T$$. You must build an energy landscape, a Hamiltonian made of local terms that each touch only a few qubits, whose lowest-energy state hands over the circuit’s output. And that landscape must be reachable by a slow anneal in polynomial time.

The obvious idea, and why it fails

The obvious idea: make the ground state be the circuit’s final output, $$U_T \cdots U_1 |\psi_{\mathrm{in}}\rangle$$, and penalize everything else.

You can write such a penalty formally: one minus the projector onto the output state. What you cannot do is compile it into local interactions, each term examining only a handful of qubits, without already knowing the state the circuit is supposed to produce. “This state is the output of that particular billion-gate computation” is a global property, and checking it means running the computation. The approach is circular.

Feynman’s move, and it is the conceptual heart of everything that follows, was to reward legal motion instead of the destination. Don’t build a landscape whose bottom is the final frame of the movie. Build a landscape whose bottom is the entire movie.

The history state

Introduce a second register alongside the $$n$$ working qubits: a clock that counts from $$0$$ to $$T$$. The state we want as the unique ground state is the history state:

$$$
|\eta\rangle \;=\; \frac{1}{\sqrt{T+1}} \sum_{t=0}^{T} \Big( U_t \cdots U_1 \,|\psi_{\mathrm{in}}\rangle \Big) \otimes |t\rangle_{\mathrm{clock}},
$$$

with $$U_0$$ read as the identity. Read it slowly, because it repays the effort. It is an equal-weight superposition of $$T+1$$ terms. In each term the clock reads some time $$t$$, and, entangled with that clock value, the work register holds the computation frozen after exactly $$t$$ gates. Every frame of the movie coexists on one strip, each frame stamped with its timestamp. The answer is in there, but only as one frame among many.

What remains is to design local energy penalties that make this state, and only this state, sit at the bottom.

Building the landscape

The clock is encoded in unary, a “thermometer” of qubits where time $$t$$ is written as $$t$$ ones followed by zeros: for $$T = 3$$, the legal readings are 000, 100, 110, 111. This looks wasteful, and that is the point. With this encoding, clock legality is checkable from adjacent pairs of clock qubits alone, and each propagation check needs only a small neighborhood: a few adjacent clock qubits plus the one or two work qubits its gate touches. Locality is the currency of the whole construction, and unary buys it.

Three families of small penalty terms make up the Hamiltonian, each a projector that charges a unit of energy to anything violating its rule:

$$$
H \;=\; H_{\mathrm{clock}} + H_{\mathrm{input}} + \sum_{t=1}^{T} H_t.
$$$

Clock penalties ($$H_{\mathrm{clock}}$$) glance at each adjacent pair of clock qubits and charge energy for any illegal thermometer pattern, meaning a 0 followed by a 1. This confines the clock to its $$T+1$$ legal readings.

Input penalties ($$H_{\mathrm{input}}$$) look only at the $$t=0$$ slice: they charge energy if the clock reads zero while any work qubit deviates from the prescribed starting value. This nails down the first frame.

Propagation penalties are the heart. For each timestep $$t$$ there is a term that can see only two adjacent frames, the parts of the state where the clock reads $$t-1$$ or $$t$$, engineered to cost zero energy precisely when frame $$t$$ equals gate $$U_t$$ applied to frame $$t-1$$. One honest note before the formula: what follows is the effective form, written in the abstract clock basis. In the literal unary encoding, each clock projector and transition becomes an operator on a few adjacent clock qubits plus the work qubits the gate touches (five-body in the original proof), which is what earns the term its locality. Written out:

$$$
H_t = \tfrac{1}{2}\Big( \mathbb{1}\otimes|t\rangle\langle t| \;+\; \mathbb{1}\otimes|t{-}1\rangle\langle t{-}1| \;-\; U_t \otimes |t\rangle\langle t{-}1| \;-\; U_t^{\dagger} \otimes |t{-}1\rangle\langle t| \Big).
$$$

You do not need to manipulate this expression to use its meaning, which fits in one sentence: this term is happy if and only if the two frames it can see are correctly linked by the right gate. It is a locally checkable “did this one step follow the rules?”, a referee who watches a single instant of the game. If you enjoy verifying such things, apply $$H_t$$ to the history state and watch the four terms cancel pairwise. The whole Hamiltonian annihilates $$|\eta\rangle$$: the ground energy is exactly zero, with every constraint satisfied simultaneously. In the jargon, the Hamiltonian is frustration-free.

The domino argument

Now the question everything hinges on: why is the history state the only thing at the bottom?

No single penalty term can see the whole computation; each referee watches only two neighboring frames. But the referees overlap. The propagation term for step $$t$$ shares frame $$t$$ with the term for step $$t+1$$, which shares frame $$t+1$$ with the next, and so on down the line. It is a chain of dominoes in which each domino constrains only its neighbor, and yet the chain, taken together, pins down the entire sequence. The only way to satisfy every myopic referee at once is a globally consistent history: correct input, legal clock, and every single gate applied correctly in order. Any component of a state that deviates anywhere (a wrong starting value, a botched gate at step 583,204, an illegal clock reading, a frame out of sequence) violates at least one overlapping constraint and pays energy for it.

Without the input penalties, incidentally, the terrain would have many valleys of equal depth: every possible starting configuration generates its own perfectly legal movie. The input terms collapse this degeneracy to a single state, the movie that begins the way your computation begins.

Local rules have enforced a global object. The same move powers error-correcting codes and, for that matter, crystals: overlapping local constraints, none of which knows the big picture, jointly determining a unique global structure.

Why the movie must be evenly exposed

One more question hides in the walker picture below: why does the ground state spread its amplitude evenly across every frame, instead of piling it onto, say, the final one?

Because of a hidden change of variables. Define the unitary $$W = \sum_t (U_t \cdots U_1) \otimes |t\rangle\langle t|$$, which loads each clock value with the computation carried out up to that moment. Undo that loading, conjugating the propagation Hamiltonian as $$W^{\dagger} H_{\mathrm{prop}} W$$, and every gate disappears from it. What remains has no computational content at all: a single quantum particle hopping along a line of $$T+1$$ sites (mathematically, the Laplacian of a path graph, acting on the clock alone). All the circuit structure was a disguise; underneath, the propagation term is a free walker on a line segment.

And the lowest-energy mode of a free walker on a line is the flat one: uniform amplitude across every site, the one configuration with no wiggle in it anywhere. (A guitar string’s fundamental is the closest musical analogue, though its pinned ends bow it into a half-sine arc; the walker’s free ends keep its ground mode perfectly flat.) Transform back, and “uniform over clock positions” becomes “uniform over movie frames.” The equal exposure of the history state is no aesthetic choice; the physics of the walk forces it.

Feynman’s movie projector

The walker was no accident of the proof. It is where the entire construction was born, and it answers a question this article has so far dodged: how does a discrete sequence of gates live inside continuous physical time in the first place?

Feynman’s 1985 paper was not about ground states. He wanted a quantum computer with no external controller, no classical machinery reaching in to apply gate after gate on cue. His answer was to build the clock into the physics itself. Take the hopping terms alone, without the diagonal penalties:

$$$
H_{\mathrm{Feynman}} \;=\; \sum_{t=1}^{T} \Big( U_t \otimes |t\rangle\langle t{-}1| \;+\; U_t^{\dagger} \otimes |t{-}1\rangle\langle t| \Big).
$$$

Switch this on and leave the system alone. Continuous Schrödinger evolution sets the clock excitation moving along its line of sites like a particle, and the construction is rigged so that the particle cannot move without computing: every hop from site $$t-1$$ to site $$t$$ applies gate $$U_t$$ to the work register, and every hop back un-applies it. Circuit time has become a particle’s position. The discrete program unfolds inside smooth, reversible, self-running physics; park a detector at the far end of the line, and when the cursor arrives, the work register is holding the output. (Feynman saw the catch himself: a cursor released from one site spreads and reflects off the ends of the line as it evolves. His fix was to lengthen the line and launch the cursor as a spatially broad wave packet with a narrow spread of momenta, so it glides across at near-constant speed with good odds of clean arrival.)

Kitaev’s later move, the one this article has been using, was to recast what Feynman played as a constraint. Add the diagonal terms and the hopping generator becomes a positive penalty whose zero-energy state is the uniform superposition over the walker’s positions: the film itself, rather than the screening. Feynman turned a circuit into motion; Kitaev turned the motion’s stillest state into an archive. The AVKLLR proof then established that the archive is reachable, adiabatically, at polynomial cost.

Reading out the answer

Back to the frozen version. Suppose the anneal has worked and the system sits in the history state. You measure the clock. With probability $$\tfrac{1}{T+1}$$ it reads $$T$$, and, because clock and work register are entangled, the work register is then holding exactly the circuit’s final output. Measure it and you are done.

A probability of $$\tfrac{1}{T+1}$$ sounds bad, but a standard cheat fixes it: pad the circuit with $$T$$ extra do-nothing identity gates. Now the movie’s entire second half consists of frames that all display the finished answer, so a clock measurement lands in that half with probability about one half. A few repetitions of the whole procedure and success is all but guaranteed.

And how do you reach the history state? Exactly the way an annealer reaches anything. Start from a Hamiltonian whose ground state is trivial to prepare (the input state parked at clock zero, propagation terms switched off) and slowly interpolate to the full Hamiltonian. The adiabatic theorem promises that a slow enough sweep keeps the system close to the instantaneous ground state the whole way, and delivers it to the bottom of the final landscape: the movie.

“Roll downhill to minimum energy” and “run these gates in order” have become, quite literally, the same physical event.

The gap is the load-bearing beam

Everything above establishes that the movie is the ground state. It does not yet establish the theorem, because “slow enough” is doing unexamined work in that last paragraph, and in adiabatic computing, “slow enough” is where algorithms go to die.

The adiabatic theorem’s price tag is set by the spectral gap $$\Delta$$: the energy difference between the ground state and the first excited state, at the worst moment along the sweep. The required runtime scales, roughly, as

$$$
t_{\mathrm{run}} \;\sim\; \frac{1}{\Delta_{\min}^{2}},
$$$

with more careful statements of the adiabatic theorem also weighing how fast $$H$$ changes. For the nastiest optimization terrains the gap closes exponentially fast as problems grow, the anneal must crawl exponentially slowly, and the whole equivalence would be hollow: the ground state would encode the computation, but reaching it would take geological time.

This is where the clock construction shows its quality. Recall the change of variables: the propagation Hamiltonian is secretly a particle hopping on a line of $$T+1$$ sites. The energy levels of that walk are known exactly,

$$$
E_k = 1 – \cos!\Big(\frac{\pi k}{T+1}\Big), \qquad k = 0, 1, \dots, T,
$$$

so the gap above the flat ground mode is

$$$
\Delta \;=\; 1 – \cos!\Big(\frac{\pi}{T+1}\Big) \;\approx\; \frac{\pi^2}{2\,(T+1)^2}.
$$$

The gap narrows as circuits lengthen, but only like $$1/T^2$$. That endpoint calculation, though, is the illustration, not the theorem. The hard part, and the AVKLLR authors’ real technical achievement, was controlling the gap along the entire interpolation: they prove it stays lower-bounded by an inverse polynomial in $$T$$ everywhere on the sweep. Feed that into the adiabatic runtime and simulating a $$T$$-gate circuit adiabatically costs time polynomial in $$T$$. A high-degree polynomial in their explicit constructions, to be clear; an exponentially closing gap would have doomed the sweep outright, while a polynomial one is a toll, and tolls can be paid.

That single spectral fact is the load-bearing beam of the AVKLLR proof. “The two models can reach the same states” is geometry; “the two models solve the same problems within polynomial resources” is the gap. (The original paper already pushed the construction onto a two-dimensional grid of six-state particles with nearest-neighbor interactions; Julia Kempe, Alexei Kitaev, and Oded Regev later reduced the interactions to pairs of qubits, and Roberto Oliveira and Barbara Terhal pinned those pairs to a 2D lattice. Complexity constructions, not hardware blueprints: the perturbative gadgets involved come with forbidding energy scales.)

Why your quantum annealer still can’t run Shor’s

Roughly once a year, a headline announces that a quantum annealer has “broken military-grade encryption,” and the AVKLLR proof gets drafted, incorrectly, as supporting evidence. The loudest recent cycle began in October 2024, when English-language media discovered a paper that Wang Chao’s group at Shanghai University had published that May in the Chinese Journal of Computers. By direct annealing on a D-Wave Advantage, they factored a 22-bit integer, a number your laptop factors before you finish reading this sentence; a hybrid quantum-classical method reached 50 bits; and the same paper’s claims against SPN block ciphers supplied the “military-grade” framing the headlines ran with. Follow-ons kept the cycle spinning: a 90-bit hybrid record in April 2025, and a paper titled “A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer” that, as I dissected at the time, factored a specially constructed 2048-bit integer whose two prime factors differ in just two bits, shrinking the search to a handful of unknown bits. None of these touches a real cryptographic modulus (quantum factoring records remain microscopic), and the coverage was standard output from the quantum panic industry I call Q-FUD. But the AVKLLR proof makes the underlying confusion understandable. If annealing and gates are provably the same computer, why shouldn’t an annealer do whatever Shor’s algorithm does?

Three reasons, and they fail at different layers.

First, the AVKLLR proof is about an idealized model, and no product implements it. The equivalence holds for universal adiabatic quantum computation, where you may build your landscape from any local Hamiltonian you can write down, including the tailored propagation couplings of the clock construction. A problem posed to a current D-Wave annealing QPU is encoded through the Ising biases $$h_i$$ and couplers $$J_{ij}$$, supplemented by scheduling controls (pauses, quenches, reverse anneals, per-qubit offsets):

$$$
H(s) \;=\; -\frac{A(s)}{2}\sum_i \sigma^x_i \;+\; \frac{B(s)}{2}\Big(\sum_i h_i\,\sigma^z_i + \sum_{i<j} J_{ij}\,\sigma^z_i \sigma^z_j\Big).
$$$

Far richer knobs than a decade ago; still nowhere near the freedom to write arbitrary local Hamiltonians, and the Feynman-Kitaev couplings in particular cannot be programmed through that interface. This restricted family is stoquastic, a technical property (no “sign problem”) that makes many of its equilibrium behaviors friendly to classical Monte-Carlo methods and long fed a widely shared belief that the family lacks universal power. That belief acquired a footnote this month: stoquasticity constrains equilibrium arguments, not deliberately out-of-equilibrium driving, and a July 2026 preprint by Matthias Werner argues that a globally driven transverse-field Ising model with a non-monotonic field can simulate arbitrary circuits with polynomial overhead. It is a preprint, not yet peer-reviewed, and its author is upfront that the overheads sit far beyond real hardware. So the honest statement in mid-2026: the theoretical wall between Ising machines and universality is lower than we thought, and the practical wall stands exactly where it was.

Second, hardware reality. The AVKLLR proof assumes a closed system at zero temperature, coherently tracking its ground state. A real annealer runs warm (by the standards of quantum coherence), open to its environment, and is operated as a heuristic sampler: thousands of fast, noisy anneals, keep the best result. Newer fast-anneal modes reach brief coherent regimes, but nothing resembling long, composable, error-corrected control. There is a deeper asymmetry underneath. For gate-model machines we possess a mature theory of fault tolerance, the threshold theorem and quantum error correction with surface codes, the apparatus that makes million-qubit factoring machines designable on paper. Adiabatic computation has error-suppression schemes of its own (stabilizer encodings, energy-gap protection, dynamical decoupling), but no comparably general threshold-and-architecture stack. Closing that gap is an open problem. The AVKLLR proof compares noiseless idealizations; the moment noise enters, the circuit model has a worked-out answer and the adiabatic model, so far, does not.

Third, even a perfect universal adiabatic computer would not make factoring any easier. Run Shor’s circuit through the clock construction and you get Shor’s algorithm delivered through different physics, with its heavy resource demands intact and, if anything, enlarged by the translation. Going the other way, recasting factoring as a bare optimization problem (the move behind the headline experiments), is not Shor’s algorithm in another notation, because it makes no use of the one structure Shor exploits. Shor’s exponential speedup exists only because factoring hides a periodicity that the quantum Fourier transform can extract; a bit-string-energy encoding of multiplication leaves that periodicity untouched on the table. Nothing in the equivalence theorem transfers Shor’s proven scaling to such formulations, and the experiments bear this out: annealer factorizations sit at toy bit lengths, with resource costs that published assessments find growing exponentially. What remains is a hard combinatorial search of exactly the kind annealers have never been shown to speed up exponentially.

So the crisp version for a board deck: the AVKLLR proof moves algorithms between models; it does not conjure new ones. Annealers remain interesting optimization heuristics and quantum simulators. They are not cryptanalytically relevant quantum computers in embryo. What determines Q-Day is scalable, fault-tolerant, universal quantum computation; today the gate-model roadmap is the only credible route to it, though this theorem is itself a caution against defining universality by the visible presence of gates. I map just how demanding that engineering path is, across nine capability dimensions, in my CRQC Quantum Capability Framework. Your post-quantum cryptography migration timeline should key off that roadmap and off the deadlines that regulators, insurers, and clients are already setting. To put it bluntly: today’s annealer headlines should move your PQC migration timeline by exactly nothing.

Why the AVKLLR proof earns its keep

If the AVKLLR proof changed no product roadmap, why care? Three reasons, in ascending order of depth.

It reshaped how algorithms are built. Adiabatic thinking now lives inside gate-model algorithms: adiabatic state preparation, digitized annealing schedules, QAOA. The border between the tribes has become a permeable membrane, and the AVKLLR proof is why crossing it is always legal.

Run in reverse, the same gadget founded a field. Before it proved the equivalence, Kitaev used the clock construction for something else: to show that estimating the ground-state energy of a local Hamiltonian is QMA-complete, as hard as any problem whose answer a quantum computer can even verify. This is the quantum analogue of the Cook–Levin theorem, and the founding result of Hamiltonian complexity. Read physically, it says something strange: an engineered ground state can encode an arbitrary computation, so the worst cases of nature’s own find-the-lowest-energy problems, the family that chemistry and materials science live in, are as hard as anything a quantum computer can verify. That is a worst-case statement about the problem class, not a claim about the caffeine molecule; but when someone asks why simulating matter is hard in general, one correct answer is that ground states, as a class, can hide computers.

And it erases a distinction we treated as bedrock. Dynamics and statics, running a program and cooling a system, turn out to be two descriptions of one object. A sequence of causes and effects can be repackaged, faithfully and at polynomial cost, as the equilibrium of a landscape; time can be traded for energy. Remember where the seed came from: Feynman planted it in 1985, in the same short paper where he was helping invent the field itself, which means the man who did more than anyone to talk physics into building quantum computers also, almost in the same breath, sketched the proof that its two future tribes would turn out to be one.

Not bad for a construction whose main ingredient is a thermometer.

Quantum Annealing’s Ideal Form Is the Gate Model in Disguise

Table of Contents

Introduction

What “equally powerful” actually claims

A circuit can fake a slow melt