License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.26
URN: urn:nbn:de:0030-drops-126947
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12694/
Go to the corresponding LIPIcs Volume Portal

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

Span Programs and Quantum Time Complexity

pdf-format:
LIPIcs-MFCS-2020-26.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{cornelissen_et_al:LIPIcs:2020:12694,
  author =	{Arjan Cornelissen and Stacey Jeffery and Maris Ozols and Alvaro Piedrafita},
  title =	{{Span Programs and Quantum Time Complexity}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12694},
  URN =		{urn:nbn:de:0030-drops-126947},
  doi =		{10.4230/LIPIcs.MFCS.2020.26},
  annote =	{Keywords: quantum query algorithms, span programs, variable-time quantum search}
}

Keywords: quantum query algorithms, span programs, variable-time quantum search
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI