17 citations · 41 across the 14 of their papers we have counts for
11 papers · 1 filter
Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
Andris Ambainis, Jānis Iraids, Martins Kokainis
We study how large the certificate complexity of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean fu…
A note about claw function with a small range
Andris Ambainis, Kaspars Balodis, Jānis Iraids
In the claw detection problem we are given two functions and (, ), and we have to determine if there is exist such th…
Quantum Lower Bounds for 2D-Grid and Dyck Language
Andris Ambainis, Kaspars Balodis, Jānis Iraids +2
We show quantum lower bounds for two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of…
Quantum Speedups for Exponential-Time Dynamic Programming Algorithms
Andris Ambainis, Kaspars Balodis, Jānis Iraids +3
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path i…
Optimal one-shot quantum algorithm for EQUALITY and AND
Andris Ambainis, Janis Iraids
We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function on an input $x\in\{0,…
Exact quantum query complexity of
Andris Ambainis, Jānis Iraids, Daniel Nagaj
In the exact quantum query model a successful algorithm must always output the correct function value. We investigate the function that is true if exactly or of the inp…
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott Aaronson, Andris Ambainis, Jānis Iraids +2
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function is computable by a 1-query quantum alg…
Quantum Lower Bound for Graph Collision Implies Lower Bound for Triangle Detection
Kaspars Balodis, Jānis Iraids
We show that an improvement to the best known quantum lower bound for GRAPH-COLLISION problem implies an improvement to the best known lower bound for TRIANGLE problem in the quant…
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…