Quantum Supremacy

In October 2019, a team at Google announced that their 53-qubit chip, Sycamore, had done in about 200 seconds a computation they estimated would take the world's fastest supercomputer thousands of years. They called the milestone quantum supremacy: the first time a quantum device performed some task — any task — that no classical computer could match in a reasonable amount of time.

The task itself sounds almost like a joke. The chip wasn't factoring a number or breaking a code. It was sampling random bit-strings from a deliberately scrambled quantum circuit. Useless output — but output with a fingerprint that is easy to produce on a quantum device and brutally hard to fake classically.

That gap between running the circuit and simulating the circuit is the whole story. It is not about a faster gadget; it is about a problem whose difficulty for ordinary computers grows explosively with size — exactly the kind of wall this site keeps running into.

Here is a tiny quantum computer with a handful of qubits. Each layer applies random single-qubit rotations and entangling gates, scrambling the state. Add layers and watch the output distribution over all bit-strings: it does not flatten into noise — it freezes into a jagged speckle pattern of peaks and valleys.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>{{qubits_label}}
    <select id="qubits">
      <option value="3">3</option>
      <option value="4" selected>4</option>
      <option value="5">5</option>
      <option value="6">6</option>
    </select>
  </label>
  <span class="layers">{{layers_label}} <b id="depth">0</b></span>
</div>
<div id="chart" class="chart"></div>
<div class="status" id="status">{{status_fresh}}</div>
<div class="btns">
  <button id="layer" type="button">{{btn_add_layer}}</button>
  <button id="sample" type="button">{{btn_sample}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: 1.2rem; font-size: .9rem; margin: .3rem 0 .6rem; }
.controls select { font: inherit; padding: .15rem .3rem; border-radius: 6px; border: 1px solid #adb1b8; }
.layers b { color: #1d3557; }
.chart { display: flex; align-items: flex-end; gap: 2px; height: 150px; padding: 4px;
         background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden; }
.bar { flex: 1 1 0; min-width: 1px; background: #1d3557; border-radius: 2px 2px 0 0;
       transition: height .25s ease; position: relative; }
.bar.sampled { background: #e63946; }
.status { font-size: .95rem; font-weight: 600; margin: .55rem 0; min-height: 1.4em; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice what is happening. With n qubits there are $2^{n}$ possible outputs, and the circuit assigns each a probability the demo computes exactly. The quantum chip samples from this distribution effortlessly. A classical computer must track all $2^{n}$ amplitudes — add one qubit and the work doubles. At 53 qubits that is roughly 9 quadrillion numbers; the speckle you see here is the same pattern, just small enough to draw.

How hard is random circuit sampling, really — and is "supremacy" actually proven?

• Verifying is also hard here. Unlike most problems on this site, you cannot quickly check a quantum sample by hand; Google used a statistical cross-entropy benchmark and classical simulation on a smaller scale to gain confidence.
• Classical cost grows exponentially. The honest simulation tracks $2^{n}$ complex amplitudes. Every added qubit doubles the memory and time, which is why 53 qubits sits at the edge of what the biggest machines can store.
• It is conjectured hard, not proven. Complexity theorists (Aaronson–Arkhipov and others) showed that exactly sampling such distributions would collapse parts of the complexity hierarchy — strong evidence, but it leans on unproven conjectures. There is no theorem saying classical computers must fail.
• The claim was contested. Within months, IBM argued a clever use of disk storage could simulate Sycamore in days, not millennia, and later tensor-network methods narrowed the gap further. The qualitative advantage survived; the headline "10,000 years" did not.

So the honest status is: quantum advantage demonstrated, supremacy not mathematically proven. It is a beautiful experimental probe of BQP — the class of problems quantum machines solve efficiently — pressed right up against the P vs NP frontier of what classical computers can do at all.

The sampled bit-strings are worthless on their own — so why does anyone care? Because the capability it proves is the doorway:

• A hardware yardstick: beating classical simulation is the cleanest way to show your qubits actually entangle and stay coherent long enough to matter.
• Certified randomness: a distribution this hard to fake can be turned into provably unpredictable random numbers, useful in cryptography and lotteries.
• A stepping stone to useful tasks: the same control underlies quantum simulation of molecules, optimization, and eventually Shor's factoring — the algorithm that threatens today's encryption.
• A reality check on conjectures: every contested simulation pushes both quantum engineers and classical algorithm designers, sharpening exactly where the quantum-classical boundary lies.

Understand random circuit sampling and you understand the first concrete crack in the wall between "easy for a quantum computer" and "hard for everything else."

Quantum supremacy is a strange kind of victory: a machine that solved a problem nobody wanted solved, just to prove it could outrun every classical rival at something. The speckle pattern you built above is the whole idea in miniature — a distribution a quantum chip samples in a blink and a classical computer must claw through $2^{n}$ amplitudes to reproduce.

The honest verdict, as of today, is demonstrated but not proven: the experiments are real and repeated (Google 2019, and Chinese photonic and superconducting follow-ups), yet the bedrock claim that no classical algorithm can ever catch up still rests on conjectures, not theorems. Either way, the wall is real — and for the first time, a quantum device walked through it.