{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T05:18:56Z","timestamp":1780636736497,"version":"3.54.1"},"reference-count":53,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T00:00:00Z","timestamp":1662595200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The applications of random quantum circuits range from quantum computing and quantum many-body systems to the physics of black holes. Many of these applications are related to the generation of quantum pseudorandomness: Random quantum circuits are known to approximate unitary t<\/mml:mi><\/mml:math>-designs. Unitary t<\/mml:mi><\/mml:math>-designs are probability distributions that mimic Haar randomness up to t<\/mml:mi><\/mml:math>th moments. In a seminal paper, Brand\u00e3o, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>t<\/mml:mi>10.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math> are approximate unitary t<\/mml:mi><\/mml:math>-designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by &#x03A9;<\/mml:mi>(<\/mml:mo>n<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>t<\/mml:mi>&#x2212;<\/mml:mo>9.5<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>. We improve this lower bound to &#x03A9;<\/mml:mi>(<\/mml:mo>n<\/mml:mi>&#x2212;<\/mml:mo>1<\/mml:mn><\/mml:mrow><\/mml:msup>t<\/mml:mi>&#x2212;<\/mml:mo>4<\/mml:mn>&#x2212;<\/mml:mo>o<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>, where the o<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:math> term goes to 0<\/mml:mn><\/mml:math> as t<\/mml:mi>&#x2192;<\/mml:mo>&#x221E;<\/mml:mi><\/mml:math>. A direct consequence of this scaling is that random quantum circuits generate approximate unitary t<\/mml:mi><\/mml:math>-designs in depth O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>t<\/mml:mi>5<\/mml:mn>+<\/mml:mo>o<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>. Our techniques involve Gao's quantum union bound and the unreasonable effectiveness of the Clifford group. As an auxiliary result, we prove fast convergence to the Haar measure for random Clifford unitaries interleaved with Haar random single qubit unitaries.<\/jats:p>","DOI":"10.22331\/q-2022-09-08-795","type":"journal-article","created":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T13:10:30Z","timestamp":1662642630000},"page":"795","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":73,"title":["Random quantum circuits are approximate unitary t<\/mml:mi><\/mml:math>-designs in depth O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>t<\/mml:mi>5<\/mml:mn>+<\/mml:mo>o<\/mml:mi>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:math>"],"prefix":"10.22331","volume":"6","author":[{"given":"Jonas","family":"Haferkamp","sequence":"first","affiliation":[{"name":"Dahlem Center for Complex Quantum Systems, Freie Universit\u00e4t Berlin, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,9,8]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"S. Aaronson and A. Arkhipov. The computational complexity of linear optics. Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333\u2013342, 2011. doi:10.1364\/QIM.2014.QTh1A.2.","DOI":"10.1364\/QIM.2014.QTh1A.2"},{"key":"1","doi-asserted-by":"publisher","unstructured":"S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. doi:10.1103\/PhysRevA.70.052328.","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"2","doi-asserted-by":"publisher","unstructured":"A. Abeyesinghe, I. Devetak, P. Hayden, and A. Winter. The mother of all protocols: restructuring quantum information's family tree. Proc. R. Soc. A, 465:2537, 2009. doi:10.1098\/rspa.2009.0202.","DOI":"10.1098\/rspa.2009.0202"},{"key":"3","doi-asserted-by":"publisher","unstructured":"D. Aharonov, I. Arad, Z. Landau, and U. Vazirani. The Detectability Lemma and Quantum Gap Amplification. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC \u201909, page 417, 2009. doi:10.1145\/1536414.1536472.","DOI":"10.1145\/1536414.1536472"},{"key":"4","doi-asserted-by":"publisher","unstructured":"D. Aharonov, A. Kitaev, and N. Nisan. Quantum circuits with mixed states. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 20\u201330, 1998. doi:10.1145\/276698.276708.","DOI":"10.1145\/276698.276708"},{"key":"5","doi-asserted-by":"publisher","unstructured":"A. Ambainis and J. Emerson. Quantum t-designs: t-wise independence in the quantum world. In Computational Complexity, 2007. CCC '07. Twenty-Second Annual IEEE Conference on, pages 129\u2013140, June 2007. doi:10.1109\/CCC.2007.26.","DOI":"10.1109\/CCC.2007.26"},{"key":"6","doi-asserted-by":"publisher","unstructured":"A. Anshu, I. Arad, and T. Vidick. Simple proof of the detectability lemma and spectral gap amplification. Phys. Rev. B, 93:205142, 2016. doi:10.1103\/PhysRevB.93.205142.","DOI":"10.1103\/PhysRevB.93.205142"},{"key":"7","doi-asserted-by":"publisher","unstructured":"J. Bourgain and A. Gamburd. A spectral gap theorem in su $(d) $. Journal of the European Mathematical Society, 14(5):1455\u20131511, 2012. doi:10.4171\/JEMS\/337.","DOI":"10.4171\/JEMS\/337"},{"key":"8","doi-asserted-by":"publisher","unstructured":"F. G. S. L. Brand\u00e3o, A. W. Harrow, and M. Horodecki. Local Random Quantum Circuits are Approximate Polynomial-Designs. Commun. Math. Phys., 346:397, 2016. doi:10.1007\/s00220-016-2706-8.","DOI":"10.1007\/s00220-016-2706-8"},{"key":"9","doi-asserted-by":"publisher","unstructured":"F. G. S. L. Brandao, A. W. Harrow, and M. Horodecki. Efficient quantum pseudorandomness. Physical review letters, 116(17):170502, 2016. doi:10.1103\/PhysRevLett.116.170502.","DOI":"10.1103\/PhysRevLett.116.170502"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brand\u00e3o, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill. Models of quantum complexity growth. PRX Quantum, 2(3):030316, 2021. doi:10.1103\/PRXQuantum.2.030316.","DOI":"10.1103\/PRXQuantum.2.030316"},{"key":"11","doi-asserted-by":"publisher","unstructured":"S. Bravyi and D. Maslov. Hadamard-free circuits expose the structure of the Clifford group. IEEE Transactions on Information Theory, 67(7):4546\u20134563, 2021. doi:10.1109\/TIT.2021.3081415.","DOI":"10.1109\/TIT.2021.3081415"},{"key":"12","doi-asserted-by":"publisher","unstructured":"A. R. Brown and L. Susskind. Second law of quantum complexity. Phys. Rev., D97:086015, 2018. doi:10.1103\/PhysRevD.97.086015.","DOI":"10.1103\/PhysRevD.97.086015"},{"key":"13","doi-asserted-by":"publisher","unstructured":"R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in Markov chains. In Proceedings 38th Annual Symposium on Foundations of Computer Science, page 223, 1997. doi:10.1109\/SFCS.1997.646111.","DOI":"10.1109\/SFCS.1997.646111"},{"key":"14","doi-asserted-by":"publisher","unstructured":"I. Chatzigeorgiou. Bounds on the Lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 17(8):1505\u20131508, 2013. doi:10.1109\/LCOMM.2013.070113.130972.","DOI":"10.1109\/LCOMM.2013.070113.130972"},{"key":"15","doi-asserted-by":"publisher","unstructured":"R. Cleve, D. Leung, L. Liu, and C. Wang. Near-linear constructions of exact unitary 2-designs. Quant. Inf. Comp., 16:0721\u20130756, 2015. doi:10.26421\/QIC16.9-10-1.","DOI":"10.26421\/QIC16.9-10-1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"C. Dankert. Efficient simulation of random quantum states and operators, 2005. doi:10.48550\/arXiv.quant-ph\/0512217.","DOI":"10.48550\/arXiv.quant-ph\/0512217"},{"key":"17","doi-asserted-by":"publisher","unstructured":"C. Dankert, R. Cleve, J. Emerson, and E. Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Phys. Rev., A80:012304, 2009. doi:10.1103\/PhysRevA.80.012304.","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"18","doi-asserted-by":"publisher","unstructured":"P. Diaconis and L. Saloff-Coste. Comparison techniques for random walk on finite groups. The Annals of Probability, pages 2131\u20132156, 1993. doi:10.1214\/aoap\/1177005359.","DOI":"10.1214\/aoap\/1177005359"},{"key":"19","doi-asserted-by":"publisher","unstructured":"D. P DiVincenzo, D. W. Leung, and B. M. Terhal. Quantum data hiding. IEEE, Trans. Inf Theory, 48:3580\u2013599, 2002. doi:10.48550\/arXiv.quant-ph\/0103098.","DOI":"10.48550\/arXiv.quant-ph\/0103098"},{"key":"20","doi-asserted-by":"publisher","unstructured":"J. Emerson, R. Alicki, and K. \u017byczkowski. Scalable noise estimation with random unitary operators. J. Opt. B: Quantum Semiclass. Opt., 7(10):S347, 2005. doi:10.1088\/1464-4266\/7\/10\/021.","DOI":"10.1088\/1464-4266\/7\/10\/021"},{"key":"21","doi-asserted-by":"publisher","unstructured":"J. Gao. Quantum union bounds for sequential projective measurements. Phys. Rev. A, 92:052331, 2015. arXiv:1410.5688, doi:10.1103\/PhysRevA.92.052331.","DOI":"10.1103\/PhysRevA.92.052331"},{"key":"22","doi-asserted-by":"publisher","unstructured":"D. Gross, K. Audenaert, and J. Eisert. Evenly distributed unitaries: On the structure of unitary designs. J. Math. Phys., 48:052104, 2007. doi:10.1063\/1.2716992.","DOI":"10.1063\/1.2716992"},{"key":"23","doi-asserted-by":"publisher","unstructured":"D. Gross, S. Nezami, and M. Walter. Schur\u2013Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations. Communications in Mathematical Physics, 385(3):1325\u20131393, 2021. doi:10.1007\/s00220-021-04118-7.","DOI":"10.1007\/s00220-021-04118-7"},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern. Linear growth of quantum circuit complexity. Nature Physics, 18:528\u2013532, 2021. doi:10.1038\/s41567-022-01539-6.","DOI":"10.1038\/s41567-022-01539-6"},{"key":"25","doi-asserted-by":"publisher","unstructured":"J. Haferkamp and N. Hunter-Jones. Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions. Physical Review A, 104(2):022417, 2021. doi:10.1103\/PhysRevA.104.022417.","DOI":"10.1103\/PhysRevA.104.022417"},{"key":"26","doi-asserted-by":"publisher","unstructured":"J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth. Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates. 2020. doi:10.48550\/arXiv.2002.09524.","DOI":"10.48550\/arXiv.2002.09524"},{"key":"27","doi-asserted-by":"publisher","unstructured":"A. Harrow and S. Mehraban. Approximate unitary $ t $-designs by short random quantum circuits using nearest-neighbor and long-range gates. arXiv preprint arXiv:1809.06957, 2018. doi:10.48550\/arXiv.1809.06957.","DOI":"10.48550\/arXiv.1809.06957"},{"key":"28","doi-asserted-by":"publisher","unstructured":"A. W. Harrow and R. A. Low. Random quantum circuits are approximate 2-designs. Communications in Mathematical Physics, 291(1):257\u2013302, 2009. doi:10.1007\/s00220-009-0873-6.","DOI":"10.1007\/s00220-009-0873-6"},{"key":"29","doi-asserted-by":"publisher","unstructured":"P. Hayden and J. Preskill. Black holes as mirrors: Quantum information in random subsystems. JHEP, 09:120, 2007. doi:10.1088\/1126-6708\/2007\/09\/120.","DOI":"10.1088\/1126-6708\/2007\/09\/120"},{"key":"30","unstructured":"N. Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits. 2019. arXiv:1905.12053."},{"key":"31","doi-asserted-by":"publisher","unstructured":"T. Jiang. How many entries of a typical orthogonal matrix can be approximated by independent normals? The Annals of Probability, 34(4):1497\u20131529, 2006. doi:10.1214\/009117906000000205.","DOI":"10.1214\/009117906000000205"},{"key":"32","doi-asserted-by":"publisher","unstructured":"E. Knill. Approximation by quantum circuits. arXiv preprint, 1995. doi:10.48550\/arXiv.quant-ph\/9508006.","DOI":"10.48550\/arXiv.quant-ph\/9508006"},{"key":"33","doi-asserted-by":"publisher","unstructured":"E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland. Randomized benchmarking of quantum gates. Phys. Rev. A, 77:012307, 2008. doi:10.1103\/PhysRevA.77.012307.","DOI":"10.1103\/PhysRevA.77.012307"},{"key":"34","doi-asserted-by":"publisher","unstructured":"L. Leone, S. F. E. Oliviero, Y. Zhou, and A. Hamma. Quantum chaos is quantum. Quantum, 5:453, 2021. doi:10.22331\/q-2021-05-04-453.","DOI":"10.22331\/q-2021-05-04-453"},{"key":"35","doi-asserted-by":"publisher","unstructured":"R. A. Low. Pseudo-randomness and Learning in Quantum Computation. arXiv preprint, 2010. PhD Thesis, 2010. doi:10.48550\/arXiv.1006.5227.","DOI":"10.48550\/arXiv.1006.5227"},{"key":"36","doi-asserted-by":"publisher","unstructured":"E. Magesan, J. M. Gambetta, and J. Emerson. Characterizing quantum gates via randomized benchmarking. Phys. Rev. A, 85:042311, 2012. arXiv:1109.6887, doi:10.1103\/PhysRevA.85.042311.","DOI":"10.1103\/PhysRevA.85.042311"},{"key":"37","doi-asserted-by":"publisher","unstructured":"R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham. Efficient quantum pseudorandomness with simple graph states. Physical Review A, 97(2):022333, 2018. doi:10.1103\/PhysRevA.97.022333.","DOI":"10.1103\/PhysRevA.97.022333"},{"key":"38","doi-asserted-by":"publisher","unstructured":"F. Montealegre-Mora and D. Gross. Rank-deficient representations in the theta correspondence over finite fields arise from quantum codes. Representation Theory of the American Mathematical Society, 25(8):193\u2013223, 2021. doi:10.1090\/ert\/563.","DOI":"10.1090\/ert\/563"},{"key":"39","doi-asserted-by":"publisher","unstructured":"F. Montealegre-Mora and D. Gross. Duality theory for Clifford tensor powers. arXiv preprint, 2022. doi:10.48550\/arXiv.2208.01688.","DOI":"10.48550\/arXiv.2208.01688"},{"key":"40","doi-asserted-by":"publisher","unstructured":"B. Nachtergaele. The spectral gap for some spin chains with discrete symmetry breaking. Commun. Math. Phys., 175:565, 1996. doi:10.1007\/BF02099509.","DOI":"10.1007\/BF02099509"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Y. Nakata, C. Hirche, M. Koashi, and A. Winter. Efficient quantum pseudorandomness with nearly time-independent hamiltonian dynamics. Physical Review X, 7(2):021006, 2017. doi:10.1103\/PhysRevX.7.021006.","DOI":"10.1103\/PhysRevX.7.021006"},{"key":"42","doi-asserted-by":"publisher","unstructured":"G. Nebe, E. M. Rains, and N. J. A Sloane. The invariants of the Clifford groups. arXiv preprint, 2001. doi:10.48550\/arXiv.math\/0001038.","DOI":"10.48550\/arXiv.math\/0001038"},{"key":"43","doi-asserted-by":"publisher","unstructured":"R. I. Oliveira. On the convergence to equilibrium of Kac's random walk on matrices. Ann. Appl. Probab., 19:1200, 2009. doi:10.1214\/08-AAP550.","DOI":"10.1214\/08-AAP550"},{"key":"44","doi-asserted-by":"publisher","unstructured":"S. F. E. Oliviero, L. Leone, and A. Hamma. Transitions in entanglement complexity in random quantum circuits by measurements. Physics Letters A, 418:127721, 2021. doi:10.1016\/j.physleta.2021.127721.","DOI":"10.1016\/j.physleta.2021.127721"},{"key":"45","doi-asserted-by":"publisher","unstructured":"E. Onorati, O. Buerschaper, M. Kliesch, W. Brown, A. H. Werner, and J. Eisert. Mixing properties of stochastic quantum Hamiltonians. Communications in Mathematical Physics, 355(3):905\u2013947, 2017. doi:10.1007\/s00220-017-2950-6.","DOI":"10.1007\/s00220-017-2950-6"},{"key":"46","doi-asserted-by":"publisher","unstructured":"M. Oszmaniec, A. Sawicki, and M. Horodecki. Epsilon-nets, unitary designs and random quantum circuits. IEEE Transactions on Information Theory, 2021. doi:10.1109\/TIT.2021.3128110.","DOI":"10.1109\/TIT.2021.3128110"},{"key":"47","doi-asserted-by":"publisher","unstructured":"L. Susskind. Black Holes and Complexity Classes. arXiv preprint, 2018. doi:10.48550\/arXiv.1802.02175.","DOI":"10.48550\/arXiv.1802.02175"},{"key":"48","doi-asserted-by":"publisher","unstructured":"P. P. Varj\u00fa. Random walks in compact groups. Doc. Math., 18:1137\u20131175, 2013. doi:10.48550\/arXiv.1209.1745.","DOI":"10.48550\/arXiv.1209.1745"},{"key":"49","doi-asserted-by":"publisher","unstructured":"J. Watrous. The theory of quantum information. Cambridge university press, 2018. doi:10.1017\/9781316848142.","DOI":"10.1017\/9781316848142"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Z. Webb. The Clifford group forms a unitary 3-design. Quantum Info. Comput., 16:1379, 2016. doi:10.5555\/3179439.3179447.","DOI":"10.5555\/3179439.3179447"},{"key":"51","doi-asserted-by":"crossref","unstructured":"S. Zhou, Z. Yang, A. Hamma, and C. Chamon. Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics. SciPost Physics, 9(6):087, 2020.","DOI":"10.21468\/SciPostPhys.9.6.087"},{"key":"52","doi-asserted-by":"publisher","unstructured":"H. Zhu. Multiqubit clifford groups are unitary 3-designs. Phys. Rev. A, 96:062336, 2017. doi:10.1103\/PhysRevA.96.062336.","DOI":"10.1103\/PhysRevA.96.062336"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-08-795\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T13:10:40Z","timestamp":1662642640000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-08-795\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,8]]},"references-count":53,"URL":"https:\/\/doi.org\/10.22331\/q-2022-09-08-795","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,8]]},"article-number":"795"}}