10 citations · 19 across the 11 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.CC2013
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…
quant-ph2013★ 5 cited
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…