218 citations · 643 across the 16 of their papers we have counts for
16 papers
Adversary Lower Bound for the Orthogonal Array Problem
Robert Spalek
We prove a quantum query lower bound Ω(n^{(d+1)/(d+2)}) for the problem of deciding whether an input string of size n contains a k-tuple which belongs to a fixed orthogonal array o…
Adversary Lower Bound for the k-sum Problem
Aleksandrs Belovs, Robert Spalek
We prove a tight quantum query lower bound for the problem of deciding whether there exist numbers among that sum up to a prescribed number, provided that…
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt +2
State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity…
A Dual Polynomial for OR
Robert Spalek
We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynom…
Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt, Robert Spalek
We give a quantum algorithm for evaluating formulas over an extended gate set, including all two- and three-bit binary gates (e.g., NAND, 3-majority). The algorithm is optimal on r…
The Multiplicative Quantum Adversary
Robert Spalek
We present a new variant of the quantum adversary method. All adversary methods give lower bounds on the quantum query complexity of a function by bounding the change of a progress…