Anticoncentration theorems for schemes showing a quantum speedup
Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany
| Published: | 2018-05-22, volume 2, page 65 |
| Eprint: | arXiv:1706.03786v4 |
| Doi: | https://doi.org/10.22331/q-2018-05-22-65 |
| Citation: | Quantum 2, 65 (2018). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
One of the main milestones in quantum information science is to realise quantum devices that exhibit an exponential computational advantage over classical ones without being universal quantum computers, a state of affairs dubbed quantum speedup, or sometimes "quantum computational supremacy". The known schemes heavily rely on mathematical assumptions that are plausible but unproven, prominently results on anticoncentration of random prescriptions. In this work, we aim at closing the gap by proving two anticoncentration theorems and accompanying hardness results, one for circuit-based schemes, the other for quantum quench-type schemes for quantum simulations. Compared to the few other known such results, these results give rise to a number of comparably simple, physically meaningful and resource-economical schemes showing a quantum speedup in one and two spatial dimensions. At the heart of the analysis are tools of unitary designs and random circuits that allow us to conclude that universal random circuits anticoncentrate as well as an embedding of known circuit-based schemes in a 2D translation-invariant architecture.
Popular summary
► BibTeX data
► References
[1] J. Preskill, Bull. Am. Phys. Soc. 58 (2013), arXiv:1203.5813.
arXiv:1203.5813
http://meetings.aps.org/link/BAPS.2013.APR.P1.2
[2] S. Trotzky, Y.-A. Chen, A. Flesch, I. P. McCulloch, U. Schollwöck, J. Eisert, and I. Bloch, Nature Phys. 8, 325 (2012), arXiv:1101.2659.
arXiv:1101.2659
[3] J.-Y. Choi, S. Hild, J. Zeiher, P. Schauß, A. Rubio-Abadal, T. Yefsah, V. Khemani, D. A. Huse, I. Bloch, and C. Gross, Science 352, 1547 (2016), arXiv:1604.04178.
https://doi.org/10.1126/science.aaf8834
arXiv:1604.04178
[4] S. Braun, M. Friesdorf, S. S. Hodgman, M. Schreiber, J. P. Ronzheimer, A. Riera, M. del Rey, I. Bloch, J. Eisert, and U. Schneider, Proc. Natl. Ac. Sc. 112, 3641 (2015), arXiv:1403.7199.
https://doi.org/10.1073/pnas.1408861112
arXiv:1403.7199
[5] S. Aaronson and A. Arkhipov, Th. Comp. 9, 143 (2013), arXiv:1011.3245.
arXiv:1011.3245
[6] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Phys. Rev. Lett. 117, 080501 (2016), arXiv:1504.07999.
https://doi.org/10.1103/PhysRevLett.117.080501
arXiv:1504.07999
[7] M. J. Bremner, A. Montanaro, and D. J. Shepherd, Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8
[8] S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics , 1 (2018), arXiv:1608.00263.
https://doi.org/10.1038/s41567-018-0124-x
arXiv:1608.00263
[9] X. Gao, S.-T. Wang, and L.-M. Duan, Phys. Rev. Lett. 118, 040502 (2017), arXiv:1607.04947.
https://doi.org/10.1103/PhysRevLett.118.040502
arXiv:1607.04947
[10] J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Phys. Rev. X 8, 021010 (2018), arXiv:1703.00466.
https://doi.org/10.1103/PhysRevX.8.021010
arXiv:1703.00466
[11] T. Morimae, Phys. Rev. A 96, 040302 (2017), arXiv:1704.03640.
https://doi.org/10.1103/PhysRevA.96.040302
arXiv:1704.03640
[12] J. Miller, S. Sanders, and A. Miyake, Phys. Rev. A 96, 062320 (2017), arXiv:1703.11002.
https://doi.org/10.1103/PhysRevA.96.062320
arXiv:1703.11002
[13] C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, ``Boson sampling in the light of sample complexity,'' arXiv:1306.3995.
arXiv:1306.3995
[14] S. Aaronson and A. Arkhipov, ``BosonSampling is far from uniform,'' arXiv:1309.7460.
arXiv:1309.7460
[15] D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Quantum Sci. Technol. 2, 015004 (2017), arXiv:1602.00703.
https://doi.org/10.1088/2058-9565/2/1/015004
arXiv:1602.00703
[16] T. Kapourniotis and A. Datta, (2017), arXiv:1703.09568.
arXiv:1703.09568
[17] L. Stockmeyer, Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, 118 (1983).
https://doi.org/10.1145/800061.808740
[18] A. P. Lund, M. J. Bremner, and T. C. Ralph, npj Quant. Inf. 3, 15 (2017), arXiv:1702.03061.
https://doi.org/10.1038/s41534-017-0018-2
arXiv:1702.03061
[19] M. Schwarz and M. V. den Nest, (2013), arXiv:1310.6749.
arXiv:1310.6749
[20] R. Jozsa and M. V. d. Nest, Quant. Inf. Comp 14, 0633–0648 (2014), arXiv:1305.6190.
arXiv:1305.6190
[21] Y. Nakata, M. Koashi, and M. Murao, New J. Phys. 16, 053043 (2014), arXiv:1311.1128.
https://doi.org/10.1088/1367-2630/16/5/053043
arXiv:1311.1128
[22] D. Gross, K. Audenaert, and J. Eisert, J. Math. Phys. 48, 052104 (2007), arXiv:quant-ph/0611002.
https://doi.org/10.1063/1.2716992
arXiv:quant-ph/0611002
[23] F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Commun. Math. Phys. 346, 397 (2016).
https://doi.org/10.1007/s00220-016-2706-8
[24] M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proc. Roy. Soc. 467, 2126 (2010), arXiv:1005.1407.
https://doi.org/10.1098/rspa.2010.0301
arXiv:1005.1407
[25] B. M. Terhal and D. P. DiVincenzo, Quant. Inf. Comp. 4, 134 (2004), arXiv:quant-ph/0205133.
arXiv:quant-ph/0205133
[26] G. Kuperberg, Theory of Computing 11, 183 (2015).
https://doi.org/10.4086/toc.2015.v011a006
[27] K. Fujii and T. Morimae, New J. Phys. 19, 033003 (2017), arXiv:1311.2128.
https://doi.org/10.1088/1367-2630/aa5fdb
arXiv:1311.2128
[28] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, (2018), arXiv:1803.04402.
arXiv:1803.04402
[29] R. L. Mann and M. J. Bremner, arXiv:1711.00686.
arXiv:1711.00686
[30] S. Aaronson, ``P$\neq$NP?'' in Open problems in mathematics (Springer, 2016).
https://doi.org/10.1007/978-3-319-32162-2
[31] L. Fortnow, in Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC '05 (ACM, 2005).
https://doi.org/10.1145/1060590.1060609
[32] R. M. Karp and R. J. Lipton, in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80 (1980).
https://doi.org/10.1145/800141.804678
[33] C. Dankert, R. Cleve, J. Emerson, and E. Livine, Phys. Rev. A 80, 012304 (2009), arXiv:quant-ph/0606161.
https://doi.org/10.1103/PhysRevA.80.012304
arXiv:quant-ph/0606161
[34] E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert, Commun. Math. Phys. 355, 905 (2017), arXiv:1606.01914.
https://doi.org/10.1007/s00220-017-2950-6
arXiv:1606.01914
[35] A. W. Harrow and R. A. Low, Commun. Math. Phys. 291, 257 (2009), arXiv:0802.1919.
https://doi.org/10.1007/s00220-009-0873-6
arXiv:0802.1919
[36] H. Zhu, R. Kueng, M. Grassl, and D. Gross, (2016), arXiv:1609.08172.
arXiv:1609.08172
[37] J. Emerson, Y. S. Weinstein, M. Saraceno, S. Lloyd, and D. G. Cory, Science 302, 2098 (2003).
https://doi.org/10.1126/science.1090790
[38] W. G. Brown, Y. S. Weinstein, and L. Viola, Phys. Rev. A 77, 040303 (2008), arXiv:0802.2675.
https://doi.org/10.1103/PhysRevA.77.040303
arXiv:0802.2675
[39] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, R. Barends, B. Burkett, Y. Chen, and Z. Chen, (2017), Science 13 360, Issue 6385, (2018).
https://doi.org/10.1126/science.aao4309
[40] P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury, and F. Vatan, Inf. Proc. Lett. 75, 101 (2000), arXiv:quant-ph/9906054.
https://doi.org/10.1016/S0020-0190(00)00084-3
arXiv:quant-ph/9906054
[41] A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation, Graduate studies in mathematics (American Mathematical Society, 2002).
[42] Y. Shi, Quant. Inf. Comp. 3, 84 (2003), arXiv:quant-ph/0205115.
arXiv:quant-ph/0205115
http://dl.acm.org/citation.cfm?id=2011508.2011515
[43] A. Paetznick and B. W. Reichardt, Phys. Rev. Lett. 111, 090505 (2013), arXiv:1304.3709.
https://doi.org/10.1103/PhysRevLett.111.090505
arXiv:1304.3709
[44] P. W. Shor, in Proc. of 37th Conf. Found. Comp. Sci. (1996) pp. 56–65, arXiv:quant-ph/9605011.
https://doi.org/10.1109/SFCS.1996.548464
arXiv:quant-ph/9605011
[45] E. Knill, R. Laflamme, and W. Zurek, (1996), arXiv:quant-ph/9610011.
arXiv:quant-ph/9610011
[46] E. Knill, R. Laflamme, and W. H. Zurek, Proc. Roy. Soc. A 454, 365 (1998).
https://doi.org/10.1098/rspa.1998.0166
[47] D. Gottesman and I. L. Chuang, Nature 402, 390 (1999).
https://doi.org/10.1038/46503
[48] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003), arXiv:quant-ph/0301052.
https://doi.org/10.1103/PhysRevA.68.022312
arXiv:quant-ph/0301052
[49] L. A. Goldberg and H. Guo, (2014), arXiv:1409.5627.
arXiv:1409.5627
[50] A. Y. Kitaev, Russ. Math. Surv. 52, 1191 (1997).
https://doi.org/10.1070/RM1997v052n06ABEH002155
[51] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge Series on Information and the Natural Sciences (Cambridge University Press, 2000).
[52] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, SIAM J. Comp. 26, 1510 (1997), arXiv:quant-ph/9701001.
https://doi.org/10.1137/S0097539796300933
arXiv:quant-ph/9701001
[53] S. Aaronson, Proc. Roy. Soc. A 461, 2063 (2005), arXiv:quant-ph/0412187.
https://doi.org/10.1098/rspa.2005.1546
arXiv:quant-ph/0412187
[54] H. Dell, T. Husfeldt, D. Marx, N. Taslaman, and M. Wahlén, ACM Trans. Algorithms 10, 21:1 (2014).
https://doi.org/10.1145/2635812
[55] S. X. Cui and Z. Wang, J. Math. Phys. 56, 032202 (2015).
https://doi.org/10.1063/1.4914941
[56] A. Bocharov, M. Roetteler, and K. M. Svore, Phys. Rev. A 91, 052317 (2015), arXiv:1409.3552.
https://doi.org/10.1103/PhysRevA.91.052317
arXiv:1409.3552
[57] R. Cleve, D. Leung, L. Liu, and C. Wang, Quant. Inf. Comp. 16, 0721 (2016), arXiv:1501.04592.
arXiv:1501.04592
[58] R. Koenig and J. A. Smolin, J. Math. Phys. 55, 122202 (2014), arXiv:1406.2170.
https://doi.org/10.1063/1.4903507
arXiv:1406.2170
[59] J. Eisert, M. Friesdorf, and C. Gogolin, Nature Phys 11, 124 (2015), arXiv:1408.5148.
arXiv:1408.5148
[60] A. Polkovnikov, K. Sengupta, A. Silva, and M. Vengalattore, Rev. Mod. Phys. 83, 863 (2011), arXiv:1007.5331.
https://doi.org/10.1103/RevModPhys.83.863
arXiv:1007.5331
[61] R. Jozsa, (2006), arXiv:quant-ph/0603163.
arXiv:quant-ph/0603163
[62] R. Impagliazzo and R. Paturi, in Proc. XIV IEEE Conf. Comp. Compl. (1999) pp. 237–240.
https://doi.org/10.1109/CCC.1999.766282
[63] S. Aaronson and L. Chen, (2016), arXiv:1612.05903.
arXiv:1612.05903
[64] M. Ozols, How to generate a random unitary matrix (Mar, 2009).
http://home.lu.lv/~sd20008/papers/essays/Random
[65] F. Mezzadri, (2006), arXiv:math-ph/0609050.
arXiv:math-ph/0609050
[66] Y. S. Weinstein and C. S. Hellberg, Phys. Rev. A 72, 022331 (2005).
https://doi.org/10.1103/PhysRevA.72.022331
[67] K. Zyczkowski and M. Kus, J. Phys. A 27, 4235 (1994).
https://doi.org/10.1088/0305-4470/27/12/028
[68] M. Pozniak, K. Zyczkowski, and M. Kus, J. Phys. A 31, 1059 (1998), arXiv:chao-dyn/9707006.
https://doi.org/10.1088/0305-4470/31/3/016
arXiv:chao-dyn/9707006
[69] F. Haake, Quantum signatures of chaos, Springer Series in Synergetics, Vol. 54 (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010).
Cited by
[1] Daniel Stilck França and Raul Garcia-Patron, "A game of quantum advantage: linking verification and simulation", Quantum 6, 753 (2022).
[2] Beatrice Magni, Alexios Christopoulos, Andrea De Luca, and Xhek Turkeshi, "Anticoncentration in Clifford Circuits and Beyond: From Random Tensor Networks to Pseudomagic States", Physical Review X 15 3, 031071 (2025).
[3] J. Haferkamp, D. Hangleiter, A. Bouland, B. Fefferman, J. Eisert, and J. Bermejo-Vega, "Closing Gaps of a Quantum Advantage with Short-Time Hamiltonian Dynamics", Physical Review Letters 125 25, 250501 (2020).
[4] Sachin Kasture, Oleksandr Kyriienko, and Vincent E. Elfving, "Protocols for classically training quantum generative models on probability distributions", Physical Review A 108 4, 042406 (2023).
[5] Yota Maeda, Hideaki Kawaguchi, and Hiroyuki Tezuka, "Estimation of mutual information via quantum kernel methods", Quantum Machine Intelligence 7 1, 29 (2025).
[6] Oskar Słowik, Oliver Reardon-Smith, and Adam Sawicki, "Fundamental solutions of the heat equation on unitary groups establish an improved relation between ε-nets and approximate unitary t-designs", Journal of Physics A: Mathematical and Theoretical 58 44, 445301 (2025).
[7] Byeongseon Go, Changhun Oh, and Hyunseok Jeong, "On computational complexity and average-case hardness of shallow-depth boson sampling", Quantum 10, 2026 (2026).
[8] Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, and Seiichiro Tani, "Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection", Theory of Computing Systems 69 1, 6 (2025).
[9] Abhinav Deshpande, Arthur Mehta, Trevor Vincent, Nicolás Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand, "Quantum computational advantage via high-dimensional Gaussian boson sampling", Science Advances 8 1, eabi7894 (2022).
[10] Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk, "Quantum advantage of unitary Clifford circuits with magic state inputs", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 475 2225, 20180427 (2019).
[11] Eby Sebastian Puthussery and Ramesh Chandra Poonia, Lecture Notes in Networks and Systems 1021, 315 (2024) ISBN:978-981-97-3590-7.
[12] Lucas Kocia and Peter Love, "Stationary Phase Method in Discrete Wigner Functions and Classical Simulation of Quantum Circuits", Quantum 5, 494 (2021).
[13] Rahul Arvind, Kishor Bharti, Jun Yong Khoo, Dax Enshan Koh, and Jian Feng Kong, "Quantum tug of war between randomness and symmetries on homogeneous spaces", Physical Review Research 7 1, 013105 (2025).
[14] Arman Sauliere, Guglielmo Lami, Corentin Boyer, Jacopo De Nardis, and Andrea De Luca, "Universality in the Anticoncentration of Noisy Quantum Circuits at Finite Depths", PRX Quantum 7 2, 020365 (2026).
[15] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Fault-tolerant quantum speedup from constant depth quantum circuits", Physical Review Research 2 3, 033444 (2020).
[16] Dominik Hangleiter and Jens Eisert, "Computational advantage of quantum random sampling", Reviews of Modern Physics 95 3, 035001 (2023).
[17] Soumik Ghosh, Dominik Hangleiter, and Jonas Helsen, "Random Regular Graph States Are Complex at Almost Any Depth", PRX Quantum 6 4, 040344 (2025).
[18] Zimu Li, Han Zheng, Junyu Liu, Liang Jiang, and Zi-Wen Liu, "Designs from Local Random Quantum Circuits with SU(d) Symmetry", PRX Quantum 5 4, 040349 (2024).
[19] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin, "Sample Complexity of Device-Independently Certified “Quantum Supremacy”", Physical Review Letters 122 21, 210502 (2019).
[20] Martin Kliesch and Ingo Roth, "Theory of Quantum System Certification", PRX Quantum 2 1, 010201 (2021).
[21] Oussama Houhou, Darren W. Moore, Sougato Bose, and Alessandro Ferraro, "Unconditional measurement-based quantum computation with optomechanical continuous variables", Physical Review A 105 1, 012610 (2022).
[22] Byeongseon Go, Changhun Oh, Liang Jiang, and Hyunseok Jeong, "Exploring shallow-depth boson sampling: Toward a scalable quantum advantage", Physical Review A 109 5, 052613 (2024).
[23] Kaifeng Bu and Dax Enshan Koh, "Efficient Classical Simulation of Clifford Circuits with Nonstabilizer Input States", Physical Review Letters 123 17, 170502 (2019).
[24] Meng Zhang, Chao Wang, and Yongjian Han, "Noisy Random Quantum Circuit Sampling and its Classical Simulation", Advanced Quantum Technologies 6 7, 2300030 (2023).
[25] Yuki Takeuchi, Yasuhiro Takahashi, and Seiichiro Tani, "Hardness of efficiently generating ground states in postselected quantum computation", Physical Review Research 3 1, 013213 (2021).
[26] Jirawat Tangpanitanon, Supanut Thanasilp, Ninnat Dangniam, Marc-Antoine Lemonde, and Dimitris G. Angelakis, "Expressibility and trainability of parametrized analog quantum systems for machine learning applications", Physical Review Research 2 4, 043364 (2020).
[27] Chenfeng Cao and Jens Eisert, "Measurement-Driven Quantum Advantages in Shallow Circuits", Physical Review Letters 136 8, 080601 (2026).
[28] Brian Barch, Razieh Mohseninia, and Daniel Lidar, "Low overhead universality and quantum supremacy using only Z control", Physical Review Research 3 3, 033207 (2021).
[29] Thomas Schuster, Chao Yin, Xun Gao, and Norman Y. Yao, "A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits", Physical Review X 15 4, 041018 (2025).
[30] Toshihiro Yada, Ryotaro Suzuki, Yosuke Mitsuhashi, and Nobuyuki Yoshioka, "Non-Haar Random Circuits form Unitary Designs as Fast as Haar Random Circuits", Physical Review Letters 136 3, 030401 (2026).
[31] Aram W. Harrow and Saeed Mehraban, "Approximate Unitary t-Designs by Short Random Quantum Circuits Using Nearest-Neighbor and Long-Range Gates", Communications in Mathematical Physics 401 2, 1531 (2023).
[32] Darrell L. Young and Mitchell A. Thornton, 2026 IEEE 19th Dallas Circuits and Systems Conference (DCAS) 1 (2026) ISBN:979-8-3315-5193-3.
[33] Alexander M. Dalzell, Aram W. Harrow, Dax Enshan Koh, and Rolando L. La Placa, "How many qubits are needed for quantum computational supremacy?", Quantum 4, 264 (2020).
[34] Michał Oszmaniec, Ninnat Dangniam, Mauro E.S. Morales, and Zoltán Zimborás, "Fermion Sampling: A Robust Quantum Computational Advantage Scheme Using Fermionic Linear Optics and Magic Input States", PRX Quantum 3 2, 020328 (2022).
[35] Paolo Braccia, Pablo Bermejo, Lukasz Cincio, and M. Cerezo, "Computing exact moments of local random quantum circuits via tensor networks", Quantum Machine Intelligence 6 2, 54 (2024).
[36] Ramis Movassagh, "The hardness of random quantum circuits", Nature Physics 19 11, 1719 (2023).
[37] Kaustav Mukherjee, Sarah Chehade, Lorenzo Versini, Karim K. Alaa El-Din, Florian Mintert, and Rick Mukherjee, "Statistical learning on randomized data to verify quantum state approximate k -designs", Physical Review Research 8 2, 023354 (2026).
[38] Antonio Anna Mele, "Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial", Quantum 8, 1340 (2024).
[39] Jacob Daigle, Hubert de Guise, and Trevor Welsh, "Mixed symmetries of Sn : immanants in the sampling of U(d) submatrices", Journal of Physics: Conference Series 3152 1, 012020 (2025).
[40] Joel Rajakumar and James D. Watson, "Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians", Quantum 10, 1981 (2026).
[41] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani, "On the complexity and verification of quantum random circuit sampling", Nature Physics 15 2, 159 (2019).
[42] David T. Stephen, Hendrik Poulsen Nautrup, Juani Bermejo-Vega, Jens Eisert, and Robert Raussendorf, "Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter", Quantum 3, 142 (2019).
[43] Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V. Gorshkov, Bill Fefferman, and Michael J. Gullans, "Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution", PRX Quantum 3 4, 040329 (2022).
[44] Nishad Maskara, Abhinav Deshpande, Adam Ehrenberg, Minh C. Tran, Bill Fefferman, and Alexey V. Gorshkov, "Complexity Phase Diagram for Interacting and Long-Range Bosonic Hamiltonians", Physical Review Letters 129 15, 150604 (2022).
[45] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, "Logical quantum processor based on reconfigurable atom arrays", Nature 626 7997, 58 (2024).
[46] Diego García-Martín, Paolo Braccia, and M Cerezo, "Architectures and random properties of symplectic quantum circuits", Quantum Science and Technology 11 1, 015012 (2026).
[47] Michal Oszmaniec, Adam Sawicki, and Michal Horodecki, "Epsilon-Nets, Unitary Designs, and Random Quantum Circuits", IEEE Transactions on Information Theory 68 2, 989 (2022).
[48] Supanut Thanasilp, Jirawat Tangpanitanon, Marc-Antoine Lemonde, Ninnat Dangniam, and Dimitris G. Angelakis, "Quantum supremacy and quantum phase transitions", Physical Review B 103 16, 165132 (2021).
[49] Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón, "Quantum advantage from energy measurements of many-body quantum systems", Quantum 5, 465 (2021).
[50] Bin Cheng, Fei Meng, Zhi-Jiong Zhang, and Man-Hong Yung, "Generalized cross-entropy benchmarking for random circuits with ergodicity", Chip 4 2, 100127 (2025).
[51] Keerthi Kumaran, Manas Sajjan, Sangchul Oh, and Sabre Kais, "Random projection using random quantum circuits", Physical Review Research 6 1, 013010 (2024).
[52] Alexios Christopoulos, Amos Chan, and Andrea De Luca, "Universal distributions of overlaps from generic dynamics in quantum many-body systems", Physical Review Research 7 4, 043035 (2025).
[53] Jirawat Tangpanitanon, Supanut Thanasilp, Marc-Antoine Lemonde, Ninnat Dangniam, and Dimitris G Angelakis, "Signatures of a sampling quantum advantage in driven quantum many-body systems", Quantum Science and Technology 8 2, 025019 (2023).
[54] Beatrice Magni, Markus Heinrich, Lorenzo Leone, and Xhek Turkeshi, "Anticoncentration and state design of doped real Clifford circuits and tensor networks", Physical Review A 113 6, 062446 (2026).
[55] 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).
[56] Xun Gao and Luming Duan, "Efficient classical simulation of noisy quantum computation", arXiv:1810.03176, (2018).
[57] Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani, "Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error", Physical Review Letters 120 20, 200502 (2018).
[58] Yuki Takeuchi and Tomoyuki Morimae, "Verification of Many-Qubit States", Physical Review X 8 2, 021060 (2018).
[59] Tomoyuki Morimae, "Hardness of classically sampling the one-clean-qubit model with constant total variation distance error", Physical Review A 96 4, 040302 (2017).
[60] 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).
[61] Bill Fefferman, Soumik Ghosh, and Wei Zhan, "Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits", arXiv:2407.19561, (2024).
[62] Man-Hong Yung and Xun Gao, "Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?", arXiv:1706.08913, (2017).
[63] Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh, "Complexity Classification of Conjugated Clifford Circuits", arXiv:1709.01805, (2017).
[64] Bin Cheng, Fei Meng, Zhi-Jiong Zhang, and Man-Hong Yung, "Generalized Cross-Entropy Benchmarking for Random Circuits with Ergodicity", arXiv:2502.09015, (2025).
[65] Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham, "Efficient approximate unitary t-designs from partially invertible universal sets and their application to quantum speedup", arXiv:1905.01504, (2019).
[66] Ryan L. Mann and Michael J. Bremner, "On the Complexity of Random Quantum Computations and the Jones Polynomial", arXiv:1711.00686, (2017).
[67] Martin Kliesch and Ingo Roth, "Theory of quantum system certification: a tutorial", arXiv:2010.05925, (2020).
[68] Stefano Cusumano, Gianluca Esposito, and Alioscia Hamma, "Probes of chaos over the Clifford group and approach to Haar values", arXiv:2603.29695, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 12:50:19) and SAO/NASA ADS (last updated successfully 2026-07-15 12:50:20). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.