Random quantum circuits are approximate unitary $t$-designs in depth $O\left(nt^{5+o(1)}\right)$

Jonas Haferkamp

Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, Germany

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


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$-designs. Unitary $t$-designs are probability distributions that mimic Haar randomness up to $t$th moments. In a seminal paper, Brandão, Harrow and Horodecki prove that random quantum circuits on qubits in a brickwork architecture of depth $O(n t^{10.5})$ are approximate unitary $t$-designs. In this work, we revisit this argument, which lower bounds the spectral gap of moment operators for local random quantum circuits by $\Omega(n^{-1}t^{-9.5})$. We improve this lower bound to $\Omega(n^{-1}t^{-4-o(1)})$, where the $o(1)$ term goes to $0$ as $t\to\infty$. A direct consequence of this scaling is that random quantum circuits generate approximate unitary $t$-designs in depth $O(nt^{5+o(1)})$. 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.

► BibTeX data

► References

[1] 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–342, 2011. doi:10.1364/​QIM.2014.QTh1A.2.

[2] S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. doi:10.1103/​PhysRevA.70.052328.

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

[4] 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 ’09, page 417, 2009. doi:10.1145/​1536414.1536472.

[5] 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–30, 1998. doi:10.1145/​276698.276708.

[6] 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–140, June 2007. doi:10.1109/​CCC.2007.26.

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

[8] J. Bourgain and A. Gamburd. A spectral gap theorem in su $(d) $. Journal of the European Mathematical Society, 14(5):1455–1511, 2012. doi:10.4171/​JEMS/​337.

[9] F. G. S. L. Brandão, 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.

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

[11] Fernando GSL Brandão, 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.

[12] S. Bravyi and D. Maslov. Hadamard-free circuits expose the structure of the Clifford group. IEEE Transactions on Information Theory, 67(7):4546–4563, 2021. doi:10.1109/​TIT.2021.3081415.

[13] A. R. Brown and L. Susskind. Second law of quantum complexity. Phys. Rev., D97:086015, 2018. doi:10.1103/​PhysRevD.97.086015.

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

[15] I. Chatzigeorgiou. Bounds on the Lambert function and their application to the outage analysis of user cooperation. IEEE Communications Letters, 17(8):1505–1508, 2013. doi:10.1109/​LCOMM.2013.070113.130972.

[16] R. Cleve, D. Leung, L. Liu, and C. Wang. Near-linear constructions of exact unitary 2-designs. Quant. Inf. Comp., 16:0721–0756, 2015. doi:10.26421/​QIC16.9-10-1.

[17] C. Dankert. Efficient simulation of random quantum states and operators, 2005. doi:10.48550/​arXiv.quant-ph/​0512217.

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

[19] P. Diaconis and L. Saloff-Coste. Comparison techniques for random walk on finite groups. The Annals of Probability, pages 2131–2156, 1993. doi:10.1214/​aoap/​1177005359.

[20] D. P DiVincenzo, D. W. Leung, and B. M. Terhal. Quantum data hiding. IEEE, Trans. Inf Theory, 48:3580–599, 2002. doi:10.48550/​arXiv.quant-ph/​0103098.

[21] J. Emerson, R. Alicki, and K. Życzkowski. 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.

[22] J. Gao. Quantum union bounds for sequential projective measurements. Phys. Rev. A, 92:052331, 2015. arXiv:1410.5688, doi:10.1103/​PhysRevA.92.052331.

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

[24] D. Gross, S. Nezami, and M. Walter. Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations. Communications in Mathematical Physics, 385(3):1325–1393, 2021. doi:10.1007/​s00220-021-04118-7.

[25] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, and N. Yunger Halpern. Linear growth of quantum circuit complexity. Nature Physics, 18:528–532, 2021. doi:10.1038/​s41567-022-01539-6.

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

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

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

[29] A. W. Harrow and R. A. Low. Random quantum circuits are approximate 2-designs. Communications in Mathematical Physics, 291(1):257–302, 2009. doi:10.1007/​s00220-009-0873-6.

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

[31] N. Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits. 2019. arXiv:1905.12053.

[32] T. Jiang. How many entries of a typical orthogonal matrix can be approximated by independent normals? The Annals of Probability, 34(4):1497–1529, 2006. doi:10.1214/​009117906000000205.

[33] E. Knill. Approximation by quantum circuits. arXiv preprint, 1995. doi:10.48550/​arXiv.quant-ph/​9508006.

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

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

[36] R. A. Low. Pseudo-randomness and Learning in Quantum Computation. arXiv preprint, 2010. PhD Thesis, 2010. doi:10.48550/​arXiv.1006.5227.

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

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

[39] 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–223, 2021. doi:10.1090/​ert/​563.

[40] F. Montealegre-Mora and D. Gross. Duality theory for Clifford tensor powers. arXiv preprint, 2022. doi:10.48550/​arXiv.2208.01688.

[41] B. Nachtergaele. The spectral gap for some spin chains with discrete symmetry breaking. Commun. Math. Phys., 175:565, 1996. doi:10.1007/​BF02099509.

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

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

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

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

[46] 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–947, 2017. doi:10.1007/​s00220-017-2950-6.

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

[48] L. Susskind. Black Holes and Complexity Classes. arXiv preprint, 2018. doi:10.48550/​arXiv.1802.02175.

[49] P. P. Varjú. Random walks in compact groups. Doc. Math., 18:1137–1175, 2013. doi:10.48550/​arXiv.1209.1745.

[50] J. Watrous. The theory of quantum information. Cambridge university press, 2018. doi:10.1017/​9781316848142.

[51] Z. Webb. The Clifford group forms a unitary 3-design. Quantum Info. Comput., 16:1379, 2016. doi:10.5555/​3179439.3179447.

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

[53] H. Zhu. Multiqubit clifford groups are unitary 3-designs. Phys. Rev. A, 96:062336, 2017. doi:10.1103/​PhysRevA.96.062336.

Cited by

[1] Valentin Heyraud, Zejian Li, Kaelan Donatella, Alexandre Le Boité, and Cristiano Ciuti, "Efficient Estimation of Trainability for Variational Quantum Circuits", PRX Quantum 4 4, 040335 (2023).

[2] Shao-Kai Jian, Gregory Bentsen, and Brian Swingle, "Linear growth of circuit complexity from Brownian dynamics", Journal of High Energy Physics 2023 8, 190 (2023).

[3] Xhek Turkeshi, Marco Schirò, and Piotr Sierant, "Measuring nonstabilizerness via multifractal flatness", Physical Review A 108 4, 042408 (2023).

[4] Eric R. Anschuetz and Bobak T. Kiani, "Quantum variational algorithms are swamped with traps", Nature Communications 13 1, 7760 (2022).

[5] Antonio A. Mele, Glen B. Mbeng, Giuseppe E. Santoro, Mario Collura, and Pietro Torta, "Avoiding barren plateaus via transferability of smooth solutions in a Hamiltonian variational ansatz", Physical Review A 106 6, L060401 (2022).

[6] Tobias Haug and Lorenzo Piroli, "Quantifying nonstabilizerness of matrix product states", Physical Review B 107 3, 035148 (2023).

[7] Klée Pollock, Peter P. Orth, and Thomas Iadecola, "Variational microcanonical estimator", Physical Review Research 5 3, 033224 (2023).

[8] Filipa C R Peres, Rafael Wagner, and Ernesto F Galvão, "Non-stabilizerness and entanglement from cat-state injection", New Journal of Physics 26 1, 013051 (2024).

[9] Scott Aaronson and Shih-Han Hung, Proceedings of the 55th Annual ACM Symposium on Theory of Computing 933 (2023) ISBN:9781450399135.

[10] Keerthi Kumaran, Manas Sajjan, Sangchul Oh, and Sabre Kais, "Random projection using random quantum circuits", Physical Review Research 6 1, 013010 (2024).

[11] Ryan O’Donnell, Rocco A. Servedio, and Pedro Paredes, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 1240 (2023) ISBN:979-8-3503-1894-4.

[12] Piotr Dulian and Adam Sawicki, "A Random Matrix Model for Random Approximate t-Designs", IEEE Transactions on Information Theory 70 4, 2637 (2024).

[13] Jeongwan Haah, Robin Kothari, Ryan O’Donnell, and Ewin Tang, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 363 (2023) ISBN:979-8-3503-1894-4.

[14] Yanglin Hu and Marco Tomamichel, "Fundamental limits on quantum cloning from the no-signaling principle", Physical Review A 109 2, 022221 (2024).

[15] M. Bilkis, M. Cerezo, Guillaume Verdon, Patrick J. Coles, and Lukasz Cincio, "A semi-agnostic ansatz with variable structure for variational quantum algorithms", Quantum Machine Intelligence 5 2, 43 (2023).

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

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

[18] Michał Oszmaniec, Marcin Kotowski, Michał Horodecki, and Nicholas Hunter-Jones, "Saturation and recurrence of quantum complexity in random local quantum dynamics", arXiv:2205.09734, (2022).

[19] Antonio Anna Mele, "Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial", arXiv:2307.08956, (2023).

[20] Tobias Haug and M. S. Kim, "Scalable Measures of Magic Resource for Quantum Computers", PRX Quantum 4 1, 010301 (2023).

[21] Markus Heinrich, Martin Kliesch, and Ingo Roth, "Randomized benchmarking with random quantum circuits", arXiv:2212.06181, (2022).

[22] Jeongwan Haah, Yunchao Liu, and Xinyu Tan, "Efficient approximate unitary designs from random Pauli rotations", arXiv:2402.05239, (2024).

[23] Scott Aaronson and Shih-Han Hung, "Certified Randomness from Quantum Supremacy", arXiv:2303.01625, (2023).

[24] Shivan Mittal and Nicholas Hunter-Jones, "Local random quantum circuits form approximate designs on arbitrary architectures", arXiv:2310.19355, (2023).

[25] Saeed Mehraban and Mehrdad Tahmasbi, "Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach", arXiv:2305.10277, (2023).

[26] Quynh T. Nguyen, "The mixed Schur transform: efficient quantum circuit and applications", arXiv:2310.01613, (2023).

[27] Diego García-Martín, Martin Larocca, and M. Cerezo, "Deep quantum neural networks form Gaussian processes", arXiv:2305.09957, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-15 08:21:19) and SAO/NASA ADS (last updated successfully 2024-04-15 08:21:20). The list may be incomplete as not all publishers provide suitable and complete citation data.