17 citations · 41 across the 14 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
quant-ph2015
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…
quant-ph2015
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…