PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Supremacy Is Both Closer and Farther than It Appears

Igor L. Markov, Aneeqa Fatima, Sergei V. Isakov, Sergio Boixo

arXiv:1807.10749v3quant-phcs.DCcs.ET

TL;DR

The paper addresses when classical simulation can compete with quantum computers on random-circuit sampling, particularly when quantum hardware has imperfect fidelity. It develops Rollright and fidelity–resource tradeoffs, finding that non-specialized cloud simulations can be competitive while refined iSWAP benchmarks substantially raise simulation difficulty.

  • Problem

    The paper asks how to compare classical simulation with near-term quantum computers on random-circuit sampling when quantum hardware incurs significant errors.

  • Method

    The authors develop Rollright, a massively parallel simulator without inter-process communication or proprietary hardware, plus approximate-simulation methods that trade fidelity for computational resources.

  • Results

    Rollright enables competitive cloud-based simulations and shows that iSWAP-based second-generation benchmarks reduce the depth attainable by leading simulation methods approximately two-fold.

  • Takeaways & Limitations

    Simulation competitiveness can be assessed against quantum computers by matching circuit fidelity and comparing total monetary cost across hardware platforms.

  • Takeaways & Limitations

    Cloud simulations are exposed to hardware-performance variations and preemptible virtual machines do not guarantee real-time execution.

Abstract

from arXiv · show

As quantum computers improve in the number of qubits and fidelity, the question of when they surpass state-of-the-art classical computation for a well-defined computational task is attracting much attention. The leading candidate task for this milestone entails sampling from the output distribution defined by a random quantum circuit. We develop a massively-parallel simulation tool Rollright that does not require inter-process communication (IPC) or proprietary hardware. We also develop two ways to trade circuit fidelity for computational speedups, so as to match the fidelity of a given quantum computer --- a task previously thought impossible. We report massive speedups for the sampling task over prior software from Microsoft, IBM, Alibaba and Google, as well as supercomputer and GPU-based simulations. By using publicly available Google Cloud Computing, we price such simulations and enable comparisons by total cost across hardware platforms. We simulate approximate sampling from the output of a circuit with 7x8 qubits and depth 1+40+1 by producing one million bitstring probabilities with fidelity 0.5%, at an estimated cost of $35184. The simulation costs scale linearly with fidelity, and using this scaling we estimate that extending circuit depth to 1+48+1 increases costs to one million dollars. Scaling the simulation to 10M bitstring probabilities needed for sampling 1M bitstrings helps comparing simulation to quantum computers. We describe refinements in benchmarks that slow down leading simulators, halving the circuit depth that can be simulated within the same time.

1 Introduction

The paper introduces Rollright, a massively parallel quantum-circuit simulator that avoids inter-process communication and proprietary hardware while targeting approximate sampling at quantum-computer fidelities. It reports large speedups and cloud-cost estimates, while refining benchmarks to expose harder-to-simulate circuits.

  • 1 Introduction: Replacing CZ gates with more sophisticated gates such as iSWAP makes refined quantum-supremacy benchmarks substantially harder to simulate.The paper estimates that iSWAP benchmarks reduce the depth attainable by leading simulation methods approximately two-fold.
  • 1 Introduction: Rollright avoids inter-process communication and proprietary hardware, enabling massively parallel simulation on commercial cloud preemptible virtual machines.The approach is designed for output-probability calculations needed by sampling and cross-entropy benchmarking.
  • 1 Introduction: 16× and 10× speedups over Microsoft and IBM simulators are achieved on a MacBook Pro for 5 × 5-qubit circuits, with lower memory use.Rollright also simulates 6 × 5-qubit circuits of any depth on the same laptop.
  • 1 Introduction: $0.24 and 20 minutes suffice for one million probabilities from a 9 × 5-qubit, depth 1 + 25 circuit, using 17.4GiB rather than Ref. [11]'s 0.5PB.The reported memory reduction is 28600 times relative to Ref. [11].
  • 1 Introduction: $8734 produces one million probabilities at 0.5% fidelity for a 7 × 7-qubit, depth 1 + 40 + 1 circuit.The calculation uses 625 Google Cloud n1-highcpu-32 servers.
  • 1 Introduction: Simulation cost scales linearly with fidelity, while extending depth from 1 + 40 + 1 to 1 + 48 + 1 raises the estimate to one million US dollars.This fidelity–cost tradeoff enables simulations matched to noisy quantum-computer performance.

