beamsplitter

Transcript

1 Generation of Universal Linear Optics by Any Beamsplitter † ∗ Adam Bouland Scott Aaronson Abstract In 1994, Reck et al. showed how to realize any unitary transformation on a single photon using a beamsplitter that nontrivially product of beamsplitters and phaseshifters. Here we show that any single mixes two modes, also densely generates the set of unitary transformations (or orthogonal transforma- m ≥ tions, in the real case) on the single-photon subspace with modes. (We prove the same result 3 for any two-mode real optical gate, and for any two-mode optical gate combined with a generic phase- shifter.) Experimentally, this means that one does not need tunable beamsplitters or phaseshifters for universality: any nontrivial beamsplitter is universal for linear optics. Theoretically, it means that one cannot produce “intermediate” models of linear optical computation (analogous to the Clifford group for qubits) by restricting the allowed beamsplitters and phaseshifters: there is a dichotomy; one either gets a trivial set or else a universal set. No similar classification theorem for gates acting on qubits is currently known. We leave open the problem of classifying optical gates that act on three or more modes. 1 Introduction Universal quantum computers have proved difficult to build. As one response, researchers have proposed limited models of quantum computation, which might be easier to realize. Three examples are the one clean qubit model of Knill and Laflamme [17], the commuting Hamiltonians model of Bremner, Jozsa, and Shepherd [3], and the BosonSampling model of Aaronson and Arkhipov [1]. None of these models are known or believed to be capable of universal quantum computation (or, depending on modeling details, classical even universal computation). But all of them can perform certain estimation or sampling tasks for which no polynomial-time classical algorithm is known. One obvious way to define a limited model of quantum computation is to restrict the set of allowed gates. However, almost every gate set is universal [19], and so are most “natural” gate sets. For example, Controlled-NOT together with any real one-qubit gate that does not square to the identity is universal [23]. As a result, very few nontrivial examples of non-universal gate sets are known. All known non-universal gate sets on O (1) qubits, such as the Clifford group [9], are efficiently classically simulable, if the input 1 and measurement outcomes both belong to an appropriately chosen qubit basis . As a result, it is tempting exist to conjecture that there does not such an intermediate gate set: or more precisely, that any gate set on O (1) qubits is either efficiently classical simulable (with appropriate input and output states), or else universal for quantum computing. Strikingly, this dichotomy conjecture remains open even for the special case of 1- and 2-qubit gates! We regard proving or disproving the conjecture as an important open problem for quantum computing theory. ∗ MIT. email: [email protected] † MIT. email: [email protected] 1 But not necessarily otherwise! For instance, suppose that a nonuniversal gate set G is efficiently simulable if inputs and ′ ′ G by a change of qubit basis to obtain a gate set G outputs are in the computational basis. . Clearly G Now conjugate is ′ efficiently classically simulable in the new qubit basis. However, it is unclear how to simulate the gates G if inputs and outputs are in the computational basis. Along these lines, there is evidence that Clifford gates [16], permutation gates [15], and even diagonal gates [3] can be hard to simulate in arbitrary bases. 1

