I’m trying to grok quantum walks, and would like to create an example that walks a perfect binary tree to find the one and only marked leaf node. Is this possible? If so, suppose the depth of the tree is five. Would that require a circuit with five wires? Would it best be realized with a Discrete Time Quantum Walk, flipping a Hadamard Coin five times? Regardless of whether these questions are on the right track, and although I’ve read a lot of papers on the subject, I’m currently at a loss for how to implement what I’ve described. Any concrete pointers?

  • $\begingroup$ If you could walk a perfect binary tree of depth $5$ to find a marked item with only $5$ Hadamard coins, you would have found $1$ item out of $32$ total in only $5$ steps - exponentially faster than searching $32$ elements for $1$ marked item. This may be difficult. Nonetheless, although it's for continuous time walks have you seen the paper on welded trees? There is an exponential speedup here. $\endgroup$ – Mark S Apr 27 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.