Abstract

In 1996, Farhi and Gutmann proposed a generalization of the query model in quantum computing, where the queries can be performed continuously in time. Since then, some interesting quantum algorithms have been discovered in this model, including the breakthrough quantum algorithm for evaluating AND-OR trees by Farhi, Goldstone, and Gutmann in 2007, which was subsequently translated into a standard discrete-time query algorithm. We show that ANY quantum algorithm in the continuous-time model can be translated into one in the discrete-time model within a sub-logarithmic factor, and also efficiently with respect to space usage. This is based on a 2009 paper with Daniel Gottesman, Michele Mosca, Rolando Somma, and David Yonge-Mallo and a paper in preparation with Dominic Berry and Sevag Gharabian.