Document Open Access Logo

Trading Inverses for an Irrep in the Solovay-Kitaev Theorem

Authors Adam Bouland , Maris Ozols

PDF

File

Thumbnail PDF
PDF
LIPIcs.TQC.2018.6.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Solovay-Kitaev theorem
  • quantum gate sets
  • gate set compilation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error epsilon using merely polylog(1/epsilon) gates from any finite universal quantum gate set G. One drawback to the theorem is that it requires the gate set G to be closed under inversion. Here we show that this restriction can be traded for the assumption that G contains an irreducible representation of any finite group G. This extends recent work of Sardharwalla et al. [Sardharwalla et al., 2016], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [Dawson and Nielsen, 2006; Kuperberg, 2015].

Cite As Get BibTex

Adam Bouland and Maris Ozols. Trading Inverses for an Irrep in the Solovay-Kitaev Theorem. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 111, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.TQC.2018.6

Author Details

Adam Bouland
  • Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA, USA
Maris Ozols
  • QuSoft and University of Amsterdam, Amsterdam, Netherlands

Funding

  • Bouland, Adam: AB was partially supported by the NSF GRFP under Grant No. 1122374, by the Vannevar Bush Fellowship from the US Department of Defense, by ARO Grant W911NF-12-1-0541, by NSF Grant CCF-1410022, and by the NSF Waterman award under grant number 1249349.
  • Ozols, Maris: Part of this work was done while MO was at the University of Cambridge where he was supported by a Leverhulme Trust Early Career Fellowship (ECF-2015-256). MO also acknowledges hospitality of MIT where this project was initiated.

