17 citations · 41 across the 14 of their papers we have counts for
3 papers · 1 filter
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…