Ambainis develops quantum algorithms and mathematical limits on their performance, including a quantum-walk solution to element distinctness and separations for exact computation.
Why included?
Ambainis works on both sides of the algorithmic question: how to obtain a quantum improvement, and how to know that a proposed method cannot be improved indefinitely. His element-distinctness algorithm uses a quantum walk to find repeated inputs with fewer queries than classical methods require. His work on exact algorithms also demonstrates that quantum improvements need not always rely on accepting a small error probability. These contributions matter because resource bounds and computational models make an advantage interpretable before a large, fault-tolerant machine is available.
Explore the contributions and sources