References

  1. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333-342. ACM, 2011. URL: http://dx.doi.org/10.1145/1993636.1993682.
  2. Dorit Aharonov, Itai Arad, Elad Eban, and Zeph Landau. Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane, 2007. URL: http://arxiv.org/abs/quant-ph/0702008.
  3. Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error rate. SIAM Journal on Computing, 38(4):1207-1282, 2008. URL: http://dx.doi.org/10.1137/S0097539799359385.
  4. Dorit Aharonov, Vaughan Jones, and Zeph Landau. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55(3):395-421, Nov 2009. URL: http://dx.doi.org/10.1007/s00453-008-9168-0.
  5. Johannes Bausch, Toby Cubitt, and Maris Ozols. The complexity of translationally invariant spin chains with low local dimension. Annales Henri Poincaré, 18(11):3449-3513, Nov 2017. URL: http://dx.doi.org/10.1007/s00023-017-0609-7.
  6. Johannes Bausch and Stephen Piddock. The complexity of translationally invariant low-dimensional spin lattices 3D. Journal of Mathematical Physics, 58(11):111901, 2017. URL: http://dx.doi.org/10.1063/1.5011338.
  7. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 792-809. IEEE, Oct 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.54.
  8. Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of probabilistic quantum circuits with fallback. Phys. Rev. A, 91(5):052317, May 2015. URL: http://dx.doi.org/10.1103/PhysRevA.91.052317.
  9. Alex Bocharov, Martin Roetteler, and Krysta M. Svore. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett., 114(8):080502, Feb 2015. URL: http://dx.doi.org/10.1103/PhysRevLett.114.080502.
  10. Adam Bouland, Joseph F. Fitzsimons, and Dax E. Koh. Complexity classification of conjugated Clifford circuits. Proc. 33rd Computational Complexity Conference (CCC), 2018. URL: http://arxiv.org/abs/1709.01805.
  11. Adam Bouland, Laura Mančinska, and Xue Zhang. Complexity classification of two-qubit commuting Hamiltonians. In Ran Raz, editor, 31st Conference on Computational Complexity (CCC 2016), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1-28:33, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.28.
  12. Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 2010. URL: http://dx.doi.org/10.1098/rspa.2010.0301.
  13. Andrew M. Childs. Fourier analysis in nonabelian groups. Lecture notes at University of Waterloo, 2013. URL: http://www.cs.umd.edu/~amchilds/teaching/w13/l06.pdf.
  14. Andrew M. Childs. Lecture notes on quantum algorithms. Lecture notes at University of Maryland, 2017. URL: http://www.cs.umd.edu/~amchilds/qa/qa.pdf.
  15. Andrew M. Childs, Debbie Leung, Laura Mančinska, and Maris Ozols. Characterization of universal two-qubit Hamiltonians. Quantum Information &Computation, 11(1&2):19-39, Jan 2011. URL: http://arxiv.org/abs/1004.1645.
  16. Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information &Computation, 6(1):81-95, Jan 2006. URL: http://arxiv.org/abs/quant-ph/0505030.
  17. Daniel Gottesman and Sandy Irani. The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. Theory of Computing, 9(2):31-116, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a002.
  18. Aram W. Harrow, Benjamin Recht, and Isaac L. Chuang. Efficient discrete approximations of quantum gates. Journal of Mathematical Physics, 43(9):4445-4451, 2002. URL: http://dx.doi.org/10.1063/1.1495899.
  19. Alexei Yu. Kitaev. Quantum computations: algorithms and error correction. Russian Mathematical Surveys, 52(6):1191-1249, 1997. URL: http://dx.doi.org/10.1070/RM1997v052n06ABEH002155.
  20. Alexei Yu. Kitaev, Alexander Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. URL: https://books.google.com/books?id=qYHTvHPvmG8C.
  21. Vadym Kliuchnikov. Synthesis of unitaries with Clifford+T circuits, 2013. URL: http://arxiv.org/abs/1306.3200.
  22. Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits. IEEE Transactions on Computers, 65(1):161-172, Jan 2016. URL: http://dx.doi.org/10.1109/TC.2015.2409842.
  23. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. URL: http://dx.doi.org/10.4086/toc.2015.v011a006.
  24. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010. URL: https://books.google.com/books?id=-s4DEy7o-a0C.
  25. Māris Ozols. The Solovay-Kitaev theorem. Essay at University of Waterloo, 2009. URL: http://home.lu.lv/~sd20008/papers/essays/Solovay-Kitaev.pdf.
  26. Adam Paetznick and Krysta M. Svore. Repeat-until-success: Non-deterministic decomposition of single-qubit unitaries. Quantum Information &Computation, 14(15&16):1277-1301, 2014. URL: http://arxiv.org/abs/1311.1074.
  27. Ori Parzanchevski and Peter Sarnak. Super-Golden-Gates for PU(2). Advances in Mathematics, 327:869-901, 2018. Special volume honoring David Kazhdan. URL: http://dx.doi.org/10.1016/j.aim.2017.06.022.
  28. Neil J. Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Information &Computation, 16(11&12):0901-0953, 2016. URL: http://dx.doi.org/10.26421/QIC16.11-12.
  29. Imdad S.B. Sardharwalla, Toby S. Cubitt, Aram W. Harrow, and Noah Linden. Universal refocusing of systematic quantum noise, 2016. URL: http://arxiv.org/abs/1602.07963.
  30. Peter Sarnak. Letter to Aaronson and Pollington on the Solvay-Kitaev Theorem and Golden Gates, 2015. URL: http://publications.ias.edu/sarnak/paper/2637.
  31. Adam Sawicki and Katarzyna Karnas. Universality of single-qudit gates. Annales Henri Poincaré, Aug 2017. URL: http://dx.doi.org/10.1007/s00023-017-0604-z.
  32. Peter Selinger. Efficient Clifford+T approximation of single-qubit operators. Quantum Information &Computation, 15(1&2):159-180, 2015. URL: http://arxiv.org/abs/1212.6253.
  33. Jean-Pierre Serre. Linear Representations of Finite Groups. Springer, 2012. URL: https://books.google.com/books?id=9mT1BwAAQBAJ.
  34. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484-1509, 1997. URL: http://dx.doi.org/10.1137/S0097539795293172.
  35. Péter Pál Varjú. Random walks in compact groups. Documenta Mathematica, 18:1137-1175, 2013. URL: http://arxiv.org/abs/1209.1745.
  36. Y. Zhiyenbayev, V. M. Akulin, and A. Mandilara. Quantum compiling with diffusive sets of gates, 2017. URL: http://arxiv.org/abs/1708.08909.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact