# Quantum walk algorithm for element distinctness

@article{Ambainis2004QuantumWA, title={Quantum walk algorithm for element distinctness}, author={Andris Ambainis}, journal={45th Annual IEEE Symposium on Foundations of Computer Science}, year={2004}, pages={22-31} }

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… Expand

#### Figures and Topics from this paper

#### 649 Citations

Time-Efficient Quantum Walks for 3-Distinctness

- Computer Science, Mathematics
- ICALP
- 2013

Two quantum walk algorithms for 3-Distinctness are presented, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. Expand

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

- Computer Science, Mathematics
- ArXiv
- 2013

An extension to the quantum walk search framework that facilitates quantum walks with nested updates is presented, to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound up to log factors. Expand

Quantum Algorithm for k-distinctness with Prior Knowledge on the Input

- Mathematics, Physics
- 2011

It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed… Expand

Quantum Adversary Lower Bound for Element Distinctness with Small Range

- Computer Science, Mathematics
- Chic. J. Theor. Comput. Sci.
- 2014

This work constructs a tight $\Omega(N^{2/3})$ adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. Expand

Quantum Algorithm for the Triangle Problem

- 2003

We present a new quantum algorithm that either finds a triangle (a copy of K3) in an undirected graph G on n nodes, or it outputs “reject” if G is triangle free. The algorithm uses O(n) queries, and… Expand

Applications of Adversary Method in Quantum Query Algorithms

- Mathematics, Physics
- 2014

In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows:
*… Expand

Quantum Algorithms for Element Distinctness

- Computer Science, Mathematics
- SIAM J. Comput.
- 2005

We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables,… Expand

Optimal Parallel Quantum Query Algorithms

- Mathematics, Computer Science
- ESA
- 2014

It is proved that quantum and classical p-parallel complexity are polynomially related for all total functions f when p is small compared to f’s block sensitivity. Expand

Efficient algorithms in quantum query complexity

- Mathematics, Computer Science
- 2014

These algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems and study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Expand

Quantum Algorithm for Element Distinctness

- Computer Science, Mathematics
- Encyclopedia of Algorithms
- 2008

In the element distinctness problem, one is given a list of N elements and one must determine if the list contains two equal elements, and there are two possible types of query: Value Queries and quantum version of this model. Expand

#### References

SHOWING 1-10 OF 85 REFERENCES

Quantum algorithms for subset finding

- Mathematics, Physics
- Quantum Inf. Comput.
- 2005

This algorithm is reviewed and a simplified and tightened analysis of its query complexity is given using techniques previously applied to the analysis of continuous-time quantum walk. Expand

Quantum Algorithms for Element Distinctness

- Computer Science, Mathematics
- SIAM J. Comput.
- 2005

We present several applications of quantum amplitude amplification for deciding whether all elements in the image of a given function are distinct, for finding an intersection of two sorted tables,… Expand

Quantum random-walk search algorithm

- Physics, Computer Science
- 2003

It will be shown that this algorithm performs an oracle search on a database of N items with $O(\sqrt{N})$ calls to the oracle, yielding a speedup similar to other quantum search algorithms. Expand

Quantum lower bounds by quantum arguments

- Mathematics, Computer Science
- STOC '00
- 2000

Two new Ω(√N) lower bounds on computing AND of ORs and inverting a permutation and more uniform proofs for several known lower bounds which have been previously proven via a variety of different techniques are proved. Expand

Quantum lower bound for the collision problem

- Mathematics, Physics
- STOC '02
- 2002

A lower bound of Ω(n1/5) is shown on the number of queries needed by a quantum computer to solve the problem of deciding whether two sets are equal or disjoint on a constant fraction of elements. Expand

Quantum cryptanalysis of hash and claw-free functions

- Mathematics, Computer Science
- SIGA
- 1997

A quantum algorithm that finds collisions in arbitrary functions after only O(3√N/τ) expected evaluations of the function, more efficient than the best possible classical algorithm, even allowing probabilism. Expand

Quantum computation and decision trees

- Physics
- 1998

Many interesting computational problems can be reformulated in terms of decision trees. A natural classical algorithm is to then run a random walk on the tree, starting at the root, to see if the… Expand

Spatial search by quantum walk

- Physics
- 2004

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a… Expand

Quantum speed-up of Markov chain based algorithms

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

It is shown that under certain conditions, the quantum version of the Markov chain gives rise to a quadratic speed-up, and that the quantum escape time, just like its classical version, depends on the spectral properties of the transition matrix with the marked rows and columns deleted. Expand

Exponential algorithmic speedup by a quantum walk

- Mathematics, Computer Science
- STOC '03
- 2003

A black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer is constructed and it is proved that no classical algorithm can solve the problem in subexponential time. Expand