How many qubits are needed for quantum computational supremacy?

Alexander M. Dalzell; Aram W. Harrow; Dax Enshan Koh; Rolando L. La Placa

doi:10.22331/q-2020-05-11-264

How many qubits are needed for quantum computational supremacy?

Alexander M. Dalzell^1,2, Aram W. Harrow³, Dax Enshan Koh^4,5, and Rolando L. La Placa³

¹Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
²Department of Physics, Massachusetts Institute of Technology, Cambrdige, Massachusetts 02139, USA
³Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
⁴Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
⁵Zapata Computing, Inc., 100 Federal Street, 20th Floor, Boston, Massachusetts 02110, USA

Published:	2020-05-11, volume 4, page 264
Eprint:	arXiv:1805.05224v3
Doi:	https://doi.org/10.22331/q-2020-05-11-264
Citation:	Quantum 4, 264 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, typically require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy ($\mathsf{PH}$) does not collapse, a stronger version of the statement that $\mathsf{P} \neq \mathsf{NP}$, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires time scaling worse than any polynomial in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing fine-grained versions of the non-collapse conjecture. Our first two conjectures poly3-NSETH($a$) and per-int-NSETH($b$) take specific classical counting problems related to the number of zeros of a degree-3 polynomial in $n$ variables over $\mathbb{F}_2$ or the permanent of an $n \times n$ integer-valued matrix, and assert that any non-deterministic algorithm that solves them requires $2^{cn}$ time steps, where $c \in \{a,b\}$. A third conjecture poly3-ave-SBSETH($a'$) asserts a similar statement about average-case algorithms living in the exponential-time version of the complexity class $\mathsf{SBP}$. We analyze evidence for these conjectures and argue that they are plausible when $a=1/2$, $b = 0.999$ and $a' = 1/2$.

Imposing poly3-NSETH(1/2) and per-int-NSETH(0.999), and assuming that the runtime of a hypothetical quantum circuit simulation algorithm would scale linearly with the number of gates/constraints/optical elements, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 208 qubits and 500 gates, Quantum Approximate Optimization Algorithm (QAOA) circuits with 420 qubits and 500 constraints and boson sampling circuits (i.e. linear optical networks) with 98 photons and 500 optical elements are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology. Imposing poly3-ave-SBSETH(1/2), we additionally rule out simulations with constant additive error for IQP and QAOA circuits of the same size. Without the assumption of linearly increasing simulation time, we can make analogous statements for circuits with slightly fewer qubits but requiring $10^4$ to $10^7$ gates.

► BibTeX data

@article{Dalzell2020howmanyqubitsare,
  doi = {10.22331/q-2020-05-11-264},
  url = {https://doi.org/10.22331/q-2020-05-11-264},
  title = {How many qubits are needed for quantum computational supremacy?},
  author = {Dalzell, Alexander M. and Harrow, Aram W. and Koh, Dax Enshan and La Placa, Rolando L.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {264},
  month = may,
  year = {2020}
}

► References

[1] S. Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 461 (2063): 3473–3482, 2005. 10.1098/rspa.2005.1546.
https://doi.org/10.1098/rspa.2005.1546

[2] S. Aaronson. A linear-optical proof that the permanent is $\#P$-hard. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2136): 3393–3405, 2011. 10.1098/rspa.2011.0232.
https://doi.org/10.1098/rspa.2011.0232

[3] S. Aaronson and A. Arkhipov. The computational complexity of linear optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pages 333–342, 2011. 10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682

[4] S. Aaronson and L. Chen. Complexity-theoretic foundations of quantum supremacy experiments. In 32nd Computational Complexity Conference (CCC 2017), volume 79, pages 22:1–22:67, 2017. 10.4230/LIPIcs.CCC.2017.22.
https://doi.org/10.4230/LIPIcs.CCC.2017.22

[5] S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban. The computational complexity of ball permutations. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 317–327, 2017. 10.1145/3055399.3055453.
https://doi.org/10.1145/3055399.3055453

[6] S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009.

[7] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574 (7779): 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[8] M. Ball, A. Rosen, M. Sabin, and P. N. Vasudevan. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, page 483–496, 2017. 10.1145/3055399.3055466.
https://doi.org/10.1145/3055399.3055466

[9] C. Beck and R. Impagliazzo. Strong ETH holds for regular resolution. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, page 487–494, 2013. 10.1145/2488608.2488669.
https://doi.org/10.1145/2488608.2488669

[10] R. Beigel and J. Tarui. On ACC. Computational Complexity, 4 (4): 350–366, 1994. 10.1007/BF01263423.
https://doi.org/10.1007/BF01263423

[11] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert. Architectures for quantum simulation showing a quantum speedup. Phys. Rev. X, 8: 021010, Apr 2018. 10.1103/PhysRevX.8.021010.
https://doi.org/10.1103/PhysRevX.8.021010

[12] A. Björklund, P. Kaski, and R. Williams. Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. Algorithmica, 81 (10): 4010–4028, 2019. 10.1007/s00453-018-0513-7.
https://doi.org/10.1007/s00453-018-0513-7

[13] A. Bouland, L. Mančinska, and X. Zhang. Complexity classification of two-qubit commuting Hamiltonians. In 31st Conference on Computational Complexity (CCC 2016), volume 50, pages 28:1–28:33, 2016. 10.4230/LIPIcs.CCC.2016.28.
https://doi.org/10.4230/LIPIcs.CCC.2016.28

[14] A. Bouland, J. F. Fitzsimons, and D. E. Koh. Complexity classification of conjugated Clifford circuits. In 33rd Computational Complexity Conference (CCC 2018), volume 102, pages 21:1–21:25, 2018. 10.4230/LIPIcs.CCC.2018.21.
https://doi.org/10.4230/LIPIcs.CCC.2018.21

[15] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani. On the complexity and verification of quantum random circuit sampling. Nature Physics, 15 (2): 159, 2019. 10.1038/s41567-018-0318-2.
https://doi.org/10.1038/s41567-018-0318-2

[16] M. J. Bremner, R. Jozsa, and D. J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2126): 459–472, 2011. 10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301

[17] M. J. Bremner, A. Montanaro, and D. J. Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett., 117: 080501, Aug 2016. 10.1103/PhysRevLett.117.080501.
https://doi.org/10.1103/PhysRevLett.117.080501

[18] E. Böhler, C. Glaßer, and D. Meister. Error-bounded probabilistic computations between $\mathsf{MA}$ and $\mathsf{AM}$. Journal of Computer and System Sciences, 72 (6): 1043–1076, 2006. 10.1016/j.jcss.2006.05.001.
https://doi.org/10.1016/j.jcss.2006.05.001

[19] C. Calabro, R. Impagliazzo, and R. Paturi. The complexity of satisfiability of small depth circuits. In Parameterized and Exact Computation, pages 75–85, 2009. 10.1007/978-3-642-11269-0_6.
https://doi.org/10.1007/978-3-642-11269-0_6

[20] M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, and S. Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, page 261–270, 2016. 10.1145/2840728.2840746.
https://doi.org/10.1145/2840728.2840746

[21] P. Clifford and R. Clifford. The classical complexity of boson sampling. In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 146–155, 2018. 10.1137/1.9781611975031.10.
https://doi.org/10.1137/1.9781611975031.10

[22] A. M. Dalzell. Lower bounds on the classical simulation of quantum circuits for quantum supremacy. Bachelor's thesis, Massachusetts Institute of Technology, 2017. URL http://hdl.handle.net/1721.1/111859.
http://hdl.handle.net/1721.1/111859

[23] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlén. Exponential time complexity of the permanent and the Tutte polynomial. ACM Trans. Algorithms, 10 (4), Aug 2014. 10.1145/2635812.
https://doi.org/10.1145/2635812

[24] E. Farhi and A. W. Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv preprint arXiv:1602.07674, 2016.
arXiv:1602.07674

[25] E. Farhi, J. Goldstone, and S. Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.
arXiv:1411.4028

[26] S. Fenner, F. Green, S. Homer, and R. Pruim. Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 455 (1991): 3953–3966, 1999. 10.1098/rspa.1999.0485.
https://doi.org/10.1098/rspa.1999.0485

[27] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Power of quantum computation with few clean qubits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55, pages 13:1–13:14, 2016. 10.4230/LIPIcs.ICALP.2016.13.
https://doi.org/10.4230/LIPIcs.ICALP.2016.13

[28] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani. Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett., 120: 200502, May 2018. 10.1103/PhysRevLett.120.200502.
https://doi.org/10.1103/PhysRevLett.120.200502

[29] O. Goldreich and G. N. Rothblum. Worst-case to average-case reductions for subclasses of $P$. In Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation, pages 249–295. 2020. 10.1007/978-3-030-43662-9_15.
https://doi.org/10.1007/978-3-030-43662-9_15

[30] Y. Han, L. A. Hemaspaandra, and T. Thierauf. Threshold computation and cryptographic security. SIAM Journal on Computing, 26 (1): 59–78, 1997. 10.1137/S0097539792240467.
https://doi.org/10.1137/S0097539792240467

[31] D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert. Anticoncentration theorems for schemes showing a quantum speedup. Quantum, 2: 65, May 2018. 10.22331/q-2018-05-22-65.
https://doi.org/10.22331/q-2018-05-22-65

[32] A. W. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, 2017. 10.1038/nature23458.
https://doi.org/10.1038/nature23458

[33] R. Hayakawa, T. Morimae, and S. Tamaki. Fine-grained quantum supremacy based on orthogonal vectors, 3-sum and all-pairs shortest paths. arXiv preprint arXiv:1902.08382, 2019.
arXiv:1902.08382

[34] C. Huang, M. Newman, and M. Szegedy. Explicit lower bounds on strong quantum simulation. arXiv preprint arXiv:1804.10368, 2018.
arXiv:1804.10368

[35] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63 (4): 512–530, 2001. 10.1006/jcss.2001.1774.
https://doi.org/10.1006/jcss.2001.1774

[36] H. Jahanjou, E. Miles, and E. Viola. Local reductions. In Automata, Languages, and Programming, pages 749–760, 2015. 10.1007/978-3-662-47672-7_61.
https://doi.org/10.1007/978-3-662-47672-7_61

[37] M. Jerrum and M. Snir. Some exact complexity results for straight-line computations over semirings. J. ACM, 29 (3): 874–897, Jul 1982. 10.1145/322326.322341.
https://doi.org/10.1145/322326.322341

[38] R. Jozsa and M. Van Den Nest. Classical simulation complexity of extended Clifford circuits. Quantum Information & Computation, 14 (7&8): 633–648, 2014. 10.26421/QIC14.7-8.
https://doi.org/10.26421/QIC14.7-8

[39] D. E. Koh. Further extensions of Clifford circuits and their classical simulation complexities. Quantum Information & Computation, 17 (3&4): 0262–0282, 2017. 10.26421/QIC17.3-4.
https://doi.org/10.26421/QIC17.3-4

[40] G. Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11 (1): 183–219, 2015. 10.4086/toc.2015.v011a006.
https://doi.org/10.4086/toc.2015.v011a006

[41] R. J. Lipton. New directions in testing. In Distributed Computing and Cryptography, volume 2, pages 191–202, 1989. 10.1090/dimacs/002/13.
https://doi.org/10.1090/dimacs/002/13

[42] D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu. Beating brute force for systems of polynomial equations over finite fields. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2190–2202. 2017. 10.1137/1.9781611974782.143.
https://doi.org/10.1137/1.9781611974782.143

[43] A. Montanaro. Quantum circuits and low-degree polynomials over $\mathbb{F}_2$. Journal of Physics A: Mathematical and Theoretical, 50 (8): 084002, Jan 2017. 10.1088/1751-8121/aa565f.
https://doi.org/10.1088/1751-8121/aa565f

[44] T. Morimae and S. Tamaki. Additive-error fine-grained quantum supremacy. arXiv preprint arXiv:1912.06336, 2019a.
arXiv:1912.06336

[45] T. Morimae and S. Tamaki. Fine-grained quantum computational supremacy. Quantum Information & Computation, 19 (13&14): 1089–1115, 2019b. 10.26421/QIC19.13-14.
https://doi.org/10.26421/QIC19.13-14

[46] T. Morimae, K. Fujii, and J. F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Phys. Rev. Lett., 112: 130502, Apr 2014. 10.1103/PhysRevLett.112.130502.
https://doi.org/10.1103/PhysRevLett.112.130502

[47] T. Morimae, Y. Takeuchi, and H. Nishimura. Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum, 2: 106, Nov 2018. 10.22331/q-2018-11-15-106.
https://doi.org/10.22331/q-2018-11-15-106

[48] R. Movassagh. Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of random circuit sampling. arXiv preprint arXiv:1810.04681, 2018.
arXiv:1810.04681

[49] R. Movassagh. Cayley path and quantum computational supremacy: A proof of average-case $\# P$-hardness of random circuit sampling with quantified robustness. arXiv preprint arXiv:1909.06210, 2019.
arXiv:1909.06210

[50] A. Neville, C. Sparrow, R. Clifford, E. Johnston, P. M. Birchall, A. Montanaro, and A. Laing. Classical boson sampling algorithms with superior performance to near-term experiments. Nature Physics, 13 (12): 1153, 2017. 10.1038/nphys4270.
https://doi.org/10.1038/nphys4270

[51] J. Preskill. Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813, 2012.
arXiv:1203.5813

[52] P. Pudlák and R. Impagliazzo. A lower bound for DLL algorithms for $k$-SAT (preliminary version). In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, page 128–136, 2000. URL https://dl.acm.org/doi/abs/10.5555/338219.338244.
https://dl.acm.org/doi/abs/10.5555/338219.338244

[53] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Phys. Rev. Lett., 73: 58–61, Jul 1994. 10.1103/PhysRevLett.73.58.
https://doi.org/10.1103/PhysRevLett.73.58

[54] M. Roetteler, M. Naehrig, K. M. Svore, and K. Lauter. Quantum resource estimates for computing elliptic curve discrete logarithms. In Advances in Cryptology – ASIACRYPT 2017, pages 241–270, 2017. 10.1007/978-3-319-70697-9_9.
https://doi.org/10.1007/978-3-319-70697-9_9

[55] H. J. Ryser. Combinatorial mathematics, volume 14. 1963. 10.5948/UPO9781614440147.
https://doi.org/10.5948/UPO9781614440147

[56] D. Shepherd and M. J. Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465 (2105): 1413–1439, 2009. 10.1098/rspa.2008.0443.
https://doi.org/10.1098/rspa.2008.0443

[57] L. Stockmeyer. The complexity of approximate counting. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, page 118–126, 1983. 10.1145/800061.808740.
https://doi.org/10.1145/800061.808740

[58] B. M. Terhal and D. P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4 (2): 134–145, 2004. 10.26421/QIC4.2.
https://doi.org/10.26421/QIC4.2

[59] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20 (5): 865–877, 1991. 10.1137/0220053.
https://doi.org/10.1137/0220053

[60] S. Toda and M. Ogiwara. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 21 (2): 316–328, 1992. 10.1137/0221023.
https://doi.org/10.1137/0221023

[61] L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8 (2): 189 – 201, 1979. 10.1016/0304-3975(79)90044-6.
https://doi.org/10.1016/0304-3975(79)90044-6

[62] M. Vyalyi. $QMA$$=$$PP$ implies that $PP$ contains $PH$. In ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, 2003. URL https://eccc.weizmann.ac.il/report/2003/021/.
https://eccc.weizmann.ac.il/report/2003/021/

[63] R. Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348 (2): 357–365, 2005. 10.1016/j.tcs.2005.09.023.
https://doi.org/10.1016/j.tcs.2005.09.023

[64] R. Williams and H. Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1867–1877. 2014. 10.1137/1.9781611973402.135.
https://doi.org/10.1137/1.9781611973402.135

[65] R. R. Williams. Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In 31st Conference on Computational Complexity (CCC 2016), volume 50, pages 2:1–2:17, 2016. 10.4230/LIPIcs.CCC.2016.2.
https://doi.org/10.4230/LIPIcs.CCC.2016.2

[66] V. V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), volume 43, pages 17–29, 2015. 10.4230/LIPIcs.IPEC.2015.17.
https://doi.org/10.4230/LIPIcs.IPEC.2015.17

[67] A. R. Woods. Unsatisfiable systems of equations, over a finite field. In Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280), pages 202–211, 1998. 10.1109/SFCS.1998.743444.
https://doi.org/10.1109/SFCS.1998.743444

