On the Role of Hadamard Gates in Quantum Circuits

Daniel Shepherd, On the Role of Hadamard Gates in Quantum Circuits. Quantum Information Processing, 5(3), pp. 161–177. May 2006. No electronic version available.


We study a reduced quantum circuit computation paradigm in which the only allowable gates either permute the computational basis states or else apply a ``global Hadamard operation'', \emph{i.e.} apply a Hadamard operation to every qubit simultaneously. In this model, we discuss complexity bounds (lower-bounding the number of global Hadamard operations) for common quantum algorithms~: we illustrate upper bounds for Shor's Algorithm, and prove lower bounds for Grover's Algorithm. We also use our formalism to display a gate that is neither quantum-universal nor classically simulable, on the assumption that Integer Factoring is not in \textbf{BPP}.

Bibtex entry.

Contact details

Publication Admin