11
$\begingroup$

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?

$\endgroup$
  • $\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 '19 at 22:31
1
$\begingroup$

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.

enter image description here

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.

References

Search Over a Quantum Walk, Equivalence of Szegedy’s and Coined Quantum Walks, Grover Search with Lackadaisical Quantum Walks, Quantum Walks and their applications, A Quantum Walk Search Algorithm

| improve this answer | |
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.