In this paper we study universality for quantum gates acting on qudits. Qudits are states in a Hilbert space of dimension d where d can be any integer ≥ 2. We determine which 2-qudit gates V have the properties (i) the collection of all 1-qudit gates together with V produces all n-qudit gates up to arbitrary precision, or (ii) the collection of all 1-qudit gates together with V produces all n-qudit gates exactly. We show that (i) and (ii) are equivalent conditions on V , and they hold if and only if V is not a primitive gate. Here we say V is primitive if it transforms any decomposable tensor into a decomposable tensor. We discuss some applications and also relations with work of other authors. We determine which 2-qudit gates V have the property that all 1-qudit gates together with V form a universal collection, in either the approximate sense or the exact sense. Here d is an arbitrary integer ≥ 2. Our results are new for the case of qubits, i.e., d = 2 (which for many is the case of primary interest). We treat the case d > 2 as well because it is of independent interest and requires no additional work. Since Deutsch [3] found a universal gate (on 3 qubits), universal gates for qubits have been extensively studied. We mention in particular the papers [1], [2] [4], [5] and [6] which will be further discussed in §2. First we set up some notations. A qudit is a (normalized) state in the Hilbert space C d . An n-qudit is a state in the tensor product Hilbert space The computational basis of H is the orthonormal basis given by the d n classical n-qudits where ||ψ|| 2 = |ψ i 1 i 2 ···in | 2 = 1. We say ψ is decomposable when it can be written as a tensor product |x 1 · · · x n = |x 1 ⊗ |x 2 ⊗ · · · ⊗ |x n of qudits. A quantum gate on n-qudits is a unitary operator L : ⊗n . These gates form the unitary group U(( . . , L k of gates constitutes a quantum circuit on n-qudits.
It is proven that single qudit gates and a two qudit gate alone are adequate to form a universal set of gates, provided that the two qudit gate is an entangling gate REF .
Universal quantum gates