Document Open Access Logo

Span Programs and Quantum Space Complexity

Author Stacey Jeffery

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.4.pdf
  • Filesize: 0.62 MB
  • 37 pages

Document Identifiers

Author Details

Stacey Jeffery
  • CWI, Amsterdam, The Netherlands
  • QuSoft, Amsterdam, The Netherlands

Funding

Supported by an NWO WISE Fellowship, an NWO Veni Innovational Research Grant under project number 639.021.752, and QuantERA project QuantAlgo 680-91-03. SJ is a CIFAR Fellow in the Quantum Information Science Program.

Acknowledgements

I am grateful to Tsuyoshi Ito for discussions that led to the construction of approximate span programs from two-sided error quantum algorithms presented in Section 3.2, and to Alex B. Grilo and Mario Szegedy for insightful comments. I thank Robin Kothari for pointing out the improved separation between certificate complexity and approximate degree in [M. Bun and J. Thaler, 2017], which led to an improvement in from (log n)^(7/6) (using [S. Aaronson et al., 2016]) to (log n)^(2-o(1)) in Theorem 32.

Cite AsGet BibTex

Stacey Jeffery. Span Programs and Quantum Space Complexity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 4:1-4:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.4

Abstract

While quantum computers hold the promise of significant computational speedups, the limited size of early quantum machines motivates the study of space-bounded quantum computation. We relate the quantum space complexity of computing a function f with one-sided error to the logarithm of its span program size, a classical quantity that is well-studied in attempts to prove formula size lower bounds. In the more natural bounded error model, we show that the amount of space needed for a unitary quantum algorithm to compute f with bounded (two-sided) error is lower bounded by the logarithm of its approximate span program size. Approximate span programs were introduced in the field of quantum algorithms but not studied classically. However, the approximate span program size of a function is a natural generalization of its span program size. While no non-trivial lower bound is known on the span program size (or approximate span program size) of any concrete function, a number of lower bounds are known on the monotone span program size. We show that the approximate monotone span program size of f is a lower bound on the space needed by quantum algorithms of a particular form, called monotone phase estimation algorithms, to compute f. We then give the first non-trivial lower bound on the approximate span program size of an explicit function.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum space complexity
  • span programs

Metrics

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

Related Versions

References

  1. S. Aaronson, S. Ben-David, and R. Kothari. Separations in query complexity using cheat sheets. In Proceedings of the forty-eighth annual ACM Symposium on Theory of Computing (STOC 2016), pages 863-876, 2016. URL: http://arxiv.org/abs/1511.01937.
  2. S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. Google Scholar
  3. L. Babai, A. Gál, and A. Wigderson. Superpolynomial Lower Bounds for Monotone Span Programs. Combinatorica, 19:301-319, 1999. Google Scholar
  4. G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum Amplitude Amplification and Estimation. In S. J. Lomonaca and H. E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series Millennium Volume, pages 53-74. AMS, 2002. URL: http://arxiv.org/abs/quant-ph/0005055v1.
  5. M. Bun and J. Thaler. A Nearly Optimal Lower Bound on the Approximate Degree of AC⁰. In Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS 2017), 2017. URL: http://arxiv.org/abs/1703.05784.
  6. B. Fefferman and C. Lin. A Complete Characterization of Unitary Quantum Space. In Proceedings of the 2018 ACM Conference on Innovations in Theoretical Computer Science (ITCS 2018), pages 4:1-4:21, 2018. URL: http://arxiv.org/abs/1604.01384.
  7. A. Gàl. A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity, 10(4):277-296, 2001. Google Scholar
  8. T. Ito and S. Jeffery. Approximate Span Programs. Algorithmica, 81(6):2158-2195, 2019. URL: http://arxiv.org/abs/1507.00432.
  9. R. Jozsa, B. Kraus, A. Miyake, and J. Watrous. Matchgate and space-bounded quantum computations are equivalent. Proceedings of the Royal Society A, 466(2115), 2009. URL: https://doi.org/10.1098/rspa.2009.0433.
  10. M. Karchmer and A. Wigderson. On span programs. In Proceedings of the IEEE 8th Annual Conference on Structure in Complexity Theory, pages 102-111, 1993. Google Scholar
  11. A. Kitaev. Quantum measurements and the Abelian stabilizer problem, 1995. URL: http://arxiv.org/abs/quant-ph/9511026.
  12. T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy. Quantum Query Complexity of State Conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 344-353, 2011. Google Scholar
  13. S. V. Lokam. Complexity Lower Bounds using Linear Algebra. Now Publishers Inc., Hanover, MA, USA, 2009. URL: https://doi.org/10.1561/0400000011.
  14. T. Pitassi and R. Robere. Strongly Exponential Lower Bounds for Monotone Computation. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 1246-1255, 2017. Google Scholar
  15. A. A. Razborov. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica, 10(1):810093, 1990. Google Scholar
  16. A. A. Razborov. On Submodular Complexity Measures. In Poceedings of the London Mathematical Society symposium on Boolean function complexity, pages 76-83, 1992. Google Scholar
  17. B. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 544-551, 2009. URL: http://arxiv.org/abs/quant-ph/0904.2759.
  18. B. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291-319, 2012. Google Scholar
  19. R. Robere, T. Pitassi, B. Rossman, and S. A. Cook. Exponential Lower Bounds for Monotone Span Programs. In Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 406-415, 2016. URL: https://doi.org/10.1109/FOCS.2016.51.
  20. Alexander A. Sherstov. The Pattern Matrix Method. SIAM Journal on Computing, 40(6):1969–2000, 2009. Google Scholar
  21. J. Watrous. Space-Bounded Quantum Complexity. Journal of Computer and System Sciences, 59(2):281-326, 1999. 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 Imprint Privacy Contact