arXiv:2609.22176

Every architecture of six two-qubit gates is locally universal on three qubits

Hyunho Cha, Jungwoo Lee

quant-phSubmitted Aug 27, 2026• Announced Aug 28, 2026• 0 citations

Abstract

We present the \emph{first} analytical determination of the exact accessible dimension for every fixed architecture of arbitrary two-qubit gates on three qubits. A support word represents which pair of qubits each two-qubit gate acts on, and its reduced length is obtained by merging consecutive gates on the same pair. If the reduced length is $r$, then the set of implementable three-qubit unitaries has accessible dimension $d(w)=\min\{63,9r+9\}$. Consequently, six arbitrary two-qubit gates are \emph{necessary and sufficient for local universality}: every fixed architecture reaches a nonempty open subset of $\mathrm{SU}(8)$ when its reduced length is at least six. The result is stronger than existence of one favorable architecture. Every reduced six-slot support word is locally universal, including the alternating nearest-neighbor line $AB,BC,AB,BC,AB,BC$. The upper bound follows from a standard parameter-counting argument. The matching lower bounds are proved by Jacobian certificates in the Pauli basis. Up to qubit relabeling and reversal, there are $22$ reduced architectures of lengths two through six. For each one, a product of rational Pauli rotations yields a nonzero maximal minor modulo the prime $1{,}000{,}003$. Thus, any obstruction to global universality with six two-qubit gates must go beyond parameter counting, connectivity, and differential rank.

Comments: 80 pages

Related papers

Local Universality and Structural Certificates for Minimal Fixed-Depth Two-Qutrit Gate Decomposition

Yurui Liu, Ruoting Dou, Peng Xu +4 more

quant-pharXiv:2607.24129Jul 28, 20260 citations

Necessary and Sufficient Conditions for Universal Gates with Pauli Strings and Beyond

Isaac D. Smith, Hans J. Briegel, Hendrik Poulsen Nautrup

quant-pharXiv:2606.12096Jun 11, 20260 citations

Universal quantum computing in linear nearest neighbor architectures

Preethika Kumar, Steven R. Skinner

Quantum Information and ComputationMar 1, 20116 citations

Minimal universal two-qubit controlled-NOT-based circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

arXiv:quant-ph/0308033Physical Review AJun 30, 2004287 citations

Exact Two-Qubit Universal Quantum Circuit

Jun Zhang, Jiří Vala, Shankar Sastry +1 more

arXiv:quant-ph/0212109Physical Review LettersJul 11, 200368 citations

Beyond light cones: State preparation complexity in quantum spin glasses

Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

quant-pharXiv:2610.02166Oct 2, 20260 citations

arXiv:2609.22176

Every architecture of six two-qubit gates is locally universal on three qubits

Hyunho Cha, Jungwoo Lee

quant-phSubmitted Aug 27, 2026• Announced Aug 28, 2026• 0 citations

arXiv HTML PDF

Abstract

r

, then the set of implementable three-qubit unitaries has accessible dimension

d(w)=\min\{63,9r+9\}

. Consequently, six arbitrary two-qubit gates are \emph{necessary and sufficient for local universality}: every fixed architecture reaches a nonempty open subset of

\mathrm{SU}(8)

when its reduced length is at least six. The result is stronger than existence of one favorable architecture. Every reduced six-slot support word is locally universal, including the alternating nearest-neighbor line

AB,BC,AB,BC,AB,BC

. The upper bound follows from a standard parameter-counting argument. The matching lower bounds are proved by Jacobian certificates in the Pauli basis. Up to qubit relabeling and reversal, there are

22

reduced architectures of lengths two through six. For each one, a product of rational Pauli rotations yields a nonzero maximal minor modulo the prime

1{,}000{,}003

. Thus, any obstruction to global universality with six two-qubit gates must go beyond parameter counting, connectivity, and differential rank.

Comments: 80 pages

Related papers

Local Universality and Structural Certificates for Minimal Fixed-Depth Two-Qutrit Gate Decomposition

Yurui Liu, Ruoting Dou, Peng Xu +4 more

