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?
Quantum Walk may not perform in optimal ways over a conventional and determinisitc binary tree data structure. In a quantum walk experimental setup, the coin will not follow a binomial distribution. Construction of a quantum superposition based index for a tree data structure would be a better model. In one of the most popular implementations, a quantum walk involves a coin flip followed by a bit shift operator. The quantum walk involves a rotation of the coin space followed by the conditional shift operator. The quantum walk begins to differ from the classical walk from the initial epochs onwards. This asymmetry arises because the Hadamard coin treats the two directions |left⟩ and |right⟩ differently.
The quantum walk propagates quadratically faster than the classical walk. the quantum walk spreads faster, at a rate proportional to the number of steps, instead of the square root of the number of steps as in the classical case, a quadratic speed up. An interesting addition to this model is to consider quantum logical states for the coin flipping experiment. The solution is to make the coin quantum too, and give it a unitary twist instead of a random toss. The quantum coin keeps track of which way you arrived at your location, allowing you to retrace your steps.
Shenvi showed that a quantum walk could search an unsorted database with a quadratic speed up. The first quantum algorithm for this problem is due to Grover, using a different method to obtain the same quadratic speed up. A classical search of an unsorted database potentially has to check all N entries in the database, and on average has to check at least half. A quantum search only needs to make √N queries, though the queries ask for many answers in superposition. The quantum walk search algorithm sort of works backwards, starting in a uniform superposition over the whole database, and converging on the answer as the quantum walk proceeds. Quantum walks are reversible: a quantum walk running backwards is also a quantum walk. A quantum walk travels through all the paths in superposition, and the quantum interference between different paths allows the quantum walker to figure out which way is forward right up to the exit, which it finds in time proportional to the width of the network.
Hence a better and scalable quantum walk implementation would be to using the combination of a Quantum Grover Search, Quantum Bloom Filter and a Quantum Superposition based Merkel Tree or a graph isomorphism based data structure.