_front.jpg){kind=link}
Ambainis develops quantum algorithms and mathematical limits on their performance, including a quantum-walk solution to element distinctness and separations for exact computation.
University of LatviaarXivUniversity of Latvia / SIAM Journal on ComputingAmbainis 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.
University of LatviaarXivUniversity of Latvia / SIAM Journal on ComputingThe work behind the recognition
Work, in context- 2003
A quantum walk for element distinctness
Ambainis introduced a quantum-walk algorithm that tests whether an input list contains equal elements using O(N^(2/3)) queries. The result matches the known query lower bound for the problem, making it an example in which both a speedup and its limits can be stated precisely.
Sole-author quantum-walk algorithm by Andris Ambainis; the resource bound is query complexity.
Source-supported recordarXiv - 2016
An advantage for exact algorithms
Ambainis reported a total Boolean function with a superlinear quantum advantage in exact query complexity over deterministic classical computation. The result concerns algorithms required to return the correct answer, expanding the settings in which a quantum query advantage can be proved.
Sole-author exact-query-complexity result by Andris Ambainis.
Source-supported recordUniversity of Latvia / SIAM Journal on Computing
Keep in perspective
Query complexity counts access to input data; it is not a direct hardware runtime benchmark.
The evidence map
Both views link each contribution to its sources. Choose a contribution on the map or read them all in the list.
A quantum walk for element distinctness
Quantum walk algorithm for element distinctness
Supports: Authorship, query bound and quantum-walk method; preprint date, journal publication 2007.
Published 1 Nov 2003 · Checked 19 Sept 2026Credit & limits: Sole-author quantum-walk algorithm by Andris Ambainis; the resource bound is query complexity.
Read the full contribution| Contribution | Evidence & what it supports | Credit & limits |
|---|---|---|
| A quantum walk for element distinctness2003 | Primary paperQuantum walk algorithm for element distinctness Authorship, query bound and quantum-walk method; preprint date, journal publication 2007. Published 1 Nov 2003 · Checked 19 Sept 2026 | Sole-author quantum-walk algorithm by Andris Ambainis; the resource bound is query complexity. |
| An advantage for exact algorithms2016 | Primary paperSuperlinear advantage for exact quantum algorithms Exact algorithm and superlinear separation for a total Boolean function. Published 2016 · Checked 19 Sept 2026 | Sole-author exact-query-complexity result by Andris Ambainis. |
Follow the evidence
3 sourcesPrimary papers, institutional records and attributed announcements. Each source supports the claims linked above.
- University of LatviaInstitutional record
Andris Ambainis
Current tenured-professor identification and computer-science research affiliation.
Checked 19 Sept 2026 - arXivPrimary paper
Quantum walk algorithm for element distinctness
Authorship, query bound and quantum-walk method; preprint date, journal publication 2007.
Published 1 Nov 2003 · Checked 19 Sept 2026 - University of Latvia / SIAM Journal on ComputingPrimary paper
Superlinear advantage for exact quantum algorithms
Exact algorithm and superlinear separation for a total Boolean function.
Published 2016 · Checked 19 Sept 2026