Quantum Subroutine Composition
share
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 p_i, and the cost of the subroutine on input i is T_i, incurs expected cost Q∑_i p_i E[T_i] 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 q_i is the average query weight on i over all queries, the cost from all quantum subroutine queries is Q∑_i q_i E[T_i]. 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π_u P_u,v E[T_u,v^2]), where T_u,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 (*).
READ FULL TEXT