Quantum Walks on the Hypercube
| dc.creator | Moore, Cristopher | |
| dc.creator | Russell, Alexander | |
| dc.date | 2001-04-29 | |
| dc.date.accessioned | 2026-07-07T06:02:00Z | |
| dc.date.available | 2026-07-07T06:02:00Z | |
| dc.description | Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical counterparts. We study two quantum walks on the n-dimensional hypercube, one in discrete time and one in continuous time. In both cases we show that the quantum walk mixes in (π/4)n steps, faster than the O(n log n) steps required by the classical walk. In the continuous-time case, the probability distribution is {\em exactly} uniform at this time. More importantly, these walks expose several subtleties in the definition of mixing time for quantum walks. Even though the continuous-time walk has an O(n) instantaneous mixing time at which it is precisely uniform, it never approaches the uniform distribution when the stopping time is chosen randomly as in [AharonovAKV2001]. Our analysis treats interference between terms of different phase more carefully than is necessary for the walk on the cycle; previous general bounds predict an exponential, rather than linear, mixing time for the hypercube. | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0104137 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0104137 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/89458 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum Walks on the Hypercube | |
| dc.type | text |