194 citations · 1.9k across the 115 of their papers we have counts for
7 papers · 1 filter
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…
Weak Parity
Scott Aaronson, Andris Ambainis, Kaspars Balodis +1
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2+eps fraction of input strings, bu…
New upper bound on block sensitivity and certificate complexity in terms of sensitivity
Andris Ambainis, Yihan Gao, Jieming Mao +2
Sensitivity \cite{CD82,CDR86} and block sensitivity \cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexi…
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…