2 Our quantum-circuit simulation framework

Rollright combines Schrödinger-style simulation within qubit blocks with Feynman-style path summation across partitions. Its implementation reduces memory and communication demands through gate decomposition, path management, sparse-block skipping, and hardware-conscious optimizations.

  • 2 Our quantum-circuit simulation framework: Rollright partitions the qubit layout into blocks and decomposes cross-partition gates into separable terms, allowing blocks to be simulated independently before summation.This Schrödinger-Feynman hybrid trades memory for additional computation.
  • 2 Our quantum-circuit simulation framework: The framework supports arbitrary gate libraries, but some optimizations target Clifford+T-like libraries and performance may be 2−3× slower on different gate libraries.Depth-limited algorithms may also give supercomputers an advantage for very deep circuits.
  • 2 Our quantum-circuit simulation framework: Gate clustering, compact bitmask encoding, cache-sized amplitude slices, and reduced floating-point additions improve CPU efficiency for supported gate libraries.Compared with Ref. [11], floating-point additions are reduced by a factor of three, while AVX2 vectorization is used.
  • 2 Our quantum-circuit simulation framework: The simulator avoids inter-process communication by assigning path prefixes to processes and checkpointing before enumerating remaining paths.The prefix strategy reduces duplicated path-prefix work compared with assigning complete paths independently.
  • 2 Our quantum-circuit simulation framework: Final-state amplitudes can be computed for arbitrary requested subsets, making the simulator suitable for sampling and cross-entropy benchmarking.Millions of amplitudes can be calculated almost as quickly as single amplitudes, although very large subsets can dominate easy simulations.

3 Trading off simulation fidelity for computational resources

The paper introduces approximate quantum-circuit simulation methods that trade fidelity for computational speed, enabling simulations matched to near-term quantum-computer accuracy. Runtime scales linearly with fidelity under the paper’s assumptions, while the approach supports arbitrary gates and cross-block multiqubit gates.

  • Approximate simulation targets the fidelity attained by noisy quantum computers, addressing sampling from random-circuit output distributions without requiring exact results.The paper identifies errors in initialization, gates, and measurements as motivation for reducing simulation accuracy.
  • The approximation drops terms from a 2^x-path simulation, assuming nearly equal path norms and near-orthogonality for random quantum-supremacy circuits.Under these assumptions, the simulation retains f^2x terms out of 2^x for requested fidelity f.
  • Attaining fidelity f requires only an f fraction of the work, making fidelity 0.1 simulations 10× faster than exact simulation.The linear scaling was also confirmed empirically in multiprocess simulation; selecting paths with smaller norms can improve the tradeoff further in general.
  • Approximate methods based on circuit error rate scale as 1/ϵ^2, whereas this approach’s runtime scales linearly with fidelity and is suited to small-fidelity simulations.The comparison is specifically made against methods in Refs. [28] [29] for quantum-supremacy circuits.
  • The method handles arbitrary gates, including cross-block multiqubit gates through operator Schmidt decompositions, without making runtime scaling depend on Schmidt rank.This extends the fidelity–runtime tradeoff beyond the specific controlled-Z decomposition discussed earlier.

4 How many amplitudes must be calculated?

The paper develops rejection-sampling procedures that estimate quantum-circuit output probabilities and reduce the number of probabilities needed per sampled bitstring. Frugal handling of high-probability outcomes achieves small statistical distance with a fixed, modest number of probability evaluations.

  • The method targets approximately 10^7 amplitudes or probabilities when sampling 1M bitstrings for cross-entropy benchmarking.The paper contrasts this with boson sampling, which requires approximately 100 probabilities per bitstring.
  • Basic rejection sampling uses a bound M ≥ max_x p(x)N and averages M probability evaluations per accepted bitstring.For ε = 10^-3 and n = 49, the paper obtains M = 41 probabilities per bitstring.
  • The statistical distance decreases exponentially with the number M′ of probabilities calculated per bitstring sample.For M′ = 10, an earlier bound gives ε = 5 · 10^-4 independent of the number of qubits.
  • The algorithms sample ℓ bitstrings from a subset of size ℓM or ℓM′ with known probabilities, differing in set-size determination and treatment of high probabilities.These distinctions define the basic and frugal rejection-sampling procedures shown in Figure 1.
  • Frugal rejection sampling does not require Porter–Thomas statistics, but without them the sampling error must be calculated numerically for each probability batch.For Figure 3, the reported numerical errors are (4.4 ± 0.7) · 10^-4 for exact simulation and (5.3 ± 0.7) · 10^-4 for approximate simulation.

