{'fraction_non_alphanumeric': 0.05872563005230623, 'fraction_numerical': 0.01367094626723728, 'mean_word_length': 3.5673181324647123, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Universality of single quantum gates

We supply a rigorous proof that an open dense set of all possible 2-qubit gates G has the property that if the quantum circuit model is restricted to only permit swap of qubits lines and the application of G to pairs of lines, then the model is still computationally universal.

The proof of "universality" of a given set of gates, i.e. universality for the class BQP (polynomial time quantum computation), consists of two steps: (1) showing that such a gate set is dense in P U (2 n ) for all n (= of qubits in system), and (2) checking polynomial efficiency, which is an exercise in the Kitaev-Solovay (K-T) algorithm [8]. It is known [2] that if the single-qubit gates alone are dense in the projective unitary group P U (2) = U (2)/U (1) ∼ = SO(3), then adding any additional 2-qubit gate which is entangling makes the gate set universal (G "entangling" means there exists a vector φ ⊗ ψ so that G(φ ⊗ ψ) = φ ⊗ ψ for any φ and ψ ).
Our theorem will also comprise these two aspects listed above but we will not comment on the efficiency aspect since this is by now routine and parallel to the discussion of Refs. [8,9].
For some open dense set O ⊂ P U (4) = U (4)/U (1), of projective unitaries on C 2 ⊗ C 2 , any gate G ∈ O is by itself universal for the class BQP (polynomial time quantum computation). Remark 1. Given [2] it is sufficient to prove that any element of P U (4) can be approximated by some composition of G and Swap gates. For among these elements will be (up to phase) general transformations of the form A⊗id, A ∈ U (2). Thus the general single-qubit gate is a consequence of denseness in P U (4). (Again the efficiency estimates are routine applications of the K-S algorithm and will not be given.) Remark 2. In the early days of the subject, the above theorem was stated by S. Lloyd [3]. After submission of this preprint, we were made aware of proofs of the statement in Refs. [4,5,6], but decided to leave this manuscript available to add another perspective.

Proof.
For some open dense O ⊂ P U (4), we will prove that for G ∈ O, the set {G, Swap • G • Swap} densely generates P U (4); as remarked this is sufficient. First we exhibit a single G with this property and then consider genericity.
Technically it is better to work with su(4), the Lie algebra g of P U (4). We find by brute force an element t ∈ g so that together with Ad Swap (t) := t , these two elements generate g as a Lie algebra. Explicitly if t i j = t αγ βδ with α, β, γ, δ qubit indices, then t γα δβ = t αγ βδ . To avoid estimating round-off errors we used exact arithmetic, choosing t 0 essentially at random from traceless 4 × 4 skew Hermitian matrices with entries of the form a i j + ıb i j , 1 ≤ i, j ≤ 4, a, b small integers. Having chosen t 0 and computed t 0 we randomly applied Lie-brackets to produce new elements until some subset of 15 (= dim su(4)) of the matrices thereby produced became linearly independent. This was established by finding a non-zero determinant when each of the 15 matrices was itself regarded as a row vector of length 15 within a 15 × 15 matrix. (The 16 th entry is determined by the trace = 0 condition and was therefore omitted.) Below we call this 15 × 15 determinant "det".
Next we show that for some open dense set Q ⊂ su(4), t ∈ Q implies that {t, t } generate su(4) as a Lie algebra. We checked Lie-generation of su(4) by verifying an open condition: det = 0. The condition det = 0 defines a (projective) real algebraic variety V inside R 15 identified with su(4) by Projective means that the variety is a union of lines through the origin: v ∈ V =⇒ a v ∈ V. A standard result [10], based on the implicit function theorem, states that varieties in R n which are proper subsets of R n are nowhere dense. Thus the points of R 15 where det = 0 form an open dense subset. It is interesting that this use of algebraic geometry can be replaced by a short self-contained number-theoretic lemma, see the Appendix.
A fundamental link between the bracket of a Lie algebra and commutators in the group is the identity [s, t] = lim →0 1 2 e s e t e − s e − t It follows that if some collection of brackets applied to {t, t } generate su(4), then for sufficiently small, the elements {e t , e t } generate a dense subgroup of SU (4). This is the key observation of the Kitaev-Solovay (K-S) algorithm [8]. Unfortunately K-S does not give a uniform upper bound on the Killing norm t K below which there is dense generation. This is because near the variety V, will have to be smaller for the higher degree terms of the Campbell-Baker-Hausdorf (CBH) formula not to spoil the linear independence of commutations of the logarithms.
However the upper bound on t K is a continuous function of the direction t/ t , which we will refer to as 0 (t/ t K ). This function vanishes precisely along the projective directions of V where det = 0. Thus there is an open subset of SU (4): where K-S applies and {e t , e t } generate a dense subgroup of SU (4). O is certainly not dense, but fortunately there is a simple extension of K-S which removes the upper bound on t . Consider the closed set C of one-parameter subgroups of SU (4) obtained as {e xt }, where det(t) = 0. LetC be the closed subset of SU (4) which is the union over C. Since conjugation by Swap commutes with taking powers, we may replace g ∈ SU (4) with any power of g in the search for a densely generating pair {g, g } := {g, Swap•g•Swap}. Consider those g belonging to the open dense subset SU (4)\C which obey the further condition that g k ∈ O for some k = 1, 2, 3, . . .. Call this subset U ⊂ SU (4). Since O is open and group multiplication is continuous, U is a union of open subsets, thus U is an open subset. Now consider: Lemma 2. Let P ∈ G be a one-parameter subgroup of a compact Lie group G, with its induced topology. Let I ⊂ P be any interval, then k∈Z I k is dense in P .
Proof. The power I k is either all of P or is itself an interval of P of length k · length(I). The first case occurs if id ∈ I or P is a circle subgroup. If id / ∈ I and P is noncompact, then {I k } consist of non-nested intervals of increasing length on a curve of irrational slope on a d-torus. Using this model, the lemma reduces to the well-known fact that lines of irrational slope are dense in the d-torus. Now consider the situation illustrated in Fig. 1. For y ∈ U, let I be an arbitrarily small interval surrounding y in its one-parameter subgroup. Using Lemma 2 and the openness of O, we can obtain aỹ such thatỹ k ∈ O. Specifically,ỹ k is required to approximate some small power x = y δ , δ 1, on the intersection of y's 1parameter subgroup with O, P y ∪ O. This establishes that U is dense in SU (4) \ C and therefore dense in SU (4), completing the proof of the theorem. Proof. First, a complex variety in C n is also a real variety in R 2n , so it is sufficient to consider the real case. To give an elementary proof, we first establish a lemma which is merely the simplest case of what is called the "weak approximation theorem" in the theory of adeles [7]. We thank Jeff Stopple and Keith Conrad for this reference.
Lemma 4 (Double Density Lemma). The map j : F −→ R × R defined by j(f ) = (j + (f ), j − (f )) has a dense image with respect to the usual metric topology.
Proof. Fix any point (p, q) ∈ R × R and consider the equations: Over R they may be solved by x = 1 2 (p + q) and y = √ 2 4 (p − q). Choosing rational approximations x 0 to x and y 0 to y we see that j + (x 0 + √ 2y 0 ) approximates p and j − (x 0 + √ 2y 0 ) approximates q to any desired precision.
Of course both embeddings j + and j − are individually dense in R. Let V ⊂ V be a proper variety, i.e. V = V , and let t ∈ V \ V. Consider a cubical neighborhood τ (t) = {s ∀ 0 < k ≤ n : t k − < s < t k + }. The double density lemma applied to each of the n coordinates implies that for any > 0 and any t ∈ V , we can find an s ∈ τ (t ) so that g(s) ∈ τ (t ). Put another way, the Galois involution g −1 = g scatters those elements of an -neighborhood of t 0 with field F coordinates uniformly over all of V , to form a dense set S which must meet τ (t ).
But the defining equation of V is algebraic, i.e. polynomial, so it holds equally before or after application of the field automorphism g. Consequently the sets V and V \ V are both preserved by g. Thus V \ V meets each τ (t ), as above, and hence is dense.