194 citations · 1.9k across the 115 of their papers we have counts for
5 papers · 2 filters
On physical problems that are slightly more difficult than QMA
Andris Ambainis
We study the complexity of computational problems from quantum physics. Typically, they are studied using the complexity class QMA (quantum counterpart of NP) but some natural comp…
Spatial Search on Grids with Minimum Memory
Andris Ambainis, Renato Portugal, Nikolay Nahimov
We study quantum algorithms for spatial search on finite dimensional grids. Patel et al. and Falk have proposed algorithms based on a quantum walk without a coin, with different op…
Parameterized Quantum Query Complexity of Graph Collision
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We present three new quantum algorithms in the quantum query model for \textsc{graph-collision} problem: \begin{itemize} \item an algorithm based on tree decomposition that uses $O…
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games
Andris Ambainis, Jānis Iraids
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local…
Exact quantum query complexity of EXACT and THRESHOLD
Andris Ambainis, Jānis Iraids, Juris Smotrovs
A quantum algorithm is exact if it always produces the correct answer, on any input. Coming up with exact quantum algorithms that substantially outperform the best classical algori…