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

Quantum Information and Computation

Exact universality from any entangling gate without inverses

Aram W. Harrow

Published Sep 1, 2009• 6 citations
Publisher

Abstract

This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V^\dag was given, or when approximate universality was demanded.
DOI
10.26421/qic9.9-10-4

Related papers

Exact universality from any entangling gate without inverses

Aram W. Harrow

This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V^{-1} was given, or when approximate universality was demanded.

arXiv:0806.0631•Jun 3, 2008•0 citations

QAC0 Can Prepare Every Logarithmic-Qubit State

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

$\mathsf{QAC}^0$ is the class of constant-depth $\mathrm{poly}(n)$-ancilla circuits obtained by extending $\mathsf{QNC}^0$, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, $\mathsf{QNC}^0_f$, obtained by including arbitrary-width FANOUT gates instead ($\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_f$ [Moo99]). In this note, we show that every $O(\log n)$-qubit state can be exactly and cleanly prepared by a $\mathrm{poly}(n)$-ancilla $\mathsf{QAC}^0$ circuit. Previous known $\mathrm{poly}(n)$-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in $\mathsf{QAC}^0$. Equivalently, prior constructions of arbitrary $n$-qubit states in $\mathsf{QAC}^0$ require doubly exponential size and we obtain an exponential factor improvement.

quant-pharXiv:2609.17408•Sep 16, 2026•0 citations

Exact universality from any entangling gate without inverses

Aram W. Harrow

This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V † was given, or when approximate universality was demanded. A common situation in quantum computing is that we can apply only a limited set S ⊂ Ud of unitary gates to some d-dimensional system. The first question we want to ask in this situation is whether gates from S can (approximately) generate any gate in PUd = Ud/U1 (the set of all d × d unitary matrices up to an overall phase). When this is possible, we say that S is (approximately) universal. See [1, 3, 4, 7] for original work on this subject, or Sect 4.5 of [9] or Chapter 8 of [8] for reviews. Formally, S is universal (for PUd) if, for all W ∈ PUd, there exists U1,...,Uk ∈ S such that W = UkUk−1 · · · U2U1, whereas U is approximately universal (for PUd) if, for all W ∈ PUd and all ǫ> 0, there exists U1,...,Uk ∈ S such that d(W,UkUk−1 · · · U2U1) < ǫ. (1) Here d(·, ·) can be any metric, but for concreteness we will take it to be the PUd analogue of operator distance: 〈ψ|U d(U,V): = 1 − inf

Quantum Information and Computation•Sep 1, 2009•9 citations

Practical Scheme for Quantum Computation with Any Two-Qubit Entangling Gate

Michael J. Bremner, Christopher M. Dawson, Jennifer L. Dodd +5 more

Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (qubits), such as the controlled-not, are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. We present an elementary proof that any entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this result for systems of arbitrary finite dimension has been provided by Brylinski and Brylinski; however, their proof relies on a long argument using advanced mathematics. In contrast, our proof provides a simple constructive procedure which is close to optimal and experimentally practical.

arXiv:quant-ph/0207072•Physical Review Letters•Nov 25, 2002•292 citations

Genuine Multipartite Entanglement between Logical Qubits via Cross-Code Lattice Surgery

Alex Steiner, Tomasz Andrzejewski, Phila Rembold +8 more

Universal quantum computers are expected to generate arbitrary complex quantum states of logical qubits encoded in many physical qubits. This capability hinges on a fault-tolerantly implemented universal gate set, which no single quantum error-correction code admits transversally but which becomes accessible by joining complementary codes via lattice surgery. Here we report on the experimental generation and certification of logical genuine multipartite entanglement in a trapped-ion quantum processor using a transversally implemented universal logical gate set. The gate set is accessed via lattice surgery across two different codes and comprises a Hadamard gate on a four-qubit surface code and a doubly controlled Pauli-$Z$ ($\overline{\mathrm{CCZ}}$) gate on an eight-qubit 3D colour code. To showcase this lattice-surgery toolbox, we generate both stabiliser (Greenberger-Horne-Zeilinger) and non-stabiliser ($|\overline{\mathrm{CCZ}}\rangle$) states of three logical qubits and verify their genuine multipartite entanglement--a form of correlation beyond statistical mixtures of bipartite entanglement across any bipartition. We further use these cross-code primitives to demonstrate arbitrary rotations of single logical qubits via a $\overline{\mathrm{CCZ}}$-based resource gadget accessing the full universal gate set through lattice surgery. Together, these demonstrations showcase the core building blocks of an architecture for fault-tolerant quantum computation and its ability to generate complex logical quantum states.

quant-pharXiv:2607.04227•Jul 7, 2026•0 citations

On the universality of almost every quantum logic gate

Nik Weaver

