Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Piotr Dulian; Adam Sawicki

doi:10.22331/q-2023-04-20-983

Matrix concentration inequalities and efficiency of random universal sets of quantum gates

Piotr Dulian^1,2 and Adam Sawicki¹

¹Center for Theoretical Physics, Polish Academy of Sciences, Al. Lotników 32/46, 02-668 Warsaw, Poland
²Faculty of Physics, University of Warsaw, Pasteura 5, 02-093 Warsaw, Poland

Published:	2023-04-20, volume 7, page 983
Eprint:	arXiv:2202.05371v3
Doi:	https://doi.org/10.22331/q-2023-04-20-983
Citation:	Quantum 7, 983 (2023).

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

Abstract

For a random set $\mathcal{S} \subset U(d)$ of quantum gates we provide bounds on the probability that $\mathcal{S}$ forms a $\delta$-approximate $t$-design. In particular we have found that for $\mathcal{S}$ drawn from an exact $t$-design the probability that it forms a $\delta$-approximate $t$-design satisfies the inequality $\mathbb{P}\left(\delta \geq x \right)\leq 2D_t \, \frac{e^{-|\mathcal{S}| x \, \mathrm{arctanh}(x)}}{(1-x^2)^{|\mathcal{S}|/2}} = O\left( 2D_t \left( \frac{e^{-x^2}}{\sqrt{1-x^2}} \right)^{|\mathcal{S}|} \right)$, where $D_t$ is a sum over dimensions of unique irreducible representations appearing in the decomposition of $U \mapsto U^{\otimes t}\otimes \bar{U}^{\otimes t}$. We use our results to show that to obtain a $\delta$-approximate $t$-design with probability $P$ one needs $O( \delta^{-2}(t\log(d)-\log(1-P)))$ many random gates. We also analyze how $\delta$ concentrates around its expected value $\mathbb{E}\delta$ for random $\mathcal{S}$. Our results are valid for both symmetric and non-symmetric sets of gates.

► BibTeX data

@article{Dulian2023matrixconcentration,
  doi = {10.22331/q-2023-04-20-983},
  url = {https://doi.org/10.22331/q-2023-04-20-983},
  title = {Matrix concentration inequalities and efficiency of random universal sets of quantum gates},
  author = {Dulian, Piotr and Sawicki, Adam},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {983},
  month = apr,
  year = {2023}
}

► References

[1] 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).
https://doi.org/10.1103/PhysRevA.86.032324

[2] J. Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[3] 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–600 (2018).
https://doi.org/10.1038/s41567-018-0124-x

[4] A. W. Harrowand A. Montanaro ``Quantum Computational Supremacy'' Nature 549, 203–209 (2017).
https://doi.org/10.1038/nature23458

[5] 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).
https://doi.org/10.1103/PhysRevLett.117.060504

[6] 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–503 (2014).
https://doi.org/10.1038/nature13171

[7] L. Susskind ``Three Lectures on Complexity and Black Holes'' Springer Cham (2020).
https://doi.org/10.1007/978-3-030-45109-7
https://arxiv.org/abs/1810.11563

[8] A. Sawickiand K. Karnas ``Criteria for universality of quantum gates'' Physical Review A 95, 062303 (2017).
https://doi.org/10.1103/physreva.95.062303

[9] A. Sawickiand K. Karnas ``Universality of Single-Qudit Gates'' Annales Henri PoincarÃ© 18, 3515â3552 (2017).
https://doi.org/10.1007/s00023-017-0604-z

[10] A. Sawicki, L. Mattioli, and Z. Zimborás, ``Universality verification for a set of quantum gates'' Phys. Rev. A 105, 052602 (2022).
https://doi.org/10.1103/PhysRevA.105.052602
arXiv:2111.03862

[11] M. A. Nielsenand I. L. Chuang ``Quantum Computation and Quantum Information: 10th Anniversary Edition'' Cambridge University Press (2010).
https://doi.org/10.1017/CBO9780511976667

[12] P. P. Varjú ``Random walks in compact groups'' Doc. Math. 18, 1137–1175 (2013).
https://doi.org/10.4171/DM/423

[13] M. Oszmaniec, A. Sawicki, and M. Horodecki, ``Epsilon-Nets, Unitary Designs, and Random Quantum Circuits'' IEEE Transactions on Information Theory 68, 989–1015 (2022).
https://doi.org/10.1109/TIT.2021.3128110

[14] A. Boulandand T. Giurgica-Tiron ``Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm'' arXiv e-prints (2021).
https://doi.org/10.48550/ARXIV.2112.02040
arXiv:2112.02040

[15] A. W. Harrow, B. Recht, and Isaac L. Chuang, ``Efficient Discrete Approximations of Quantum Gates'' J. Math. Phys. 43, 4445 (2002).
https://doi.org/10.1063/1.1495899

[16] 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).
https://doi.org/10.1103/physreva.89.062321
arXiv:1308.2928

[17] A. M. Dalzell, N. Hunter-Jones, and F. G. S. L. BrandÃ£o, ``Random quantum circuits transform local noise into global white noise'' arXiv e-prints (2021).
https://doi.org/10.48550/ARXIV.2111.14907
arXiv:2111.14907

[18] 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–2563 (2009).
https://doi.org/10.1098/rspa.2009.0202

[19] J. Radhakrishnan, M. RÃ¶tteler, and P. Sen, ``Random measurement bases, quantum state distinction and applications to the hidden subgroup problem'' Algorithmica 55, 490â516 (2009).
https://doi.org/10.1007/s00453-008-9231-x

