Introduction

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.

Build a Random Circuit

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">A tiny quantum computer. Each <b>layer</b> applies random single-qubit
rotations and entangling gates, scrambling the state. The bars show the exact probability
of every output bit-string. Add layers and watch the speckle form — then sample like a
real chip would.</p>
<div class="controls">
  <label>Qubits:
    <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: <b id="depth">0</b></span>
</div>
<div id="chart" class="chart"></div>
<div class="status" id="status">A fresh state: all probability on |0⋯0⟩.</div>
<div class="btns">
  <button id="layer" type="button">+ Add a random layer</button>
  <button id="sample" type="button">Sample 200 times</button>
  <button id="reset" type="button" class="ghost">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Random circuit sampling, the heart of Google’s 2019 quantum-supremacy demo.
// We keep the FULL state vector of n qubits: 2^n complex amplitudes. Each layer
// applies a random single-qubit rotation to every qubit, then a controlled-Z on
// adjacent pairs (entanglement). The output distribution P(x) = |amplitude_x|^2
/* is NOT flat: it forms a jagged "speckle" (Porter-Thomas). A quantum chip samples
this in one shot; a classical computer must track all 2^n amplitudes — doubling
the work with every qubit. That exponential cost is what "supremacy" is about. */
let n = 4;
let re = [], im = [];      // state vector amplitudes
let depth = 0;
let lastSample = null;

function reset() {
  const dim = 1 << n;
  re = new Array(dim).fill(0); im = new Array(dim).fill(0);
  re[0] = 1;                 // start in |00...0>
  depth = 0; lastSample = null;
  document.getElementById('depth').textContent = depth;
  render(); setStatus(`A fresh state: all probability on |0⋯0⟩.`);
}

// Apply a single-qubit 2x2 unitary [[a,b],[c,d]] (complex) to qubit q.
function applyGate(q, a, b, c, d) {
  const dim = 1 << n, bit = 1 << q;
  for (let i = 0; i < dim; i++) {
    if (i & bit) continue;          // process each pair (i, i|bit) once
    const j = i | bit;
    const r0 = re[i], i0 = im[i], r1 = re[j], i1 = im[j];
    // new[i] = a*amp0 + b*amp1 ; new[j] = c*amp0 + d*amp1  (complex mult)
    re[i] = a.r*r0 - a.i*i0 + b.r*r1 - b.i*i1;
    im[i] = a.r*i0 + a.i*r0 + b.r*i1 + b.i*r1;
    re[j] = c.r*r0 - c.i*i0 + d.r*r1 - d.i*i1;
    im[j] = c.r*i0 + c.i*r0 + d.r*i1 + d.i*r1;
  }
}

// Random single-qubit rotation: U = Rz(g) Ry(b) Rz(a), a Haar-ish scramble.
function randomSingleQubit(q) {
  const a = Math.random()*2*Math.PI, b = Math.acos(2*Math.random()-1), g = Math.random()*2*Math.PI;
  const cb = Math.cos(b/2), sb = Math.sin(b/2);
  // e^{i*theta} helper
  const E = t => ({ r: Math.cos(t), i: Math.sin(t) });
  const m00 = E(-(a+g)/2), m01 = E((a-g)/2), m10 = E((g-a)/2), m11 = E((a+g)/2);
  applyGate(q,
    { r: m00.r*cb, i: m00.i*cb },
    { r: -m01.r*sb, i: -m01.i*sb },
    { r: m10.r*sb, i: m10.i*sb },
    { r: m11.r*cb, i: m11.i*cb });
}

// Controlled-Z between control c and target t: flip sign of amplitudes where both bits set.
function cz(c, t) {
  const dim = 1 << n, mask = (1<<c)|(1<<t);
  for (let i = 0; i < dim; i++) if ((i & mask) === mask) { re[i] = -re[i]; im[i] = -im[i]; }
}

function addLayer() {
  for (let q = 0; q < n; q++) randomSingleQubit(q);
  const offset = depth % 2;                       // alternate which pairs entangle
  for (let q = offset; q + 1 < n; q += 2) cz(q, q+1);
  depth++; lastSample = null;
  document.getElementById('depth').textContent = depth;
  render();
  setStatus(fmt(`Layer %depth% applied — %v% amplitudes scrambled.`, { depth: depth, v: 1<<n }));
}

function probs() {
  const dim = 1 << n, p = new Array(dim);
  for (let i = 0; i < dim; i++) p[i] = re[i]*re[i] + im[i]*im[i];
  return p;
}

function render() {
  const p = probs(), dim = 1 << n, maxP = Math.max(...p, 1e-9);
  const chart = document.getElementById('chart'); chart.innerHTML = '';
  for (let i = 0; i < dim; i++) {
    const bar = document.createElement('div');
    bar.className = 'bar' + (i === lastSample ? ' sampled' : '');
    bar.style.height = (4 + 96 * (p[i] / maxP)) + '%';
    bar.title = '|' + i.toString(2).padStart(n,'0') + '⟩  p=' + p[i].toFixed(4);
    chart.appendChild(bar);
  }
}

// Sample one bit-string from P(x) (what the quantum chip does in hardware).
function sampleOnce(p) {
  let r = Math.random(), acc = 0;
  for (let i = 0; i < p.length; i++) { acc += p[i]; if (r <= acc) return i; }
  return p.length - 1;
}

function sampleMany() {
  const p = probs();
  const counts = {}; let top = 0, topI = 0;
  for (let s = 0; s < 200; s++) { const x = sampleOnce(p); counts[x] = (counts[x]||0)+1;
    if (counts[x] > top) { top = counts[x]; topI = x; } }
  lastSample = topI; render();
  setStatus(fmt(`Sampled 200 shots. Most frequent: |%topI%⟩ (%top%×) — peaks dominate, exactly as theory predicts.`, { topI: topI.toString(2).padStart(n,'0'), top: top }));
}

function setStatus(t){ document.getElementById('status').textContent = t; }

document.getElementById('layer').addEventListener('click', addLayer);
document.getElementById('sample').addEventListener('click', sampleMany);
document.getElementById('reset').addEventListener('click', reset);
document.getElementById('qubits').addEventListener('change', e => { n = +e.target.value; reset(); });
reset();
Result
Console

Notice what is happening. With n qubits there are 2n2^{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 2n2^{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.

The Real Complexity

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 2n2^{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.

Where It Matters

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

Conclusion

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 2n2^{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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/quantum-supremacy/Content licensed under CC BY-NC 4.0.