We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).

arXiv:1302.7316Feb 28, 20135 citations

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

Stacey Jeffery, Sebastian Zur

arXiv:2208.13492TheoretiCSMar 4, 20253 citations

Annual Symposium on Foundations of Computer Science

Quantum Walk Algorithm for Element Distinctness

Andris Ambainis

Published Dec 23, 2004• 215 citations

Publisher

Abstract

DOI: 10.1109/focs.2004.54

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^{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.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})$ 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.

SIAM Journal on ComputingJan 1, 2007704 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

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

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates

Andrew M. Childs, Stacey Jeffery, Robin Kothari +1 more

arXiv:1302.7316Feb 28, 20135 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