Cited by

[1] Lu Li, Kaifeng Bu, Dax Enshan Koh, Arthur Jaffe, and Seth Lloyd, "Wasserstein complexity of quantum circuits", Journal of Physics A: Mathematical and Theoretical 58 26, 265302 (2025).

[2] Zeheng Wang, Timothy van der Laan, and Muhammad Usman, "Self‐Adaptive Quantum Kernel Principal Component Analysis for Compact Readout of Chemiresistive Sensor Arrays", Advanced Science 12 15, 2411573 (2025).

[3] Daniel Jost Brod and Michał Oszmaniec, "Classical simulation of linear optics subject to nonuniform losses", Quantum 4, 267 (2020).

[4] Benjamin A. Cordier, Nicolas P. D. Sawaya, Gian Giacomo Guerreschi, and Shannon K. McWeeney, "Biology and medicine in the landscape of quantum advantages", Journal of The Royal Society Interface 19 196, 20220541 (2022).

[5] Akib Karim, Shaobo Zhang, and Muhammad Usman, "Low depth virtual distillation of quantum circuits by deterministic circuit decomposition", Physical Review Research 6 3, 033223 (2024).

[6] Neha Sharma and Vikas Saxena, "A systematic review of strategic approaches and applications in quantum computing", Optical and Quantum Electronics 57 8, 438 (2025).