5 Simulation results

Rollright achieves large speed and memory advantages across conventional simulators while scaling approximate simulations to hard circuits and millions of amplitudes on cloud hardware.

  • 31× and 16× speedups over Microsoft QDK and IBM QISKit-Terra/QASM, respectively, extend to 877× over QISKit for a 32-qubit circuit, while memory use is 886× and 590× lower.These comparisons cover single-server, GPU-assisted, and non-GPU configurations.
  • Shared cloud hardware introduces runtime variation from CPU diversity and transient loads, although processes on the same node tend to have similar runtimes.Individual branches on a given CPU remain within 10–20% of that CPU’s mean runtime.
  • Approximate simulations use up to 625 Google Cloud servers for 7 × 7 and 7 × 8 qubit circuits at depths 1 + 39 + 1 and 1 + 40 + 1.Table 3 reports simulations saving one million randomly requested amplitudes on v2 benchmark circuits.
  • $52 at fidelity 2^-22 for depth 1 + 48 + 1 implies an estimated one-million-dollar cost at 0.5% fidelity under linear fidelity scaling.The estimate uses 512 n1-highcpu-32 virtual servers and extrapolates computational cost linearly with fidelity.
  • Saving 10^6 amplitudes causes a 17% slowdown, whereas saving 10^7 causes a 2.76× slowdown, yielding a 3.6 × 10^6 speedup over one-amplitude-at-a-time generation.Rollright produces amplitudes in batches, supporting the scale needed to compare simulation with many quantum-computer samples.

6 Refined quantum-supremacy benchmarks

The refined benchmarks target weaknesses in prior quantum-supremacy circuits so that small, reproducible circuit changes make simulation harder without changing the gate family.

  • Depth must reach at least 1 + 40 + 1 for 7 × 7 circuits because variable-elimination simulation difficulty grows exponentially with depth.The benchmark size and depth are chosen to challenge simulation methods optimized for low-depth circuits.
  • Replacing post-CZ T gates, adding a final Hadamard cycle, and alternating horizontal and vertical two-qubit gates complicate many simulation approaches.These changes retain the same gate family while preserving numerous non-Clifford gates that hamper stabilizer-based simulation [28] [29].
  • The revised benchmark files are publicly available, enabling reproducible runtime comparisons across simulation methods.The authors recommend reporting specific circuit files because benchmark details materially affect comparisons.

7 Harder benchmarks through two-qubit gates

More complex two-qubit gates increase simulation branching and can sharply reduce the circuit depth manageable within a fixed time, especially when gates cross partitions.

  • Replacing cross-block CZ gates with more complicated gates can impose greater costs than changing gates within tensor blocks.Within-block gate-library upgrades generally produce only a constant-times runtime difference, while cross-block changes affect branching.
  • Replacing CZ gates with iSWAP increases the multiprocess branching factor from two to four, halving the circuit depth that fits within a fixed runtime.The iSWAP decomposition is minimal, so this penalty is not removed by a shorter equivalent decomposition.
  • Cross-partition arbitrary two-qubit gates contribute to simulation branching, whereas gates applied within tensor partitions remain as efficient as existing benchmark gates.This makes gate placement relative to the simulator’s partitioning a key determinant of difficulty.

8 Conclusions

