×

Element distinctness revisited. (English) Zbl 1451.81179

Summary: The element distinctness problem is the problem of determining whether the elements of a list are distinct, that is, if \(x=(x_1,\dots ,x_N)\) is a list with \(N\) elements, we ask whether the elements of \(x\) are distinct or not. The solution in a classical computer requires \(N\) queries because it uses sorting to check whether there are equal elements. In the quantum case, it is possible to solve the problem in \(O(N^{2/3})\) queries. There is an extension which asks whether there are \(k\) colliding elements, known as element \(k\)-distinctness problem. This work obtains optimal values of two critical parameters of A. Ambainis’ seminal quantum algorithm [SIAM J. Comput. 37, No. 1, 210–239 (2007; Zbl 1134.81010)]. The first critical parameter is the number of repetitions of the algorithm’s main block, which inverts the phase of the marked elements and calls a subroutine. The second parameter is the number of quantum walk steps interlaced by oracle queries. We show that, when the optimal values of the parameters are used, the algorithm’s success probability is \(1-O(N^{1/(k+1)})\), quickly approaching 1. The specification of the exact running time and success probability is important in practical applications of this algorithm.

MSC:

81P68 Quantum computation
81U05 \(2\)-body potential quantum scattering theory
60G50 Sums of independent random variables; random walks

Citations:

Zbl 1134.81010
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Yao, A.C.C.: Near-optimal time-space tradeoff for element distinctness. In: Proceedings of 29th Annual Symposium on Foundations of Computer Science, pp. 91-97 (1988)
[2] Grigoriev, D; Karpinski, M; Heide, FM; Smolensky, R, A lower bound for randomized algebraic decision trees, Comput. Complex., 6, 357-375, (1996) · Zbl 0895.68049 · doi:10.1007/BF01270387
[3] Beame, P; Saks, M; Sun, X; Vee, E, Time-space trade-off lower bounds for randomized computation of decision problems, J. ACM, 50, 154-195, (2003) · Zbl 1326.68144 · doi:10.1145/636865.636867
[4] Aaronson, S; Shi, Y, Quantum lower bounds for the collision and the element distinctness problems, J. ACM, 51, 595-605, (2004) · Zbl 1169.68406 · doi:10.1145/1008731.1008735
[5] Ambainis, A, Polynomial degree and lower bounds in quantum complexity: collision and element distinctness with small range, Theory Comput., 1, 37-46, (2005) · Zbl 1213.68281 · doi:10.4086/toc.2005.v001a003
[6] Buhrman, H; Dürr, C; Heiligman, M; Høyer, P; Magniez, F; Santha, M; Wolf, R, Quantum algorithms for element distinctness, SIAM J. Comput., 34, 1324-1330, (2005) · Zbl 1081.68029 · doi:10.1137/S0097539702402780
[7] Ambainis, A.: Quantum walk algorithm for element distinctness. In: FOCS’04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 22-31, Washington, DC (2004)
[8] Ambainis, A, Quantum walk algorithm for element distinctness, SIAM J. Comput., 37, 210-239, (2007) · Zbl 1134.81010 · doi:10.1137/S0097539705447311
[9] 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, Washington, DC (2004)
[10] Magniez, F; Santha, M; Szegedy, M, Quantum algorithms for the triangle problem, SIAM J. Comput., 37, 413-424, (2007) · Zbl 1166.68032 · doi:10.1137/050643684
[11] Childs, AM; Eisenberg, JM, Quantum algorithms for subset finding, Quantum Inf. Comput., 5, 593-604, (2005) · Zbl 1175.81050
[12] Kutin, S, Quantum lower bound for the collision problem with small range, Theory Comput., 1, 29-36, (2005) · Zbl 1213.68286 · doi:10.4086/toc.2005.v001a002
[13] Brassard, G., Høyer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Proceedings of LATIN’98: Theoretical Informatics: Third Latin American Symposium, Campinas, pp. 163-169 (1998)
[14] Santha, M.: Quantum walk based search algorithms. In: Proceedings of Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi’an, pp. 31-46 (2008) · Zbl 1139.68338
[15] Childs, AM, On the relationship between continuous- and discrete-time quantum walk, Commun. Math. Phys., 294, 581-603, (2010) · Zbl 1207.81029 · doi:10.1007/s00220-009-0930-1
[16] Farhi, E; Gutmann, S, Quantum computation and decision trees, Phys. Rev. A, 58, 915-928, (1998) · doi:10.1103/PhysRevA.58.915
[17] Belovs, A.: Learning-graph-based quantum algorithm for \(k\)-distinctness. In: Proceedings of 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 207-216 (2012)
[18] Belovs, A., Childs, A.M., Jeffery, S., Kothari, R., Magniez, F.: Time-efficient quantum walks for 3-distinctness. In: Proceedings of Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, pp. 105-122 (2013) · Zbl 1336.68081
[19] Rosmanis, A, Quantum adversary lower bound for element distinctness with small range, Chic. J. Theor. Comput. Sci., 4, 2014, (2014) · Zbl 1372.68108
[20] Kaplan, M, Quantum attacks against iterated block ciphers, Mat. Vopr. Kriptogr., 7, 71-90, (2016) · doi:10.4213/mvk185
[21] Jeffery, S; Magniez, F; Wolf, R, Optimal parallel quantum query algorithms, Algorithmica, 79, 509-529, (2017) · Zbl 1372.68107 · doi:10.1007/s00453-016-0206-z
[22] Portugal, R; Santos, RAM; Fernandes, TD; Gonçalves, DN, The staggered quantum walk model, Quantum Inf. Process., 15, 85-101, (2016) · Zbl 1333.81213 · doi:10.1007/s11128-015-1149-z
[23] Portugal, R, Establishing the equivalence between szegedy’s and coined quantum walks using the staggered model, Quantum Inf. Process., 15, 1387-1409, (2016) · Zbl 1338.81143 · doi:10.1007/s11128-015-1230-7
[24] Portugal, R, Staggered quantum walks on graphs, Phys. Rev. A, 93, 062335, (2016) · doi:10.1103/PhysRevA.93.062335
[25] Abreu, A.S.: Tesselaç oes em grafos e suas aplicaç oes em computaç ao quântica. Master’s thesis, UFRJ (2017)
[26] Shenvi, N; Kempe, J; Whaley, KB, A quantum random walk search algorithm, Phys. Rev. A, 67, 052307, (2003) · doi:10.1103/PhysRevA.67.052307
[27] Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1099-1108 (2005) · Zbl 1297.68076
[28] Tulsi, A, General framework for quantum search algorithms, Phys. Rev. A, 86, 042331, (2012) · doi:10.1103/PhysRevA.86.042331
[29] Portugal, R.: Quantum Walks and Search Algorithms. Springer, New York (2013) · Zbl 1275.81004 · doi:10.1007/978-1-4614-6336-8
[30] West, D.B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (2000)
[31] Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM, Philadelphia (1999) · Zbl 0919.05001 · doi:10.1137/1.9780898719796
[32] Harary, F.: Graph Theory. Addison-Wesley, Boston (1969) · Zbl 0182.57702 · doi:10.21236/AD0705364
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.