[7] Vitaly V. Kocharovsky and Kunwar Kalra, "Wigner Distribution Sets Universal Lower Bound for Quantum Advantage in Gaussian Boson Sampling", Entropy 28 2, 188 (2026).

[8] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random Quantum Circuits Transform Local Noise into Global White Noise", Communications in Mathematical Physics 405 3, 78 (2024).

[9] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random Quantum Circuits Anticoncentrate in Log Depth", PRX Quantum 3 1, 010333 (2022).

[10] Zhenning Liu, Dhruv Devulapalli, Dominik Hangleiter, Yi-Kai Liu, Alicia J. Kollár, Alexey V. Gorshkov, and Andrew M. Childs, "Efficiently Verifiable Quantum Advantage on Near-Term Analog Quantum Simulators", PRX Quantum 6 1, 010341 (2025).

[11] Carsten Robens, Iñigo Arrazola, Wolfgang Alt, Dieter Meschede, Lucas Lamata, Enrique Solano, and Andrea Alberti, "Boson sampling with ultracold atoms in a programmable optical lattice", Physical Review A 110 1, 012615 (2024).

[12] Pierre Cazals, Aymeric François, Loïc Henriet, Lucas Leclerc, Malory Marin, Yassine Naghmouchi, Wesley da Silva Coelho, Florian Sikora, Vittorio Vitale, Rémi Watrigant, Monique Witt Garzillo, and Constantin Dalyac, "Identifying hard native instances for the maximum-independent-set problem on neutral-atom quantum processors", Physical Review Applied 25 3, 034085 (2026).

