Quantum subroutine composition

An important tool in algorithm design is the ability to build algorithms from other algorithms that run as subroutines. In the case of quantum algorithms, a subroutine may be called on a superposition of different inputs, which complicates things. For example, a classical algorithm that calls a subroutine Q times, where the average probability of querying the subroutine on input i is pi, and the cost of the subroutine on input i is Ti, incurs expected cost Q∑ipiE[Ti] from all subroutine queries. While this statement is obvious for classical algorithms, for quantum algorithms, it is much less so, since naively, if we run a quantum subroutine on a superposition of inputs, we need to wait for all branches of the superposition to terminate before we can apply the next operation. We nonetheless show an analogous quantum statement (*): If qi is the average query weight on i over all queries, the cost from all quantum subroutine queries is Q∑iqiE[Ti]. Here the query weight on i for a particular query is the probability of measuring i in the input register if we were to measure right before the query. We prove this result using the technique of multidimensional quantum walks, recently introduced in arXiv:2208.13492. We present a more general version of their quantum walk edge composition result, which yields variable-time quantum walks, generalizing variable-time quantum search, by, for example, replacing the update cost with ∑u,vπuPu,vE[T2u,v]−−−−−−−−−−−−−−√, where Tu,v is the cost to move from vertex u to vertex v. The same technique that allows us to compose quantum subroutines in quantum walks can also be used to compose in any quantum algorithm, which is how we prove (*).

• View at Publisher

Free Full Text ( Final Version , 798kb )