Document Open Access Logo

Span Programs and Quantum Time Complexity

Authors Arjan Cornelissen, Stacey Jeffery, Maris Ozols, Alvaro Piedrafita

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.26.pdf
  • Filesize: 490 kB
  • 14 pages

Document Identifiers

Author Details

Arjan Cornelissen
  • QuSoft, Amsterdam, The Nehterlands
  • University of Amsterdam, The Netherlands
Stacey Jeffery
  • QuSoft, Amsterdam, The Netherlands
  • CWI, Amsterdam, The Netherlands
Maris Ozols
  • QuSoft, Amsterdam, The Netherlands
  • University of Amsterdam, The Netherlands
Alvaro Piedrafita
  • QuSoft, Amsterdam, The Netherlands
  • CWI, Amsterdam, The Netherlands

Funding

  • Jeffery, Stacey: Supported by an NWO Veni Innovational Research Grant under project number 639.021.752, an NWO WISE Grant, and QuantERA project QuantAlgo 680-91-03. SJ is a CIFAR Fellow in the Quantum Information Science Program.
  • Ozols, Maris: Supported by an NWO Vidi grant VI.Vidi.192.109.

Acknowledgements

Stacey Jeffery thanks Tsuyoshi Ito for illuminating discussions on the topic of span programs and time complexity.

Cite AsGet BibTex

Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita. Span Programs and Quantum Time Complexity. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.26

Abstract

Span programs are an important model of quantum computation due to their correspondence with quantum query and space complexity. While the query complexity of quantum algorithms obtained from span programs is well-understood, it is not generally clear how to implement certain query-independent operations in a time-efficient manner. In this work, we prove an analogous connection for quantum time complexity. In particular, we show how to convert a sufficiently-structured quantum algorithm for f with time complexity T into a span program for f such that it compiles back into a quantum algorithm for f with time complexity 𝒪̃(T). This shows that for span programs derived from algorithms with a time-efficient implementation, we can preserve the time efficiency when implementing the span program, which means that span programs capture time, query and space complexities and are a complete model of quantum algorithms. One practical advantage of being able to convert quantum algorithms to span programs in a way that preserves time complexity is that span programs compose very nicely. We demonstrate this by improving Ambainis’s variable-time quantum search result using our construction through a span program composition for the OR function.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum query complexity
  • Theory of computation → Algorithm design techniques
  • Theory of computation → Quantum complexity theory
Keywords
  • quantum query algorithms
  • span programs
  • variable-time quantum search

Metrics

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

Related Versions

References

  1. Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210-239, 2007. URL: https://doi.org/10.1137/S0097539705447311.
  2. Andris Ambainis. Quantum search with variable times. Theory of Computing Systems, 47(3):786-807, October 2010. URL: https://doi.org/10.1007/s00224-009-9219-1.
  3. Agnis Āriņš. Span-program-based quantum algorithms for graph bipartiteness and connectivity. In Jan Kofroň and Tomáš Vojnar, editors, Mathematical and Engineering Methods in Computer Science (MEMICS 2015), volume 9548 of Lecture Notes in Computer Science, pages 35-41. Springer International Publishing, 2016. URL: https://doi.org/10.1007/978-3-319-29817-7_4.
  4. Salman Beigi and Leila Taghavi. Quantum speedup based on classical decision trees. Quantum, 4(241), 2020. URL: https://doi.org/10.22331/q-2020-03-02-241.
  5. Aleksandrs Belovs. Learning-graph-based quantum algorithm for k-distinctness. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 207-216, October 2012. URL: https://doi.org/10.1109/FOCS.2012.18.
  6. Aleksandrs Belovs. Span programs for functions with constant-sized 1-certificates. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, pages 77-84, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2213977.2213985.
  7. Aleksandrs Belovs and Ben W. Reichardt. Span programs and quantum algorithms for st-connectivity and claw detection. In Leah Epstein and Paolo Ferragina, editors, Algorithms - ESA 2012, volume 7501 of Lecture Notes in Computer Science, pages 193-204, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-33090-2_18.
  8. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian dynamics with a truncated Taylor series. Phys. Rev. Lett., 114(9):090502, March 2015. URL: https://doi.org/10.1103/PhysRevLett.114.090502.
  9. Chris Cade, Ashley Montanaro, and Aleksandrs Belovs. Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness. Quantum Information and Computation, 18(1&2):0018-0050, February 2018. URL: https://doi.org/10.26421/QIC18.1-2.
  10. Arjan Cornelissen, Stacey Jeffery, Maris Ozols, and Alvaro Piedrafita. Span programs and quantum time complexity, 2020. URL: http://arxiv.org/abs/2005.01323.
  11. Tsuyoshi Ito and Stacey Jeffery. Approximate span programs. Algorithmica, 81(6):2158-2195, 2019. URL: https://doi.org/10.1007/s00453-018-0527-1.
  12. Michael Jarret, Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum algorithms for connectivity and related problems. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1-49:13, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.49.
  13. Stacey Jeffery. Span programs and quantum space complexity. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1-4:37, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.4.
  14. Stacey Jeffery and Shelby Kimmel. Quantum algorithms for graph connectivity and formula evaluation. Quantum, 1:26, August 2017. URL: https://doi.org/10.22331/q-2017-08-17-26.
  15. Mauricio Karchmer and Avi Wigderson. On span programs. In Proceedings of the 8th Annual IEEE Conference on Structure in Complexity Theory, pages 102-111, May 1993. URL: https://doi.org/10.1109/SCT.1993.336536.
  16. Troy Lee, Frédéric Magniez, and Miklos Santha. Improved quantum query algorithms for triangle detection and associativity testing. Algorithmica, 77(2):459-486, 2017. URL: https://doi.org/10.1007/s00453-015-0084-9.
  17. Ben W. Reichardt. Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pages 544-551, October 2009. URL: https://doi.org/10.1109/FOCS.2009.55.
  18. Ben W. Reichardt and Robert Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291-319, 2012. URL: https://doi.org/10.4086/toc.2012.v008a013.
  19. Qisheng Wang and Mingsheng Ying. Quantum random access stored-program machines, 2020. URL: http://arxiv.org/abs/2003.03514.
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