On the hitting times of quantum versus random walks. (English) Zbl 1236.68072
Summary: The hitting time of a classical random walk (Markov chain) is the time required to detect the presence of – or equivalently, to find – a marked state. The hitting time of a quantum walk is subtler to define; in particular, it is unknown whether the detection and finding problems have the same time complexity. In this paper we define new Monte Carlo type classical and quantum hitting times, and we prove several relationships among these and the already existing Las Vegas type definitions. In particular, we show that for some marked state the two types of hitting time are of the same order in both the classical and the quantum case.
Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of A. Tulsi from his recent theorem in [“Faster quantum-walk algorithm for the two-dimensional spatial search”, Phys. Rev. A (3) 78, No. 1, 012310, 6 p. (2008; doi:10.1103/PhysRevA.78.012310)] for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks – the quantum analogue of state-transitive reversible ergodic Markov chains.
Further, we prove that for any reversible ergodic Markov chain \(P\), the quantum hitting time of the quantum analogue of \(P\) has the same order as the square root of the classical hitting time of \(P\). We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.
Then, we present new quantum algorithms for the detection and finding problems. The complexities of both algorithms are related to the new, potentially smaller, quantum hitting times. The detection algorithm is based on phase estimation and is particularly simple. The finding algorithm combines a similar phase estimation based procedure with ideas of A. Tulsi from his recent theorem in [“Faster quantum-walk algorithm for the two-dimensional spatial search”, Phys. Rev. A (3) 78, No. 1, 012310, 6 p. (2008; doi:10.1103/PhysRevA.78.012310)] for the 2D grid. Extending his result, we show that we can find a unique marked element with constant probability and with the same complexity as detection for a large class of quantum walks – the quantum analogue of state-transitive reversible ergodic Markov chains.
Further, we prove that for any reversible ergodic Markov chain \(P\), the quantum hitting time of the quantum analogue of \(P\) has the same order as the square root of the classical hitting time of \(P\). We also investigate the (im)possibility of achieving a gap greater than quadratic using an alternative quantum walk. In doing so, we define a notion of reversibility for a broad class of quantum walks and show how to derive from any such quantum walk a classical analogue. For the special case of quantum walks built on reflections, we show that the hitting time of the classical analogue is exactly the square of the quantum walk.
MSC:
| 68Q12 | Quantum algorithms and complexity in the theory of computing |
| 81P68 | Quantum computation |
| 60G50 | Sums of independent random variables; random walks |
| 60J20 | Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) |
References:
| [1] | Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory Comput. 1(4), 47–79 (2005) · Zbl 1213.68279 · doi:10.4086/toc.2005.v001a004 |
| [2] | Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proceedings of the 33rd ACM Symposium on Theory of Computing, pp. 50–59 (2001) · Zbl 1323.81020 |
| [3] | Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pp. 37–49 (2001) · Zbl 1323.81021 |
| [4] | Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 1099–1108 (2005) · Zbl 1297.68076 |
| [5] | Ambainis, A.: Quantum walks and their algorithmic applications. Int. J. Quantum Inf. 1, 507–518 (2003) · Zbl 1069.81505 · doi:10.1142/S0219749903000383 |
| [6] | Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210–239 (2007) · Zbl 1134.81010 · doi:10.1137/S0097539705447311 |
| [7] | Buhrman, H., Špalek, R.: Quantum verification of matrix products. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 880–889 (2006) · Zbl 1192.81056 |
| [8] | Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. Ser. A, Math. Phys. Sci. 454, 339–354 (1998) · Zbl 0915.68050 · doi:10.1098/rspa.1998.0164 |
| [9] | Childs, A., Goldstone, J.: Spatial search and the Dirac equation. Phys. Rev. A 70, 042312 (2004) · Zbl 1227.81156 |
| [10] | Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 212–219 (1996) · Zbl 0922.68044 |
| [11] | Kitaev, A.: Quantum measurements and the Abelian stabilizer problem. ECCC technical report 96-003 and arXiv:quant-ph/9511026 (1995) |
| [12] | Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding is as easy as detecting for quantum walks. In: Proceedings of 37st International Colloquium on Automata, Languages and Programming, LNCS (2010) · Zbl 1288.68072 |
| [13] | Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation. Graduate Studies in Mathematics, vol. 47. Am. Math. Soc., Providence (2002) · Zbl 1022.68001 |
| [14] | Magniez, F., Nayak, A.: Quantum complexity of testing group commutativity. Algorithmica 48(3), 221–232 (2007) · Zbl 1121.68056 · doi:10.1007/s00453-007-0057-8 |
| [15] | Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceedings of the 39th ACM Symposium on Theory of Computing, pp. 575–584 (2007) · Zbl 1232.68053 |
| [16] | Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 611–629 (2007) · Zbl 1166.68032 · doi:10.1137/050643684 |
| [17] | Nayak, A., Vishwanath, A.: Quantum walk on the line. Technical report. arXiv:quant-ph/0010117 (2000) |
| [18] | Santha, M.: Quantum walk based search algorithms. In: Proceedings of the 5th Conference on Theory and Applications of Models of Computation, LNCS, vol. 4978, pp. 31–46 (2008) · Zbl 1139.68338 |
| [19] | Shenvi, N., Kempe, J., Whaley, K.: A quantum random walk search algorithm. Phys. Rev. A 67, 052307 (2003) · doi:10.1103/PhysRevA.67.052307 |
| [20] | Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Symposium on Foundations of Computer Science, pp. 32–41 (2004) |
| [21] | Tulsi, A.: Faster quantum walk algorithm for the two dimensional spatial search. Phys. Rev. A 78, 012310 (2008) · Zbl 1255.81118 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