Lloyd [Phys. Rev. Lett. 75, 346 (1995)] showed that almost every quantum logic gate is universal in the sense that it can be used to approximate any unitary transformation. The argument relied on a more general fact whose proof was not given in detail. We give a complete proof of this more general fact.

Journal of Mathematical Physics•Jan 1, 2000•27 citations
QAC0\mathsf{QAC}^0QAC0 is the class of constant-depth poly(n)\mathrm{poly}(n)poly(n)-ancilla circuits obtained by extending QNC0\mathsf{QNC}^0QNC0, the class of local circuits, to include nonlocal interactions via arbitrary width Toffoli gates. It is believed to be weaker than its counterpart, QNCf0\mathsf{QNC}^0_fQNCf0​, obtained by including arbitrary-width FANOUT gates instead (QAC0⊆QNCf0\mathsf{QAC}^0 \subseteq \mathsf{QNC}^0_fQAC0⊆QNCf0​ [Moo99]). In this note, we show that every O(log⁡n)O(\log n)O(logn)-qubit state can be exactly and cleanly prepared by a poly(n)\mathrm{poly}(n)poly(n)-ancilla QAC0\mathsf{QAC}^0QAC0 circuit. Previous known poly(n)\mathrm{poly}(n)poly(n)-ancilla circuits for arbitrary such states are only known via additional access to either FANOUT or QRAM (indexing) gates [Ros21b, GGJ26b], neither of which are known to be in QAC0\mathsf{QAC}^0QAC0. Equivalently, prior constructions of arbitrary nnn-qubit states in QAC0\mathsf{QAC}^0QAC0 require doubly exponential size and we obtain an exponential factor improvement.
This note proves that arbitrary local gates together with any entangling bipartite gate V are universal. Previously this was known only when access to both V and V † was given, or when approximate universality was demanded. A common situation in quantum computing is that we can apply only a limited set S ⊂ Ud of unitary gates to some d-dimensional system. The first question we want to ask in this situation is whether gates from S can (approximately) generate any gate in PUd = Ud/U1 (the set of all d × d unitary matrices up to an overall phase). When this is possible, we say that S is (approximately) universal. See [1, 3, 4, 7] for original work on this subject, or Sect 4.5 of [9] or Chapter 8 of [8] for reviews. Formally, S is universal (for PUd) if, for all W ∈ PUd, there exists U1,...,Uk ∈ S such that W = UkUk−1 · · · U2U1, whereas U is approximately universal (for PUd) if, for all W ∈ PUd and all ǫ> 0, there exists U1,...,Uk ∈ S such that d(W,UkUk−1 · · · U2U1) < ǫ. (1) Here d(·, ·) can be any metric, but for concreteness we will take it to be the PUd analogue of operator distance: 〈ψ|U d(U,V): = 1 − inf
Which gates are universal for quantum computation? Although it is well known that certain gates on two-level quantum systems (qubits), such as the controlled-not, are universal when assisted by arbitrary one-qubit gates, it has only recently become clear precisely what class of two-qubit gates is universal in this sense. We present an elementary proof that any entangling two-qubit gate is universal for quantum computation, when assisted by one-qubit gates. A proof of this result for systems of arbitrary finite dimension has been provided by Brylinski and Brylinski; however, their proof relies on a long argument using advanced mathematics. In contrast, our proof provides a simple constructive procedure which is close to optimal and experimentally practical.
Universal quantum computers are expected to generate arbitrary complex quantum states of logical qubits encoded in many physical qubits. This capability hinges on a fault-tolerantly implemented universal gate set, which no single quantum error-correction code admits transversally but which becomes accessible by joining complementary codes via lattice surgery. Here we report on the experimental generation and certification of logical genuine multipartite entanglement in a trapped-ion quantum processor using a transversally implemented universal logical gate set. The gate set is accessed via lattice surgery across two different codes and comprises a Hadamard gate on a four-qubit surface code and a doubly controlled Pauli-ZZZ (CCZ‾\overline{\mathrm{CCZ}}CCZ) gate on an eight-qubit 3D colour code. To showcase this lattice-surgery toolbox, we generate both stabiliser (Greenberger-Horne-Zeilinger) and non-stabiliser (∣CCZ‾⟩|\overline{\mathrm{CCZ}}\rangle∣CCZ⟩) states of three logical qubits and verify their genuine multipartite entanglement--a form of correlation beyond statistical mixtures of bipartite entanglement across any bipartition. We further use these cross-code primitives to demonstrate arbitrary rotations of single logical qubits via a CCZ‾\overline{\mathrm{CCZ}}CCZ-based resource gadget accessing the full universal gate set through lattice surgery. Together, these demonstrations showcase the core building blocks of an architecture for fault-tolerant quantum computation and its ability to generate complex logical quantum states.