Multidimensional quantum walks,recursion, and quantum divide & conquer

We introduce an object called a subspace graph that formalizes the technique of multidimen- sional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another applica- tion, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity.

• View at arXiv

Free Full Text ( Final Version , 557kb )