qiskit-textbook
qiskit-textbook copied to clipboard
qiskit-community
New section on quantum walks
What should the reader gain from this new content?
After reading this chapter, the student will know the basics of quantum walks and implement a quantum walk search algorithm that finds a marked vertex in a 4-dimensional hypercube via a quantum walk. The student will learn how to implement a quantum walk on the hypercube and how this, together with the inverse Fourier transform and a phase estimation, results in a quantum walk search algorithm. The implementation is based on the MNRS algorithm (linked below).
Where do you expect this new content to fit in with the current content?
Chapter 3. Preferably after quantum Fourier transform and phase estimation, both are used in the quantum walk search algorithm.
What material should this new content be based on?
It will be based on this algorithm (MNRS): https://arxiv.org/abs/quant-ph/0608026 and this description of its implementation: https://arxiv.org/abs/1907.09415 (p. 60 - 62)
The QFT and phase estimation implementations are based on the the implementations in Qiskit textbook.
Are you proposing to write this new content? (y/n)
Yes. We have written a master's thesis on quantum walks where we design quantum circuits for the quantum walk search algorithm and how to use it to find the hitting time for a quantum walk.
Proposed outline:
A short introduction on classical Markov chains (quantum walks are the quantum equivalence of a Markov chain) and quantum walks
How to quantize a Markov chain: describe the two most common models, quantum walk with coins and Szegedy’s quantum walk
Equivalence of coined and Szegedy’s quantum walk (important for the algorithm)
Implementation of one step of the quantum walk on a graph (we have implemented on hypercube, 2-dimensional lattice with periodic boundary conditions, complete bipartite graph and complete graph). This is something that we later will use in the quantum walk. We can either select one or more graphs
The quantum walk search algorithm and its implementation