Quantum Algorithms & Quantum Advantage
Factoring and chemistry resource estimates, quantum simulation algorithms, random-circuit sampling, verifiable advantage and the classical-simulation counterattack.
Most influential
- Quantum supremacy using a programmable superconducting processor
This is an updated version of supplementary information to accompany "Quantum supremacy using a programmable superconducting processor", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): a…
Article7,735 citationsarXiv:1910.11333doi:10.1038/s41586-019-1666-5 - Is there evidence for exponential quantum advantage in quantum chemistry?
The idea to use quantum mechanical devices to simulate other quantum systems is commonly ascribed to Feynman. Since the original suggestion, concrete proposals have appeared for simulating molecular and materials chemistry through quantum computation, as a potential ``killer application''. Indications of potential exponential quantum advantage in artificial …
Article253 citationsarXiv:2208.02199doi:10.1038/s41467-023-37587-6 - Characterizing Quantum Supremacy in Near-Term Devices
A critical question for the field of quantum computing in the near future is whether quantum devices without error correction can perform a well-defined computational task beyond the capabilities of state-of-the-art classical computers, achieving so-called quantum supremacy. We study the task of sampling from the output distributions of (pseudo-)random quant…
Article1,167 citationsarXiv:1608.00263doi:10.1038/s41567-018-0124-x - A polynomial-time classical algorithm for noisy random circuit sampling
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse polynomial total variation distance. This gives strong evidence that, in the presence of a constant rate of noise per gate, random circuit sampling (RCS) cannot be the basis of a scala…
Article69 citationsarXiv:2211.03999doi:10.1145/3564246.3585234 - Boundaries of quantum supremacy via random circuit sampling
Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling, that is beyond the practical reach of modern supercomputers. We examine the constraints of the observed quantum runtime advantage in an extrapolation to circuits with a larger number of qubits and gates. Du…
Article55 citationsarXiv:2005.02464doi:10.1038/s41534-023-00703-x - Quantum Supremacy and the Complexity of Random Circuit Sampling
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Samp…
Article63 citationsarXiv:1803.04402doi:10.1038/s41567-018-0318-2 - NISQ Computers: A Path to Quantum Supremacy
The quest for quantum advantage, wherein quantum computers surpass the computational capabilities of classical computers executing state-of-the-art algorithms on well-defined tasks, represents a pivotal race in the domain of quantum computing. NISQ (Noisy Intermediate-Scale Quantum) computing has witnessed remarkable advancements, culminating in significant …
Article76 citationsarXiv:2310.01431doi:10.1109/access.2024.3432330 - Noise and the frontier of quantum supremacy
Noise is the defining feature of the NISQ era, but it remains unclear if noisy quantum devices are capable of quantum speedups. Quantum supremacy experiments have been a major step forward, but gaps remain between the theory behind these experiments and their actual implementations. In this work we initiate the study of the complexity of quantum random circu…
Article38 citationsarXiv:2102.01738doi:10.1109/focs52979.2021.00127 - Complexity-Theoretic Foundations of Quantum Supremacy Experiments
In the near future, there will likely be special-purpose quantum computers with 40-50 high-quality qubits. This paper lays general theoretical foundations for how to use such devices to demonstrate "quantum supremacy": that is, a clear quantum speedup for some task, motivated by the goal of overturning the Extended Church-Turing Thesis as confidently as poss…
Article218 citationsarXiv:1612.05903doi:10.14288/1.0343134 - Full quantum tomography study of Google’s Sycamore gate on IBM’s quantum computers
Abstract The potential of achieving computational hardware with quantum advantage depends heavily on the quality of quantum gate operations. However, the presence of imperfect two-qubit gates poses a significant challenge and acts as a major obstacle in developing scalable quantum information processors. Google’s Quantum AI and collaborators claimed to have …
Abstract excerpt by M. AbuGhanem et al., CC-BY, https://doi.org/10.1140/epjqt/s40507-024-00248-8; truncated.
Article31 citationsdoi:10.1140/epjqt/s40507-024-00248-8 - Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale
The numerical simulation of quantum circuits is an indispensable tool for development, verification and validation of hybrid quantum-classical algorithms on near-term quantum co-processors. The emergence of exascale high-performance computing (HPC) platforms presents new opportunities for pushing the boundaries of quantum circuit simulation. We present a mod…
Article32 citationsarXiv:2104.10523doi:10.1145/3547334 - Superconducting quantum computers: who is leading the future?
Abstract Superconducting quantum computing has emerged as a leading platform in the pursuit of practical quantum computers, driven by rapid advances from industry, academia, and government initiatives. This review examines the state of superconducting quantum technology, with emphasis on qubit design, processor architecture, scalability, and supporting quant…
Abstract excerpt by M. AbuGhanem, CC-BY, https://doi.org/10.1140/epjqt/s40507-025-00405-7; truncated.
Article28 citationsdoi:10.1140/epjqt/s40507-025-00405-7 - No imminent quantum supremacy by boson sampling
It is predicted that quantum computers will dramatically outperform their conventional counterparts. However, large-scale universal quantum computers are yet to be built. Boson sampling is a rudimentary quantum algorithm tailored to the platform of photons in linear optics, which has sparked interest as a rapid way to demonstrate this quantum supremacy. Phot…
Article179 citationsarXiv:1705.00686doi:10.1038/nphys4270 - Variational Quantum Algorithms
Applications such as simulating complicated quantum systems or solving large-scale linear algebra problems are very challenging for classical computers due to the extremely high computational cost. Quantum computers promise a solution, although fault-tolerant quantum computers will likely not be available in the near future. Current quantum devices have seri…
Article3,362 citationsarXiv:2012.09265doi:10.1038/s42254-021-00348-9 - Quantum supremacy and random circuits
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing…
Preprint23 citationsarXiv:1909.06210
Newest work
- A VLSI-Like Design and Verification Flow for Quantum Circuits: A Case Study in PI EstimationPreprintarXiv:2610.39263
- Adiabatic training of VQAs for entanglement detectionPreprintarXiv:2610.39577doi:10.1109/qai63978.2025.00012
- Quantum advantage by designing beneficial dissipation from lossless dynamicsPreprintarXiv:2610.38183
- Symmetry-Preserving Hierarchical Quantum Approximate Optimization Algorithm with Subproblems Beyond the Qubit LimitPreprintarXiv:2610.38344
- Sample-Based Quantum Diagonalization for Variable Molecular GeometriesPreprintarXiv:2610.38701
- Execution bias, repeatability and mitigation cost in parameter-frozen molecular VQE energy evaluationPreprintarXiv:2610.38885
- Mitigating Errors in Variational Quantum Eigensolver Calculations through Extended Random Phase ApproximationPreprintarXiv:2610.38904
- Fate of Quantum MagicPreprintarXiv:2610.39059
- Effective Noise Thresholds for Reliable Quantum Approximation Optimisation Algorithm under Noisy EnvironmentPreprintarXiv:2610.36597
- Magic in Grover's Algorithm and the Role of Oracle SynthesisPreprintarXiv:2610.37772