[20] D. A. Robertsand B. Yoshida ``Chaos and complexity by design'' Journal of High Energy Physics 2017, 121 (2017).
https://doi.org/10.1007/JHEP04(2017)121
arXiv:1610.04903

[21] M. Oszmaniec, M. Horodecki, and N. Hunter-Jones, ``Saturation and recurrence of quantum complexity in random quantum circuits'' arXiv e-prints (2022).
https://doi.org/10.48550/ARXIV.2205.09734
arXiv:2205.09734

[22] 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 (2022).
https://doi.org/10.1038/s41567-022-01539-6
arXiv:2106.05305

[23] J. Bourgainand A. Gamburd ``A spectral gap theorem in SU(d)'' J. Eur. Math. Soc. 14, 1455â1511 (2012).
https://doi.org/10.4171/JEMS/337

[24] J Bourgainand Alex Gamburd ``On the spectral gap for finitely-generated subgroups of SU(2).'' Invent. math. 171, 83â121 (2008).
https://doi.org/10.1007/s00222-007-0072-z

[25] A. Bocharov, Y. Gurevich, and K. M. Svore, ``Efficient decomposition of single-qubit gates into V basis circuits'' Phys. Rev. A 88, 012313 (2013).
https://doi.org/10.1103/physreva.88.012313

[26] V. Kliuchnikov, A. Bocharov, M. Roetteler, and J. Yard, ``A Framework for Approximating Qubit Unitaries'' arXiv e-prints (2015).
https://doi.org/10.48550/arXiv.1510.03888
arXiv:1510.03888

[27] 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–630 (2013).
https://doi.org/10.26421/QIC13.7-8-4

[28] P. Selinger ``Efficient Clifford+T approximation of single-qubit operators'' Quantum Information and Computation 15, 159â180 (2015).
https://doi.org/10.26421/QIC15.1-2-10

[29] P. Sarnak ``Letter to Scott Aaronson and Andy Pollington on the Solovay-Kitaev theorem'' (2015).

[30] A. Lubotzky, R. Phillips, and P. Sarnak, ``Hecke operators and distributing points on S2. II'' Communications on Pure and Applied Mathematics 40, 401–420 (1987).
https://doi.org/10.1002/cpa.3160400402

[31] J. A. Tropp ``An Introduction to Matrix Concentration Inequalities'' Now Publishers Inc (2015).
https://doi.org/10.1561/2200000048
https://arxiv.org/abs/1501.01571

[32] M. Abu-Hamedand S. Gelaki ``Frobenius-Schur indicators for semisimple Lie algebras'' Journal of Algebra 315, 178–191 (2007).
https://doi.org/10.1016/j.jalgebra.2007.06.003

[33] J. Emerson, R. Alicki, and K. Å»yczkowski, ``Scalable noise estimation with random unitary operators'' Journal of Optics B: Quantum and Semiclassical Optics 7, S347 (2005).
https://doi.org/10.1088/1464-4266/7/10/021

[34] 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).
https://doi.org/10.1103/PhysRevA.80.012304

[35] 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).
https://doi.org/10.1103/PRXQuantum.2.030339
arXiv:2102.12617

[36] E. S. Meckes ``The Random Matrix Theory of the Classical Compact Groups'' Cambridge University Press (2019).
https://doi.org/10.1017/9781108303453

[37] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani, ``Experimental realization of any discrete unitary operator'' Phys. Rev. Lett. 73, 58–61 (1994).
https://doi.org/10.1103/PhysRevLett.73.58

[38] A. Sawicki ``Universality of beamsplitters'' Quantum Information and Computation 16, 291–312 (2016).
https://doi.org/10.26421/QIC16.3-4-6

[39] E. H. Lieb ``Convex trace functions and the Wigner-Yanase-Dyson conjecture'' Advances in Mathematics 11, 267–288 (1973).
https://doi.org/10.1016/0001-8708(73)90011-X

[40] S. Golden ``Lower Bounds for the Helmholtz Function'' Phys. Rev. 137, B1127âB1128 (1965).
https://doi.org/10.1103/PhysRev.137.B1127

[41] C. J. Thompson ``Inequality with Applications in Statistical Mechanics'' J. Math. Phys. 6, 1812â1813 (1965).
https://doi.org/10.1063/1.1704727

[42] B. C. Hall ``Lie Groups Lie Algebras and Representations An Elementary Introduction'' Springer-Verlag New York (2004).
https://doi.org/10.1007/978-3-319-13467-3

[43] 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â567 (1994).
https://doi.org/10.1006/jabr.1994.1166

[44] T. Bröckerand T. Dieck ``Representations of Compact Lie Groups'' Springer Berlin Heidelberg (2003).
https://doi.org/10.1007/978-3-662-12918-0
https://books.google.pl/books?id=AfBzWL5bIIQC

[45] D. Ruiz-Antolinand J. Segura ``A new type of sharp bounds for ratios of modified Bessel functions'' J. Math. Anal. Appl. 443, 1232–1246 (2016).
https://doi.org/10.1016/j.jmaa.2016.06.011

Cited by

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

[2] Dmitry Grinko and Maris Ozols, "Linear programming with unitary-equivariant constraints", arXiv:2207.05713, (2022).

[3] Piotr Dulian and Adam Sawicki, "A random matrix model for random approximate $t$-designs", arXiv:2210.07872, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-21 10:18:06) and SAO/NASA ADS (last updated successfully 2024-05-21 10:18:07). 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.