17 citations · 29 across the 6 of their papers we have counts for
7 papers · 1 filter
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,…
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…
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…