Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2312.03515 · Quantum

The Hadamard gate cannot be replaced by a resource state in universal quantum computation

Benjamin D. M. Jones, Noah Linden, Paul Skrzypczyk

Published Sep 11, 2024• 5 citations
arXivHTMLPDF

Abstract

We consider models of quantum computation that involve operations performed on some fixed resourceful quantum state. Examples that fit this paradigm include magic state injection and measurement-based approaches. We introduce a framework that incorporates both of these cases and focus on the role of coherence (or superposition) in this context, as exemplified through the Hadamard gate. We prove that given access to incoherent unitaries (those that are unable to generate superposition from computational basis states, e.g. CNOT, diagonal gates), classical control, computational basis measurements, and any resourceful ancillary state (of arbitrary dimension), it is not possible to implement any coherent unitary (e.g. Hadamard) exactly with non-zero probability. We also consider the approximate case by providing lower bounds for the induced trace distance between the above operations and n Hadamard gates. To demonstrate the stability of this result, this is then extended to a similar no-go result for the case of using k Hadamard gates to exactly implement n>k Hadamard gates.

DOI
10.22331/q-2024-09-11-1470

Related papers

On the Role of Hadamard Gates in Quantum Circuits

Shepherd Daniel

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}.

•Jan 1, 2006•0 citations

Universal quantum computation via quantum controlled classical operations

Sebastian Horvat, Xiaoqin Gao, Borivoje Dakić

Abstract A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. It is well known that a universal set for classical computation augmented with the Hadamard gate results in universal quantum computing. Motivated by the latter, we pose the following question: can one perform universal quantum computation by supplementing a set of classical gates with a quantum control, and a set of quantum gates operating solely on the latter? In this work we provide an affirmative answer to this question by considering a computational model that consists of 2n target bits together with a set of classical gates controlled by log (2n + 1) ancillary qubits. We show that this model is equivalent to a quantum computer operating on n qubits. Furthermore, we show that even a primitive computer that is capable of implementing only SWAP gates, can be lifted to universal quantum computing, if aided with an appropriate quantum control of logarithmic size. Our results thus exemplify the information processing power brought forth by the quantum control system.

arXiv:2104.06424•Journal of Physics A Mathematical and Theoretical•Dec 15, 2021•3 citations

Universal quantum computation by the unitary control of ancilla qubits and using a fixed ancilla-register interaction

Timothy J Proctor, Erika Andersson, Viv M. Kendon

We characterize a model of universal quantum computation where the register (computational) qubits are controlled by ancillary qubits, using only a single fixed interaction between register and ancillary qubits. No additional access is required to the computational register and the dynamics of both the register and ancilla are unitary. This scheme is inspired by the measurement-based ancilla-driven quantum computation of Anders et al. [Phys. Rev. A 82, 020301(R) (2010)], but does not require measurements of the ancillas, and in this respect is similar to the original gate-based model of quantum computation. We consider what possible forms this ancilla-register interaction can take, with a proof that the interaction is necessarily locally equivalent to swap combined with an entangling controlled gate. We further show which Hamiltonians can create such interactions and discuss two examples; the two-qubit XY Hamiltonian and a particular case of the XXZ Hamiltonian. We then give an example of a simple, finite, and fault-tolerant gate set for universal quantum computation in this model.

arXiv:1307.6095•Physical Review A•Oct 24, 2013•13 citations

Using and reusing coherence to realize quantum processes

María García Díaz, Kun Fang, Xin Wang +4 more

Coherent superposition is a key feature of quantum mechanics that underlies the advantage of quantum technologies over their classical counterparts. Recently, coherence has been recast as a resource theory in an attempt to identify and quantify it in an operationally well-defined manner. Here we study how the coherence present in a state can be used to implement a quantum channel via incoherent operations and, in turn, to assess its degree of coherence. We introduce the robustness of coherence of a quantum channel-which reduces to the homonymous measure for states when computed on constant-output channels-and prove that: i) it quantifies the minimal rank of a maximally coherent state required to implement the channel; ii) its logarithm quantifies the amortized cost of implementing the channel provided some coherence is recovered at the output; iii) its logarithm also quantifies the zero-error asymptotic cost of implementation of many independent copies of a channel. We also consider the generalized problem of imperfect implementation with arbitrary resource states. Using the robustness of coherence, we find that in general a quantum channel can be implemented without employing a maximally coherent resource state. In fact, we prove that every pure coherent state in dimension larger than 2 , however weakly so, turns out to be a valuable resource to implement some coherent unitary channel. We illustrate our findings for the case of single-qubit unitary channels.

arXiv:1805.04045•Quantum•Oct 19, 2018•88 citations

Both Toffoli and Controlled-NOT need little help to do universal quantum computation

Yaoyun Shi

What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.

arXiv:quant-ph/0205115•May 18, 2002•91 citations

Uniqueness of imaginarity-assisted exact transformation from real orthogonal operations to arbitrary unitary operations

Yasuaki Nakayama, Yuki Takeuchi, Seiseki Akibue

The computational universality with an elementary gate set $\{H,CCZ\}$ can be transformed to the strict universality by using a maximally imaginary state $|+i \rangle$ and some non-imaginary ancillary qubits. From the viewpoint of operational resource theory, it would be intriguing to elucidate a resource for the universality transformation. In this paper, we consider the exact universality transformation in which arbitrary real orthogonal matrices can be applied and a supplied resource state is used to simulate unitary operations exactly and deterministically. Within this operational model, we explore a necessary and sufficient condition for resource states to realize the universality transformation under free real operations. We show that $|+i \rangle$ is a unique resource state up to the free operations. Moreover, we obtain a stronger conclusion. If a given resource state cannot be used for the universality transformation, then realizable quantum gates are restricted to unitary matrices proportional to real orthogonal matrices. Therefore, we can tell that $|+i \rangle$ is unique (up to the free operations) not only as a state whose resource measure of imaginarity is maximal, but also as a state which empowers real operations with the ability to apply at least one non-real quantum gate (regardless of the magnitudes of its imaginary parts).