[13] Savvas Varsamopoulos, Evan Philip, Vincent E. Elfving, Herman W. T. van Vlijmen, Sairam Menon, Ann Vos, Natalia Dyubankova, Bert Torfs, and Anthony Rowe, "Quantum extremal learning", Quantum Machine Intelligence 6 2, 42 (2024).

[14] Ghazi Khan and Thomas E. Roth, "Field-based formalism for calculating multiqubit exchange-coupling rates for transmon qubits", Physical Review Applied 22 6, 064084 (2024).

[15] Marvin Bechtold, Johanna Barzen, Frank Leymann, Alexander Mandl, Julian Obst, Felix Truger, and Benjamin Weder, "Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices", Quantum Science and Technology 8 4, 045022 (2023).

[16] Vlad Stirbu and Tommi Mikkonen, Lecture Notes in Business Information Processing 500, 471 (2024) ISBN:978-3-031-53226-9.

[17] Venkat Aneesh Padmasola, Zhaotong Li, Rupak Chatterjee, and Wesley Dyk, "Solving the traveling salesman problem via different quantum computing architectures", International Journal of Quantum Information 24 03, 2540003 (2026).

[18] Domenik Eichhorn, Tobias Pett, Tobias Osborne, and Ina Schaefer, Proceedings of the 27th ACM International Systems and Software Product Line Conference - Volume A 1 (2023) ISBN:9798400700910.

