Quantum approaches: two speedups at their true price
The quantum computer is the list's oldest deus ex machina, invoked in the puzzle's first month and every few years since. There are exactly two real stories to tell: Grover's quadratic speedup, and annealing on a QUBO encoding. This page tells both properly, does the arithmetic against Eternity II's actual numbers, and reports the complete community record: nineteen years of asides, one unfinished embedding attempt, zero runs.
The quantum computer entered the Eternity II archive in the puzzle's first
month. In May 2007, weeks before most members had written a solver, one
proposed founding the "Homebrew Quantum Computer Club"
(message 263). It was a joke,
and the first appearance of a figure that would haunt the list for nineteen years:
the machine from the future that dissolves the whole problem. It has been
invoked as fantasy, as satire, as Santa's-list wish, and occasionally as a
genuine technical question. What it has never been, anywhere in the record,
is used: no member has ever reported running any quantum hardware or
simulator against any Eternity II instance, of any size.
That thin record is worth a page anyway, for two reasons. First, there are
exactly two real quantum stories relevant to E2, Grover search and
annealing on an Ising encoding, and both can be told with actual
arithmetic, in a way the list's scattered asides never quite assembled.
Second, the arithmetic is clarifying: quantum computing offers the single
strongest speedup any physics currently promises for blind search, and
pricing E2 against it shows sharply why this puzzle resists: the same
walls the structure pages map, seen from the
far side.
Grover's algorithm is the
headline result of quantum search. Given N possibilities and a black-box test for
"is this one a solution?", a quantum computer finds a solution in about
4πN evaluations of the test, where a classical machine
needs on the order of N. Two fine-print clauses matter here:
The speedup is quadratic, and that is a theorem, not a lower bound to be
beaten. For black-box search, Bennett, Bernstein, Brassard and
Vazirani proved the square root
is optimal: no quantum algorithm does better without exploiting problem
structure. Quantum computers are not known to solve NP-complete problems
in polynomial time; on unstructured search they halve the exponent, full
stop.
With M solutions the cost is N/M. Plentiful solutions help
quantum search exactly as they help classical search. Eternity II was
designed to have essentially one. The
adversarial design that starves classical solvers starves Grover too.
Now the arithmetic, against E2's actual numbers.
Against the raw space. The naive configuration count (every piece
anywhere, any rotation) is the famous ∼10557
(known facts). Grover turns that into
10557≈10278.5
sequential oracle calls. Halving 557 leaves 278: a number that does not
care whether your machine does one operation per second or per Planck time.
Nothing more needs saying about the unstructured version.
Against the structured tree. The fair comparison is not the raw space
but the tree a good backtracker actually walks, and the community did this
arithmetic itself, in the one genuinely technical Grover exchange in the
archive. In October 2021, prompted by Akos's estimate that a full sweep of
the search space needs at minimum 3.4×1040 operations,
Peter McGavin asked whether Grover could search that tree in
3.4×1040≈1.8×1020 operations on a machine
with log2(3.4×1040)=135 qubits
(message 10258), and restated
it carefully two messages later: "Could Grover's or another quantum
algorithm search the E2 tree in O(sqrt(N)) operations?"
(message 10260). Nobody on
the list answered. The literature does: yes, almost.
Montanaro's quantum backtracking walks a
classical backtracking tree of T nodes in roughly T (times
polynomial factors) quantum steps, structure and pruning included. Take this
wiki's own number for the tree's plateau width, about 1045 partial
boards (complex theory):
1045≈3×1022 quantum steps.
Is 3×1022 feasible? Grant the machine an absurd gift: one full
oracle call (verifying an entire board's 480 edge constraints, reversibly)
every nanosecond. Grover iterations are inherently sequential (running k
machines in parallel only buys k, not k), so that is
3×1013 seconds: about a million years. At the kHz–MHz logical
gate rates that error-corrected machines actually project, it is longer than
the age of the universe. And McGavin's 135 qubits count only the index
register: the oracle must hold the board (256 cells × 10 bits of
piece-rotation is already ~2,560 logical qubits), the used-piece
bookkeeping, and the ancillas that make the check reversible. That adds up
to thousands of
logical qubits, meaning millions of physical ones at current error-correction
overheads, against the roughly 150 noisy qubits accessible in 2026
(message 11813).
The remarkable thing is that the list got this right early, from an
armchair. In February 2009 Max, reading a David Deutsch essay, concluded
that "even if we had a large quantum computer today, the speedup for
problems like chess and likely also E2 would be very moderate"; one would
need new, undiscovered algorithms on top
(message 6484). That is the
BBBV theorem, paraphrased on a puzzle mailing list two years into the hunt.
Story two: annealing, and the puzzle as an energy landscape#
The second story is more interesting because it is closer to buildable.
Quantum annealers (D-Wave's machines) do not run Grover. They physically
cool a network of coupled qubits toward the ground state of a programmable
energy function, a QUBO (quadratic unconstrained binary optimization),
equivalently an Ising model.
Lucas's 2014 catalogue gives Ising
formulations for all of Karp's 21 NP-complete problems, and edge matching
encodes exactly in its style. Take the same variable the
SAT encoding uses,
xp,c,r=1 if piece p sits at cellc with rotation r, and write
with A>B>0: the first term punishes cells not holding exactly one
placement, the second punishes pieces not used exactly once, the third adds
B per mismatched interior join. The ground state has energy zero exactly
when the board is a perfect solution. Pleasingly, low-lying excited
states are high-scoring partials, so the encoding natively speaks the
record ladder's language.
Then you size it.
Variables:256×256×4=262,144 logical binaries.
Couplings: every cell's 1,024 candidate placements are mutually
exclusive, which means (21024)≈5×105 quadratic terms
per cell, and again per piece: order 108 couplings before the
mismatch terms are counted.
Hardware: the largest annealers in 2026 carry on the order of
5,000 physical qubits, each coupled to 15–20 neighbours. Mapping a logical
problem onto that sparse graph (minor-embedding) represents each
densely connected variable by a chain of physical qubits; the practical
ceiling for a fully connected problem is a couple of hundred logical
variables per chip. A single cell's one-hot group (1,024 mutually
coupled variables) already exceeds that several times over, and there are
256 cells.
The gap is not an engineering generation; it is three-plus orders of
magnitude in variables and four in couplings, before chain overhead.
(D-Wave's hybrid solvers accept million-variable QUBOs, but there the
quantum processor is a subroutine inside a classical heuristic; a hybrid
"result" would not be a quantum result.) And behind the size wall stands an
older one: an annealer, at any size, is a physical local-search machine
descending this energy landscape, the same landscape on which the
community's simulated annealing and local search
plateaued in the 460s. Nothing in quantum annealing theory promises to
tunnel through the scarcity that was engineered into this
puzzle; on spin-glass-like instances the
adiabatic gap closes and the anneal time blows up. Alan's cheerful 2010
remark that "Simulated Annealing is one problem QComputers are expected to
be especially good at"
(message 7802) is precisely
the hope, and it remains, on this problem class, a hope rather than a result.
The "Quantum computing" thread: "an obvious way to solve the puzzle... how many bits can they manage?"; Anurag: no hardware exists; Grech: a real QC is worth more than the prize; a counterfactual-computation joke
Quantum listed among "other ways" (3995), doubted for interference (4032), wished for (4850), satirized as the "time-travelling quantum computer" (5413, 5442), joked about (5542), tied to P=NP musings (5629), listed with holographic and DNA computing (5736)
"We either need a 2048 bit quantum computer or else buy a lottery ticket"; D-Wave named (first hardware pointer); the Ambainis and Aaronson–Ambainis papers posted; quantum tunnelling hopes
The "Pseudoquantum" processor-per-cell idea; quantum annealing + D-Wave's free community time suggested; the one hands-on attempt, a D-Wave DQM model stuck on embedding: 15-way connectivity vs 22 colours, "hoping they can yield a Zephyr chip soon"
IBM's 127-qubit campus machine flagged (11283); quantum listed among realms a breakthrough could come from (11346); Google's Willow announcement relayed (11407)
Quantum computers named as one of the two near-term routes (11788); is the SAT work "pre-work... for an eventual quantum computer?" (11812); the sizing answer: ~150 noisy qubits exist, an E2 set-cover circuit needs 3,000+, a ~30-qubit QAOA/Grover proof-of-concept is the realistic ceiling; "this does not look like something that will solve Eternity II anytime soon"
That is everything. (The archive's remaining "quantum" hits are figurative
uses like "quantum leap", or physics asides unrelated to computing.) Summed
up: three technical moments in nineteen years (Max's 2009 armchair theorem,
McGavin's 2021 square root, mulisak's 2026 qubit count), one unfinished
D-Wave embedding, and zero reported runs of anything, on any instance. The
community record is thin, and this page's job is to say so rather than
inflate it.
Quantum as a lens, not a tool
Here is the sober use of all this. Grover-type search is the strongest
generic speedup any known physics offers: it halves the exponent, where
every hardware story on this wiki (FPGA,
GPU, clusters) only divides by a
constant. And E2 shrugs it off: 1045→1022.5 still loses to any
conceivable clock. The argument of
why a faster computer doesn't help
survives even the best speedup physics has on offer, which is the
strongest form of that argument. Meanwhile the annealing story lands on
the other wall: as an energy landscape, E2 was
built to have one needle and no gradient toward it.
Quantum's real E2 relevance today is that pricing the puzzle against
hypothetical hardware locates the difficulty precisely where the structure
pages say it lives: in the tree, not the clock.
The gap between "wished for" and "measured" is, for once, cheap to close.
Annealer time is rentable by the minute, and the experiment itself is small:
Encode the ladder, not the puzzle. Write the QUBO above (or Poitras's
discrete-variable form, message 11176)
for Brendan Owen's benchmark suite starting
at 4×4 and 5×5, sizes whose one-hot groups actually embed on a
~5,000-qubit chip.
Run three solvers on the same H: the real QPU, classical simulated
annealing, and a modern tabu/SA hybrid: same energy function, same
cutoff. The QPU must beat the classical anneal on its own encoding
before any larger claim means anything.
On gate hardware, do mulisak's proof-of-concept: QAOA or Grover on a
~30-qubit set-cover toy (message 11813),
knowing in advance it demonstrates machinery, not progress.
Report the scaling curve, not the anecdote: success probability and
time-to-solution versus board size, alongside the classical baseline. The
realistic best case is not a solved 6×6; it is a measured crossover or,
more likely, a clean, sourced entry for the
dead ends ledger, which on this wiki also
counts as progress.
Until someone does that, the scoreboard reads: two beautiful
algorithms, one arithmetic that ends in 1022 sequential steps, one
encoding three orders of magnitude too large for its hardware, and a
nineteen-year archive in which the quantum computer remains what it was in
May 2007: the club nobody ever built.