The conclusions argue that improved classical simulation narrows quantum supremacy claims, while circuit depth, fidelity, gate choice, and cost remain decisive moving targets.

  • 8 Conclusions: Full-circuit fidelity can be traded for computational resources, allowing simulations to match the requested fidelity of a quantum computer.The paper also presents interactive validation using lower-fidelity simulations.
  • 8 Conclusions: Limited-depth circuits now admit surprisingly efficient simulation on cloud computers, while deep uncorrected circuits remain difficult for both classical simulation and quantum chips.Simulation faces exponentially growing resource requirements, whereas quantum chips face exponentially accumulating gate errors.
  • 8 Conclusions: Schrödinger-Feynman simulation favors conventional CPUs over GPUs and supercomputers by avoiding fast interconnects, and could scale through distributed volunteer computing.The approach can be cast as an Internet-scale SETI@Home-style effort.
  • 8 Conclusions: Approximate simulation is effective in practice because simulation complexity scales linearly with circuit fidelity, raising the bar for supremacy experiments with noisy quantum circuits.Quantum gate errors lower circuit fidelity, creating opportunities for approximate classical simulation.
  • 8 Conclusions: Replacing CZ gates with iSWAP gates appears to reduce the circuit depth attainable by leading simulation methods by approximately two-fold.The revised benchmarks remain implementable on quantum computers, making two-qubit gate fidelity a key experimental parameter.
  • 8 Conclusions: Cloud pricing per amplitude enables cost comparisons across classical hardware and quantum computers, although supercomputers may simulate larger circuits within a fixed time at greater cost.Meaningful comparisons must include resources used and the number of runs needed for trustworthy results.

9 Infrastructure and Performance estimation

Rollright combines a partitioned Schrödinger-Feynman implementation with fidelity-controlled approximate simulation, explicit runtime modeling, and extensive validation of its outputs.

  • 9 Infrastructure and Performance estimation: Rollright partitions the qubit array into two blocks and splits circuit depth into reusable and branched portions to estimate simulation runtime.The model accounts for block sizes, depth components, path branching, and the number of requested amplitudes.
  • 9 Infrastructure and Performance estimation: Ttot(f, q1, q2, dp, db, xp, xb, na) models total runtime using fidelity, block sizes, path counts, depth, and requested amplitudes, with implementation-specific constants C1, C2, and C3.The expression separates core simulation, branching, and amplitude-collection costs.
  • 9 Infrastructure and Performance estimation: Runtime is affected by process sharing and memory contention, while RAM usage scales with the number of processes and is independent of circuit depth.The slowdown factor ω(p) is reported as roughly 1.5–2 for common process counts of 16–32.
  • 9 Infrastructure and Performance estimation: The implementation uses C++11, AVX-2 instructions, shared Google Cloud hardware, and independent simulator comparisons to validate performance and correctness.Validation includes Schrödinger, Schrödinger-Feynman, variable-elimination, QuIDDPro, and IBM QISKit-Terra simulators.
  • 9 Infrastructure and Performance estimation: Approximate-simulation validation found empirical fidelity matching the requested path fraction and, in a separate experiment, matching requested values within 2%.The experiments used fractions f = 1/16, 1/32, 1/64, and 1/128, plus requested fidelities 10^-4, 10^-2, and 1/64.
  • 9 Infrastructure and Performance estimation: Output-probability distributions from exact and approximate simulations match the Porter-Thomas distribution for the tested circuits.The approximate case uses fidelity 1/196 for a 7 × 8-qubit circuit with depth 1 + 40 + 1.

A Comparisons to Microsoft QDK

Against Microsoft QDK on Google quantum-supremacy benchmarks, Rollright achieves substantial runtime and memory advantages, though the comparison covers only a narrow benchmark scope.

  • A Comparisons to Microsoft QDK: The performance ratios remain similar across the reported configurations, with Rollright using substantially less memory than QDK.The comparison protocol converted the circuit descriptions into Q# and used laptop and mid-range-server settings.
  • A Comparisons to Microsoft QDK: Rollright is 19× faster than Microsoft QDK with a 3× memory advantage on the tested 30-qubit benchmark.The comparison used an 18-core Linux server after QDK exceeded the 16 GiB available on the laptop.
  • A Comparisons to Microsoft QDK: The comparison is limited to quantum-supremacy benchmarks and does not represent Microsoft’s priorities or QDK’s value outside circuit simulation.Microsoft may continue improving its software, and broader applications are outside this paper’s scope.
  • A Comparisons to Microsoft QDK: Table 5 compares Rollright and Microsoft QDK on 24-, 25-, and 30-qubit Google v2 benchmarks using runtime and memory increase relative to a 16-qubit baseline.For 30 qubits, the Schrödinger-Feynman configuration with 18 parallel processes gives Rollright its larger improvement.

B Comparisons to IBM QISKit and IBM Q