[19] De Rosal Ignatius Moses Setiadi, T. Sutojo, Supriadi Rustad, Muhamad Akrom, Sudipta Kr Ghosal, Minh T. Nguyen, and Arnold Adimabua Ojugo, "Single Qubit Quantum Logistic-Sine XYZ-Rotation Maps: An Ultra-Wide Range Dynamics for Image Encryption", Computers, Materials & Continua 83 2, 2161 (2025).

[20] Nahual Sobrino, Unai Aseginolaza, Joaquim Jornet-Somoza, and Juan Borge, "A useful metric for the NISQ era: Qubit error probability and its role in zero noise extrapolation", AVS Quantum Science 8 1, 013803 (2026).

[21] Noah H. Oldfield, Christoph Laaber, Tao Yue, and Shaukat Ali, "Faster and Better Quantum Software Testing through Specification Reduction and Projective Measurements", ACM Transactions on Software Engineering and Methodology 34 7, 1 (2025).

[22] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[23] Julien Codsi and John van de Wetering, "Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach", Physical Review A 111 1, 012422 (2025).

[24] Kaifeng Bu and Dax Enshan Koh, "Classical Simulation of Quantum Circuits by Half Gauss Sums", Communications in Mathematical Physics 390 2, 471 (2022).

[25] Michel Barbeau, Erwan Beurier, Joaquin Garcia-Alfaro, Randy Kuang, Marc-Oliver Pahl, and Dominique Pastor, "1. Quantum Applications - Fachbeitrag: The Quantum What? Advantage, Utopia or Threat?", Digitale Welt 5 4, 34 (2021).

[26] He-Liang Huang, Xiao-Yue Xu, Chu Guo, Guojing Tian, Shi-Jie Wei, Xiaoming Sun, Wan-Su Bao, and Gui-Lu Long, "Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation", Science China Physics, Mechanics & Astronomy 66 5, 250302 (2023).

[27] Vitaly V. Kocharovsky, Vladimir V. Kocharovsky, William D. Shannon, and Sergey V. Tarasov, "Towards the Simplest Model of Quantum Supremacy: Atomic Boson Sampling in a Box Trap", Entropy 25 12, 1584 (2023).

[28] V. V. Kocharovsky, Vl. V. Kocharovsky, and S. V. Tarasov, "Atomic boson sampling in a Bose-Einstein-condensed gas", Physical Review A 106 6, 063312 (2022).

[29] Mogens Dalgaard and Felix Motzoi, "Fast, high precision dynamics in quantum optimal control theory", Journal of Physics B: Atomic, Molecular and Optical Physics 55 8, 085501 (2022).

[30] Unai Aseguinolaza, Nahual Sobrino, Gabriel Sobrino, Joaquim Jornet-Somoza, and Juan Borge, "Error estimation in current noisy quantum computers", Quantum Information Processing 23 5, 181 (2024).

[31] Tomoyuki Morimae and Suguru Tamaki, "Additive-error fine-grained quantum supremacy", Quantum 4, 329 (2020).

[32] Vincenzo Tamma and Simon Laibacher, "Boson sampling with random numbers of photons", Physical Review A 104 3, 032204 (2021).

[33] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Entanglement perspective on the quantum approximate optimization algorithm", Physical Review A 106 2, 022423 (2022).

