Document Open Access Logo

Complexity Classification of Conjugated Clifford Circuits

Authors Adam Bouland , Joseph F. Fitzsimons, Dax Enshan Koh

PDF
Thumbnail PDF

File

LIPIcs.CCC.2018.21.pdf
  • Filesize: 0.71 MB
  • 25 pages

Document Identifiers

Author Details

Adam Bouland
  • Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA, USA
Joseph F. Fitzsimons
  • Singapore University of Technology and Design, 8 Somapah Road, Singapore 487372 , Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore 117543
Dax Enshan Koh
  • Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

Funding

  • Bouland, Adam: AB was partially supported by the NSF GRFP under Grant No. 1122374, by a Vannevar Bush Fellowship from the US Department of Defense, and by an NSF Waterman award under grant number 1249349.
  • Fitzsimons, Joseph F.: JFF acknowledges support from the Air Force Office of Scientific Research under AOARD grant no. FA2386-15-1-4082. This material is based on research supported in part by the Singapore National Research Foundation under NRF Award No. NRF-NRFF2013-01.
  • Koh, Dax Enshan: DEK is supported by the National Science Scholarship from the Agency for Science, Technology and Research (A*STAR).

Cite As Get BibTex

Adam Bouland, Joseph F. Fitzsimons, and Dax Enshan Koh. Complexity Classification of Conjugated Clifford Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 21:1-21:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.CCC.2018.21

Abstract

Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
  • Theory of computation → Computational complexity and cryptography
Keywords
  • gate set classification
  • quantum advantage
  • sampling problems
  • polynomial hierarchy

Metrics

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

Related Versions

