Arjan Cornelissen - Span programs and quantum time complexity

Arjan Cornelissen - QuSoft - University of Amsterdam

The span program formalism is an important tool in the design of quantum algorithms. It is known that there is a constructive correspondence between span programs and quantum algorithms with optimal query complexity, making this framework especially suitable for designing query-efficient algortihms. However, much less is known about the time complexity of the algorithms produced by this formalism. In our work, we make progress in understanding the time complexity of quantum algorithms compiled from span programs.

We provide a construction that turns a quantum algorithm into a span program, and subsequently back into a quantum algorithm, in such a way that the success probability, and the query, time and space complexity are not significantly affected. This implies that for every boolean function, there exists a span program that produces a quantum algorithm that evaluates this function with optimal time complexity, up to polylogarithmic factors, indicating that span programs are also useful in the design of time-efficient algorithms.

We subsequently demonstrate the applicability of our techniques by improving the best-known quantum algorithm for the variable-time search problem. Whereas the previous construction only allowed for a speed-up in either the query or time complexity, we obtain the same speed-up in both simultaneously.