[34] Bart Kolodziejczyk, Emergence of Quantum Computing Technologies in Automotive Applications: Opportunities and Future Use Cases (2024).

[35] Muhammad AbuGhanem and Hichem Eleuch, "NISQ Computers: A Path to Quantum Supremacy", IEEE Access 12, 102941 (2024).

[36] Rajesh K. Malla, Hiroki Sukeno, Hongye Yu, Tzu-Chieh Wei, Andreas Weichselbaum, and Robert M. Konik, "Feedback-based quantum algorithm inspired by counterdiabatic driving", Physical Review Research 6 4, 043068 (2024).

[37] Zheng-Hang Sun, Yong-Yi Wang, Jian Cui, and Heng Fan, "Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry", New Journal of Physics 25 1, 013015 (2023).

[38] Daniil Rabinovich, Andrey Kardashin, and Soumik Adhikary, "Role of overparametrization in quantum approximate optimization", Physical Review A 113 6, 062617 (2026).

[39] Nolan J. Coble and Matthew Coudron, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) 598 (2022) ISBN:978-1-6654-2055-6.

[40] Christiane P. Koch, Ugo Boscain, Tommaso Calarco, Gunther Dirr, Stefan Filipp, Steffen J. Glaser, Ronnie Kosloff, Simone Montangero, Thomas Schulte-Herbrüggen, Dominique Sugny, and Frank K. Wilhelm, "Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe", EPJ Quantum Technology 9 1, 19 (2022).

[41] Daniel Oliveira, Edoardo Giusto, Emanuele Dri, Nadir Casciola, Betis Baheri, Qiang Guan, Bartolomeo Montrucchio, and Paolo Rech, 2022 52nd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN) 137 (2022) ISBN:978-1-6654-1693-1.

[42] Javier Mancilla and Christophe Pere, "A Preprocessing Perspective for Quantum Machine Learning Classification Advantage in Finance Using NISQ Algorithms", Entropy 24 11, 1656 (2022).

[43] Jacob Smith, Hwangsun Kim, Ke An, Yan Chen, Ondrej Dyck, Kate Reidy, and Miaofang Chi, "Unraveling Materials Synthesis Mechanisms Using In Situ Transmission Electron Microscopy and Neutron Scattering", Chemical Reviews 125 18, 8731 (2025).

[44] Yuxuan Li, Lin Gan, Mingcheng Chen, Yaojian Chen, Haitian Lu, Chaoyang Lu, Jianwei Pan, Haohuan Fu, and Guangwen Yang, "Benchmarking 50-Photon Gaussian Boson Sampling on the Sunway TaihuLight", IEEE Transactions on Parallel and Distributed Systems 33 6, 1357 (2022).

[45] Zhimin Wang, Zhaoyun Chen, Shengbin Wang, Wendong Li, Yongjian Gu, Guoping Guo, and Zhiqiang Wei, "A quantum circuit simulator and its applications on Sunway TaihuLight supercomputer", Scientific Reports 11 1, 355 (2021).

[46] Tianci Zhou and Aram W. Harrow, "Maximal entanglement velocity implies dual unitarity", Physical Review B 106 20, L201104 (2022).

[47] Bence Bakó, Dániel T R Nagy, Péter Hága, Zsófia Kallus, and Zoltán Zimborás, "Problem-informed graphical quantum generative learning", Quantum Science and Technology 11 3, 035012 (2026).

[48] Chon-Fai Kam and En-Jui Kuo, "Quantum supremacy through Fock state q-boson sampling with transmon qubits", New Journal of Physics 27 12, 124509 (2025).

[49] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang, "Statistical complexity of quantum circuits", Physical Review A 105 6, 062431 (2022).

[50] Zain H. Saleem, Teague Tomesh, Bilal Tariq, and Martin Suchara, "Approaches to Constrained Quantum Approximate Optimization", SN Computer Science 4 2, 183 (2023).

[51] Juan Borge, Unai Aseguinolaza, Nahual Sobrino, Gabriel Sobrino, and Joaquim Jornet-Somoza, "Error Estimation in Current Noisy Quantum Computers", (2023).

[52] Haolin Huang, Liam G. Thomas, Muhammad Usman, Rajib Rahman, and David N. Jamieson, "Million‐Atom Wave Function Simulations of a Single Donor Qubit Made in Silicon Utilizing Ion Implantation Technology", Advanced Quantum Technologies 9 1, e00675 (2026).

[53] Omar Faruque Siyam and Jiann-Shiun Yuan, "Machine Learning for Adaptive Surface Code Distance Selection", IEEE Access 14, 76876 (2026).

