REVIEW 15 cited by
Classical Simulation of Quantum Supremacy Circuits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Classical Simulation of Quantum Supremacy Circuits
read the original abstract
It is believed that random quantum circuits are difficult to simulate classically. These have been used to demonstrate quantum supremacy: the execution of a computational task on a quantum computer that is infeasible for any classical computer. The task underlying the assertion of quantum supremacy by Arute et al. (Nature, 574, 505--510 (2019)) was initially estimated to require Summit, the world's most powerful supercomputer today, approximately 10,000 years. The same task was performed on the Sycamore quantum processor in only 200 seconds. In this work, we present a tensor network-based classical simulation algorithm. Using a Summit-comparable cluster, we estimate that our simulator can perform this task in less than 20 days. On moderately-sized instances, we reduce the runtime from years to minutes, running several times faster than Sycamore itself. These estimates are based on explicit simulations of parallel subtasks, and leave no room for hidden costs. The simulator's key ingredient is identifying and optimizing the "stem" of the computation: a sequence of pairwise tensor contractions that dominates the computational cost. This orders-of-magnitude reduction in classical simulation time, together with proposals for further significant improvements, indicates that achieving quantum supremacy may require a period of continuing quantum hardware developments without an unequivocal first demonstration.
Forward citations
Cited by 15 Pith papers
-
Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
Coherent-state propagation enables quasi-polynomial classical simulation of bosonic circuits with logarithmically many Kerr gates at exponentially small trace-distance error, with polynomial runtime in the weak-nonlin...
-
Basis-Adaptive Sparse-State Simulation of Quantum Circuits
BASS adapts qubit bases via single-qubit RDM eigenbases to cluster amplitudes for truncation, yielding up to order-of-magnitude state-overlap gains versus fixed-basis sparse simulation on disordered Ising circuits.
-
Clifft: Fast Exact Simulation of Near-Clifford Quantum Circuits
Clifft introduces a factored-state simulator that shifts exponential cost to a dynamic active subspace, generalizing Stim's compile-once model to near-Clifford circuits and enabling the first exact end-to-end simulati...
-
Efficient simulation of noisy IQP circuits with amplitude-damping noise
A classical polynomial-time sampler exists for the output distribution of amplitude-damped IQP circuits with logarithmic depth and arbitrary l-local diagonal gates.
-
Hardness and Complexity Transition of Noisy Random Circuit Sampling
Under the standard ideal-RCS #P-hardness conjecture, noisy random circuit sampling remains hard for depolarizing noise γ = O(log n/(nd)), and matching simulability results make γ = Θ(log n/(nd)) the transition scale.
-
Simulating quantum circuits with a neural statebank
A compact neural statebank based on autoregressive Transformers simulates 34-qubit quantum circuits with ~0.01 infidelity using 0.3 million parameters, outperforming tested approximate simulators.
-
Clifft: Fast Exact Simulation of Near-Clifford Quantum Circuits
Clifft achieves fast exact simulation of near-Clifford quantum circuits via dynamic active subspaces, delivering orders-of-magnitude speedups and the first full end-to-end simulations of magic state cultivation over h...
-
Quantum-to-Classical Computability Transition via Negative Markov Chains
For unitaries from local or pairwise interactions, depolarizing noise above a critical strength makes open quantum spin chain dynamics exactly classically simulable by halting growth in the negative Markov chain repre...
-
Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry
Spectral bounds relate graph Laplacian eigenvalues to the congestion of binary-tree embeddings, with an efficient spectral-ordering algorithm and applications to tensor-network contraction complexity.
-
Hierarchical Search of Tree Tensor Networks for High-Dimensional Data
A hierarchical, entropy-guided search algorithm automatically rewires tree tensor networks and reshapes their indices, delivering 2.5–100× better compression than fixed Tensor Train/Hierarchical Tucker formats on phys...
-
Position: Quantum Program Generation Must Prioritize Validity Over Probabilistic Scaling
The paper argues that probabilistic scaling alone cannot fix the validity gap in quantum circuit generation, so quantum code assistants must build verification into generation rather than filter outputs after the fact.
-
Loophole-Robust Certification of Quantum Advantage
For any bounded-reward task, a classical strategy with benchmark-dependent side information can improve over the loophole-free classical score by at most the total-variation strength η of that dependence.
-
Quantum Algorithm for Distributed Reduction of Entanglements (QADR): A Trainable and Simulation-Efficient QML Framework
QADR decomposes n-qubit VQCs into local sub-circuits to reduce memory from O(2^n) to O(n * 2^{2d+1}) and mitigate barren plateaus, scaling to 2000 features on MNIST and wind turbine diagnostics while matching classica...
-
Bond-dimension scaling of a local-refinement advantage over hyperoptimized tensor-network contraction on Sycamore like topologies
Local refinement after cotengra yields a bond-dimension-dependent cost advantage on Sycamore topologies that is absent on random or QAOA graphs.
-
SparQSim: Simulating Scalable Quantum Algorithms via Sparse Quantum State Representations
SparQSim is a sparse-state quantum simulator in C++ supporting QRAM that outperforms dense Schrödinger simulators on high-sparsity benchmark circuits and produces consistent results for quantum linear system solvers.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.