# Quantum Algorithms & Quantum Advantage Domain: Quantum Computing & Information · 182 papers indexed · newest 2026-10-29 Factoring and chemistry resource estimates, quantum simulation algorithms, random-circuit sampling, verifiable advantage and the classical-simulation counterattack. Key concepts: quantum advantage, quantum supremacy, random circuit sampling, Shor, resource estimate, quantum simulation algorithm, quantum chemistry, variational quantum ## Most influential - **[Quantum supremacy using a programmable superconducting processor](https://space-kitty.com/papers/arxiv:1910.11333)**. Frank Arute, Kunal Arya, Ryan Babbush et al. · 2019 · Nature (arXiv:1910.11333 · doi:10.1038/s41586-019-1666-5 · 7,735 citations). Source: > 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): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References \[1,65\]; miscellaneous updates for clarity and style consistency; miscellaneous typogr… - **[Is there evidence for exponential quantum advantage in quantum chemistry?](https://space-kitty.com/papers/arxiv:2208.02199)**. Seunghoon Lee, Joonho Lee, Huanchen Zhai et al. · 2022 · Nat Commun 14, 1952 (2023) (arXiv:2208.02199 · doi:10.1038/s41467-023-37587-6 · 253 citations). Source: > 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 tasks have increased interest in this application, thus, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum c… - **[Characterizing Quantum Supremacy in Near-Term Devices](https://space-kitty.com/papers/arxiv:1608.00263)**. Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy et al. · 2016 · Nature Physics 14, 595-600 (2018) (arXiv:1608.00263 · doi:10.1038/s41567-018-0124-x · 1,167 citations). Source: > 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 quantum circuits, a natural task for benchmarking quantum computers. Crucially, sampling this distribution classically requires a direct numerical simulation of the circuit, with computational cost exponential in the number of qubits. This requi… - **[A polynomial-time classical algorithm for noisy random circuit sampling](https://space-kitty.com/papers/arxiv:2211.03999)**. Dorit Aharonov, Xun Gao, Zeph Landau et al. · 2022 · In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) (arXiv:2211.03999 · doi:10.1145/3564246.3585234 · 69 citations). Source: > 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 scalable experimental violation of the extended Church-Turing thesis. Our algorithm is not practical in its current form, and does not address finite-size RCS based quantum supremacy experiments. - **[Boundaries of quantum supremacy via random circuit sampling](https://space-kitty.com/papers/arxiv:2005.02464)**. Alexander Zlokapa, Sergio Boixo, Daniel Lidar · 2020 · npj Quantum Information, 9, 36 (2023) (arXiv:2005.02464 · doi:10.1038/s41534-023-00703-x · 55 citations). Source: > 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. Due to the exponential decrease of the experimental fidelity with the number of qubits and gates, we demonstrate for current fidelities a theoretical classical runtime advantage for circuits deeper than a few hundred gates, while quantum runt… - **[Quantum Supremacy and the Complexity of Random Circuit Sampling](https://space-kitty.com/papers/arxiv:1803.04402)**. Adam Bouland, Bill Fefferman, Chinmay Nirkhe et al. · 2018 (arXiv:1803.04402 · doi:10.1038/s41567-018-0318-2 · 63 citations). Source: > 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 Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical propo… - **[NISQ Computers: A Path to Quantum Supremacy](https://space-kitty.com/papers/arxiv:2310.01431)**. Muhammad AbuGhanem, Hichem Eleuch · 2023 · IEEE Access 12, 102941- 102961, (2024) (arXiv:2310.01431 · doi:10.1109/access.2024.3432330 · 76 citations). Source: > 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 milestones on the journey towards the realization of universal fault-tolerant quantum computers. This transformative turning point, known as quantum supremacy, has been achieved amid a series of breakthroughs, signifying the dawn of the qua… - **[Noise and the frontier of quantum supremacy](https://space-kitty.com/papers/arxiv:2102.01738)**. Adam Bouland, Bill Fefferman, Zeph Landau et al. · 2021 · 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 1308-1317 (arXiv:2102.01738 · doi:10.1109/focs52979.2021.00127 · 38 citations). Source: > 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 circuit sampling experiments with realistic amounts of noise. Actual quantum supremacy experiments have high levels of uncorrected noise and exponentially decaying fidelities. It is natural to ask if there is any signal of exponential complexity… - **[Complexity-Theoretic Foundations of Quantum Supremacy Experiments](https://space-kitty.com/papers/arxiv:1612.05903)**. Scott Aaronson, Lijie Chen · 2016 (arXiv:1612.05903 · doi:10.14288/1.0343134 · 218 citations). Source: > 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 possible. First, we study the hardness of sampling the output distribution of a random quantum circuit, along the lines of a recent proposal by the the Quantum AI group at Google. We show that there's a natural hardness assumption, which has no… - **[Full quantum tomography study of Google’s Sycamore gate on IBM’s quantum computers](https://space-kitty.com/papers/doi:10.1140/epjqt/s40507-024-00248-8)**. M. AbuGhanem, Hichem Eleuch · 2024 · EPJ Quantum Technology (doi:10.1140/epjqt/s40507-024-00248-8 · 31 citations). Source: > 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 conducted a supremacy regime experiment. In this experiment, a new two-qubit universal gate called theSycamoregate is constructed and employed to generate random quantum circuits (RQCs), using a programmable quantum processor with 53 qubits… > _Abstract excerpt by M. AbuGhanem et al., CC-BY, https://doi.org/10.1140/epjqt/s40507-024-00248-8; truncated._ - **[Tensor Network Quantum Virtual Machine for Simulating Quantum Circuits at Exascale](https://space-kitty.com/papers/arxiv:2104.10523)**. Thien Nguyen, Dmitry I. Lyakh, Eugene Dumitrescu et al. · 2022 · ACM Transactions on Quantum Computing (arXiv:2104.10523 · doi:10.1145/3547334 · 32 citations). Source: > 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 modernized version of the Tensor Network Quantum Virtual Machine (TNQVM) which serves as a quantum circuit simulation backend in the eXtreme-scale ACCelerator (XACC) framework. The new version is based on the general purpose, scalable tensor n… - **[Superconducting quantum computers: who is leading the future?](https://space-kitty.com/papers/doi:10.1140/epjqt/s40507-025-00405-7)**. M. AbuGhanem · 2025 · EPJ Quantum Technology (doi:10.1140/epjqt/s40507-025-00405-7 · 28 citations). Source: > 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 quantum software. We compare the hardware strategies and performance milestones of key players—including IBM Quantum, Google Quantum AI, Rigetti Computing, Intel Quantum, QuTech, and Oxford Quantum Circuits—highlighting innovations in qubit cohe… > _Abstract excerpt by M. AbuGhanem, CC-BY, https://doi.org/10.1140/epjqt/s40507-025-00405-7; truncated._ - **[No imminent quantum supremacy by boson sampling](https://space-kitty.com/papers/arxiv:1705.00686)**. Alex Neville, Chris Sparrow, Raphaël Clifford et al. · 2017 · Nature Physics 13, 1153-1157 (2017) (arXiv:1705.00686 · doi:10.1038/nphys4270 · 179 citations). Source: > 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. Photon statistics are governed by intractable matrix functions known as permanents, which suggests that sampling from the distribution obtained by injecting photons into a linear-optical network could be solved more quickly by a photonic experi… - **[Variational Quantum Algorithms](https://space-kitty.com/papers/arxiv:2012.09265)**. M. Cerezo, Andrew Arrasmith, Ryan Babbush et al. · 2020 · Nature Reviews Physics 3, 625-644 (2021) (arXiv:2012.09265 · doi:10.1038/s42254-021-00348-9 · 3,362 citations). Source: > 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 serious constraints, including limited numbers of qubits and noise processes that limit circuit depth. Variational Quantum Algorithms (VQAs), which use a classical optimizer to train a parametrized quantum circuit, have emerged as a leading str… - **[Quantum supremacy and random circuits](https://space-kitty.com/papers/arxiv:1909.06210)**. Ramis Movassagh · 2019 (arXiv:1909.06210 · 23 citations). Source: > 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 Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is… ## Newest - **[A VLSI-Like Design and Verification Flow for Quantum Circuits: A Case Study in PI Estimation](https://space-kitty.com/papers/arxiv:2610.39263)**. Yu-Ting Kao, Yeong-Jar Chang · 2026 (arXiv:2610.39263). Source: - **[Adiabatic training of VQAs for entanglement detection](https://space-kitty.com/papers/arxiv:2610.39577)**. E. Acosta, C. Cano, D. Manzano et al. · 2026 · Proceedings - 2025 IEEE International Conference on Quantum Artificial Intelligence, QAI 2025, 27-33 (arXiv:2610.39577 · doi:10.1109/qai63978.2025.00012). Source: - **[Quantum advantage by designing beneficial dissipation from lossless dynamics](https://space-kitty.com/papers/arxiv:2610.38183)**. Zeng-Zhao Li, Xiao Xue · 2026 (arXiv:2610.38183). Source: - **[Symmetry-Preserving Hierarchical Quantum Approximate Optimization Algorithm with Subproblems Beyond the Qubit Limit](https://space-kitty.com/papers/arxiv:2610.38344)**. Zhaoyang Song, Wei Zhang, Ji Cao et al. · 2026 (arXiv:2610.38344). Source: - **[Sample-Based Quantum Diagonalization for Variable Molecular Geometries](https://space-kitty.com/papers/arxiv:2610.38701)**. Matthieu Fortin-Deschenes, Ibrahim Shehzad · 2026 (arXiv:2610.38701). Source: - **[Execution bias, repeatability and mitigation cost in parameter-frozen molecular VQE energy evaluation](https://space-kitty.com/papers/arxiv:2610.38885)**. Julen Larrucea · 2026 (arXiv:2610.38885). Source: - **[Mitigating Errors in Variational Quantum Eigensolver Calculations through Extended Random Phase Approximation](https://space-kitty.com/papers/arxiv:2610.38904)**. Michael Wagner, Pavel Begy, Jiří Brabec et al. · 2026 (arXiv:2610.38904). Source: - **[Fate of Quantum Magic](https://space-kitty.com/papers/arxiv:2610.39059)**. Liuke Lyu, Erik S. Sørensen, William Witczak-Krempa · 2026 (arXiv:2610.39059). Source: - **[Effective Noise Thresholds for Reliable Quantum Approximation Optimisation Algorithm under Noisy Environment](https://space-kitty.com/papers/arxiv:2610.36597)**. Yozef Tjandra, Hendrik Santoso Sugiarto, Celine Vania Setiadi et al. · 2026 (arXiv:2610.36597). Source: - **[Magic in Grover's Algorithm and the Role of Oracle Synthesis](https://space-kitty.com/papers/arxiv:2610.37772)**. Alessio Paviglianiti, Vincenzo Savona · 2026 (arXiv:2610.37772). Source: --- Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.