A feasibility study of output-aware tensor-network contraction against real quantum hardware. Two real IBM Quantum jobs, 40,960 shots total, and six corrections to my own conclusions along the way. This is not a discovery, and it is not a quantum advantage claim — it is an honest account of trying to find one and coming up short, with the measurements kept and the mistakes left in.
The Question We Were Testing
We set out to test whether quantum circuits could be built where exact classical simulation cost grows much faster than the physical circuit depth needed to run them. If that gap exists and is large enough, it is the kind of thing that separates quantum computers from classical ones on a specific, well-defined task.
The honest answer is no — not on any hardware available today. But getting to that answer required correcting our own conclusions six times, and the corrections turned out to be more useful than the result itself. A seventh correction followed after publication — and then an eighth, on 11 September, which withdrew the seventh entirely after we found our own measurement was wrong. Both are covered at the end of this piece, including how the error was caught.
Classical contraction cost scales as 2w in practice, with a measured exponent of 1.984 over ten consecutive doublings of circuit width. Effective two-qubit error on IBM's Heron architecture is gate-local at 0.845%, stable across an 11.6× span in gate count and reproducible across two independent hardware jobs with different control settings. Memory is not a constraint — slicing removes it for a 1.00–3.18× FLOP penalty, and slices parallelise perfectly. Connectivity degree, not planarity, is the dominant topological lever. Standard error suppression — dynamical decoupling plus twirling — made things worse, costing 8–14% net fidelity on this circuit class. And qubit count is a hard ceiling that no amount of circuit cleverness or gate quality can raise.
Three simultaneous hardware requirements follow from this, and no currently available machine satisfies all three. More on that below.
The Method
The approach began as an "elastic box" idea: expand only the part of a computation currently needed, collapse what's finished. Formalised, that is variable elimination with an active frontier — for a graph G and elimination order π, you carry only the variables still connecting processed to unprocessed regions. A frontier of w binary variables means at most 2w table entries.
The circuit family used throughout was two layers of single-qubit RY rotations separated by a graph-defined CZ layer, which gives a deliberately modifiable interaction graph while remaining exactly simulable as a reference. The graphs themselves were banded: for n vertices and band parameter w, edges connect (i,j) whenever i < j ≤ min(n-1, i+w). This family has provably exact treewidth w — not approximately, not usually, exactly — which makes width a dial you can turn rather than a lottery you hope to win.
The hypothesis: find graphs where 2w grows fast while physical depth stays shallow enough to execute on real hardware.
The Six Corrections
Our null result was a cache artifact
An early experiment increased the contraction-cost metric by 42× and measured only a 3.5% wall-clock change. We took that as evidence the cost model was wrong.
It wasn't. At 16 qubits with frontier width 5, the state table is a few hundred bytes and lives entirely in L1 cache, so we were timing Python dispatch and memory setup — not arithmetic. Re-running at 30 qubits across widths 12–22 produced clean scaling at every step: 945× growth over ten doublings, a fitted exponent of 1.984 against a theoretical 2.000.
If your working set fits in cache, you are not measuring your algorithm.
There was no memory wall
From the scaling table we concluded memory was the binding constraint — band 27 on a 32 GB machine, and an absurd 37 exabytes at width 58.
Wrong, because it assumed dense unsliced contraction. Slicing fixes a subset of indices and contracts each assignment separately, cutting peak memory by 2k for k sliced indices. Measured overhead across every case tested: 1.00× to 3.18× FLOPs. Worse for the hardness case: slices are independent, so the computation is embarrassingly parallel and a cluster attacks it near-linearly — exactly how the classical rebuttals to Google's 53-qubit claim moved the estimate from 10,000 years to days.
Hardness must be quoted as total FLOPs against a named adversary. Width and single-machine memory are not hardness measures.
We overstated a depth penalty by using the wrong metric
Doubling the entangling layer appeared to degrade agreement badly — up to 32% relative error on one observable. But relative error on a Pauli expectation is misleading when the ideal value is small. Converting to effective fidelity (⟨P⟩measured / ⟨P⟩ideal), the real cost was F 0.93 → 0.75, not the 4× collapse the relative-error figures implied. One "57% error" observable turned out to be sampling-limited — its ideal value was 0.0267 against a ±0.01 shot-noise floor at 10k shots.
Under depolarizing-type noise, relative error on ⟨P⟩ is approximately 1−F regardless of the observable's magnitude. Report effective fidelity, and always state the shot-noise floor beside it.
Apparent depth-dependent error growth didn't survive more data
Two data points suggested effective error grew with depth: 0.48% per gate at 15 gates, 0.96% at 30. If real, that would have killed any extrapolation to the several-hundred-gate circuits we cared about. It doesn't survive a five-point measurement on native edges with no SWAP routing — the original two points were confounded by routing overhead and by the model error described next.
Our own mirror-circuit fit was wrong
We measured fidelity using mirror circuits — apply U then U†, so the ideal output is exactly |0…0⟩ with probability 1, with no classical simulation needed at any size. Our first analysis fitted a one-parameter model and reported error falling from 2.52% to 0.98% as gate count increased — and then flagged that as unphysical.
The model was wrong, not the data. A mirror circuit carries a constant penalty independent of gate count — readout error on every qubit, plus single-qubit gate error. Dividing a constant penalty by a growing gate count manufactures exactly that spurious decline. The correct two-parameter model, P(0…0) = A · (1 − ε)G, fitted to A = 0.7409, ε = 0.845% with maximum residual 2.5σ across an 11.6× span in gate count — and the fit validated itself: A = 0.7409 over 20 qubits implies per-qubit readout error of 1.49%, matching IBM Heron's published 1–2% spec.
Always separate state-prep-and-measurement error from gate-scaling error. A one-parameter fit to mirror data will always appear to show error improving with depth.
Error suppression made it worse
Effective error of 0.845% is 4.1× the device's own nominal best-quartile figure of 0.204%. We argued that gap was crosstalk, idle decoherence and readout — not gate quality — and therefore fixable with control rather than new hardware. We tested it: identical circuits, same seed, plus dynamical decoupling, Pauli gate twirling, and measurement twirling.
Every point got worse. Net fidelity fell 1–14% across the sweep. Twirling inserts extra single-qubit pulses around every two-qubit gate — several hundred at 208 gates, each with its own error. Measurement twirling adds 20 X gates immediately before readout, directly degrading the SPAM term. And dynamical decoupling protects idle qubits, but these circuits keep nearly everything busy, so its added pulses were mostly pure cost.
ε measured 0.845% and 0.860% in two independent jobs under very different control settings. That stability validates the error model more strongly than one job could — the number is robust; only our explanation for it was wrong.
What We Established
Connectivity degree dominates planarity. Measuring width bought per gate spent across topologies at n≈100 showed degree-8 random graphs buying far more contraction width per gate than heavy-hex, IBM's own planar degree-3 topology — de-planarising at fixed degree gave only 1.5×, not the 4× we expected. Degree is the lever.
Heavy-hex cannot be simultaneously hard and executable. On the real 156-qubit coupling map, the deepest circuit that still returns signal has optimised contraction width 6 — under a millisecond of classical work. Reaching two hours of classical cost takes 822 gates, where fidelity has collapsed to 3×10−4.
Qubit count is a hard ceiling. Contraction width saturates at roughly n, so maximum achievable classical cost is about G·2n regardless of connectivity or fidelity. Against a 1000-GPU adversary at 30 days, that requires n >rsim 65–70.
The Scorecard
Three requirements have to hold simultaneously: at least 65–70 qubits to set the hardness ceiling, connectivity degree of 4 or more (ideally all-to-all) to make that ceiling reachable at feasible gate count, and effective error at or below 0.1% at roughly 1,750 gates so signal survives. No device available today satisfies all three.
| Device | Qubits | Connectivity | Gate Error |
|---|---|---|---|
| IBM Fez | 156 ✓ | planar deg-3 ✗ | 0.845% measured ✗ |
| Quantinuum H2 | 56 ✗ | all-to-all ✓ | 0.06% ✓ |
| IonQ Forte | 36 ✗ | all-to-all ✓ | ~0.4% ~ |
IBM satisfies one requirement. Quantinuum satisfies two and is short only on qubit count — which is the quantity hardware roadmaps actually deliver, unlike topology, which is fixed at fabrication. A note on vendor claims: 56 all-to-all qubits at 2,000 gates is roughly four hours on a serious cluster by the accounting above. "Beyond classical simulation" claims refer to specific algorithms against specific classical methods, not to a general bound.
What This Does Not Show
- No quantum advantage, and no claim to it.
- No novel algorithm. Frontier contraction is variable elimination, which is textbook. Multi-amplitude reuse is established in the literature. The banded-graph treewidth result is standard graph theory.
- No verified large-width result. At width beyond ~50 the ideal amplitudes cannot be computed classically — that is the point of the regime. Any serious attempt needs a verification strategy designed in from the start.
- All classical cost figures are upper bounds favourable to the quantum side. We used a weak contraction optimiser; stronger presets lower adversary cost further.
What's Missing Is Not Theory
The programme's structural assumptions hold up. Classical cost scales as claimed, error does not blow up with depth, and a concrete circuit exists — degree-8 connectivity, depth 10, 395 gates, contraction width 108 — that would be classically intractable and hardware-executable at roughly 8 million shots, fewer samples than Google used for Sycamore.
What's missing is a device with roughly 70 all-to-all qubits at around 0.06% error. That is a specification, not a research direction, and it is close enough to current roadmaps to be worth writing down.
We also now know which plausible shortcut does not work, which has independent value: you cannot close a 4× effective-error gap with dynamical decoupling and twirling on this circuit class. That cost us one hardware job to learn, and might save someone else the same.
A Seventh Correction — And Then An Eighth, Which Withdrew It
Two days after publishing, one more conclusion had to be corrected — and it appeared to work against the argument above.
The 2×10w cost figure describes exact contraction. So the obvious question is what happens if you stop insisting on exact: prune the frontier table, dropping configurations whose amplitude is small relative to the largest one currently active.
At width 20, keeping 104 configurations out of 1,048,576 — 0.01% — appeared to produce an answer accurate to 1.5×10-4, running roughly 14,000× faster. Error also seemed to improve as width grew. We published that, and drew the conclusion that classical hardness must be quoted against a named accuracy target rather than a width alone.
That result was wrong, and it is now withdrawn. The error was ours, and we found it two days later while testing the same idea on real IBM heavy-hex hardware topology.
We had reported absolute error only. The pruned computation was not approximating the answer — it was returning essentially no answer. Because the true amplitudes are themselves around 10-4, an output of roughly zero registers as a small absolute error.
The headline figure reproduces exactly: 1.459×10-4 at width 20 on 104 configurations. But the largest amplitude being computed at that point is 1.4685×10-4. The relative error is 99.4%. Weighing a 2-gram letter, reporting “0 grams”, and calling it a 2-gram error.
The “error improves with width” finding falls with it: absolute error was tracking the amplitude scale, which shrinks as width grows. It never measured approximation quality at all.
Decisively, there is no threshold that both saves work and stays correct. Where pruning is faithful it removes nothing; where it removes anything meaningful the relative error is ~100%. The two regions do not overlap.
Which direction this cuts. The withdrawn addendum argued against our own hardness claim. Retracting it therefore restores the 2w position rather than weakening it. What is newly established is narrow but real: the naive magnitude cutoff destroys the answer on both families we tested, so the most obvious cheap classical attack on that figure is now closed, with a script anyone can run.
The scope limit, plainly. We tested only the naive global-magnitude cutoff. Proper SVD and bond-dimension truncation is far stronger and remains untested. The honest claim is “the naive shortcut fails”, not “no shortcut exists”.
The lesson, which is now the actual result. An accuracy claim must be quoted relative to the scale of the quantity being computed, and an approximation must be shown to return a non-zero answer. Reporting absolute error alone let an output of exactly zero be published as a 10-4 accuracy. Both scripts now report relative error and raise an explicit flag when the output is identically zero, so this cannot recur silently.
The original addendum is preserved unedited in the record, so the withdrawn claim stays reproducible and the correction stays independently checkable. That is the point of publishing this way.
The full technical writeup, all reproducibility scripts, and the raw IBM Quantum job data are published on Zenodo with a permanent DOI — no login or endorsement required to access it. Version 3 withdraws Addendum VI and adds Addendum VII with the audit script that reproduces the correction.
Read the Full Technical Record
Complete writeup, reproducibility scripts, and hardware job data — openly published under CC-BY-4.0.
View on Zenodo Get in Touch