Cross-Entropy Benchmarking
XEB = 2^n·⟨p_circuit(x)⟩_x − 1
Each output bitstring x has probability p(x).
For random circuits: p(x) ≈ Porter-Thomas distribution.
XEB ≈ 1: Quantum device works perfectly
XEB ≈ 0: Classical noise / random guessing
Google's Sycamore (2019): XEB=0.002 on 53-qubit, depth-20 circuit — classical simulation estimated to take 10,000 years.
Classical Simulation Cost
Full state vector: 2^n complex amplitudes.
At n=53: 2^53 ≈ 9×10¹⁵ amplitudes × 16 bytes = 144 petabytes.
Time: scales as O(2^n × d). Each gate: O(2^n) ops.
Tensor network contraction approaches (Huang 2020) cut Google's 10,000-year estimate dramatically, but still classical advantage at >50 qubits with low fidelity.
Classical time estimate:
—