Rollright substantially outperforms IBM QISKit simulators on the tested quantum-supremacy circuits and remains faster than IBM Q simulations despite an unfavorable hardware comparison.

  • B Comparisons to IBM QISKit and IBM Q: On a 32-qubit depth 1+26+1 circuit, Rollright is 430.6× faster and uses 1331× less memory than QASM.On the corresponding 30-qubit benchmark, Rollright is 16× faster and uses 590× less memory.
  • B Comparisons to IBM QISKit and IBM Q: Rollright outperforms IBM QISKit QASM and state-vector simulation, with the QASM simulator faster than QISKit’s state-vector simulator on these circuits.The 32-qubit result benefits from Schrödinger-Feynman exploitation of the oblong 4x8 qubit array.
  • B Comparisons to IBM QISKit and IBM Q: IBM QISKit GPU support improves runtime by almost 30% on 30-qubit circuits without changing measured memory usage.The comparison does not measure memory inside the GPU.
  • B Comparisons to IBM QISKit and IBM Q: Whether GPU acceleration lowers total simulation cost remains open because modern GPU resources can be costly.The paper suggests implementing its algorithms on GPUs could provide additional speedup.
  • B Comparisons to IBM QISKit and IBM Q: Even when comparing Rollright on a MacBook Pro with QISKit on IBM Q, Rollright is twice as fast and uses 30–70% less memory.The comparison is explicitly described as unfavorable to Rollright.

C Validation of simulation results

The paper validates approximate quantum-circuit simulation through a verifier–claimant protocol that estimates fidelity from shared amplitudes. Rollright also shows strong performance against QISKit simulators across benchmark circuits.

  • Validation protocol: The verifier estimates fidelity by comparing k shared amplitudes from claimant and approximate verifier states, rejecting trials when |f_e − f_1| exceeds δ.The protocol uses pseudo-random amplitude indices and can be repeated to increase certainty.
  • Validation protocol: A generic approximate state with fidelity f_1 ≪1 has expected fidelity f_1f with the correct state, allowing a handful of unpredictable approximate states to validate |ψ⟩.The verifier may select circuits from a family and repeat the test.

E “Easy” 42-qubit depth 1 + 25 + 1 simulation

Rollright scales an “easy” 42-qubit circuit simulation through a single-cut tensor-product decomposition and massive parallelism. The reported run uses hundreds of processes and substantial wall-clock time to produce one million amplitudes.

  • E “Easy” 42-qubit depth 1 + 25 + 1 simulation: The revised 7x6 benchmark is described as harder to simulate than older quantum-supremacy benchmarks.This scope statement accompanies the Schrödinger-Feynman simulation setup.
  • E “Easy” 42-qubit depth 1 + 25 + 1 simulation: The 42-qubit simulation uses a horizontal 24q + 18q cut with 18 xCZ gates and projection-based branches to request 1,000,000 amplitudes.The circuit is a 7x6 Google benchmark with 27 cycles.
  • E “Easy” 42-qubit depth 1 + 25 + 1 simulation: The simulation uses 64 processes with four threads each, requiring 23 batches on one node and 8,970 MiB peak memory.The state representation size is 130 MiB.
  • E “Easy” 42-qubit depth 1 + 25 + 1 simulation: The run takes 5.534 hours on average wall-clock time, with 6.016 hours maximum and 6.016×10^-6 billable hours per amplitude.Average user time is 10.26 hours.

F 64-qubit depth 1 + 22 simulation

The paper extends Rollright to 64-qubit and revised 49-qubit Google circuits using tensor-product cuts, projection-based branching, and distributed execution. These simulations require large cloud-scale resources and substantial billable runtime.

  • F 64-qubit depth 1 + 22 simulation: A 7x6 simulation on 64 Google Cloud virtual machines achieves a 1.7× runtime improvement using half as many nodes in a commercial cloud environment.The comparison concerns related GPU and distributed-cluster work using altered CZ-gate layouts.
  • F 64-qubit depth 1 + 22 simulation: The 64-qubit simulation uses a horizontal 32q + 32q cut with 16 xCZ gates and requests 16,384 amplitudes.It uses a single-cut sum-of-tensor-products representation with projection-based branches.
  • F 64-qubit depth 1 + 22 simulation: The 64-qubit run uses 256 processes across 64 nodes, with 64 GiB state representation and 12,288 GiB peak memory.The configuration runs 32 threads per process.
  • F 64-qubit depth 1 + 22 simulation: The 64-qubit simulation takes 14.726 hours average wall-clock time and 1.190×10^3 billable hours.The maximum wall-clock time is 18.593 hours.
Loading 1807.10749v3…