194 citations · 1.9k across the 115 of their papers we have counts for
7 papers · 2 filters
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…
The Minimum Distance Problem for Two-Way Entanglement Purification
Andris Ambainis, Daniel Gottesman
Entanglement purification takes a number of noisy EPR pairs and processes them to produce a smaller number of more reliable pairs. If this is done with only a forward classical sid…
Distributed construction of quantum fingerprints
Andris Ambainis, Yaoyun Shi
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/…
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
Andris Ambainis
We give a general method for proving quantum lower bounds for problems with small range. Namely, we show that, for any symmetric problem defined on functions $f:\{1, ..., N\}\to\{1…
Polynomial degree vs. quantum query complexity
Andris Ambainis
The degree of a polynomial representing (or approximating) a function f is a lower bound for the number of quantum queries needed to compute f. This observation has been a source o…
Multiparty Quantum Coin Flipping
Andris Ambainis, Harry Buhrman, Yevgeniy Dodis +1
We investigate coin-flipping protocols for multiple parties in a quantum broadcast setting: (1) We propose and motivate a definition for quantum broadcast. Our model of quantum bro…
Quantum Search of Spatial Regions
Scott Aaronson, Andris Ambainis
Can Grover's algorithm speed up search of a physical region - for example a 2-D grid of size sqrt(n) by sqrt(n)? The problem is that sqrt(n) time seems to be needed for each query,…