quant-pharXiv:2603.11812•Scientific Reports•Mar 13, 2026•0 citations
We consider models of quantum computation that involve operations performed on some fixed resourceful quantum state. Examples that fit this paradigm include magic state injection and measurement-based approaches. We introduce a framework that incorporates both of these cases and focus on the role of coherence (or superposition) in this context, as exemplified through the Hadamard gate. We prove that given access to incoherent unitaries (those that are unable to generate superposition from computational basis states, e.g. CNOT, diagonal gates), classical control, computational basis measurements, and any resourceful ancillary state (of arbitrary dimension), it is not possible to implement any coherent unitary (e.g. Hadamard) exactly with non-zero probability. We also consider the approximate case by providing lower bounds for the induced trace distance between the above operations and n Hadamard gates. To demonstrate the stability of this result, this is then extended to a similar no-go result for the case of using k Hadamard gates to exactly implement n>k Hadamard gates.
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}.
Abstract A universal set of gates for (classical or quantum) computation is a set of gates that can be used to approximate any other operation. It is well known that a universal set for classical computation augmented with the Hadamard gate results in universal quantum computing. Motivated by the latter, we pose the following question: can one perform universal quantum computation by supplementing a set of classical gates with a quantum control, and a set of quantum gates operating solely on the latter? In this work we provide an affirmative answer to this question by considering a computational model that consists of 2n target bits together with a set of classical gates controlled by log (2n + 1) ancillary qubits. We show that this model is equivalent to a quantum computer operating on n qubits. Furthermore, we show that even a primitive computer that is capable of implementing only SWAP gates, can be lifted to universal quantum computing, if aided with an appropriate quantum control of logarithmic size. Our results thus exemplify the information processing power brought forth by the quantum control system.
We characterize a model of universal quantum computation where the register (computational) qubits are controlled by ancillary qubits, using only a single fixed interaction between register and ancillary qubits. No additional access is required to the computational register and the dynamics of both the register and ancilla are unitary. This scheme is inspired by the measurement-based ancilla-driven quantum computation of Anders et al. [Phys. Rev. A 82, 020301(R) (2010)], but does not require measurements of the ancillas, and in this respect is similar to the original gate-based model of quantum computation. We consider what possible forms this ancilla-register interaction can take, with a proof that the interaction is necessarily locally equivalent to swap combined with an entangling controlled gate. We further show which Hamiltonians can create such interactions and discuss two examples; the two-qubit XY Hamiltonian and a particular case of the XXZ Hamiltonian. We then give an example of a simple, finite, and fault-tolerant gate set for universal quantum computation in this model.
Coherent superposition is a key feature of quantum mechanics that underlies the advantage of quantum technologies over their classical counterparts. Recently, coherence has been recast as a resource theory in an attempt to identify and quantify it in an operationally well-defined manner. Here we study how the coherence present in a state can be used to implement a quantum channel via incoherent operations and, in turn, to assess its degree of coherence. We introduce the robustness of coherence of a quantum channel-which reduces to the homonymous measure for states when computed on constant-output channels-and prove that: i) it quantifies the minimal rank of a maximally coherent state required to implement the channel; ii) its logarithm quantifies the amortized cost of implementing the channel provided some coherence is recovered at the output; iii) its logarithm also quantifies the zero-error asymptotic cost of implementation of many independent copies of a channel. We also consider the generalized problem of imperfect implementation with arbitrary resource states. Using the robustness of coherence, we find that in general a quantum channel can be implemented without employing a maximally coherent resource state. In fact, we prove that every pure coherent state in dimension larger than 2 , however weakly so, turns out to be a valuable resource to implement some coherent unitary channel. We illustrate our findings for the case of single-qubit unitary channels.
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suffices, except those that preserve the computational basis. The result of Gottesman and Knill[quant-ph/9807006] implies that any quantum circuit involving only the Controlled-NOT and Hadamard gates can be efficiently simulated by a classical circuit. In contrast, we prove that Controlled-NOT plus any single-qubit real gate that does not preserve the computational basis and is not Hadamard (or its alike) are universal for quantum computing. Previously only a ``generic'' gate, namely a rotation by an angle incommensurate with pi, is known to be sufficient in both problems, if only one single-qubit gate is added.
The computational universality with an elementary gate set {H,CCZ}\{H,CCZ\}{H,CCZ} can be transformed to the strict universality by using a maximally imaginary state ∣+i⟩|+i \rangle∣+i⟩ and some non-imaginary ancillary qubits. From the viewpoint of operational resource theory, it would be intriguing to elucidate a resource for the universality transformation. In this paper, we consider the exact universality transformation in which arbitrary real orthogonal matrices can be applied and a supplied resource state is used to simulate unitary operations exactly and deterministically. Within this operational model, we explore a necessary and sufficient condition for resource states to realize the universality transformation under free real operations. We show that ∣+i⟩|+i \rangle∣+i⟩ is a unique resource state up to the free operations. Moreover, we obtain a stronger conclusion. If a given resource state cannot be used for the universality transformation, then realizable quantum gates are restricted to unitary matrices proportional to real orthogonal matrices. Therefore, we can tell that ∣+i⟩|+i \rangle∣+i⟩ is unique (up to the free operations) not only as a state whose resource measure of imaginarity is maximal, but also as a state which empowers real operations with the ability to apply at least one non-real quantum gate (regardless of the magnitudes of its imaginary parts).