Quantum Walks on Necklaces and Mixing
arXiv:1111.4433
Abstract
We analyze continuous-time quantum walks on necklace graphs - cyclical graphs consisting of many copies of a smaller graph (pearl). Using a Bloch-type ansatz for the eigenfunctions, we block-diagonalize the Hamiltonian, reducing the effective size of the problem to the size of a single pearl. We then present a general approach for showing that the mixing time scales (with growing size of the necklace) similarly to that of a simple walk on a cycle. Finally, we present results for mixing on several necklace graphs.
arXiv comment11 pages, 5 figures, typos corrected, acknowledgements updated
References in corpus (8)
- Quantum Computation and Decision Trees
- Exponential algorithmic speedup by quantum walk
- Simple proof of equivalence between adiabatic quantum computation and the circuit model
- Hamiltonian complexity
- A new construction for a QMA complete 3-local Hamiltonian
- Hamiltonian Quantum Cellular Automata in 1D
- Universal 2-local Hamiltonian Quantum Computing
- Mixing Times in Quantum Walks on Two-Dimensional Grids