2 In this paper, we prove a related conjecture in the quantum linear optics model. In quantum optics, the Hilbert space is not built up as a tensor product of qubits; instead it’s built up as a direct of optical sum gate is then just a unitary transformation that acts nontrivially on (1) of the modes, and modes. An optical O -mode gate, we assume that we can apply it to any subset k as the identity on the rest. Whenever we have a k modes (in any order), as often as desired. The most common optical gates considered are beamsplitters , of 2 2 unitary matrix with determinant − 1 ; which act on two modes and correspond to a 2 phaseshifters , × and iθ . Note that any unitary transformation acting on the which act on one mode and simply apply a phase e one-photon Hilbert space automatically gets “lifted,” by homomorphism, to a unitary transformation acting n on the Hilbert space of n -photon linear-optical group — photons. Furthermore, every element of the n that is, every -photon unitary transformation achievable using linear optics—arises in this way (see [1], Sec. III for details). Of course, if ≥ 2 , then there are also n -photon unitaries that cannot be achieved n n linear-optically: that is, the -photon linear-optical group is a proper subgroup of the full unitary group on n -photon Hilbert space. S universal on m modes if it generates a dense subset of either SU ( m ) We call a set of optical gates not (in the complex case) or m ) (in the real case). To clarify, if S is universal, this does ( mean that SO linear optics with S is universal for quantum computing! It only means that S densely generates the one- photon linear-optical group—or equivalently, the n -photon linear-optical group for any value of n . The latter kind of universality is certainly relevant for quantum computation: first, it already suffices for the BosonSampling proposal of Aaronson and Arkhipov [1]; and second, if the single resource of adaptive measurements is added, then universal linear optics becomes enough for universal quantum computation, by the famous result of Knill, Laflamme, and Milburn (KLM) [18]. On the other hand, if we wanted to -qubit Hilbert space onto an m -mode linear-optical Hilbert space, then as observed by Cerf, map a directly k k Adami and Kwiat [6], we would need m just for dimension-counting reasons. ≥ 2 all phaseshifters and all beamsplitters is universal for Previously, Reck et al. [22] showed that the set of linear optics, on any number of modes. Therefore it is natural to ask: is there S set of beamsplitters any and phaseshifters that generates a nontrivial set of linear-optical transformations, yet that still falls short of all S does something more than permuting generating of them? Here by “nontrivial,” we simply mean that the modes around or adding phases to them. S existed, we could then ask the further question of whether the n -photon subgroup gener- If such a set ated by S was (a) efficiently simulable using a classical computer, despite being nontrivial (much like the Clifford group for qubits), n (b) already sufficient for applications like BosonSampling and KLM, despite not being the full -photon linear-optical group, or (c) of “intermediate” status, neither sufficient for BosonSampling and KLM nor efficiently simulable classically. The implications for our dichotomy conjecture would of course depend on the answer to that further question. no such set S exists . In this paper, however, we show that the further question never even arises, since Indeed, any beamsplitter that acts nontrivially on two modes is universal on three or more modes. What makes this result surprising is that it holds even if the beamsplitter angles are all rational multiples of π . A priori, one might guess that by restricting the beamsplitter angles to (say) , one could produce a 4 π/ linear-optical analogue of the Clifford group; but our result shows that one cannot. 2 +1 [21]. Note that these two Some references use a different convention and assume that beamsplitters have determinant ( ) 0 1 . conventions are equivalent if one assumes that one can permute modes, i.e. apply the matrix which has determinant − 1 1 0 2

3 Our proof uses standard representation theory and the classification of closed subgroups of SU (3) [8, 13, 11]. From an experimental perspective, our result shows that any complex nontrivial beamsplit- ter suffices to create any desired optical network. From a computational complexity perspective, it implies a dichotomy theorem for optical gate sets: any set of beamsplitters or phaseshifters generates a set of op- -photon input states), or else universal for trivially erations that is either n classically simulable (even on quantum linear optics. In particular, any nontrivial beamsplitter can be used to perform BosonSampling; 3 there is no way to define an “intermediate” model of BosonSampling by restricting the allowed beamsplit- ters and phaseshifters. Note that our result holds only for beamsplitters, i.e., optical gates that act on two modes and have . We leave as an open problem whether our result can be extended to arbitrary two-mode determinant − 1 gates, or to gates that act on three or more modes. Our work is the first that we know of to explore limiting the power of quantum linear optics by limiting Previous work has considered varying the available input states and measurements. the gate set. For example, as mentioned earlier, Knill, Laflamme, and Milburn [18] showed that linear optics with adaptive measurements is universal for quantum computation. Restricting to nonadaptive measurements seems to reduce the computational power of linear optics, but Aaronson and Arkhipov [1] gave evidence that the resulting model is still impossible to simulate efficiently using a classical computer. If Gaussian states are used as inputs and measurements are taken in the Gaussian basis only, then the model is efficiently simulable photon-number measurements, there is recent evidence classically [2]; but with Gaussian-state inputs and 4 for computational hardness. -based We hope that this work will serve as a first step toward proving the dichotomy conjecture for qubit quantum circuits (i.e., the conjecture that every set of gates is either universal for quantum computation or else efficiently classically simulable). The tensor product structure of qubits gives rise to a much more complicated problem than the direct sum structure of linear optics. For that reason, one might expect the linear-optical “model case” to be easier to tackle first, and the present work confirms that expectation. 2 Background and Our Results modes, the state of a photon is described by a vector | ψ 〉 in an m - In a linear optical system with m 〉 s ,s dimensional Hilbert space. The basis states of the system are represented by strings ...s | where 1 m 2 th m 0 , 1 } s i denotes the number of photons in the mode, and Σ ∈ { is the total number of photons (in s i j =1 j 100 . , | 010 〉 and | 001 〉 | this case, one). For example a one-photon, three-mode system has basis states 〉 k -local gate is a k × g unitary matrix which acts on k modes at a time while acting in direct sum A k m − k modes. A beamsplitter b is a two-local gate with determinant − 1 . with the identity on the remaining ( ) ∗ α β 2 2 | b where | α = Therefore any beamsplitter has the form + | β | b = 1 . Let denote the matrix ∗ ij α β − action of applying the beamsplitter to modes i j of a one-photon system. For example, if m = 3 , we and have that     ∗ ∗ α − α β β 0 0 ∗     0 0 α − β 1 0 b b = = 31 12 ∗ β 0 α 1 0 0 when written in the computational basis. A beamsplitter is called nontrivial if | α | 6 = 0 and | β | 6 = 0 , i.e. if the beamsplitter mixes modes. We say that a set of optical gates densely generates a continuous group G of unitary transformations, S H H if the group is a dense subgroup of G (that is, if generated by ≤ G and H contains arbitrarily S close approximations to every element of G ). Then we call S universal on m modes if it densely generates ) SU m ) or SO ( m ( when acting on m modes. (Due to the irrelevance of global phases, this is physically 3 Here by “intermediate,” we mean computationally intermediate between classical computation and universal BosonSampling. 4 See http://www.scottaaronson.com/blog/?p=1579 3

4 equivalent to generating U m ) or O ( m ) respectively.) In this definition we are assuming that whenever we ( k -mode gate in , we can apply it to any subset of k modes (in any order), as often as desired. Note have a S ( m evolutions to be universal as well; this is because the distinction between real that we consider real SO ) 5 to computational applications of linear optics, such as and complex optical networks is mostly irrelevant the KLM protocol [18] and BosonSampling [1]. A basic result in quantum optics, proved by Reck et al. [22], says that the collection of all beamsplitters and phaseshifters is universal. Specifically, given any target unitary modes, there exists a sequence U on m 2 m U ) beamsplitters and phaseshifters whose product is exactly of . Reck et al.’s proof also shows an O ( can be written as the product O analogous result for real beamsplitters - namely, that any orthogonal matrix 2 ′ b real beamsplitters. Furthermore, it can easily be shown that there exist two beamsplitters b , ( ) of m O ′ . Therefore b and b whose products densely generate can be used to simulate any real beamsplitter, (2) O ′ b,b and hence by Reck et al. [22], the set } is universal for linear optics. { In this paper, we consider the universality of a single b . If b is trivial, then on m modes beamsplitter b P , the set of m × m unitary matrices with all entries having the matrices generates a subgroup of m ij norm zero or one. This is obviously non-universal, and the state evolutions on any number of photons are trivial to simulate classically. Our main result is that any nontrivial beamsplitter densely generates either all orthogonal transformations on three modes (in the real case), or all unitary transformations on three modes (in the complex case). From this, it follows easily from Reck et al. [22] that such a beamsplitter is also m modes for any ≥ 3 . universal on m Let b be any nontrivial beamsplitter. Then the set S Theorem 2.1. { b , obtained by applying ,b } ,b = 23 12 13 6 are densely generates either SO (3) b b to all possible pairs among three photon modes, (if all entries of real) or SU (3) (if any entry of b is non-real). Corollary 2.2. Any nontrivial beamsplitter is universal on m ≥ 3 modes. Proof. By Theorem 2.1, the set { b S ,b = ,b densely generates all orthogonal matrices with deter- } 23 13 12 . But since b has determinant − 1 , we know that S must generate all orthogonal matrices with 1 minant 7 ′ densely generates the action of any real beamsplitter Therefore, S as well. b 1 acting on determinant − S also densely generates all orthogonal matrices on m modes two out of three modes. So by Reck et al [22], m . 3 ≥ for Note that, although our proof of universality on three modes is nonconstructive, by the Solovay-Kitaev , finds a sequence of b ’s ap- Theorem [7], there is an efficient algorithm that, given any target unitary U ( ) 3 . 97 1 log U up to error ε ( in O proximating ) time. Thus, our universality result also implies an efficient ε algorithm to construct any target unitary using beamsplitters in the same manner as Reck et al. [22]. We now proceed to a proof of Theorem 2.1. 3 Proof of Main Theorem We first consider applying a fixed beamsplitter ) ( ∗ α β , b = ∗ α − β 5 The one case we know about where the real vs. complex distinction might matter is when using error-correcting codes. There, applying all possible orthogonal transformations to the physical modes/qubits might not suffice to apply all orthogonal transformations to the encoded modes/qubits. This could conceivably be an issue, for example, in the scheme of Gottesman, Kitaev, and Preskill [10] for universal quantum computing with linear optics. 6 Technically, we could also consider the unitaries b to the same pairs of modes but reversing , b b , b , obtained by applying 32 21 31 their order. However, this turns out not to give us any advantage. 1 − 7 ′ ′ ′ can be written as O = b Indeed any orthogonal O − 1 with determinant O = . O O for some b 1 of determinant 12 12 4

5 2 2 where are complex and | α | α + | β | β = 1 , to two modes of a three-mode optical system. We and take pairwise products of these beamsplitter actions to generate three special unitary matrices. These three unitaries densely generate some group of matrices (3) . We then use the representation theory of G ≤ SU described in the work of Fairbairn et al. [8], Hanany & He [13, 14], and Grimus & Ludl (3) subgroups of SU matrices (if the beamsplitter is real) or all [11] to show that the beamsplitter must generate either all SO (3) matrices (if the beamsplitter has a complex entry). (3) SU ,R ,R Consider applying our beamsplitter to a three-mode system. Let R be defined as the pairwise 3 2 1 products of the beamsplitter actions below:     ∗ 2 ∗ ∗ β α αβ α 0 β 2 ∗ ∗ 2 ∗     | | α β − αβ β α | | α − β R = b = b b = b , R = , 13 12 1 2 23 13 ∗ ∗ ∗ 2 α − β 0 β β α α −   ∗ ∗ 2 α αβ β ∗ ∗ 2   β −| α β | − α b = = b R . 23 12 3 ∗ − β α 0 R ,R ,R . Since (3) are even products of matrices of determinant − 1 , they are all elements of SU 3 1 2 G ≤ SU (3) be the subgroup densely generated by products of the elements { R and their ,R } Let ,R 3 1 2 8 . Let inverses be the set of matrices representing G under this construction. First we will show that G M these matrices G . form an irreducible representation of G M Claim 3.1. { R The set ,R . ,R G } generates an irreducible three-dimensional representation of 3 2 1 Suppose that some matrix Proof.   A D G   B E H U = C F I , commutes with R R , and R I . Then we claim that U is a constant multiple of the identity, i.e. A = E = 3 1 2 D = G = H = and = C = F = 0 . B From the claim, it follows easily that the representation is irreducible. Indeed, suppose the representa- tion is reducible, so preserves a non-trivial subspace. Since our representation is unitary, this implies that 9 our representation is decomposable, i.e. by a change of basis it can be brought into block-diagonal form. In the new basis, the matrix consisting of 1’s on the diagonal in the first block, and 2’s in the diagonal of G R the second block, commutes with all elements of ,R , and in particular with ,R . But that matrix 3 1 2 is not a multiple of the identity. Hence if only multiples of the identity commute with , the ,R ,R R 2 1 3 representation must be irreducible. We now prove the claim. First, since commutes with R , U 1         ∗ ∗ ∗ ∗ 2 2 αβ A D G αβ β α α A D G β 2 2 ∗ ∗         B E H − αβ | β | αβ − B E H α | β | α = . ∗ ∗ C F I α β β 0 0 C F I − α − This imposes nine equations. Below we give the equations coming from the (1,1), (1,2), (2,2), (2,3), and 1 − 8 b Since = b , the beamsplitter is capable of generating the inverses of the R as well. ij i ij 9 To see the equivalence of “reducible” and “decomposable” for unitary representations, it suffices to note that, if a set of unitary matrices always map a subspace V to itself, then they cannot map any vector not in V to a vector in V , since this would violate unitarity. 5

6 (3,2) entries of the above matrices respectively. ∗ + G ) β = ( Cα + B ) β ( , (1) Dα ∗ 2 ∗ A ) β − = D ( α − + α Fα ) , (2) ( E ∗ ∗ = Dαβ , (3) Bβ Fββ + ∗ ∗ ∗ ∗ ∗ = Gαβ − + − + Iββ Hα , (4) Bαβ Eββ Hα ∗ = Dβ. (5) Cβ Note that equations (5) and (1) imply that ∗ Gβ . (6) = Bβ So by equation (4) we have ∗ ∗ . Eββ (7) Iββ = I < | < 1 , we have β = E . So since | 0 ∗ ∗ E , = Bβ = and Cβ I = Dβ . In total so far we have Gβ commutes with U Next, since , R 2         ∗ ∗ A D G β α 0 α β 0 A D G ∗ ∗ 2 2 ∗ ∗         B E H β | | α − α β β β | | α − α B E H . = 2 ∗ ∗ 2 ∗ ∗ C F E − α β β α α − β β α C F E This imposes another nine equations. Here are the equations from the (1,1), (2,1) and (2,2) entries respec- ∗ ∗ E , Gβ = Bβ tively, which we have simplified using and Cβ I = Dβ : = ∗ ∗ = − Gα β, Dβ (8) Dββ ∗ ∗ ∗ ∗ ∗ = Aββ Hα − Cα (9) β β , Eββ − ∗ ∗ ∗ − Fα = β Hβ . (10) Dββ ∗ Gβ = Bβ , imply that Dβ = Hβ , and Note that equations (8) and (10), combined with the fact that hence D = H . ∗ ∗ ∗ ∗ ∗ ∗ Plugging this in to equation (9), we see that Dα − Cα Eββ β β . Using Cβ = = Dβ Aββ − ∗ ∗ these last two terms cancel, so , and hence E = Aββ . So overall we have established that Eββ = A ∗ ∗ I , D = H , B = F , Gβ A Bβ = and Cβ E = Dβ . = = B . Then we have from above that B = F = = 0 = 0 . By equation (8) we also have Now suppose G ∗ ∗ D ⇒ Dβ = 0 since 0 < | β | < 1 . Hence we have C = 0 as well by the fact that Cβ = = Dβ . Dββ U is a multiple of the identity, as desired. Therefore = 0 ; then we will derive a contradiction. B 6 = 0 So it suffices to prove that B . Suppose commutes with R , Since U 3         ∗ ∗ 2 2 ∗ ∗ β α αβ α αβ A D G β A D G ∗ ∗ 2 2 ∗ ∗         B A D | B A D − α β −| α | β − α β β −| α . = ∗ ∗ β 0 α − β C B A 0 C B A − α This imposes yet another nine equations, but we will only need the one coming from the (2,2) entry of the above matrices to complete the proof: ∗ ∗ ∗ Bα β = . (11) Bαβ − ∗ 6 = 0 , equation (11) implies that Since = − α B , i.e. α is pure imaginary. Furthermore, since α ∗ = Bβ , we have Gβ G 6 = 0 as well. Using this, we can write out equations (2) and (3) as follows: ∗ 2 − ) β ( = D ( α Bα − α ) ⇒ Gβ = D (1 − α ) , (12) ∗ ∗ Bβ Dαβ + Fββ ⇒ = G = Dα + Gβ. (13) 6

7 Summing these equations, we see that = . Plugging back into equation (13), we see that β = 1 − α . G D 2 2 is pure imaginary this contradicts Since + | β | | = 1 . | α α G , then is a multiple of the identity. This proves U To summarize, if commutes with all elements of U the claim and hence the theorem. G . We now G We have learned that the set forms a three-dimensional irreducible representation of M , to show that G is not finite. leverage this fact, along with the classification of finite subgroups of SU (3) is infinite. Claim 3.2. G is finite then { R Proof. ,R G By Claim 3.1, if . The } generates an irreducible representation of G ,R 3 2 1 (3) consist of the finite subgroups of SU (2) , finite subgroups of exceptional finite subgroups, and two SU 12 infinite families of “dihedral-like” groups, whose irreducible representations are classified in [8, 13, 14, 11]. could be, and showing that Our proof proceeds by simply enumerating the possible finite groups that G ,R ,R } cannot generate an irreducible representation of any of them. R { 1 3 2 SU (3) . Of the 12 excep- G First we eliminate the possibility that is an exceptional finite subgroup of , Σ(60) × Z , tional subgroups, only eight of them have three-dimensional irreps: they are labeled Σ(60) 3 × × Z , , Σ(216) , Σ(36 × 3) , Σ(216 Σ(168) 3) , and Σ(360 × 3) . So by Claim 3.1, if G is finite and Σ(168) 3 exceptional, then it is one of these eight groups. The character tables of these groups are provided in [8] and [13]. Recall that the character of an element R ,R of a representation is the trace of its representative matrix. The traces of the matrices , denoted ,R 3 2 1 ,T , are given by T ,T 3 1 2 ∗ 2 (14) 2 α α = T − 1 ∗ 2 T ) (15) + 2 α = ( α 2 2 ∗ 2 −| T + α − α −| = = α | α + 2Im( α ) (16) | 3 Σ(60) , We will show that these cannot be the characters of the elements of a three-dimensional irrep of × Z Z , Σ(168) , Σ(168) × Σ(60) . , Σ(216) , Σ(36 × 3) , Σ(216 × 3) , or Σ(360 × 3) 3 3 Σ(60) up to conjugation [8]. The characters of their elements There are two three-dimensional irreps of { } √ √ 1+ 5 5 1 − 2 1 , , , 3 0 − all lie in the set | . Note that 0 < , α | cannot be in this < 1 , which means that T 3 2 2 √ √ √ 5 5 − 1 − 1 and Im( α ) = 0 . But then this implies α T ± = , T and . Plugging this into T set unless = 1 2 3 2 2 Σ(60) is not . G we see they are not in the set of allowed values. Hence Z The characters of the three-dimensional irreps of are identical to those of Σ(60) , but with the Σ(60) × 3 2 πi 4 πi 3 3 additional possibility that they can be multiplied by e . The same argument as above shows that in e or √ √ √ √ ) ( 1+ 1 − 5 5 = or α = ± order for T . to be in the set of allowed characters, we must have ± 1 ± α 3 i 3 8 2 T are not in the set of allowed characters, hence is T , we see the possible values of Plugging these into G 1 1 Z not . Σ(60) × 3 up to conjugation [8]. The characters of their elements Σ(168) There are two three-dimensional irreps of √ } { 1 2 | i − 7) ( . Since 0 < ± α | 1 < 1 , if T is in this set it must have , 0 , ± 1 , 3 all lie in the set S = 3 2 √ √ √ 7 7 1 1 3 − 2 7) = ± i α ± ± 1 and i . This implies that α . Therefore we must have = − ( i ± value 2 8 4 8 4 √ 7 1 ∗ 2 α ± = ± S i . Regardless of the signs chosen, this means that T is not in the set of allowed values. 1 2 2 G is not Σ(168) . Hence Σ(168) × Z The characters of the three-dimensional irreps of are identical to those of Σ(168) , but with 3 2 πi 4 πi 3 3 e . The same argument as above shows the additional possibility that they can be multiplied by e or √ √ √ 7 1 1 = α = i , α to be in the set of allowed characters, we must have ± , ( ± that in order for 5 ± i ± 3) T 3 4 4 4 √ √ √ √ 3+ 7 1 √ or 21 − 13 ± ± = α 7 T i . Plugging these into T , we see that the possible values of are not 1 1 8 4 2 in the set of allowed characters, hence G is not Σ(168) × Z . 3 7

8 There is one three-dimensional irrep of up to conjugation [8]. The characters of its elements all Σ(216) cannot be in this set, 0 , 3 } . Since T lie in the set 1 G is not Σ(216) . − { , 3 3) up to conjugation [13]. The characters of their There are eight three-dimensional irreps of Σ(36 × πi 2 2 7 11 2 n ± e . , ± e elements all lie in the set S , ± e = , ± e { 0 , ± e , ± ± 3 , ± 3 e 1 , ± 3 e , e } where e = 3 n 3 4 12 3 12 3 2 2 11 2 7 | Re( and 0 < | α | T < 1 , if T . ∈ S then we must have T } ∈ {± e Since , ± e ) = e −| ± e α ± , , 3 3 3 3 12 12 3 { } √ √ √ √ ± 3 1 − i 8 ± ± i ± 3 5 α α ∈ Solving for gives us . A straightforward evaluation of possible values of , 4 4 S shows T . / ∈ T . So T 3) and T × cannot be characters of these irreps, and hence G is not Σ(36 3 1 1 1 × up to conjugation [13]. The characters of their There are seven three-dimensional irreps of 3) Σ(216 elements all lie in the set 7 4 7 4 2 5 2 5 2 5 7 4 7 5 2 4 2 − e , − e , , − e e , − e ± , , e . + e e , 2 e ± + e , , − e 3 − 2 e , 1 ,e ± + e , ,e 0 + 2 e { , − 2 e = − e S } ± 3 9 9 9 9 9 9 9 9 3 9 9 9 9 9 9 9 9 and hence T S , then for each case we can solve for α ∈ T If . As above, a straightforward calculation 1 3 T Σ(216 ∈ S do we have T . ∈ S . Hence G is not shows that for no × 3) 1 3 Σ(360 × 3) up to conjugation [13]. The characters of their There are four three-dimensional irreps of elements all lie in the set 8 2 11 2 2 3 4 14 2 7 13 4 ± e e } , 3 e S , 3 e = e , − e − − e { 0 , − e , e − e ± − , − e , − e 1 , , − ± e e − e . − , − e , 15 5 3 3 15 5 5 15 15 3 15 15 3 5 15 15 Hence ∈ T ∈ S . do we have G is not Again a straightforward calculation shows that for no S T 1 3 . × Σ(360 3) is not an irrep of an exceptional finite subgroup of We have therefore shown that (3) . G SU M Next we will show that is not in one of the two infinite families of “dihedral-like” finite subgroups G M SU , known as the C-series and the D-series groups. The most well-known members of these series are of (3) 2 2 2 ∆(6 n n ) , labeled by n ∈ N , which consist of all 3 by 3 even permutation matrices (for ∆(3 n ) ) ) and ∆(3 2 ∆(6 ) ) whose entries are replaced by n th roots of unity. In early or all 3 by 3 permutation matrices (for n 2 2 , such as Fairbairn, Fulton, and Klink [8], only ∆(3 n n ) and ∆(6 works describing subgroups of SU ) (3) However in 2011, Ludl [20] pointed out that there exist nontrivial appear as elements of these series. 2 2 which are missing from these references. Fortunately these groups have ∆(6 n n ) ) and subgroups of ∆(3 now been fully classified [12], and sufficient constraints have been placed on their representations [11] that G is an irrep of any C or D-series group. we can eliminate the possibility that 2 2 ∆(3 n is an irrep of ) or ∆(6 In the following, we first eliminate the possibility that G ) following n M G the work of Fairbairn, Fulton, and Klink [8]. Afterwards we show that these arguments suffice to prove M is not an irrep of any of the C-series or D-series groups, using the work of Grimus and Ludl [11]. 2 ,m ) are labeled by integers m n The three-dimensional irreps of ∈ { 0 ,...,n − 1 } , and have ∆(3 1 2 − A,C,E ∈{ 0 ,...,n p,q 1 } . The respective characters and numbers conjugacy classes labeled by letters 0 for conjugacy classes C ( p,q ) and E ( p,q ) or are either πi 2 2 πi 2 πi m p + m )+ q ) q + ) p p ( m ( q − m m ( p + q )) − ( ( m 2 1 1 2 1 2 n n n e + e e (17) + A ( ) . for conjugacy class p,q 2 ) G n ∆(3 is an irrep of for some n —we will derive a contradiction shortly. Then the Assume that M R E must be zero (if R ) or of the form of equation is a representative of conjugacy class C or trace of each i i R is a representative of conjugacy class A ). However, we can show that none of the traces T can be (17) (if i i 2 T 0 cannot be zero as 0 < | α | because our beamsplitter is nontrivial. Indeed < 1 . We know that in order 3 ∗ 2 . to be zero, we need = 2 α for , which implies | α | = 2 which is not possible, and likewise with T α T 1 2 must have the form of equation (17), which implies each R Hence each is in conjugacy class T ( p ,q ) A i i i i p ,q . However, looking at the multiplication table for this group provided in [8, Table for some choice of i i ′ ′ ′ ′ ) A ( p VIII], we have that ,q A ) = A ( p + q mod n,p ( + q p,q mod n ) . Hence the T ’s cannot possibly i 2 ∆(3 n n ) for any generate all of , since they cannot generate elements in the conjugacy classes C ( p,q ) or 8

9 2 E . This contradicts our assumption that the R ( ’s generate an irrep of ∆(3 n p,q ) . Therefore G ) is not i M 2 ) for any n . ∆(3 an irrep of n is an irrep of any of the C-series We now extend this argument to eliminate the possibility that G M groups. In Appendix E of [11], Grimus and Ludl show that for any three-dimensional irrep of a C-series group, there exists a basis (and an ordering of that basis) in which all elements of the A conjugacy classes are represented by diagonal matrices and E(0,0) is represented by   0 1 0   0 0 1 . (18) 1 0 0 From this it can be easily shown that in any three-dimensional irrep of a C-series group, all elements of 2 10 n ) as a type C and E are represented by traceless matrices. In our previous arguments eliminating ∆(3 R can be traceless, so each of the possibility, we showed that none of the generators R must be of type i i A. Again this is a contradiction since elements of type A generate an abelian group and is nonabelian. G M Hence G cannot be an irrep of one of the C-series groups. M (3) . We begin by showing that G Next we turn our attention to the D-series finite subgroups of SU M 2 cannot be an irrep of ) for any n , and we will later generalize this to eliminate all D-series groups as ∆(6 n 2 n ) contains 6 ∆(6 A,B,C,D,E,F and possbilities. The group families of conjugacy classes, labeled by 2 as above. The three-dimensional irreps of ∆(6 n , which ) are again labeled by ( m by integers ,m p,q ) 2 1 0) , (0 ,m ) or ( m,m ) , as well as t ∈{ m, , 1 } . The character of each element is 0 now take values in ( πi 2 2 πi 2 πi p m p + m q ) + p m )+ ( ( m q − m ( ( p + q )) m ) q − ( 1 1 2 1 2 2 n n n A ( Tr( e )) = p,q + (19) e + e 2 πi ) ( t q p + m m 2 1 n 1) Tr( e B ( p,q )) = ( (20) − n 2 πi q − p − p ( m )+ m t ( ) 1 2 n 2 )) = ( p,q D − Tr( 1) (21) e ( n 2 πi m ( + m q q − p − ) t ( ) 1 2 n 2 p,q F 1) − )) = ( e ( Tr( (22) C p,q )) = Tr( E ( ( )) = 0 (23) Tr( p,q 2 . Again assume by way of is an irrep of ∆(6 n We now eliminate the possibility that G for any n ) M 2 n n G ) for some ∆(6 . Then each R is an irrep of must be in one of the families of contradiction that i M A,B,C,D,E,F , and each trace T must have the corresponding character from equations conjugacy classes i T . cannot be 0 (19)-(23). As noted previously each R F must be in classes A,B,D or , so in fact each i i Furthemore, we will show the following Lemma: 2 ) . is an irrep of ∆(6 Lemma 3.3. G If , then at least two of the R A are in conjugacy class family n i M By Lemma 3.3, at most one of the R . ’s is in class B , D or F while the remaining R A ’s are in class i i However, by examining the multiplication table for this group provided in [8, Table VIII], one can see that F , D , or B cannot generate A any number of elements from conjugacy class plus one element from class 2 the entire group. This contradicts our assumption that the R n ’s generate an irrep of ) . Hence G is ∆(6 i M 2 2 n ) so G cannot be ∆(6 not an irrep of ∆(6 ) by Claim 3.1. n We now prove Lemma 3.3 before continuing the proof of Claim 3.2. 2 n is an irrep of ∆(6 G Proof of Lemma 3.3. ) . We will show that at most one of the matrices Assume that M ,R must be representatives of R can be of class B , D or F . Hence at least two of { R ,R ,R } ,R 1 2 2 3 3 1 and show that it is not possible conjugacy class R A , R . We proceed by enumerating all pairs for i 6 = j j i R . and R for both B , D or F to be of class j i 10 To see this, note that by the group multiplication table in [13] Table VIII, we have that A(p,q)=E(p,q)E(0,0)E(0,0), so A(p,q) is in a D-series group if and only if E(p,q) is in the group. Additionally, since A(p,q)E(0,0)=E(p,q), all elements of type E are obtainable by multiplying an element of type A by E(0,0). Since in this basis the A matrices are diagonal, and E(0,0) is represented by the above matrix (18), this implies the claim for elements of type E. A similar argument holds for the elements of type C. 9

10 Let a bi where a and b are real. If R α is of conjugacy class B,D or F , then T = has norm 1 , which + i i : a imposes the following equations on and b 2 2 2 2 2 2 | + b | T = 1 + 4[ a ⇒ (1 − a ) + b ( (3 + a )] = 1 (24) a ) 1 2 2 2 2 2 2 a T b ⇒ ) = 1 + 4[ a | (1 + a ) + b ( (1 − 3 a )] = 1 (25) | + 2 2 2 2 2 2 a T + b | ) = 1 + 4 b ⇒ = 1 (26) | ( 3 R and First suppose that R are both members of conjugacy classes B , D , or F . Then | T = | 1 1 2 2 2 2 | . 0 < | α | = 1 = a | + b The only solutions to equations (24) and (25) in which < 1 are T 2 ) ( √ ) ( √ √ √ √ √ 1 1 ± ± 2 − 5 3( and 5 − 2) ,b = a = Note also that the product . 2 5 − ,b = 0 = ± a 2 2 R R must be in conjugacy class C or E according to the group multiplication table in [8, Table VIII]. 1 2 2 is an irrep of Hence the trace of must be 0 if G . This implies that R ∆(6 n R ) 2 1 M ) ( 3 2 ∗ 2 3 2 ∗ α α | β | α ) = 1 + β + β Tr( −| α | R (27) −| + | R = 0 − 1 2 a = + bi Since we have a and b are one of the six possibilities above, one can see α where the values of 3 ∗ 3 which satisfies equation (27). Indeed, note that α α β is nonzero and pure imaginary, that there is no − while the rest of the expression is real, so the terms in equation (27) cannot sum to zero. This provides the , desired contradiction. We conclude that R R cannot both be of conjugacy class B . D , or F and 1 2 R and Next suppose that R . If are both of conjugacy class B , D or F . Then | T = 1 | = | T | 3 1 3 1 2 2 2 + bi as before, the equations (24) and (26), combined with the fact that 0 < | α | α = a = + b a < 1 , √ √ imply that ± and = 5 − 2 . Again, using the group multiplication table in [8, Table VIII] we a = 0 b E R is of class C or must have that so R 3 1 2 ∗ 2 ∗ ∗ 3 2 2 β α α | + + α α ) = + | β | Tr( (1 + | + β R + α R ) = 0 (28) 1 3 √ √ 2 3 ∗ + 5 − 2 , this is a contradiction—for the terms α | α α of equation (28) are nonzero and | i ± α Since = , cannot both be of conjugacy class R pure imaginary while the remaining terms are real. Hence R B and 3 1 D , or F . R | and R . If are both of conjugacy class B , D , or F . Then | T = 1 Finally suppose that = | T | 3 3 2 2 2 2 2 a bi 0 < | α | + = a then the only solutions to equations (25) and (26) in which + b = < 1 are α ( ) √ √ = ± ,b = 0 a ≈± and a ≈ 0 5 437668 ,b ( 0 . 457975) . Furthermore using the group multiplica- 2 − . tion table in [8, Table VIII] we must have that R R is of class C or E so 3 2 3 ∗ ∗ 2 2 ∗ ∗ ∗ 2 ) = R − α | α | (29) + | β | Tr( ( αβ α − α R β − − 2 α α ) = 0 3 2 With slightly more work, one can again check that equation (29) cannot be satisfied with the above values 2 2 , under the additional constraint that | α | of + | β | α = 1 , providing the desired contradiction. Hence R 2 R cannot both be of conjugacy class B , and , or F , which completes the proof of Lemma 3.3. D 3 2 2 6 is an irrep of n We have therefore eliminated the possiblity that ) for any n , and so G ∆(6 = ∆(6 n G ) M by Claim 3.1. We now extend this argument to eliminate the possibility that G is an irrep of any of the D-series M groups. In Appendix G of [11], Grimus and Ludl show that for any three-dimensional irrep of a D-series group, there exists a basis (and an ordering of that basis) in which all elements of the A conjugacy classes are represented by diagonal matrices, and E(0,0) and B(0,0) are represented by     0 1 0 1 0 0     0 0 1 0 0 1 → 0) , (0 E (30) B (0 , . 0) →± 0 1 0 1 0 0 10

11 From this it can be easily shown that in any three-dimensional irrep of a D-series group, all elements of type C and E are represented by traceless matrices, and all elements of type B, D and F are represented 11 2 n In our previous arguments eliminating ) as a possibility, by matrices whose trace has unit norm. ∆(6 we showed none of our generators can be traceless, and at most one of them can have a trace of norm R i 1. Hence at least two of our generators are of type A and at most one of them is of type B, D or F. Again this is a contradiction since two elements of type A and one of type B, D or F do not suffice to generate any D-series group - in particular they cannot generate E(0,0). Hence G cannot be an irrep of any of the M cannot be an irrep of any of the dihedral-like subgroups G D-series groups. This concludes the proof that M of (3) . SU SU (2) . Since SU (2) is a double cover of SO (3) , G Finally we will show that is not a finite subgroup of is a finite subgroup of SU (2) if G must be either a finite subgroup of SO (3) or else the double cover G , then SO . The dihedral and cyclic subgroups of such a subgroup. We first eliminate the finite subgroups of (3) cannot be one of these by Claim 3.1. The icosahedral subgroup G have no three-dimensional irreps; hence Σ(60) so has already been eliminated. The octahedral and tetrahedral subgroups do have is isomorphic to 0 , ± 1 three-dimensional irreps. However, the characters of their elements all lie in the set ± 3 } , so these { , SU (3) were eliminated. can be eliminated just as the exceptional groups of SO (3) . The binary dihedral groups, Now all that remains are double covers of the finite subgroups of G also known as the dicyclic groups, have no three-dimensional irreps, so cannot be a binary dihedral group by Claim 3.1. The binary tetrahedral group has one three-dimensional irrep, with character values in the set . So 1 , ± 3 } ± T { cannot be in this set as noted above. , 0 3 0 , ± 1 , ± 3 } , The binary octahedral group has two three-dimensional irreps, with character values also in { so is likewise eliminated. The binary icosahedral group has two three-dimensional irreps, with all characters √ 5 ± 1 − , 3 , , 0 { in the set 1 } . As discussed in the case of , our traces cannot take these values. Σ(60) 2 SU In summary, by enumeration of the finite subgroups of , we have shown that G cannot be finite. (3) G is a continuous (Lie) subgroup of SU (3) . Corollary 3.4. Proof. G G is closed because it is the set of matrices densely generated is infinite by Claim 3.2. Furthermore ,R { by ,R . It is well-known that a closed, infinite subgroup of a Lie group is also a Lie group (this is R } 3 2 1 Cartan’s theorem [5]). The corollary follows. Next we show that G must be either SO (3) , SU (2) or SU (3) . Furthermore, the set of matrices G M densely generated by R { ,R matrices. ,R (3) } consists of either all SO (3) matrices or all SU 3 2 1 G is either SO (3) , SU (2) , or SU (3) . Furthermore, G 3 consists of either all 3 × Claim 3.5. special M unitary matrices (if the beamsplitter has a non-real entry), or all 3 × 3 special orthogonal matrices (if b is b real). G R is a Lie , R Proof. , and R G do not commute, Since is nonabelian. By Corollary 3.4, we know 3 1 2 group, and furthermore G is closed. The nonabelian closed connected Lie subgroups of SU (3) are well- known [4]: they are SU (3) , SU (2) × U (1) , SU (2) , and SO (3) . Meanwhile, the closed disconnected Lie ∞ subgroups of ∆(3 ∞ ) and ∆(6 are ) , as described in [8]. (3) SU 2 2 ) and ∆(6 ∞ ) are the analogues of ∆(3 n Note that ) and ∆(6 n ∆(3 ) as n → ∞ . Our above ∞ 2 2 6 = ∆(3 n arguments showing that ) and G 6 = ∆(6 n G ) carry over in this limit, because at no point did we use the fact that or m were finite. Therefore G cannot be either of these continuous groups. n By Claim 3.1, G has a three-dimensional irrep. Of the remaining groups, only SU (2) , SO (3) , and SU (3) have three-dimensional irreps. Furthermore, it is well known that the only three-dimensional irrep 11 The fact that matrices representing elements of type C and E are traceless follows from the previous arguments regarding C-series groups. The fact that matrices representing elements of type B, D and F have traces of norm 1 follows by an identical argument since A(p,q)=B(p,q)B(0,0), A(p,q)B(0,0)=B(p,q), A matrices have diagonal representatives, and B(0,0) is represented by the above in this basis. A similar argument holds for elements of type D and F. 11

12 of SU is as SO (3) . This is because SU (2) has exactly one irrep in each finite dimension (See [4, Section (2) SU (2) SO (3) via the fact that SU (2) is a II.5] or [24] for details), and has an obvious representation as (3) double cover of . Since we are only concerned with the set of matrices generated, without loss SO G M is either or SU (3) . of generality we can assume (3) SO G is the natural one, as the group of all (3) It is well-known that the only three-dimensional irrep of SU 3 SO (3) is × 3 special unitary matrices ([4, Section VI.5]). Likewise, the only three-dimensional irrep of consists of either all 3 × 3 special unitary G the natural one, up to conjugation by a unitary [4]. Hence M × 3 special orthogonal matrices conjugated by some unitary U matrices (case A), or all 3 (case B). b We now show that if the beamsplitter is real, then we are in case B and without loss of generality the orthogonal matrices. Otherwise, if is real. Hence is the set of all 3 × 3 U b has a conjugating unitary G M 3 is the set of all complex entry, we will show we are in case A and × G special unitary matrices. 3 M is real. Then all matrices in our generating set are orthogonal, so all matrices in G First, suppose b M B are orthogonal. Hence we are in case G are real, without loss of generality U , and since all matrices in M is a real matrix as well. b has a complex entry. Then either α or β are not real. First, suppose Now suppose that is not real. α 2 ∗ Tr( ) = α Then − 2 α R is not real because 0 < | α | < 1 . But since conjugating a matrix by a unitary 1 ) preserves its trace, and we are in case must be real. In particular Tr( R , the traces of all matrices in G B 1 M must be real, which is a contradiction. Therefore if α is not real then we must be in case A. is not real. Then we can obtain a similar contradiction. Let β = p + qi where p and Next, suppose β ) ( 4 ∗ 2 q R β R + 2 )) = are real. By direct calculation one can show that β | Im (Tr( R β . Since our R | 1 2 1 3 4 ∗ 2 + 2 6 = 0 , so this quantity is 0 if and only if beamsplitter is nontrivial, | | β β = 0 ⇔ 2 q (1 − p ) = 0 . But β this cannot occur, since q 6 = 0 (because β is not real), and 1 − p 6 = 0 (because the beamsplitter is nontrivial). Hence in this case Tr( R R is imaginary, which contradicts the fact we are in case B. Therefore if R ) R 1 3 1 2 is not real then we must be in case A, which completes the proof. β Theorem 2.1 follows from Claim 3.5. Having proved our main result, we can now easily show two alternative versions of the theorem as well. ) ( a b = Corollary 3.6. (not necessarily of determinant − 1 ), plus g Any nontrivial two-mode optical gate c d ( m ) on m ≥ 3 modes. the set of all phaseshifters densely generates SU π − θ i iθ 2 e Proof. for some θ Since g with a phase of e g is unitary we have det( g ) = . By composing , we ′ ′ − 1 . The gate g g of determinant obtain a nontrivial beamsplitter is universal by Theorem 2.1, hence this gate set is universal as well. Corollary 3.7. Any nontrivial two-mode real optical gate g is universal for quantum linear optics. Proof. g is real, g must have determinant ± 1 . The case of det( g ) = − 1 is handled by Theorem Since 2.1, so we now prove the det( g ) = +1 case. In this case g is a rotation by an angle θ . The fact that g is nontrivial means is not a multiple of π/ 2 . The beamsplitter actions b θ ,b can be viewed as ,b 13 23 12 about the x , three-dimensional rotations by angle and z axes. So the question reduces to “For which θ y θ (other than multiples of π/ 2 ) do rotations by angles about the x , y and z axes fail to densely generate all θ possible rotations?” This question is easily answered using the well-known classification of closed subgroups of SO (3) . The finite subgroups of SO (3) are the cyclic, dihedral, tetrahedral, octahedral, and icosahedral groups. One can easily check that our gate g cannot generate a representation of one of these groups, and hence densely generates some infinite group G is a Lie . By the same reasoning as in Corollary 3.4, we conclude that G subgroup of SO (3) . SO (3) are (all rotations (3) , U (1) (all rotations about one axis) and U (1) × Z The Lie subgroups of SO 2 about one axis, plus a rotation by perpendicular to the axis). Again one can easily eliminate the possibility π that G is U (1) or U (1) × Z . , and hence G must be all of SO (3) 2 12

13 We have proven universality on three modes for real nontrivial g +1 . Universality on with determinant ≥ 3 SO ( m ) can m modes follows by a real analogue of Reck et al. [22], namely that any rotation matrix in 2 ( O ) real 2 × m optical gates of determinant 1 . be expressed as the product of 2 4 Open Questions At the moment our dichotomy theorem only holds for beamsplitters, which act on two modes at a time and have determinant − . As we said before, we leave open whether the dichotomy can be extended to two- 1 − . Although the phases of gates are irrelevant in the qubit model, mode gates with determinant other than 1 the phases unfortunately are relevant in linear optics—and that is the source of the difficulty. Note that the previous universality result of Reck et al. [22] simply assumed that arbitrary phaseshifters were available for free, so this issue did not arise. k Another open problem is whether our dichotomy can be extended to -mode optical gates for all con- stants k . Such a result would complete the linear-optical analogue of the dichotomy conjecture for standard quantum circuits. The case k = 3 seems doable because the representations of all finite subgroups of SU (4) are known [14]. But already the case k = 4 seems more difficult, because the representations of all finite subgroups of SU have not yet been classified. Thus, a proof for arbitrary k would probably require more (5) advanced techniques in representation theory. 5 Acknowledgements We thank Bela Bauer for pointing out reference [20] and Patrick Otto Ludl for helpful correspondence. A.B. was supported by the National Science Foundation Graduate Research Fellowship under Grant No. 1122374 and by the Center for Science of Information (CSoI), an NSF Science and Technology Center, under grant agreement CCF-0939370. S.A. was supported by the National Science Foundation under Grant No. 0844626, by a TIBCO Chair, and by an Alan T. Waterman Award. References Theory of Computing , [1] S. Aaronson and A. Arkhipov. The Computational Complexity of Linear Optics. 9(4):143–252, 2013. [2] S. D. Bartlett and B. C. Sanders. Requirement for quantum computation. Journal of Modern Optics , 50:2331–2340, 2003. [3] M. Bremner, R. Jozsa, and D. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proc. Roy. Soc. London , A467(2126):459–472, 2010. ̈ [4] T. Br ocker and T. tom Dieck. . Springer, 2003. Representations of Compact Lie Groups ́ La th [5] E. Cartan. eorie des groupes finis et continus et l’analysis situs. M emorial des Sciences ́ Math , 42:1–61, 1930. ematiques ́ Phys. Rev. A , 57:R1477– [6] N. J. Cerf, C. Adami, and P. G. Kwiat. Optical simulation of quantum logic. R1480, 1998. [7] C. Dawson and M. Nielsen. The Solovay-Kitaev Algorithm. Quantum Information and Computation , 6(1):81–95, 2006. [8] W. M. Fairbairn, T. Fulton, and W. H. Klink. Finite and Disconnected Subgroups of SU(3) and their Application to the Elementary-Particle Spectrum. Journal of Mathematical Physics , 5(8):1038, 1964. 13

14 [9] D. Gottesman. The Heisenberg representation of quantum computers. In S. P. Corney, R. Delbourgo and P. D. Jarvis, editors, Group22: Proceedings of the XXII International Colloquium on Group The- , volume 1, pages 32–43, Cambridge, MA, 1999. International Press. oretical Methods in Physics , 64:012310, [10] D. Gottesman, A. Kitaev, and J. Preskill. Encoding a qubit in an oscillator. Phys. Rev. A 2001. J. Phys. A: Math. Theor. [11] W. Grimus and P. O. Ludl. Finite flavour groups of fermions. 45:233001, 2012. [12] W. Grimus and P. O. Ludl. On the characterization of the SU(3)-subgroups of type C and D. J. Phys. 45:233001, 2012. A: Math. Theor. Non-abelian finite gauge theories. [13] A. Hanany and Y. He. , Journal of High Energy Physics 1999(02):013, 1999. [14] A. Hanany and Y.-H. He. A monograph on the classification of the discrete subgroups of SU(4). Journal of High Energy Physics , 2001(02):027, 2001. [15] S. P. Jordan. Permutational quantum computing. Quantum Information and Computation , 10(5):470– 497, 2010. [16] R. Jozsa and M. Nest. Classical simulation complexity of extended Clifford circuits. arXiv:1305.6190 , 2013. [17] E. Knill and R. Laflamme. Power of One Bit of Quantum Information. , Physical Review Letters 81(25):5672–5675, 1998. [18] E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature , 409(6816):46–52, 2001. [19] S. Lloyd. Almost any quantum logic gate is universal. Physical Review Letters , 75(2):346–349, 1995. [20] P. O. Ludl. Comments on the classification of the finite subgroups of SU(3). J. Phys. A: Math. Theor. 44:255204, 2011. [21] M. Nielsen and I. Chuang. . Cambridge University Quantum Computation and Quantum Information Press, 2000. [22] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani. Experimental realization of any discrete unitary operator. Physical Review Letters , 73(1):58–61, 1994. [23] Y. Shi. Both Toffoli and controlled-NOT need little help to do universal quantum computation. Quan- tum Information and Computation , 3(1):84–92, 2003. [24] Q. Yuan. http://qchu.wordpress.com/2011/06/26/the-representation-theory-of-su2/, 2011. 14

Related documents

GOES RSeriesDataBook

GOES RSeriesDataBook

GOES R Series - Data Book Prepared for National Aeronautics and Space Administration GOES - R Series Program Office Goddard Space Flight Center Greenbelt, Maryland 20771 Pursuant to Contract NNG09HR00...

More info »
ZEN 2 (blue edition)   Software Guide

ZEN 2 (blue edition) Software Guide

Software Guide ZEN 2 (blue edition)

More info »
Science Journals — AAAS

Science Journals — AAAS

| SCIENCE ADVANCES RESEARCH ARTICLE APPLIED SCIENCES AND ENGINEERING Copyright © 2019 Authors, some The rights reserved; High-pressure, high-temperature molecular exclusive licensee American Associati...

More info »
CfP104

CfP104

ESO Call for Proposals – P 104 Proposal Deadline: 28 March 2019 , 12:00 noon CET

More info »