Exact universality from any entangling gate without inverses
Aram W. Harrow · 2009
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