2
$\begingroup$

I am working on a project to implement a quantum random walk through two glued binary trees of depth n=4.

glued binary trees

What is the difference in the math behind characterizing a quantum walk in discrete or continuous time? How would a simulation of either quantum walk differ?

PS: This is my first post on this site, so I apologize if I am accidentally violating rules (spoken or unspoken)

$\endgroup$
1
  • 1
    $\begingroup$ Your question looks roughly okay to me, but not I decide, instead a vote. This vote wasn't initiated until now. They only problem what I can see that it seems a little bit too broad (imagine a question, "What is the difference between fox and dog?" - you wouldn't even know, where to start to answer it). Dig more deeply on the details. $\endgroup$
    – peterh
    May 2 '17 at 18:27
1
$\begingroup$

So, the basic difference between discrete and continuous time quantum walk is how your initial state evolves.

In DTQW you have your initial state defined in two spaces: coin and position. Thus the evolution must be performed by subsequently applying two unitary operations defined on those spaces respectively.

In CTQW the evolution of a walker on a graph is described by Schrodinger equation with Hamiltonian defined as Laplacian or as an adjacency matrix of a given graph. Just like in CT Random Walks vertices of a graph will continuously exchange probabilities.

More on that and about CTQW on glued trees can be found here.

Since your tree is designed in such a way that at every position the walker has two options of propagating further you can use DTQW, which would be similar to a Hadamard walk on line

Simulating CTQW and DTQW differs in the way you describe evolution. In DTQW you basically need to create a loop where you will apply the same coin and shift operators over and over again. In CTQW you will be applying an operator which continously evolves in time. In the second case you have the ability to define different timesteps while in DTQW you are stuck with your operators.

$\endgroup$
0
$\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

$\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.