We study a dimension-saturating fixed-core ansatz in which four copies of a fixed, non-tunable two-qutrit core $K\in SU(9)$ are interleaved with five adjustable local layers from $L=SU(3)\otimes SU(3)$ . Since $\dim SU(9)=80$ and $5\dim L=80$ , this is the shortest fixed-core architecture not excluded by parameter counting. We formulate the smooth map $Φ_K:L^5\to SU(9)$ and use its right-trivialized differential to give verifiable certificates for local universality. We construct an explicit Clifford-word core whose Pauli-label splitting makes the identity-point differential an exact isometry, and we classify all 2304 symplectic actions satisfying the same splitting criterion. We also prove a structural obstruction for an important symmetry class: every complex-symmetric core $K=K^{T}$ , including every core generated by a time-independent real-symmetric Hamiltonian in the chosen computational basis, has identity-point differential rank at most 78; hence any full-rank certificate for such a core must occur away from that point. We then assess a hardware-motivated superconducting core generated by a noncommuting, temporally asymmetric drive. Direct calculation verifies $K_{\rm sc}\neq K_{\rm sc}^{\mathsf T}$ , and the core achieves $F_{\rm avg}\ge 0.999$ for all 1000 Haar-random targets tested under the stated restart protocol. We also report favorable sampled Jacobian-rank, structured-target, and robustness diagnostics. These results establish local universality at the parameter-counting-minimal, dimension-saturating depth, with an exact Clifford certificate complemented by a hardware-motivated numerical case study. Throughout, we separate exact local certificates from numerical evidence for broader synthesis performance.We study a dimension-saturating fixed-core ansatz in which four copies of a fixed, non-tunable two-qutrit core $K\in SU(9)$ are interleaved with five adjustable local layers from $L=SU(3)\otimes SU(3)$. Since $\dim SU(9)=80$ and $5\dim L=80$, this is the shortest fixed-core architecture not excluded by parameter counting. We formulate the smooth map $Φ_K:L^5\to SU(9)$ and use its right-trivialized differential to give verifiable certificates for local universality. We construct an explicit Clifford-word core whose Pauli-label splitting makes the identity-point differential an exact isometry, and we classify all 2304 symplectic actions satisfying the same splitting criterion. We also prove a structural obstruction for an important symmetry class: every complex-symmetric core $K=K^{T}$, including every core generated by a time-independent real-symmetric Hamiltonian in the chosen computational basis, has identity-point differential rank at most 78; hence any full-rank certificate for such a core must occur away from that point. We then assess a hardware-motivated superconducting core generated by a noncommuting, temporally asymmetric drive. Direct calculation verifies $K_{\rm sc}\neq K_{\rm sc}^{\mathsf T}$, and the core achieves $F_{\rm avg}\ge 0.999$ for all 1000 Haar-random targets tested under the stated restart protocol. We also report favorable sampled Jacobian-rank, structured-target, and robustness diagnostics. These results establish local universality at the parameter-counting-minimal, dimension-saturating depth, with an exact Clifford certificate complemented by a hardware-motivated numerical case study. Throughout, we separate exact local certificates from numerical evidence for broader synthesis performance.

quant-pharXiv:2607.24129Jul 28, 20260 citations

Necessary and Sufficient Conditions for Universal Gates with Pauli Strings and Beyond

Isaac D. Smith, Hans J. Briegel, Hendrik Poulsen Nautrup

Any quantum computation consists of a sequence of unitary evolutions described by a finite set of Hamiltonians. For the case where this set consists of only products of Pauli operators, known as Pauli strings, we provide a necessary and sufficient condition for it to generate $\mathfrak{su}(2^n)$ , i.e., to be universal for quantum computation on $n$ qubits. When combining Pauli strings with a general Hamiltonian, we show a sufficient (and in certain circumstances even necessary) condition for universality based on the Pauli-basis expansion of the Hamiltonian. As an application of these results, we prove two corollaries: (i) a necessary and sufficient condition for the universality of a general Hamiltonian given arbitrary single-qubit control on all qubits, and (ii) the universality of an XYZ Heisenberg Hamiltonian with local control of just two adjacent qubits.Any quantum computation consists of a sequence of unitary evolutions described by a finite set of Hamiltonians. For the case where this set consists of only products of Pauli operators, known as Pauli strings, we provide a necessary and sufficient condition for it to generate $\mathfrak{su}(2^n)$, i.e., to be universal for quantum computation on $n$ qubits. When combining Pauli strings with a general Hamiltonian, we show a sufficient (and in certain circumstances even necessary) condition for universality based on the Pauli-basis expansion of the Hamiltonian. As an application of these results, we prove two corollaries: (i) a necessary and sufficient condition for the universality of a general Hamiltonian given arbitrary single-qubit control on all qubits, and (ii) the universality of an XYZ Heisenberg Hamiltonian with local control of just two adjacent qubits.

