On the role of Hadamard gates in quantum circuits

DOI10.1007/S11128-006-0023-4MaRDI QIDQ850548zbMATH OpenOpenAlexFDO

Authors D. J. Shepherd

Publication date 3 November 2006

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0508153

zbMATH Keywords

Fourier hierarchylower-bounding Grover's algorithmquantum depth in quantum circuitsShor's algorithm with Toffoli gates only

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Abstract: 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", 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 BPP.

Recommendations

• ON THE NON-EXISTENCE OF A UNIVERSAL HADAMARD GATE
• Quantum circuit optimization by Hadamard gate reduction
• Quantum and classical tradeoffs
• Quantum oracles in terms of universal gate set
• Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)

Cited in

(13)

• Realization of commonly used quantum gates using perturbed harmonic oscillator
• Probabilistic implementation of Hadamard and unitary gates
• Use of global interactions in efficient quantum circuit constructions
• ON THE NON-EXISTENCE OF A UNIVERSAL HADAMARD GATE
• Non-Markovian quantum Hadamard gate preparation in a hybrid bath: a Lyapunov approach
• Realization of the three-qubit quantum controlled gate based on matching Hermitian generators
• Forrelation: a problem that optimally separates quantum from classical computing
• Realization of quantum gates based on three-dimensional harmonic oscillator in a time-varying electromagnetic field
• A quantum probability splitter and its application to qubit preparation
• HADAMARD TYPE OPERATIONS FOR QUBITS
• Quantum circuit optimization by Hadamard gate reduction
• Quantum implementation of image registration
• Simulation of QTRNG on IBM's Q experience using rotation and phase quantum gates

This page was built for publication: On the role of Hadamard gates in quantum circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850548)