Document Open Access Logo

A Complete Characterization of Unitary Quantum Space

Authors Bill Fefferman, Cedric Yen-Yu Lin

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.4.pdf
  • Filesize: 0.66 MB
  • 21 pages

Document Identifiers

Author Details

Bill Fefferman
Cedric Yen-Yu Lin

Cite AsGet BibTex

Bill Fefferman and Cedric Yen-Yu Lin. A Complete Characterization of Unitary Quantum Space. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 4:1-4:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.4

Abstract

Motivated by understanding the power of quantum computation with restricted number of qubits, we give two complete characterizations of unitary quantum space bounded computation. First we show that approximating an element of the inverse of a well-conditioned efficiently encoded 2^k(n) x 2^k(n) matrix is complete for the class of problems solvable by quantum circuits acting on O(k(n)) qubits with all measurements at the end of the computation. Similarly, estimating the minimum eigenvalue of an efficiently encoded Hermitian 2^k(n) x 2^k(n) matrix is also complete for this class. In the logspace case, our results improve on previous results of Ta-Shma by giving new space-efficient quantum algorithms that avoid intermediate measurements, as well as showing matching hardness results. Additionally, as a consequence we show that preciseQMA, the version of QMA with exponentially small completeness-soundess gap, is equal to PSPACE. Thus, the problem of estimating the minimum eigenvalue of a local Hamiltonian to inverse exponential precision is PSPACE-complete, which we show holds even in the frustration-free case. Finally, we can use this characterization to give a provable setting in which the ability to prepare the ground state of a local Hamiltonian is more powerful than the ability to prepare PEPS states. Interestingly, by suitably changing the parameterization of either of these problems we can completely characterize the power of quantum computation with simultaneously bounded time and space.
Keywords
  • Quantum complexity
  • space complexity
  • complete problems
  • QMA

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. Google Scholar
  2. Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computing (STOC), pages 20-29, 2003. Google Scholar
  3. Eric W. Allender and Klaus W. Wagner. Counting hierarchies: polynomial time and constant depth circuits. In G. Rozenberg and A. Salomaa, editors, Current trends in Theoretical Computer Science, pages 469-483. World Scientific, 1993. Google Scholar
  4. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 2009. Google Scholar
  5. Stuart J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inf. Process. Lett., 18(3):147-150, 1984. URL: http://dx.doi.org/10.1016/0020-0190(84)90018-8.
  6. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse hamiltonians. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 283-292. ACM, 2014. URL: http://dx.doi.org/10.1145/2591796.2591854.
  7. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Physical Review Letters, 114:090502, 2015. Google Scholar
  8. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 792-809, 2015. URL: https://arxiv.org/abs/quant-ph/1501.01715.
  9. Allan Borodin, Stephen A. Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1-3):113-136, 1983. URL: http://dx.doi.org/10.1016/S0019-9958(83)80060-6.
  10. Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-sat. arXiv preprint https://arxiv.org/abs/quant-ph/0602108, 2006.
  11. Andrew Childs. On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics, 294:581-603, 2010. Google Scholar
  12. Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1-3):2-21, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80041-3.
  13. Dean Doron, Amir Sarid, and Amnon Ta-Shma. On approximating the eigenvalues of stochastic matrices in probabilistic logspace. Electronic Colloquium on Computational Complexity (ECCC) preprint TR16-120, 2016. Google Scholar
  14. Dean Doron and Amnon Ta-Shma. On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 419-431, 2015. Google Scholar
  15. Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura. Space-efficient error reduction for unitary quantum computations. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 14:1-14:14, 2016. Google Scholar
  16. François Le Gall. Solving Laplacian systems in logarithmic space. arXiv preprint 1608.01426, 2016. Google Scholar
  17. David Gosset and Daniel Nagaj. Quantum 3-SAT is QMA1-complete. In Proceedings of the 54th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 756-765, 2013. Google Scholar
  18. Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review letters, 103(15):150502, 2009. Google Scholar
  19. Tsuyoshi Ito, Hirotada Kobayashi, and John Watrous. Quantum interactive proofs with weak error bounds. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ITCS), pages 266-275, 2012. Google Scholar
  20. Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A, 466(2115):809-830, 2010. URL: http://dx.doi.org/10.1098/rspa.2009.0433.
  21. Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A, 464(2100):3089-3106, 2008. URL: http://dx.doi.org/10.1098/rspa.2008.0189.
  22. Julia Kempe and Oded Regev. 3-local Hamiltonian is QMA-complete. Quantum Information & Computation, 3(3):258-264, 2003. Google Scholar
  23. A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi. Classical and Quantum Computation. American Mathematical Society, Boston, MA, USA, 2002. Google Scholar
  24. Chris Marriott and John Watrous. Quantum arthur-merlin games. Computational Complexity, 14(2):122-152, 2005. URL: http://dx.doi.org/10.1007/s00037-005-0194-x.
  25. Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information & Computation, 9(11):1053-1068, 2011. URL: http://www.rintonpress.com/xxqic9/qic-9-1112/1053-1068.pdf.
  26. M. A. Nielsen and I. L. Chuang. Quantum Information and Computation. Cambridge University Press, Cambridge, UK, 2000. Google Scholar
  27. John H. Reif. Logarithmic depth circuits for algebraic functions. SIAM J. Comput., 15(1):231-242, 1986. URL: http://dx.doi.org/10.1137/0215017.
  28. Norbert Schuch, Michael M. Wolf, Frank Verstraete, and J. Ignacio Cirac. Computational complexity of projected entangled pair states. Physical Review Letters, 98:140506, 2007. Google Scholar
  29. Yaoyun Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information & Computation, 3(1):84-92, 2003. URL: http://dl.acm.org/citation.cfm?id=2011508.2011515.
  30. Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 881-890. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488720.
  31. Barbara M. Terhal and David P. DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65(3):032325, 2002. URL: http://dx.doi.org/10.1103/PhysRevA.65.032325.
  32. Leslie G. Valiant. Quantum circuits that can be simulated classically in polynomial time. SIAM J. Comput., 31(4):1229-1254, 2002. URL: http://dx.doi.org/10.1137/S0097539700377025.
  33. Dieter van Melkebeek and Thomas Watson. Time-space efficient simulations of quantum computations. Theory of Computing, 8:1-51, 2012. Google Scholar
  34. F. Verstraete and J. I. Cirac. Renormalization algorithms for quantum-many body systems in two and higher dimensions. arXiv preprint https://arxiv.org/abs/cond-mat/0407066, 2004.
  35. John Watrous. Space-bounded quantum complexity. J. Comput. Syst. Sci., 59(2):281-326, 1999. URL: http://dx.doi.org/10.1006/jcss.1999.1655.
  36. John Watrous. On the complexity of simulating space-bounded quantum computations. Computational Complexity, 12(1):48-84, 2003. Google Scholar
  37. John Watrous. Quantum computational complexity. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 7174-7201. Springer, 2009. URL: http://dx.doi.org/10.1007/978-0-387-30440-3_428.
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 Imprint Privacy Contact