On the role of Hadamard gates in quantum circuits

DOI10.1007/S11128-006-0023-4zbMATH Open1103.68055arXivquant-ph/0508153OpenAlexW1988916413MaRDI QIDQ850548FDOQ850548

Authors: D. J. Shepherd 

Publication date: 3 November 2006

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

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.

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

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\)

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

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