References

  1. Universal sets of gates for SU(3)?, 2012. Accessed: 2017-08-01. URL: https://cstheory.stackexchange.com/questions/11308/universal-sets-of-gates-for-su3.
  2. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 461(2063):3473-3482, 2005. URL: http://dx.doi.org/10.1098/rspa.2005.1546.
  3. 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. Google Scholar
  4. Scott Aaronson and Lijie Chen. Complexity-theoretic foundations of quantum supremacy experiments. Proc. CCC, 2017. Google Scholar
  5. Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5):052328, 2004. Google Scholar
  6. Scott Aaronson, Daniel Grier, and Luke Schaeffer. The classification of reversible bit operations. In Proceedings of Innovations in Theoretical Computer Science (ITCS), 2017. Google Scholar
  7. Dorit Aharonov and Michael Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the twenty-ninth annual ACM Symposium on Theory of Computing, pages 176-188. ACM, 1997. Google Scholar
  8. Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. arXiv:1608.00263, 2016. Google Scholar
  9. Adam Bouland and Scott Aaronson. Generation of universal linear optics by any beam splitter. Physical Review A, 89(6):062316, 2014. Google Scholar
  10. Adam Bouland, Laura Mancinska, and Xue Zhang. Complexity classification of two-qubit commuting hamiltonians. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 28:1-28:33. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2016.28.
  11. Sergey Bravyi, David Gosset, and Robert Koenig. Quantum advantage with shallow circuits. arXiv:1704.00690, 2017. Google Scholar
  12. Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Physical Review A, 86(5):052329, 2012. Google Scholar
  13. Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A, 71(2):022316, 2005. Google Scholar
  14. Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, page rspa20100301. The Royal Society, 2010. Google Scholar
  15. Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Average-case complexity versus approximate simulation of commuting quantum computations. Physical Review Letters, 117(8):080501, 2016. Google Scholar
  16. Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. Achieving quantum supremacy with sparse and noisy commuting quantum computations. Quantum, 1, 2017. Google Scholar
  17. Hans J Briegel, David E Browne, W Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5(1):19-26, 2009. Google Scholar
  18. Christopher M Dawson and Michael A Nielsen. The Solovay-Kitaev algorithm. Quantum Information &Computation, 6(1):81-95, 2006. Google Scholar
  19. David P. DiVincenzo and Peter W. Shor. Fault-tolerant error correction with efficient quantum codes. Phys. Rev. Lett., 77:3260-3263, Oct 1996. URL: http://dx.doi.org/10.1103/PhysRevLett.77.3260.
  20. Bryan Eastin and Emanuel Knill. Restrictions on transversal encoded quantum gate sets. Physical Review Letters, 102(11):110502, 2009. Google Scholar
  21. Edward Farhi and Aram W Harrow. Quantum supremacy through the quantum approximate optimization algorithm. arXiv:1602.07674, 2016. Google Scholar
  22. Bill Fefferman and Christopher Umans. On the power of quantum fourier sampling. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, September 27-29, 2016, Berlin, Germany, volume 61 of LIPIcs, pages 1:1-1:19. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.TQC.2016.1.
  23. Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Impossibility of classically simulating one-clean-qubit computation. arXiv:1409.6777, 2014. Google Scholar
  24. Daniel Gottesman. Stabilizer codes and quantum error correction. Ph.D. Thesis, California Institute of Technology, arXiv:quant-ph/9705052, 1997. Google Scholar
  25. Daniel Gottesman. The Heisenberg representation of quantum computers. Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics, pages 32-43, 1999. Google Scholar
  26. Chris Granade and Ben Criger. QuaEC: Quantum error correction analysis in Python. http://www.cgranade.com/python-quaec/groups.html#, 2012. Accessed: 2017-06-01.
  27. Daniel Grier and Luke Schaeffer. The classification of stabilizer operations over qubits. arXiv:1603.03999, 2016. Google Scholar
  28. Amihay Hanany and Yang-Hui He. A monograph on the classification of the discrete subgroups of SU(4). Journal of High Energy Physics, 2001(02):027, 2001. Google Scholar
  29. Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert. Anti-concentration theorems for schemes showing a quantum computational supremacy. arXiv:1706.03786, 2017. Google Scholar
  30. Daniel Harlow. Jerusalem lectures on black holes and quantum information. Reviews of Modern Physics, 88(1):015002, 2016. Google Scholar
  31. Aram Harrow and Saeed Mehraban. Personal communication, 2018. Google Scholar
  32. Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 464(2100):3089-3106, 2008. URL: http://dx.doi.org/10.1098/rspa.2008.0189.
  33. Richard Jozsa and Maarten Van den Nest. Classical simulation complexity of extended Clifford circuits. Quantum Information and Computation, 14(7/8):633-648, 2014. Google Scholar
  34. Dax Enshan Koh. Further extensions of Clifford circuits and their classical simulation complexities. Quantum Information &Computation, 17(3&4):0262-0282, 2017. Google Scholar
  35. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11(6):183-219, 2015. Google Scholar
  36. Richard E. Ladner. On the structure of polynomial time reducibility. J. ACM, 22(1):155-171, 1975. Google Scholar
  37. Raymond Laflamme, Cesar Miquel, Juan Pablo Paz, and Wojciech Hubert Zurek. Perfect quantum error correcting code. Physical Review Letters, 77(1):198, 1996. Google Scholar
  38. Easwar Magesan, Jay M Gambetta, and Joseph Emerson. Scalable and robust randomized benchmarking of quantum processes. Physical Review Letters, 106(18):180504, 2011. Google Scholar
  39. Ryan L. Mann and Michael J. Bremner. On the complexity of random quantum computations and the Jones polynomial. arXiv:1711.00686, 2017. Google Scholar
  40. Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L O'Brien. Experimental realization of shor’s quantum factoring algorithm using qubit recycling. Nature Photonics, 6(11):773-776, 2012. Google Scholar
  41. Dmitri Maslov and Martin Roetteler. Shorter stabilizer circuits via Bruhat decomposition and quantum circuit transformations. arXiv:1705.09176, 2017. Google Scholar
  42. Tomoyuki Morimae. Hardness of classically sampling one clean qubit model with constant total variation distance error. arXiv:1704.03640, 2017. Google Scholar
  43. Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical Review Letters, 112(13):130502, 2014. Google Scholar
  44. Gabriele Nebe, Eric M Rains, and Neil JA Sloane. The invariants of the clifford groups. Designs, Codes and Cryptography, 24(1):99-122, 2001. Google Scholar
  45. Gabriele Nebe, Eric M Rains, and Neil James Alexander Sloane. Self-dual codes and invariant theory, volume 17. Springer, 2006. Google Scholar
  46. Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002. Google Scholar
  47. Michał Oszmaniec and Zoltán Zimborás. Universal extensions of restricted classes of quantum operations. arXiv:1705.11188, 2017. Google Scholar
  48. John Preskill. Quantum computing and the entanglement frontier. arXiv:1203.5813, 2012. Google Scholar
  49. Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical Review Letters, 86(22):5188, 2001. Google Scholar
  50. Robert Raussendorf, Daniel E Browne, and Hans J Briegel. Measurement-based quantum computation on cluster states. Physical Review A, 68(2):022312, 2003. Google Scholar
  51. Imdad SB Sardharwalla, Toby S Cubitt, Aram W Harrow, and Noah Linden. Universal refocusing of systematic quantum noise. arXiv:1602.07963, 2016. Google Scholar
  52. Adam Sawicki and Katarzyna Karnas. Criteria for universality of quantum gates. Phys. Rev. A, 95:062303, Jun 2017. Google Scholar
  53. Peter W Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303-332, 1999. Google Scholar
  54. Andrew Steane. Multiple-particle interference and quantum error correction. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 452(1954):2551-2577, 1996. URL: http://dx.doi.org/10.1098/rspa.1996.0136.
  55. Larry Stockmeyer. The complexity of approximate counting. In Proceedings of the fifteenth annual ACM Symposium on Theory of Computing, pages 118-126. ACM, 1983. Google Scholar
  56. Barbara M Terhal and David P DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information &Computation, 4(2):134-145, 2004. Google Scholar
  57. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  58. Zak Webb. The Clifford group forms a unitary 3-design. Quantum Information and Computation, 16:1379-1400, 2016. Google Scholar
  59. Huangjun Zhu. Multiqubit clifford groups are unitary 3-designs. Physical Review A, 96(6):062336, 2017. Google Scholar
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact