Efficient discrete-time simulations of continuous-time quantum query algorithms

Understand

The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time.

• Interesting algorithms have been discovered in this model, such as an algorithm for evaluating nand trees more efficiently than any classical algorithm.
• Subsequent work has shown that there also exists an efficient algorithm for nand trees in the discrete query model; however, there is no efficient conversion known for continuous-time query algorithms for arbitrary problems.
• We show that any quantum algorithm in the continuous-time query model whose total query time is T can be simulated by a quantum algorithm in the discrete query model that makes O[T log(T) / log(log(T))] queries.