quant-pharXiv:2606.12096Jun 11, 20260 citations

Universal quantum computing in linear nearest neighbor architectures

Preethika Kumar, Steven R. Skinner

We introduce a scheme for realizing universal quantum computing in a linear nearest neighbor architecture with fixed couplings. We first show how to realize a controlled-NOT gate operation between two adjacent qubits without having to isolate the two qubits from qubits adjacent to them. The gate operation is implemented by applying two consecutive pulses of equal duration, but varying amplitudes, on the target qubit. Since only a single control parameter is required in implementing our scheme, it is very efficient. We next show how our scheme can be used to realize single qubit rotations and two-qubit controlled-unitary operations. As most proposals for solid state implementations of a quantum computer use a one-dimensional line of qubits, the schemes presented here will be extremely useful.We introduce a scheme for realizing universal quantum computing in a linear nearest neighbor architecture with fixed couplings. We first show how to realize a controlled-NOT gate operation between two adjacent qubits without having to isolate the two qubits from qubits adjacent to them. The gate operation is implemented by applying two consecutive pulses of equal duration, but varying amplitudes, on the target qubit. Since only a single control parameter is required in implementing our scheme, it is very efficient. We next show how our scheme can be used to realize single qubit rotations and two-qubit controlled-unitary operations. As most proposals for solid state implementations of a quantum computer use a one-dimensional line of qubits, the schemes presented here will be extremely useful.

Quantum Information and ComputationMar 1, 20116 citations

Minimal universal two-qubit controlled-NOT-based circuits

Vivek Shende, Igor L. Markov, Stephen S. Bullock

We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in $\mathrm{C}++$ .We give quantum circuits that simulate an arbitrary two-qubit unitary operator up to a global phase. For several quantum gate libraries we prove that gate counts are optimal in the worst and average cases. Our lower and upper bounds compare favorably to previously published results. Temporary storage is not used because it tends to be expensive in physical implementations. For each gate library, the best gate counts can be achieved by a single universal circuit. To compute the gate parameters in universal circuits, we use only closed-form algebraic expressions, and in particular do not rely on matrix exponentials. Our algorithm has been coded in $\mathrm{C}++$.

arXiv:quant-ph/0308033Physical Review AJun 30, 2004287 citations

Exact Two-Qubit Universal Quantum Circuit

Jun Zhang, Jiří Vala, Shankar Sastry +1 more

We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.We provide an analytic way to implement any arbitrary two-qubit unitary operation, given an entangling two-qubit gate together with local gates. This is shown to provide explicit construction of a universal quantum circuit that exactly simulates arbitrary two-qubit operations in SU(4). Each block in this circuit is given in a closed form solution. We also provide a uniform upper bound of the applications of the given entangling gates, and find that exactly half of all the controlled-unitary gates satisfy the same upper bound as the CNOT gate. These results allow for the efficient implementation of operations in SU(4) required for both quantum computation and quantum simulation.

arXiv:quant-ph/0212109Physical Review LettersJul 11, 200368 citations

Beyond light cones: State preparation complexity in quantum spin glasses

Omar Al-Ghattas, David Gamarnik, Bobak T Kiani

