Document Open Access Logo

Power of Quantum Computation with Few Clean Qubits

Authors Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.13.pdf
  • Filesize: 468 kB
  • 14 pages

Document Identifiers

Author Details

Keisuke Fujii
Hirotada Kobayashi
Tomoyuki Morimae
Harumichi Nishimura
Shuhei Tamate
Seiichiro Tani

Cite As Get BibTex

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Power of Quantum Computation with Few Clean Qubits. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.13

Abstract

This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state. No initializations of qubits are allowed during the computation, nor are intermediate measurements. The main contribution of this paper is to develop unexpectedly strong error-reduction methods for such quantum computations that simultaneously reduce the number of necessary clean qubits. It is proved that any problem solvable by a polynomialtime quantum computation with one-sided bounded error that uses logarithmically many clean qubits is also solvable with exponentially small one-sided error using just two clean qubits, and with polynomially small one-sided error using just one clean qubit. It is further proved in the twosided-error case that any problem solvable by such a computation with a constant gap between completeness and soundness using logarithmically many clean qubits is also solvable with exponentially small two-sided error using just two clean qubits. If only one clean qubit is available, the problem is again still solvable with exponentially small error in one of the completeness and soundness and with polynomially small error in the other. An immediate consequence is that the Trace Estimation problem defined with fixed constant threshold parameters is complete for BQ_{[1]}P and BQ_{log}P, the classes of problems solvable by polynomial-time quantum computations with completeness 2/3 and soundness 1/3 using just one and logarithmically many clean qubits, respectively. The techniques used for proving the error-reduction results may be of independent interest in themselves, and one of the technical tools can also be used to show the hardness of weak classical simulations of one-clean-qubit computations (i.e., DQC1 computations).

Subject Classification

Keywords
  • DQC1
  • quantum computing
  • complete problems
  • error reduction

Metrics

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

