quantum algorithm of Buhrman et al. [SIAM J. Comput., 34 (2005), pp. 1324–1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 (2004), pp. 595–605]. We also give an

O(N^{k/(k+1)})

query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

DOI: 10.1137/s0097539705447311

Related papers

Quantum walk algorithm for element distinctness

Andris Ambainis

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman et.al. (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm.We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman et.al. (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086). The algorithm also solves the generalization of element distinctness in which we have to find k equal items among N items. For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm.

arXiv:quant-ph/0311001Nov 1, 200320 citations

Quantum Walk Algorithm for Element Distinctness

Andris Ambainis

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N/sup 2/3/) query quantum algorithm. This improves the previous O(N/sup 3/4/) quantum algorithm of Buhrman et al. and matches the lower bound by Shi. We also give an O(N/sup k/(k+1)/) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N/sup 2/3/) query quantum algorithm. This improves the previous O(N/sup 3/4/) quantum algorithm of Buhrman et al. and matches the lower bound by Shi. We also give an O(N/sup k/(k+1)/) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

Annual Symposium on Foundations of Computer ScienceDec 23, 2004215 citations

Quantum algorithms for subset finding

Andrew M. Childs, J.M. Eisenberg

Recently, Ambainis gave an $O(N^{2/3})$ -query discrete-time quantum walk algorithm for the element distinctness problem, and more generally, an $O(N^{L/(L+1)})$ -query algorithm for finding $L$ equal numbers. We review this algorithm and give a simplified and tightened analysis of its query complexity using techniques previously applied to the analysis of continuous-time quantum walk. We also briefly discuss applications of the algorithm and pose two open problems regarding continuous-time quantum walk and lower bounds.Recently, Ambainis gave an $O(N^{2/3})$-query discrete-time quantum walk algorithm for the element distinctness problem, and more generally, an $O(N^{L/(L+1)})$-query algorithm for finding $L$ equal numbers. We review this algorithm and give a simplified and tightened analysis of its query complexity using techniques previously applied to the analysis of continuous-time quantum walk. We also briefly discuss applications of the algorithm and pose two open problems regarding continuous-time quantum walk and lower bounds.

Quantum Information and ComputationNov 1, 200537 citations

Quantum algorithms for subset finding

Andrew M. Childs, Eisenberg, J M

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.

Nov 6, 200353 citations

Improved Approximate Degree Bounds For k-distinctness

Nikhil S. Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

arXiv:2002.08389Leibniz international proceedings in informaticsJan 1, 20204 citations

Multidimensional Quantum Walks, with Application to $k$ -DistinctnessMultidimensional Quantum Walks, with Application to $k$-Distinctness

Stacey Jeffery, Sebastian Zur

While the quantum query complexity of $k$ -distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$ , the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$ . We give a new upper bound of $\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCSWhile the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of $\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCS

arXiv:2208.13492TheoretiCSMar 4, 20253 citations

O(N^{2/3})

query quantum algorithm. This improves the previous

O(N^{3/4})

quantum algorithm of Buhrman et al. [SIAM J. Comput., 34 (2005), pp. 1324–1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 (2004), pp. 595–605]. We also give an

O(N^{k/(k+1)})

query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

Recently, Ambainis gave an

O(N^{2/3})

-query discrete-time quantum walk algorithm for the element distinctness problem, and more generally, an

O(N^{L/(L+1)})

-query algorithm for finding

L

equal numbers. We review this algorithm and give a simplified and tightened analysis of its query complexity using techniques previously applied to the analysis of continuous-time quantum walk. We also briefly discuss applications of the algorithm and pose two open problems regarding continuous-time quantum walk and lower bounds.

Multidimensional Quantum Walks, with Application to

k

-Distinctness

While the quantum query complexity of

k

-distinctness is known to be

O\left(n^{3/4-1/4(2^k-1)}\right)

for any constant

k \geq 4

, the best previous upper bound on the time complexity was

\widetilde{O}\left(n^{1-1/k}\right)

. We give a new upper bound of

\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)

on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in

O(n)

queries and

O(n^2)

time using this new technique, showing that the new quantum walk framework can achieve exponential speedups. Comment: Journal version for TheoretiCS