247 citations · 830 across the 24 of their papers we have counts for
4 papers · 1 filter
The quantum query complexity of read-many formulas
Andrew M. Childs, Shelby Kimmel, Robin Kothari
The quantum query complexity of evaluating any read-once formula with n black-box input bits is Theta(sqrt(n)). However, the corresponding problem for read-many formulas (i.e., for…
Speed from Repetition
Shelby Kimmel
We present an oracle problem, which we call the Repeated Randomness problem, that a quantum algorithm can solve in one query, while any classical algorithm requires que…
Quantum Adversary (Upper) Bound
Shelby Kimmel
We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound. This nonconst…
Super-Polynomial Quantum Speed-ups for Boolean Evaluation Trees with Hidden Structure
Bohua Zhan, Shelby Kimmel, Avinatan Hassidim
We give a quantum algorithm for evaluating a class of boolean formulas (such as NAND trees and 3-majority trees) on a restricted set of inputs. Due to the structure of the allowed…