We introduce a technique for studying state preparation complexity in the quantum $p$ -spin model on $n$ qubits, a disordered quantum spin system with random interactions on every set of $p$ qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight- $p$ Pauli strings. We show that, for sufficiently large fixed $p$ , any class with local profile complexity $O(n^2)$ remains separated from the ground-state energy by $Ω(\sqrt n)$ , a gap on the leading energy scale. When the profile complexity is $o(n^2)$ , we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an $Ω(n^2/\log n)$ gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with $T$ -gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.We introduce a technique for studying state preparation complexity in the quantum $p$-spin model on $n$ qubits, a disordered quantum spin system with random interactions on every set of $p$ qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-$p$ Pauli strings. We show that, for sufficiently large fixed $p$, any class with local profile complexity $O(n^2)$ remains separated from the ground-state energy by $Ω(\sqrt n)$, a gap on the leading energy scale. When the profile complexity is $o(n^2)$, we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an $Ω(n^2/\log n)$ gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with $T$-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.

quant-pharXiv:2610.02166Oct 2, 20260 citations

r

, then the set of implementable three-qubit unitaries has accessible dimension

d(w)=\min\{63,9r+9\}

. Consequently, six arbitrary two-qubit gates are \emph{necessary and sufficient for local universality}: every fixed architecture reaches a nonempty open subset of

\mathrm{SU}(8)

AB,BC,AB,BC,AB,BC

. The upper bound follows from a standard parameter-counting argument. The matching lower bounds are proved by Jacobian certificates in the Pauli basis. Up to qubit relabeling and reversal, there are

22

reduced architectures of lengths two through six. For each one, a product of rational Pauli rotations yields a nonzero maximal minor modulo the prime

1{,}000{,}003

. Thus, any obstruction to global universality with six two-qubit gates must go beyond parameter counting, connectivity, and differential rank.

We study a dimension-saturating fixed-core ansatz in which four copies of a fixed, non-tunable two-qutrit core

K\in SU(9)

are interleaved with five adjustable local layers from

L=SU(3)\otimes SU(3)

. Since

\dim SU(9)=80

and

5\dim L=80

, this is the shortest fixed-core architecture not excluded by parameter counting. We formulate the smooth map

Φ_K:L^5\to SU(9)

and use its right-trivialized differential to give verifiable certificates for local universality. We construct an explicit Clifford-word core whose Pauli-label splitting makes the identity-point differential an exact isometry, and we classify all 2304 symplectic actions satisfying the same splitting criterion. We also prove a structural obstruction for an important symmetry class: every complex-symmetric core

K=K^{T}

, including every core generated by a time-independent real-symmetric Hamiltonian in the chosen computational basis, has identity-point differential rank at most 78; hence any full-rank certificate for such a core must occur away from that point. We then assess a hardware-motivated superconducting core generated by a noncommuting, temporally asymmetric drive. Direct calculation verifies

K_{\rm sc}\neq K_{\rm sc}^{\mathsf T}

, and the core achieves

F_{\rm avg}\ge 0.999

for all 1000 Haar-random targets tested under the stated restart protocol. We also report favorable sampled Jacobian-rank, structured-target, and robustness diagnostics. These results establish local universality at the parameter-counting-minimal, dimension-saturating depth, with an exact Clifford certificate complemented by a hardware-motivated numerical case study. Throughout, we separate exact local certificates from numerical evidence for broader synthesis performance.

\mathfrak{su}(2^n)

, i.e., to be universal for quantum computation on

n

qubits. When combining Pauli strings with a general Hamiltonian, we show a sufficient (and in certain circumstances even necessary) condition for universality based on the Pauli-basis expansion of the Hamiltonian. As an application of these results, we prove two corollaries: (i) a necessary and sufficient condition for the universality of a general Hamiltonian given arbitrary single-qubit control on all qubits, and (ii) the universality of an XYZ Heisenberg Hamiltonian with local control of just two adjacent qubits.

\mathrm{C}++

We introduce a technique for studying state preparation complexity in the quantum

p

-spin model on

n

qubits, a disordered quantum spin system with random interactions on every set of

p

qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-

p

Pauli strings. We show that, for sufficiently large fixed

p

, any class with local profile complexity

O(n^2)

remains separated from the ground-state energy by

Ω(\sqrt n)

, a gap on the leading energy scale. When the profile complexity is

o(n^2)

, we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an

Ω(n^2/\log n)

gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with

T

-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.