On mixing in continuous-time quantum walks on some circulant graphs

作者: Christino Tamon , Ryan Belk , Carolyn Wendler , Amir Ahmadi

DOI: 10.26421/QIC3.6-4

关键词:

摘要: Classical random walks on well-behaved graphs are rapidly mixing towards the uniform distribution. Moore and Russell showed that continuous-time quantum walk hypercube is instantaneously mixing. We show other do not exhibit this prove only amongst balanced complete multipartite have instantaneous exactly property two, three four vertices, cycle graph vertices. Our proof exploits circulant structure of these graphs. Furthermore, we conjecture most cycles Cayley symmetric group lack as well.

参考文章(10)
Andrew M. Childs, Sam Gutmann, Edward Farhi, An Example of the Difference Between Quantum and Classical Random Walks Quantum Information Processing. ,vol. 1, pp. 35- 43 ,(2002) , 10.1023/A:1019609420309
Julia Kempe, Quantum Random Walks Hit Exponentially Faster arXiv: Quantum Physics. ,(2002)
Heath Gerhardt, John Watrous, Continuous-time quantum walks on the symmetric group randomization and approximation techniques in computer science. pp. 290- 301 ,(2003) , 10.1007/978-3-540-45198-3_25
Cristopher Moore, Alexander Russell, Quantum Walks on the Hypercube randomization and approximation techniques in computer science. pp. 164- 178 ,(2002) , 10.1007/3-540-45726-7_14
Edward Farhi, Sam Gutmann, Quantum computation and decision trees Physical Review A. ,vol. 58, pp. 915- 928 ,(1998) , 10.1103/PHYSREVA.58.915
Daniel A. Spielman, Andrew M. Childs, Richard Cleve, Sam Gutmann, Edward Farhi, Enrico Deotto, Exponential algorithmic speedup by a quantum walk symposium on the theory of computing. pp. 59- 68 ,(2003) , 10.1145/780542.780552
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh Vazirani, Quantum walks on graphs Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 50- 59 ,(2001) , 10.1145/380752.380758
Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous, One-dimensional quantum walks Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 37- 49 ,(2001) , 10.1145/380752.380757
Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms ,(1995)
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman, Exponential algorithmic speedup by quantum walk arXiv: Quantum Physics. ,(2002) , 10.1145/780542.780552