15 citations · 36 across the 7 of their papers we have counts for
4 papers · 2 filters
A note on the classical lower bound for a quantum walk algorithm
Stephen A. Fenner, Yong Zhang
A recent paper on quantum walks by Childs et al. [STOC'03] provides an example of a black-box problem for which there is a quantum algorithm with exponential speedup over the best…
Bounds on the Power of Constant-Depth Quantum Circuits
Stephen Fenner, Frederic Green, Steven Homer +1
We show that if a language is recognized within certain error bounds by constant-depth quantum circuits over a finite family of gates, then it is computable in (classical) polynomi…
Quantum Lower Bounds for Fanout
Maosen Fang, Stephen Fenner, Frederic Green +2
We prove several new lower bounds for constant depth quantum circuits. The main result is that parity (and hence fanout) requires log depth circuits, when the circuits are composed…
Implementing the fanout gate by a Hamiltonian
Stephen A. Fenner
We show that, for even n, evolving n qubits according to a simple Hamiltonian can be used to exactly implement an (n+1)-qubit parity gate, which is equivalent in constant depth to…