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

Piotr Dulian1,2 and Adam Sawicki1

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

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

► 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-04-19 01:52:34) and SAO/NASA ADS (last updated successfully 2024-04-19 01:52:36). The list may be incomplete as not all publishers provide suitable and complete citation data.