{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,7]],"date-time":"2026-01-07T07:58:46Z","timestamp":1767772726097},"reference-count":45,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T00:00:00Z","timestamp":1681948800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Centre, Poland","award":["UMO-2020\/37\/B\/ST2\/02478"],"award-info":[{"award-number":["UMO-2020\/37\/B\/ST2\/02478"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"For a random set S<\/mml:mi><\/mml:mrow>&#x2282;<\/mml:mo>U<\/mml:mi>(<\/mml:mo>d<\/mml:mi>)<\/mml:mo><\/mml:math> of quantum gates we provide bounds on the probability that S<\/mml:mi><\/mml:mrow><\/mml:math> forms a &#x03B4;<\/mml:mi><\/mml:math>-approximate t<\/mml:mi><\/mml:math>-design. In particular we have found that for S<\/mml:mi><\/mml:mrow><\/mml:math> drawn from an exact t<\/mml:mi><\/mml:math>-design the probability that it forms a &#x03B4;<\/mml:mi><\/mml:math>-approximate t<\/mml:mi><\/mml:math>-design satisfies the inequality P<\/mml:mi><\/mml:mrow>(<\/mml:mo>&#x03B4;<\/mml:mi>&#x2265;<\/mml:mo>x<\/mml:mi><\/mml:mrow>)<\/mml:mo><\/mml:mrow>&#x2264;<\/mml:mo>2<\/mml:mn>D<\/mml:mi>t<\/mml:mi><\/mml:msub>e<\/mml:mi>&#x2212;<\/mml:mo>|<\/mml:mo><\/mml:mrow>S<\/mml:mi><\/mml:mrow>|<\/mml:mo><\/mml:mrow>x<\/mml:mi>a<\/mml:mi>r<\/mml:mi>c<\/mml:mi>t<\/mml:mi>a<\/mml:mi>n<\/mml:mi>h<\/mml:mi><\/mml:mrow>(<\/mml:mo>x<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup>(<\/mml:mo>1<\/mml:mn>&#x2212;<\/mml:mo>x<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo>|<\/mml:mo><\/mml:mrow>S<\/mml:mi><\/mml:mrow>|<\/mml:mo><\/mml:mrow>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:mfrac>=<\/mml:mo>O<\/mml:mi>(<\/mml:mo>2<\/mml:mn>D<\/mml:mi>t<\/mml:mi><\/mml:msub>(<\/mml:mo>e<\/mml:mi>&#x2212;<\/mml:mo>x<\/mml:mi>2<\/mml:mn><\/mml:msup><\/mml:mrow><\/mml:msup>1<\/mml:mn>&#x2212;<\/mml:mo>x<\/mml:mi>2<\/mml:mn><\/mml:msup><\/mml:msqrt><\/mml:mfrac>)<\/mml:mo><\/mml:mrow>|<\/mml:mo><\/mml:mrow>S<\/mml:mi><\/mml:mrow>|<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:msup><\/mml:mrow>)<\/mml:mo><\/mml:mrow><\/mml:math>, where D<\/mml:mi>t<\/mml:mi><\/mml:msub><\/mml:math> is a sum over dimensions of unique irreducible representations appearing in the decomposition of U<\/mml:mi>&#x21A6;<\/mml:mo>U<\/mml:mi>&#x2297;<\/mml:mo>t<\/mml:mi><\/mml:mrow><\/mml:msup>&#x2297;<\/mml:mo>U<\/mml:mi>&#x00AF;<\/mml:mo><\/mml:mover><\/mml:mrow>&#x2297;<\/mml:mo>t<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math>. We use our results to show that to obtain a &#x03B4;<\/mml:mi><\/mml:math>-approximate t<\/mml:mi><\/mml:math>-design with probability P<\/mml:mi><\/mml:math> one needs O<\/mml:mi>(<\/mml:mo>&#x03B4;<\/mml:mi>&#x2212;<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:msup>(<\/mml:mo>t<\/mml:mi>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>d<\/mml:mi>)<\/mml:mo>&#x2212;<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>&#x2212;<\/mml:mo>P<\/mml:mi>)<\/mml:mo>)<\/mml:mo>)<\/mml:mo><\/mml:math> many random gates. We also analyze how &#x03B4;<\/mml:mi><\/mml:math> concentrates around its expected value E<\/mml:mi><\/mml:mrow>&#x03B4;<\/mml:mi><\/mml:math> for random S<\/mml:mi><\/mml:mrow><\/mml:math>. Our results are valid for both symmetric and non-symmetric sets of gates.<\/jats:p>","DOI":"10.22331\/q-2023-04-20-983","type":"journal-article","created":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T12:27:02Z","timestamp":1681993622000},"page":"983","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["Matrix concentration inequalities and efficiency of random universal sets of quantum gates"],"prefix":"10.22331","volume":"7","author":[{"given":"Piotr","family":"Dulian","sequence":"first","affiliation":[{"name":"Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotnik\u00f3w 32\/46, 02-668 Warsaw, Poland"},{"name":"Faculty of Physics, University of Warsaw, Pasteura 5, 02-093 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam","family":"Sawicki","sequence":"additional","affiliation":[{"name":"Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotnik\u00f3w 32\/46, 02-668 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2023,4,20]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, ``Surface codes: Towards practical large-scale quantum computation'' Phys. Rev. A 86, 032324 (2012).","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"1","doi-asserted-by":"publisher","unstructured":"J. Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"2","doi-asserted-by":"publisher","unstructured":"S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, ``Characterizing Quantum Supremacy in Near-Term Devices'' Nature Physics 14, 595\u2013600 (2018).","DOI":"10.1038\/s41567-018-0124-x"},{"key":"3","doi-asserted-by":"publisher","unstructured":"A. W. Harrowand A. Montanaro ``Quantum Computational Supremacy'' Nature 549, 203\u2013209 (2017).","DOI":"10.1038\/nature23458"},{"key":"4","doi-asserted-by":"publisher","unstructured":"C. J. Ballance, T. P. Harty, N. M. Linke, M. A. Sepiol, and D. M. Lucas, ``High-fidelity quantum logic gates using trapped-ion hyperfine qubits'' Phys. Rev. Lett. 117, 060504 (2016).","DOI":"10.1103\/PhysRevLett.117.060504"},{"key":"5","doi-asserted-by":"publisher","unstructured":"R. Barends, J. Kelly, A. Megrant, A. Veitia, D. Sank, E. Jeffrey, T. C. White, J. Mutus, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, C. Neill, P. O`Malley, P. Roushan, A. Vainsencher, J. Wenner, A. N. Korotkov, A. N. Cleland, and John M. Martinis, ``Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing'' Nature 508, 500\u2013503 (2014).","DOI":"10.1038\/nature13171"},{"key":"6","doi-asserted-by":"publisher","unstructured":"L. Susskind ``Three Lectures on Complexity and Black Holes'' Springer Cham (2020).","DOI":"10.1007\/978-3-030-45109-7"},{"key":"7","doi-asserted-by":"publisher","unstructured":"A. Sawickiand K. Karnas ``Criteria for universality of quantum gates'' Physical Review A 95, 062303 (2017).","DOI":"10.1103\/physreva.95.062303"},{"key":"8","doi-asserted-by":"publisher","unstructured":"A. Sawickiand K. Karnas ``Universality of Single-Qudit Gates'' Annales Henri Poincar\u00c3\u00a9 18, 3515\u00e2\u0080\u00933552 (2017).","DOI":"10.1007\/s00023-017-0604-z"},{"key":"9","doi-asserted-by":"publisher","unstructured":"A. Sawicki, L. Mattioli, and Z. Zimbor\u00e1s, ``Universality verification for a set of quantum gates'' Phys. Rev. A 105, 052602 (2022).","DOI":"10.1103\/PhysRevA.105.052602"},{"key":"10","doi-asserted-by":"publisher","unstructured":"M. A. Nielsenand I. L. Chuang ``Quantum Computation and Quantum Information: 10th Anniversary Edition'' Cambridge University Press (2010).","DOI":"10.1017\/CBO9780511976667"},{"key":"11","doi-asserted-by":"publisher","unstructured":"P. P. Varj\u00fa ``Random walks in compact groups'' Doc. Math. 18, 1137\u20131175 (2013).","DOI":"10.4171\/DM\/423"},{"key":"12","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 68, 989\u20131015 (2022).","DOI":"10.1109\/TIT.2021.3128110"},{"key":"13","doi-asserted-by":"publisher","unstructured":"A. Boulandand T. Giurgica-Tiron ``Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm'' arXiv e-prints (2021).","DOI":"10.48550\/ARXIV.2112.02040"},{"key":"14","doi-asserted-by":"publisher","unstructured":"A. W. Harrow, B. Recht, and Isaac L. Chuang, ``Efficient Discrete Approximations of Quantum Gates'' J. Math. Phys. 43, 4445 (2002).","DOI":"10.1063\/1.1495899"},{"key":"15","doi-asserted-by":"publisher","unstructured":"J. M. Epstein, A. W. Cross, E. Magesan, and J. M. Gambetta, ``Investigating the limits of randomized benchmarking protocols'' Physical Review A 89, 062321 (2014).","DOI":"10.1103\/physreva.89.062321"},{"key":"16","doi-asserted-by":"publisher","unstructured":"A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. Brand\u00c3\u00a3o, ``Random quantum circuits transform local noise into global white noise'' arXiv e-prints (2021).","DOI":"10.48550\/ARXIV.2111.14907"},{"key":"17","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'' Proceedings of the Royal Society of London Series A 465, 2537\u20132563 (2009).","DOI":"10.1098\/rspa.2009.0202"},{"key":"18","doi-asserted-by":"publisher","unstructured":"J. Radhakrishnan, M. R\u00c3\u00b6tteler, and P. Sen, ``Random measurement bases, quantum state distinction and applications to the hidden subgroup problem'' Algorithmica 55, 490\u00e2\u0080\u0093516 (2009).","DOI":"10.1007\/s00453-008-9231-x"},{"key":"19","doi-asserted-by":"publisher","unstructured":"D. A. Robertsand B. Yoshida ``Chaos and complexity by design'' Journal of High Energy Physics 2017, 121 (2017).","DOI":"10.1007\/JHEP04(2017)121"},{"key":"20","doi-asserted-by":"publisher","unstructured":"M. Oszmaniec, M. Horodecki, and N. Hunter-Jones, ``Saturation and recurrence of quantum complexity in random quantum circuits'' arXiv e-prints (2022).","DOI":"10.48550\/ARXIV.2205.09734"},{"key":"21","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 (2022).","DOI":"10.1038\/s41567-022-01539-6"},{"key":"22","doi-asserted-by":"publisher","unstructured":"J. Bourgainand A. Gamburd ``A spectral gap theorem in SU(d)'' J. Eur. Math. Soc. 14, 1455\u00e2\u0080\u00931511 (2012).","DOI":"10.4171\/JEMS\/337"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J Bourgainand Alex Gamburd ``On the spectral gap for finitely-generated subgroups of SU(2).'' Invent. math. 171, 83\u00e2\u0080\u0093121 (2008).","DOI":"10.1007\/s00222-007-0072-z"},{"key":"24","doi-asserted-by":"publisher","unstructured":"A. Bocharov, Y. Gurevich, and K. M. Svore, ``Efficient decomposition of single-qubit gates into V basis circuits'' Phys. Rev. A 88, 012313 (2013).","DOI":"10.1103\/physreva.88.012313"},{"key":"25","doi-asserted-by":"publisher","unstructured":"V. Kliuchnikov, A. Bocharov, M. Roetteler, and J. Yard, ``A Framework for Approximating Qubit Unitaries'' arXiv e-prints (2015).","DOI":"10.48550\/arXiv.1510.03888"},{"key":"26","doi-asserted-by":"publisher","unstructured":"V. Kliuchnikov, D. Maslov, and M. Mosca, ``Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates'' Quantum Information and Computation 13, 607\u2013630 (2013).","DOI":"10.26421\/QIC13.7-8-4"},{"key":"27","doi-asserted-by":"publisher","unstructured":"P. Selinger ``Efficient Clifford+T approximation of single-qubit operators'' Quantum Information and Computation 15, 159\u00e2\u0080\u0093180 (2015).","DOI":"10.26421\/QIC15.1-2-10"},{"key":"28","unstructured":"P. Sarnak ``Letter to Scott Aaronson and Andy Pollington on the Solovay-Kitaev theorem'' (2015)."},{"key":"29","doi-asserted-by":"publisher","unstructured":"A. Lubotzky, R. Phillips, and P. Sarnak, ``Hecke operators and distributing points on S2. II'' Communications on Pure and Applied Mathematics 40, 401\u2013420 (1987).","DOI":"10.1002\/cpa.3160400402"},{"key":"30","doi-asserted-by":"publisher","unstructured":"J. A. Tropp ``An Introduction to Matrix Concentration Inequalities'' Now Publishers Inc (2015).","DOI":"10.1561\/2200000048"},{"key":"31","doi-asserted-by":"publisher","unstructured":"M. Abu-Hamedand S. Gelaki ``Frobenius-Schur indicators for semisimple Lie algebras'' Journal of Algebra 315, 178\u2013191 (2007).","DOI":"10.1016\/j.jalgebra.2007.06.003"},{"key":"32","doi-asserted-by":"publisher","unstructured":"J. Emerson, R. Alicki, and K. \u00c5\u00bbyczkowski, ``Scalable noise estimation with random unitary operators'' Journal of Optics B: Quantum and Semiclassical Optics 7, S347 (2005).","DOI":"10.1088\/1464-4266\/7\/10\/021"},{"key":"33","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. A 80, 012304 (2009).","DOI":"10.1103\/PhysRevA.80.012304"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Y. Nakata, D. Zhao, T. Okuda, E. Bannai, Y. Suzuki, S. Tamiya, K. Heya, Z. Yan, K. Zuo, S. Tamate, Y. Tabuchi, and Y. Nakamura, ``Quantum Circuits for Exact Unitary $t$-Designs and Applications to Higher-Order Randomized Benchmarking'' PRX Quantum 2, 030339 (2021).","DOI":"10.1103\/PRXQuantum.2.030339"},{"key":"35","doi-asserted-by":"publisher","unstructured":"E. S. Meckes ``The Random Matrix Theory of the Classical Compact Groups'' Cambridge University Press (2019).","DOI":"10.1017\/9781108303453"},{"key":"36","doi-asserted-by":"publisher","unstructured":"M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, ``Experimental realization of any discrete unitary operator'' Phys. Rev. Lett. 73, 58\u201361 (1994).","DOI":"10.1103\/PhysRevLett.73.58"},{"key":"37","doi-asserted-by":"publisher","unstructured":"A. Sawicki ``Universality of beamsplitters'' Quantum Information and Computation 16, 291\u2013312 (2016).","DOI":"10.26421\/QIC16.3-4-6"},{"key":"38","doi-asserted-by":"publisher","unstructured":"E. H. Lieb ``Convex trace functions and the Wigner-Yanase-Dyson conjecture'' Advances in Mathematics 11, 267\u2013288 (1973).","DOI":"10.1016\/0001-8708(73)90011-X"},{"key":"39","doi-asserted-by":"publisher","unstructured":"S. Golden ``Lower Bounds for the Helmholtz Function'' Phys. Rev. 137, B1127\u00e2\u0080\u0093B1128 (1965).","DOI":"10.1103\/PhysRev.137.B1127"},{"key":"40","doi-asserted-by":"publisher","unstructured":"C. J. Thompson ``Inequality with Applications in Statistical Mechanics'' J. Math. Phys. 6, 1812\u00e2\u0080\u00931813 (1965).","DOI":"10.1063\/1.1704727"},{"key":"41","doi-asserted-by":"publisher","unstructured":"B. C. Hall ``Lie Groups Lie Algebras and Representations An Elementary Introduction'' Springer-Verlag New York (2004).","DOI":"10.1007\/978-3-319-13467-3"},{"key":"42","doi-asserted-by":"publisher","unstructured":"G. Benkart, M. Chakrabarti, T. Halverson, R. Leduc, C. Lee, and J. Stroomer, ``Tensor product representations of general linear groups and their connections with Brauer algebras'' J. Algebra 166, 529\u00e2\u0080\u0093567 (1994).","DOI":"10.1006\/jabr.1994.1166"},{"key":"43","doi-asserted-by":"publisher","unstructured":"T. Br\u00f6ckerand T. Dieck ``Representations of Compact Lie Groups'' Springer Berlin Heidelberg (2003).","DOI":"10.1007\/978-3-662-12918-0"},{"key":"44","doi-asserted-by":"publisher","unstructured":"D. Ruiz-Antolinand J. Segura ``A new type of sharp bounds for ratios of modified Bessel functions'' J. Math. Anal. Appl. 443, 1232\u20131246 (2016).","DOI":"10.1016\/j.jmaa.2016.06.011"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-04-20-983\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,20]],"date-time":"2023-04-20T12:27:09Z","timestamp":1681993629000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-04-20-983\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,20]]},"references-count":45,"URL":"https:\/\/doi.org\/10.22331\/q-2023-04-20-983","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,20]]},"article-number":"983"}}