How many qubits are needed for quantum computational supremacy?

Alexander M. Dalzell1,2, Aram W. Harrow3, Dax Enshan Koh4,5, and Rolando L. La Placa3

1Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA
2Department of Physics, Massachusetts Institute of Technology, Cambrdige, Massachusetts 02139, USA
3Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
4Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
5Zapata Computing, Inc., 100 Federal Street, 20th Floor, Boston, Massachusetts 02110, USA

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


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

► 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[10] R. Beigel and J. Tarui. On ACC. Computational Complexity, 4 (4): 350–366, 1994. 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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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:/​/​​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.

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

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

[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.

[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.

[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.

[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.

[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.

[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.

[32] A. W. Harrow and A. Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, 2017. 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.

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

[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.

[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.

[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.

[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.

[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.

[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.

[41] R. J. Lipton. New directions in testing. In Distributed Computing and Cryptography, volume 2, pages 191–202, 1989. 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.

[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.

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

[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.

[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.

[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.

[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.

[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.

[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.

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

[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:/​/​​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.

[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.

[55] H. J. Ryser. Combinatorial mathematics, volume 14. 1963. 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.

[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.

[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.

[59] S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20 (5): 865–877, 1991. 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.

[61] L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8 (2): 189 – 201, 1979. 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:/​/​​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.

[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.

[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.

[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.

[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.

Cited by

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

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

[3] Felix Truger, Martin Beisel, Johanna Barzen, Frank Leymann, and Vladimir Yussupov, "Selection and Optimization of Hyperparameters in Warm-Started Quantum Optimization for the MaxCut Problem", Electronics 11 7, 1033 (2022).

[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] 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).

[6] 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).

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

[8] 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).

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

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

[11] 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).

[12] 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).

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

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

[15] 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).

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

[17] 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).

[18] 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).

[19] 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).

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

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

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

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

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

[25] 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).

[26] 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).

[27] 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).

[28] 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).

[29] 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.

[30] 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).

[31] 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).

[32] 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).

[33] 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.

[34] 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).

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

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

[37] 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).

[38] 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).

[39] 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).

[40] 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).

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

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

[43] 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).

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

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

[46] 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, 46 (2019).

[47] 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).

[48] 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).

[49] 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).

[50] 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).

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

[52] Daniel Jost Brod and Michał\ Oszmaniec, "Classical simulation of linear optics subject to nonuniform losses", arXiv:1906.06696, (2019).

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

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

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

[56] 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).

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

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

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

[60] 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).

[61] 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 2023-06-08 19:31:18) and SAO/NASA ADS (last updated successfully 2023-06-08 19:31:19). The list may be incomplete as not all publishers provide suitable and complete citation data.