Dahlemi komplekssete kvantsüsteemide keskus, Freie Universität Berlin, Saksamaa
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
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 $ttoinfty$. 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-i andmed
► Viited
[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.
https://doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https://doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/10.48550/arXiv.quant-ph/0512217
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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/10.48550/arXiv.quant-ph/0103098
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.
https://doi.org/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.
https:///doi.org/10.1103/PhysRevA.92.052331
arXiv: 1410.5688
[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.
https:///doi.org/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.
https://doi.org/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.
https://doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/10.48550/arXiv.1809.06957
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.
https://doi.org/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.
https://doi.org/10.1088/1126-6708/2007/09/120
[31] N. Hunter-Jones. Unitary designs from statistical mechanics in random quantum circuits. 2019. arXiv:1905.12053.
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.
https:///doi.org/10.1214/009117906000000205
[33] E. Knill. Approximation by quantum circuits. arXiv preprint, 1995. doi:10.48550/arXiv.quant-ph/9508006.
https:///doi.org/10.48550/arXiv.quant-ph/9508006
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.
https:///doi.org/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.
https://doi.org/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.
https:///doi.org/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.
https:///doi.org/10.1103/PhysRevA.85.042311
arXiv: 1109.6887
[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.
https:///doi.org/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.
https://doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https:///doi.org/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.
https://doi.org/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.
https:///doi.org/10.1109/TIT.2021.3128110
[48] L. Susskind. Black Holes and Complexity Classes. arXiv preprint, 2018. doi:10.48550/arXiv.1802.02175.
https:///doi.org/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.
https:///doi.org/10.48550/arXiv.1209.1745
[50] J. Watrous. The theory of quantum information. Cambridge university press, 2018. doi:10.1017/9781316848142.
https:///doi.org/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.
https:///doi.org/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.
arXiv: 1906.01079v1
[53] H. Zhu. Multiqubit clifford groups are unitary 3-designs. Phys. Rev. A, 96:062336, 2017. doi:10.1103/PhysRevA.96.062336.
https:///doi.org/10.1103/PhysRevA.96.062336
Viidatud
[1] Tobias Haug ja Lorenzo Piroli, "Matrixi toote olekute ebastabiilsuse kvantifitseerimine", arXiv: 2207.13076.
[2] Matthias C. Caro, Hsin-Yuan Huang, Nicholas Ezzell, Joe Gibbs, Andrew T. Sornborger, Lukasz Cincio, Patrick J. Coles ja Zoë Holmes, "Out-of-distribution generalization for learning quantum dynamics" arXiv: 2204.10268.
[3] Michał Oszmaniec, Michał Horodecki ja Nicholas Hunter-Jones, "Kvantkeerukuse küllastumine ja kordumine juhuslikes kvantahelates", arXiv: 2205.09734.
[4] Antonio Anna Mele, Glen Bigan Mbeng, Giuseppe Ernesto Santoro, Mario Collura ja Pietro Torta, „Avoiding barren platood via transferability of sile solutions in Hamiltonian Variational Ansatz”, arXiv: 2206.01982.
Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-09-11 01:16:57). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.
On Crossrefi viidatud teenus teoste viitamise andmeid ei leitud (viimane katse 2022-09-11 01:16:55).
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