References

  1. Scott Aaronson. Quantum computing, postselection, and probabilistic polynomial-time. Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. URL: http://dx.doi.org/10.1098/rspa.2005.1546.
  2. Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. Theory of Computing, 9:143-252, 2013. URL: http://dx.doi.org/10.4086/toc.2013.v009a004.
  3. Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang. Quantum computability. SIAM Journal on Computing, 26(5):1524-1540, 1997. URL: http://dx.doi.org/10.1137/S0097539795293639.
  4. Andris Ambainis and Rūsiņš Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. In 39th Annual Symposium on Foundations of Computer Science, pages 332-341, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743469.
  5. Andris Ambainis, Leonard J. Schulman, and Umesh Vazirani. Computing with highly mixed states. Journal of the ACM, 53(3):507-531, 2006. URL: http://dx.doi.org/10.1145/1147954.1147962.
  6. Elmar Böhler, Christian Glaßer, and Daniel Meister. Error-bounded probabilistic computations between MA and AM. Journal of Computer and System Sciences, 72(6):1043-1076, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2006.05.001.
  7. 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 A, 467(2126):459-472, 2011. URL: http://dx.doi.org/10.1098/rspa.2010.0301.
  8. Daniel J. Brod. The complexity of simulating constant-depth BosonSampling. Physical Review A, 91(4):article 042316, 2015. URL: http://dx.doi.org/10.1103/PhysRevA.91.042316.
  9. Joseph Emerson, Yaakov S. Weinstein, Seth Lloyd, and D. G. Cory. Fidelity decay as an efficient indicator of quantum chaos. Physical Review Letters, 89(28), 2002. URL: http://dx.doi.org/10.1103/PhysRevLett.89.284102.
  10. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. In Automata, Languages, and Programming, 43rd International Colloquium, ICALP 2016, Proceedings, Leibniz International Proceedings in Informatics, 2016. Google Scholar
  11. Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Power of quantum computation with few clean qubits. arXiv.org e-Print archive, arXiv:1509.07276 [quant-ph], 2015. URL: http://arxiv.org/abs/1507.05592.
  12. Stephen P. Jordan and Gorjan Alagic. Approximating the Turaev-Viro invariant of mapping tori is complete for one clean qubit. In Dave Bacon, Miguel Martin-Delgado, and Martin Roetteler, editors, Theory of Quantum Computation, Communication, and Cryptography, 6th Conference, TQC 2011, Madrid, Spain, May 24-26, 2011, Revised Selected Papers, volume 6745 of Lecture Notes in Computer Science, pages 53-72. Springer-Verlag, 2014. URL: http://dx.doi.org/10.1007/978-3-642-54429-3_5.
  13. Stephen P. Jordan and Pawel Wocjan. Estimating Jones and HOMFLY polynomials with one clean qubit. Quantum Information and Computation, 9(3-4):0264-0289, 2009. Google Scholar
  14. Richard Jozsa and Maarten Van den Nest. Classical simulation complexity of extended Clifford circuits. Quantum Information and Computation, 14(7-8):0633-0648, 2014. Google Scholar
  15. E. Knill and R. Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672-5675, 1998. URL: http://dx.doi.org/10.1103/PhysRevLett.81.5672.
  16. Greg Kuperberg. How hard is it to approximate the Jones polynomial? Theory of Computing, 11:183-219 (article 6), 2015. URL: http://dx.doi.org/10.4086/toc.2015.v011a006.
  17. Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical Review Letters, 112(13):article 130502, 2014. URL: http://dx.doi.org/10.1103/PhysRevLett.112.130502.
  18. Xiaotong Ni and Maarten Van den Nest. Commuting quantum circuits: Efficient classical simulations versus hardness results. Quantum Information and Computation, 13(1-2):0054-0072, 2013. Google Scholar
  19. David Poulin, Robin Blume-Kohout, Raymond Laflamme, and Harold Ollivier. Exponential speedup with a single bit of quantum information: Measuring the average fidelity decay. Physical Review Letters, 92(17), 2004. URL: http://dx.doi.org/10.1103/PhysRevLett.92.177906.
  20. David Poulin, Raymond Laflamme, G. J. Milburn, and Juan Pablo Paz. Testing integrability with a single bit of quantum information. Physical Review A, 68(2):article 022302, 2003. URL: http://dx.doi.org/10.1103/PhysRevA.68.022302.
  21. D. J. Shepherd. Computation with unitaries and one pure qubit. arXiv.org e-Print archive, arXiv:quant-ph/0608132, 2006. URL: http://arxiv.org/abs/quant-ph/0608132.
  22. Daniel James Shepherd. Quantum Complexity : restrictions on algorithms and architectures. PhD thesis, Department of Computer Science, Faculty of Engineering, University of Bristol, 2009. arXiv.org e-Print archive, arXiv:1005.1425 [cs.CC]. URL: http://arxiv.org/abs/1005.1425.
  23. Peter W. Shor and Stephen P. Jordan. Estimating Jones polynomials is a complete problem for one clean qubit. Quantum Information and Computation, 8(8-9):0681-0714, 2008. Google Scholar
  24. Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, and Kazuyuki Tanaka. Commuting quantum circuits with few outputs are unlikely to be classically simulatable. In Computing and Combinatorics, 21st International Conference, COCOON 2015, volume 9198 of Lecture Notes in Computer Science, pages 223-234, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21398-9_18.
  25. Yasuhiro Takahashi, Takeshi Yamazaki, and Kazuyuki Tanaka. Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates. Quantum Information and Computation, 14(13-14):1149-1164, 2014. Google Scholar
  26. Barbara M. Terhal and David P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information and Computation, 4(2):134-145, 2004. Google Scholar
  27. Seinosuke Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865-877, 1991. URL: http://dx.doi.org/10.1137/0220053.
  28. John Watrous. Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences, 62(2):376-391, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1732.
  29. Edward Witten. Quantum field theory and the Jones polynomial. Communications in Mathematical Physics, 121(3):351-399, 1989. URL: http://dx.doi.org/10.1007/BF01217730.
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