Spatial search by continuous-time quantum walk with multiple marked vertices. (English) Zbl 1338.81152
Summary: In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of \(K_M\) complete graphs” with all configurations of two marked vertices, two configurations of \(M+1\) marked vertices, and two configurations of \(2(M+1)\) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration’s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.
MSC:
| 81P68 | Quantum computation |
| 68P10 | Searching and sorting |
| 60G50 | Sums of independent random variables; random walks |
Keywords:
Grover’s algorithm; quantum search; spatial search; quantum random walk; multiple marked verticesReferences:
| [1] | Schrödinger, E.: An undulatory theory of the mechanics of atoms and molecules. Phys. Rev. 28, 1049-1070 (1926) · JFM 52.0965.07 · doi:10.1103/PhysRev.28.1049 |
| [2] | Sakurai, J.J.: Modern Quantum Mechanics, Revised edn. Addison Wesley, Boston (1993) |
| [3] | Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915-928 (1998) · Zbl 0988.83043 · doi:10.1103/PhysRevA.58.915 |
| [4] | Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004) · doi:10.1103/PhysRevA.70.022314 |
| [5] | Farhi, E., Goldstone, J., Gutmann, S.: A quantum algorithm for the Hamiltonian NAND tree. Theory Comput. 4(8), 169-190 (2008) · Zbl 1213.68284 · doi:10.4086/toc.2008.v004a008 |
| [6] | Rudinger, K., Gamble, J.K., Wellons, M., Bach, E., Friesen, M., Joynt, R., Coppersmith, S.N.: Noninteracting multiparticle quantum random walks applied to the graph isomorphism problem for strongly regular graphs. Phys. Rev. A 86, 022334 (2012) · doi:10.1103/PhysRevA.86.022334 |
| [7] | Childs, A.M.: Universal computation by quantum walk. Phys. Rev. Lett. 102, 180501 (2009) · doi:10.1103/PhysRevLett.102.180501 |
| [8] | Mochon, C.: Hamiltonian oracles. Phys. Rev. A 75, 042313 (2007) · doi:10.1103/PhysRevA.75.042313 |
| [9] | Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. STOC ’96, pp. 212-219. ACM, New York (1996) · Zbl 0922.68044 |
| [10] | Farhi, E., Gutmann, S.: Analog analogue of a digital quantum computation. Phys. Rev. A 57(4), 2403-2406 (1998) · doi:10.1103/PhysRevA.57.2403 |
| [11] | Wong, T.G.: Nonlinear quantum search. PhD dissertation (2014) · JFM 52.0965.07 |
| [12] | Wong, T.G.: Grover search with lackadaisical quantum walks. J. Phys. A: Math. Theor. 48, 435304 (2015). doi:10.1088/1751-8113/48/43/435304 · Zbl 1326.81053 · doi:10.1088/1751-8113/48/43/435304 |
| [13] | Wong, T.G.: Quantum walk search through potential barriers. arXiv:1503.06605 [quant-ph] (2015) · Zbl 1354.81010 |
| [14] | Janmark, J., Meyer, D.A., Wong, T.G.: Global symmetry is unnecessary for fast quantum search. Phys. Rev. Lett. 112, 210502 (2014) · doi:10.1103/PhysRevLett.112.210502 |
| [15] | Meyer, D.A., Wong, T.G.: Connectivity is a poor indicator of fast quantum search. Phys. Rev. Lett. 114, 110503 (2015) · Zbl 1274.93130 · doi:10.1103/PhysRevLett.114.110503 |
| [16] | Novo, L., Chakraborty, S., Mohseni, M., Neven, H., Omar, Y.: Systematic dimensionality reduction for quantum walks: optimal spatial search and transport on non-regular graphs. Sci. Rep. 5, 13304 (2015) · doi:10.1038/srep13304 |
| [17] | Wong, T.G., Ambainis, A.: Quantum search with multiple walk steps per oracle query. Phys. Rev. A 92, 022338 (2015) · doi:10.1103/PhysRevA.92.022338 |
| [18] | Kempe, J.: Quantum random walks: an introductory overview. Contemp. Phys. 44(4), 307-327 (2003) · doi:10.1080/00107151031000110776 |
| [19] | Meyer, D.A.: From quantum cellular automata to quantum lattice gases. J. Stat. Phys. 85(5-6), 551-574 (1996) · Zbl 0952.37501 · doi:10.1007/BF02199356 |
| [20] | Meyer, D.A.: On the absence of homogeneous scalar unitary cellular automata. Phys. Lett. A 223(5), 337-340 (1996) · Zbl 1037.82529 · doi:10.1016/S0375-9601(96)00745-1 |
| [21] | Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pp. 1099-1108 (2005) · Zbl 1297.68076 |
| [22] | Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys. Rev. A 67, 052307 (2003) · doi:10.1103/PhysRevA.67.052307 |
| [23] | Nahimovs, N., Rivosh, A.: Quantum walks on two-dimensional grids with multiple marked locations. In: Proceedings of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM ’16. Harrachov (2016). To appear arXiv:1507.03788 · Zbl 1397.68080 |
| [24] | Ambainis, A., Rivosh, A.: Quantum walks with multiple or moving marked locations. In: V. Geffert, J. Karhumöki, A. Bertoni, B. Preneel, P. Návrat, M. Bieliková (eds.) Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2008, pp. 485-496 (2008) · Zbl 1132.68383 |
| [25] | Nahimovs, N., Rivosh, A.: Exceptional congurations of quantum walks with Grover’s coin. In: Proceedings of the 10th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS ’15. Telc̆ (2015). To appear arXiv:1509.06862 |
| [26] | Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’04, pp. 32-41 (2004) |
| [27] | Krovi, H., Magniez, F., Ozols, M., Roland, J.: Quantum walks can find a marked element on any graph. Algorithmica (2015). doi:10.1007/s00453-015-9979-8 · Zbl 1336.68083 |
| [28] | Wong, T.G.: Faster quantum walk search on a weighted graph. Phys. Rev. A 92, 032320 (2015) · doi:10.1103/PhysRevA.92.032320 |
| [29] | Wong, T.G.: Diagrammatic approach to quantum search. Quantum Inf. Process. 14(6), 1767-1775 (2015) · Zbl 1317.81071 · doi:10.1007/s11128-015-0959-3 |
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.
