Document Open Access Logo

Power of Uninitialized Qubits in Shallow Quantum Circuits

Authors Yasuhiro Takahashi, Seiichiro Tani

PDF
Thumbnail PDF

File

LIPIcs.STACS.2018.57.pdf
  • Filesize: 0.64 MB
  • 13 pages

Document Identifiers

Author Details

Yasuhiro Takahashi
Seiichiro Tani

Cite As Get BibTex

Yasuhiro Takahashi and Seiichiro Tani. Power of Uninitialized Qubits in Shallow Quantum Circuits. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 57:1-57:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.STACS.2018.57

Abstract

We study the computational power of shallow quantum circuits
with O(log n) initialized and n^{O(1)} uninitialized ancillary
qubits, where n is the input length and the initial state of
the uninitialized ancillary qubits is arbitrary. First, we show
that such a circuit can compute any symmetric function on n bits
that is classically computable in polynomial time. Then, we
regard such a circuit as an oracle and show that a
polynomial-time classical algorithm with the oracle can estimate
the elements of any unitary matrix corresponding to a
constant-depth quantum circuit on n qubits. Since it seems unlikely
that these tasks can be done with only O(log n) initialized
ancillary qubits, our results give evidences that adding
uninitialized ancillary qubits increases the computational power
of shallow quantum circuits with only O(log n) initialized
ancillary qubits. Lastly, to understand the limitations of
uninitialized ancillary qubits, we focus on
near-logarithmic-depth quantum circuits with them and show
the impossibility of computing the parity function on n bits.

Subject Classification

Keywords
  • quantum circuit complexity
  • shallow quantum circuit
  • uninitialized qubit

Metrics

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

References

  1. A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter. Elementary gates for quantum computation. Physical Review A, 52(5):3457-3467, 1995. Google Scholar
  2. D. Bera. Quantum circuits: power and limitations. PhD thesis, Boston University, 2010. Google Scholar
  3. D. Bera. A lower bound method for quantum circuits. Information Processing Letters, 111(15):723-726, 2011. Google Scholar
  4. S. Bravyi, D. Gosset, and R. König. Quantum advantage with shallow circuits, 2017. arXiv:1704.00690. Google Scholar
  5. H. Buhrman, R. Cleve, M. Koucký, B. Loff, and F. Speelman. Computing with a full memory: catalytic space. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), pages 857-866, 2014. Google Scholar
  6. R. Cleve and J. Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), pages 526-536, 2000. Google Scholar
  7. D. P. DiVincenzo. The physical implementation of quantum computation. Fortschritte der Physik, 48(9-11):771-783, 2000. Google Scholar
  8. M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang. Quantum lower bounds for fanout. Quantum Information and Computation, 6(1):46-57, 2006. Google Scholar
  9. S. Fenner, F. Green, S. Homer, and Y. Zhang. Bounds on the power of constant-depth quantum circuits. In Proceedings of Fundamentals of Computation Theory (FCT), volume 3623 of Lecture Notes in Computer Science, pages 44-55, 2005. Google Scholar
  10. F. Green, S. Homer, C. Moore, and C. Pollett. Counting, fanout, and the complexity of quantum ACC. Quantum Information and Computation, 2(1):35-65, 2002. Google Scholar
  11. P. Høyer and R. Špalek. Quantum fan-out is powerful. Theory of Computing, 1(5):81-103, 2005. Google Scholar
  12. S. Jukna. Boolean Function Complexity: Advances and Frontiers. Springer, 2012. Google Scholar
  13. E. Knill and R. Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672-5675, 1998. Google Scholar
  14. T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O'Brien. Quantum computing. Nature, 464:45-53, 2010. Google Scholar
  15. G. De las Cuevas, W. Dür, M. van den Nest, and M. A. Martin-Delgado. Quantum algorithms for classical lattice models. New Journal of Physics, 13(093021), 2011. Google Scholar
  16. C. Moore and M. Nilsson. Parallel quantum computation and quantum codes. SIAM Journal on Computing, 31(3):799-815, 2001. Google Scholar
  17. X. Ni and M. van den Nest. Commuting quantum circuits: efficient classical simulations versus hardness results. Quantum Information and Computation, 13(1&2):54-72, 2013. Google Scholar
  18. M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google Scholar
  19. Y. Takahashi and N. Kunihiro. A quantum circuit for Shor’s factoring algorithm using 2n+2 qubits. Quantum Information and Computation, 6(2):184-192, 2006. Google Scholar
  20. Y. Takahashi and S. Tani. Collapse of the hierarchy of constant-depth exact quantum circuits. Computational Complexity, 25(4):849-881, 2016. Google Scholar
  21. Y. Takahashi and S. Tani. Power of uninitialized qubits in shallow quantum circuits, 2017. arXiv:1608.07020v3. Google Scholar
  22. Y. Takahashi, T. Yamazaki, and K. 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
  23. J. Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1-2):48-84, 2003. 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