Arjan Cornelissen - QuSoft - University of Amsterdam, June 22, 2020 at 2:30 p.m. Zoom webinar
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.
Please click the link below to join the webinar:
https://zoom.us/j/94513650220?pwd=TnFidUliL2MyUnhxYlB2ZWtNOVBVdz09
Password: CornelQS1
Or iPhone one-tap :
US: +13126266799, 94513650220#, 0#, 396841# or
+13462487799, 94513650220#, 0#, 396841#
Or Telephone:
Dial(for higher quality, dial a number based on your current location):
US: +1 312 626 6799 or +1 346 248 7799 or +1 646 558 8656 or +1 669 900 9128
or +1 253 215 8782 or +1 301 715 8592
Webinar ID: 945 1365 0220
Password: 396841
International numbers available: https://zoom.us/u/aI6hgiRTL