[54] Alberto Di Meglio, Karl Jansen, Ivano Tavernelli, Constantia Alexandrou, Srinivasan Arunachalam, Christian W. Bauer, Kerstin Borras, Stefano Carrazza, Arianna Crippa, Vincent Croft, Roland de Putter, Andrea Delgado, Vedran Dunjko, Daniel J. Egger, Elias Fernández-Combarro, Elina Fuchs, Lena Funcke, Daniel González-Cuadra, Michele Grossi, Jad C. Halimeh, Zoë Holmes, Stefan Kühn, Denis Lacroix, Randy Lewis, Donatella Lucchesi, Miriam Lucio Martinez, Federico Meloni, Antonio Mezzacapo, Simone Montangero, Lento Nagano, Vincent R. Pascuzzi, Voica Radescu, Enrique Rico Ortega, Alessandro Roggero, Julian Schuhmacher, Joao Seixas, Pietro Silvi, Panagiotis Spentzouris, Francesco Tacchino, Kristan Temme, Koji Terashi, Jordi Tura, Cenk Tüysüz, Sofia Vallecorsa, Uwe-Jens Wiese, Shinjae Yoo, and Jinglei Zhang, "Quantum Computing for High-Energy Physics: State of the Art and Challenges", PRX Quantum 5 3, 037001 (2024).

[55] Nicolas PD Sawaya, Albert T Schmitz, and Stuart Hadfield, "Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems", Quantum 7, 1111 (2023).

[56] Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, and Matthew J. Reagor, "Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm", PRX Quantum 3 4, 040339 (2022).

[57] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi, and Damian Markham, "Efficient verification of Boson Sampling", Quantum 5, 578 (2021).

[58] Vitaly Kocharovsky, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 1063 (2025) ISBN:979-8-3315-5736-2.

[59] Paulina Schindler and Johannes Ruhland, Lecture Notes in Networks and Systems 506, 404 (2022) ISBN:978-3-031-10460-2.

[60] Martin Kliesch and Ingo Roth, "Theory of Quantum System Certification", PRX Quantum 2 1, 010201 (2021).

[61] Sergey Tarasov, William Shannon, Vladimir Kocharovsky, and Vitaly Kocharovsky, "Multi-Qubit Bose–Einstein Condensate Trap for Atomic Boson Sampling", Entropy 24 12, 1771 (2022).

[62] Barry C. Sanders, "Quantum computing for data science", Journal of Physics: Conference Series 2438 1, 012007 (2023).

[63] Alexander Zlokapa, Benjamin Villalonga, Sergio Boixo, and Daniel A. Lidar, "Boundaries of quantum supremacy via random circuit sampling", npj Quantum Information 9 1, 36 (2023).

[64] V Vijendran, Aritra Das, Dax Enshan Koh, Syed M Assad, and Ping Koy Lam, "An expressive ansatz for low-depth quantum approximate optimisation", Quantum Science and Technology 9 2, 025010 (2024).

[65] Haoyu Qi, Diego Cifuentes, Kamil Brádler, Robert Israel, Timjan Kalajdzievski, and Nicolás Quesada, "Efficient sampling from shallow Gaussian quantum-optical circuits with local interactions", Physical Review A 105 5, 052412 (2022).

[66] Dominik Hangleiter, Marcin Kalinowski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail D. Lukin, and Michael J. Gullans, "Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum Polynomial Circuits on Hypercubes", PRX Quantum 6 2, 020338 (2025).

[67] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).

[68] Daniil Rabinovich, Soumik Adhikary, Ernesto Campos, Vishwanathan Akshay, Evgeny Anikin, Richik Sengupta, Olga Lakhmanskaya, Kirill Lakhmanskiy, and Jacob Biamonte, "Ion-native variational ansatz for quantum approximate optimization", Physical Review A 106 3, 032418 (2022).

[69] Kaifeng Bu, Dax Enshan Koh, Lu Li, Qingxian Luo, and Yaobo Zhang, "Effects of quantum resources and noise on the statistical complexity of quantum circuits", Quantum Science and Technology 8 2, 025013 (2023).

[70] Vitaly Kocharovsky, "Hybrid Boson Sampling", Entropy 26 11, 926 (2024).

[71] P. Krantz, M. Kjaergaard, F. Yan, T. P. Orlando, S. Gustavsson, and W. D. Oliver, "A quantum engineer's guide to superconducting qubits", Applied Physics Reviews 6 2, 021318 (2019).

[72] Gavin E. Crooks, "Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem", arXiv:1811.08419, (2018).

[73] Michał Oszmaniec and Daniel J. Brod, "Classical simulation of photonic linear optics with lost particles", New Journal of Physics 20 9, 092002 (2018).

[74] Abhinav Deshpande, Bill Fefferman, Minh C. Tran, Michael Foss-Feig, and Alexey V. Gorshkov, "Dynamical Phase Transitions in Sampling Complexity", Physical Review Letters 121 3, 030501 (2018).

[75] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random quantum circuits transform local noise into global white noise", arXiv:2111.14907, (2021).

[76] Pak Hong Leung and Kenneth R. Brown, "Entangling an arbitrary pair of qubits in a long ion crystal", Physical Review A 98 3, 032318 (2018).

[77] Ming-Cheng Chen, Riling Li, Lin Gan, Xiaobo Zhu, Guangwen Yang, Chao-Yang Lu, and Jian-Wei Pan, "Quantum-Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits", Physical Review Letters 124 8, 080502 (2020).

[78] Ramis Movassagh, "Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling", arXiv:1810.04681, (2018).

[79] Mikkel V. Larsen, Xueshi Guo, Casper R. Breum, Jonas S. Neergaard-Nielsen, and Ulrik L. Andersen, "Fiber-coupled EPR-state generation using a single temporally multiplexed squeezed light source", npj Quantum Information 5 1, 46 (2019).

[80] Will Finigan, Michael Cubeddu, Thomas Lively, Johannes Flick, and Prineha Narang, "Qubit Allocation for Noisy Intermediate-Scale Quantum Computers", arXiv:1810.08291, (2018).

[81] Thomas Hummel, Claudéric Ouellet-Plamondon, Ela Ugur, Irina Kulkova, Toke Lund-Hansen, Matthew A. Broome, Ravitej Uppu, and Peter Lodahl, "Efficient demultiplexed single-photon source with a quantum dot coupled to a nanophotonic waveguide", Applied Physics Letters 115 2, 021102 (2019).

[82] Iskren Vankov, Daniel Mills, Petros Wallden, and Elham Kashefi, "Methods for classically simulating noisy networked quantum architectures", Quantum Science and Technology 5 1, 014001 (2020).

[83] Matthew Coudron, Jalex Stark, and Thomas Vidick, "Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits", Communications in Mathematical Physics 382 1, 49 (2021).

[84] Matthew Coudron, Jalex Stark, and Thomas Vidick, "Trading locality for time: certifiable randomness from low-depth circuits", arXiv:1810.04233, (2018).

[85] Dominik Hangleiter, "Sampling and the complexity of nature", arXiv:2012.07905, (2020).

[86] Samuele Ferracin, Theodoros Kapourniotis, and Animesh Datta, "Accrediting outputs of noisy intermediate-scale quantum computing devices", arXiv:1811.09709, (2018).

[87] Alexander Zlokapa, Sergio Boixo, and Daniel Lidar, "Boundaries of quantum supremacy via random circuit sampling", arXiv:2005.02464, (2020).

[88] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan, "Implementation of the XY interaction family with calibration of a single pulse", arXiv:1912.04424, (2019).

[89] Alexander M. Dalzell, Nicholas Hunter-Jones, and Fernando G. S. L. Brandão, "Random quantum circuits anti-concentrate in log depth", arXiv:2011.12277, (2020).

[90] Ryu Hayakawa, Tomoyuki Morimae, and Suguru Tamaki, "Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths", arXiv:1902.08382, (2019).

[91] Noah H. Oldfield, Christoph Laaber, Tao Yue, and Shaukat Ali, "Faster and Better Quantum Software Testing through Specification Reduction and Projective Measurements", arXiv:2405.15450, (2024).

[92] Martin Kliesch and Ingo Roth, "Theory of quantum system certification: a tutorial", arXiv:2010.05925, (2020).

[93] Peter Clifford and Raphaël Clifford, "Faster classical boson sampling", Physica Scripta 99 6, 065121 (2024).

[94] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh, "Entanglement scaling in quantum advantage benchmarks", Physical Review A 101 1, 012349 (2020).

[95] Jacob D. Biamonte, Mauro E. S. Morales, and Dax Enshan Koh, "Entanglement Scaling in Quantum Advantage Benchmarks", arXiv:1808.00460, (2018).

[96] Tomoyuki Morimae, Yuki Takeuchi, and Seiichiro Tani, "Sampling of globally depolarized random quantum circuit", arXiv:1911.02220, (2019).

[97] Xi Chen, Bin Cheng, Zhaokai Li, Xinfang Nie, Nengkun Yu, Man-Hong Yung, and Xinhua Peng, "Experimental cryptographic verification for near-term quantum cloud computing", Science Bulletin 66 1, 23 (2021).

[98] Cupjin Huang, Michael Newman, and Mario Szegedy, "Explicit Lower Bounds on Strong Quantum Simulation", IEEE Transactions on Information Theory 66 9, 5585 (2020).

[99] Tomoyuki Morimae and Suguru Tamaki, "Fine-grained quantum computational supremacy", arXiv:1901.01637, (2019).

[100] Michael Cubeddu, Will Finigan, Thomas Lively, Johannes Flick, and Prineha Narang, "Introducing Control Flow in Qubit Allocation for Quantum Turing Machines", arXiv:1907.07113, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 05:23:53) and SAO/NASA ADS (last updated successfully 2026-07-16 16:22:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-17 05:23:53: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

How many qubits are needed for quantum computational supremacy?

Abstract

► BibTeX data

► References

Cited by

4 thoughts on “How many qubits are needed for quantum computational supremacy?”