Abstract:
We describe a method for using a classical computer to generate a particular sequence of elementary operations (SEO), an instruction set for a quantum computer. Such a SEO will induce a quantum computer to perform a unitary transformation U that we call an Irreps Gen U. This U simultaneously diagonalizes a set of operators H μ  called HYPs (Hermitian Young Projectors) for n particles with d colors or, equivalently, for n qu(d)its. H μ  projects out n particle irrep μ of U(d).

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
       [0001]    This patent application makes reference to patent application Ser. No. 14/499,539 by R. R. Tucci entitled: “Method For Projecting Out Irreducible Representations From a Quantum State Of Multiple Qubits”. 
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT 
       [0002]    Not Applicable 
       REFERENCE TO COMPUTER PROGRAM LISTING 
       [0003]    A computer program listing consisting of a single file entitled:
       IrrepsGen-d-colors-maxima.txt,
 
in ASCII format, is included with this patent application. The file is a collection of Maxima commands which do most of the labor-intensive calculations underpinning this invention. Maxima is a free, open source Symbolic Manipulation Program (SMP).
       
 
       BACKGROUND OF THE INVENTION 
       [0005]    (A) Field of the Invention 
         [0006]    The invention relates to a quantum computer; that is, an array of quantum bits (called qubits). More specifically, it relates to methods for using a classical computer to generate a sequence of operations that can be used to operate a quantum computer. 
         [0007]    (B) Description of Related Art 
         [0008]    Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.
       Ref.Bac is D. Bacon, “How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem”, arXiv:quant-ph/0612107   Ref.BCH1 is D. Bacon, I. Chuang, and A. Harrow, “Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms”, arXiv:quant-ph/0407082   Ref.BCH2 is D. Bacon, I. Chuang, and A. Harrow, “The Quantum Schur Transform: I. Efficient Qudit Circuits”, arXiv:quant-ph/0601001   Ref.CSD is R. R. Tucci, “A Rudimentary Quantum Compiler (2cnd Ed.)”, arXiv quant-ph/9902062   Ref.Cvi is Predrag Cvitanovic,  Group theory: birdtracks, Lie&#39;s, and exceptional groups  (Princeton University Press, 2008) Also available on the web.   Ref.Dev is S. Devitt, Kae Nemoto, and W. Munro, “Quantum error correction for beginners”, arXiv:0905.2794   Ref.Har is A. Harrow, “Applications of coherent classical communication and the Schur transform to quantum information theory”, arXiv:quant-ph/0512255   Ref.Jak is P. Jakubczyk, Y. Kravets, D. Jakubczyk, “An alternative approach to the construction of Schur-Weyl transform”, arXiv:1409.6130   Ref.Kep is S. Keppeler, M. Sjodahl, “Hermitian Young Operators”, arXiv:1307.6147   Ref.Ma is Zhong-Qi Ma,  Group Theory for Physicists  (World Scientific, 2007)   Ref.NaMi is P. Nataf, F. Mila, “Exact Diagonalization of Heisenberg SU(N) models”, arXiv:1408.5341 [quant-ph]   Ref.Paulinesia is R. R. Tucci, “QC Paulinesia”, arXiv:quant-ph/0407215   Ref.RevKit is M. Soeken, S. Frehse, R. Wille, and R. Drechsler, “RevKit: A Toolkit for Reversible Circuit Design”,  Multiple - Valued Logic and Soft Computing  18, no. 1 (012): 55-65.   Ref.Schen is Irene Verona Schensted,  A course on the application of group theory to quantum mechanics  (Peaks Island, Me.: Neo Press, 1976)   Ref.Tuc-HYP is R. R. Tucci, “Quantum Circuit For Unitary Matrix that Simultaneously Diagonalizes Set of Hermitian Young Projection Operators”. Unpublished. Copy included as an appendix to Ref.Tuc-HYP-PAT.   Ref.Tuc-HYP-PAT is R. R. Tucci, “Method For Projecting Out Irreducible Representations from a Quantum State Of Multiple Qubits”, patent application Ser. No. 14/499,539   Ref.TucOpAv is R. R. Tucci, “Method for Evaluating Quantum Operator Averages”, U.S. Pat. No. 8,612,499   Ref.Tuc-PRISM is R. R. Tucci, “How to Calculate and Compile the Irreps Generator for n Qu(d)its”. Unpublished. Copy included as an appendix to this patent application.       
 
         [0027]    This invention deals with quantum computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating those qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer follows a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, matrices, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs for quantum computers are often represented by quantum circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. One can find on the Internet many excellent expositions on quantum computing. 
         [0028]    By compiling a unitary matrix, we mean expressing it as a SEO (a.k.a, a quantum circuit). 
         [0029]    This invention gives an application of Group Theory (or, more specifically, Group Representation Theory) to quantum computing. 
         [0030]    Group Representation Theory is of great importance in Physics. For a non-rigorous, addressed mainly to physicists, introduction to Group Representation Theory, see, for example, the textbooks Ref.Schen, Ref.Ma, Ref.Cvi. Out of those textbooks, Ref.Cvi by Cvitanovic is unique in that it is the only one of the three that uses diagrammatic notation that Cvitanovic calls “birdtracks”. Cvitanovic was not the first to use birdtracks, but he greatly advanced and popularized their use in Group Theory. Birdtracks are closely related to another diagrammatic notation, the quantum circuits used in quantum computing. This invention tries to merge these 2 types of diagrammatic notations. 
         [0031]    A very important tool in Group Representation Theory is that of Young diagrams and their associated Young Projectors. Young diagrams have a long, illustrious history. They are discussed at length in the textbooks Ref.Schen, Ref.Ma, Ref.Cvi. 
         [0032]    Young projectors are not generally Hermitian, but it is possible to construct Hermitian operators that project out the same subspaces as the usual Young projectors. We shall call such operators HYPs (Hermitian Young Projectors). Keppeler and Sjodahl were the first to give, in Ref.Kep, a method for constructing HYPs, together with a proof of the correctness of their method. In this invention, the Keppeler, Sjodahl method for constructing HYPs will be used frequently. 
         [0033]    In this patent, the letters n and d will be reserved to denote the following. If d=2, 3, 4, . . . , then qu(d)its are the fundamental particles or quarks of U(d) (the set of d×d unitary matrices). Qu(d)its have d orthonormal states labeled |j&gt; with j∈{0, 1, 2, . . . , d−1}. A qu(d)it lives in the complex span of these d states. The d in U(d) is often called the number of colors. Qu(d)its with d=2 are called qubits. Each horizontal line or wire in a quantum circuit carries one qu(d)it. The letter n is often used to denote the number of horizontal lines in the quantum circuit. In this patent, the same number n will also be referred to as the number of particles or qu(d)its. 
         [0034]    Since all the HYPs for a fixed (n, d) are mutually orthogonal, they will also commute with each other. By definition, the HYPs are all Hermitian. It follows that one can find a transformation U that diagonalizes at once all of the HYPs for fixed (n, d). We shall refer to this U as the Irreps Generator (or Irreps Gen for short) for n qu(d)its. 
         [0035]    This patent builds on the results of Ref.Tuc-HYP-PAT, which is a previous patent application also by Tucci. Ref.Tuc-HYP-PAT gives a method of calculating and compiling an Irreps Gen for an arbitrary number n of particles but only for d=2 colors (qubits). Unfortunately, the method of Ref.Tuc-HYP-PAT does not generalize easily to arbitrary n and d (qu(d)its). 
         [0036]    The preferred embodiment of this invention is a method for calculating and compiling an Irreps Gen U for arbitrary (n, d). Thus, the method of this patent is more general than that of Ref.Tuc-HYP-PAT in the values of d to which it applies. Furthermore, the methods of both patents are significantly different, even for d=2. 
         [0037]    Whereas in Ref.Tuc-HYP-PAT, we referred to U as the stabsXqu(d)its or quantum Young transform, in this patent we change its name to the Irreps Gen. 
         [0038]    To compile U in the preferred embodiment of this invention, we use the CS-Decomposition of Linear Algebra. This decomposition was first used for quantum computing in Ref.CSD. See Ref.CSD for references discussing the history and theory behind the CS Decomposition. 
         [0039]    To compile U in the preferred embodiment of this invention, we first express it as a product of unitary matrices Λ μ   554  , each corresponding to a different irrep μ. Then we apply the CS-Decomposition to each Λ μ   554   separately. Since the method of compilation given in this paper respects the symmetry of the problem by applying the CS-Decomposition to each irrep μ separately rather than to the whole U at once, we expect that it will lead to much shorter SEOs than if the method did not respect the symmetry of the problem. 
         [0040]      FIG. 7  below is dedicated to explaining some of the many applications of the Irreps Gen. 
         [0041]    Bacon, Chuang and Harrow have defined, in Ref.BCH1, Ref.BCH2, Ref.Har, and Ref.Bac, two transforms that they call the Clebsch Gordan (CG) and Schur transforms. When n=2, the Schur and CG transforms are equal. For arbitrary n, the Schur transform is a chain of CG transforms. In Ref.Tuc-HYP, we explain several significant differences between our Irreps Gen and their Schur transform. 
         [0042]    In Ref.Jak, Jakubczyk et al give an “alternative approach” to calculating the same transform as Bacon, Chuang and Harrow. They don&#39;t mention the Keppeler, Sjodahl HYPs. 
       BRIEF SUMMARY OF THE INVENTION 
       [0043]    The usual Young projectors are not generally Hermitian, but, inspired by conjectures of previous workers, Keppeler and Sjodahl showed in 2013 how to construct Hermitian operators that project out the same subspaces as the usual Young projectors. We shall call such operators HYPs (Hermitian Young Projectors). All HYPs for a fixed number n of qu(d)its are mutually commuting and Hermitian so there exists a unitary matrix that diagonalizes all of them at once. We call such a unitary matrix an Irreps Generator or Irreps Gen for short. The invention presented here is a method of constructing a quantum circuit for the Irreps Gen for arbitrary (n, d), where n is the number of particles or qu(d)its and d is the number of colors. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0044]      FIG. 1  shows a block diagram of a classical computer feeding data to a quantum computer. 
           [0045]      FIG. 2  shows some nonstandard notation used in this patent. For example, this figure shows how we use projectors to indicate the partitioning of a matrix into 4 sub-blocks. 
           [0046]      FIG. 3  shows how we define J-properties and H-properties, and how one can express the Irreps Gen U as a sum of operators with each summand corresponding to a different irrep μ. 
           [0047]      FIG. 4  shows how to calculate a J μ , and a D μ  for each μ=1, 2, . . . , N ir . 
           [0048]      FIG. 5  shows how to express the Irreps Gen U as a product of μ-Householder Transformations At where Λ μ   554  =1, 2, . . . , N ir . 
           [0049]      FIG. 6  shows how to express the Irreps Gen U as a quantum circuit by applying the CS-decomposition to each Λ μ   554   obtained in  FIG. 5 . 
           [0050]      FIG. 7  shows two applications of the Irreps Gen U, (a) to produce exotic CNOTs and (b) to express conveniently an arbitrary qu(d)it permutation. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0051]    This section describes in detail a preferred embodiment of the invention and other possible embodiments of the invention. For extra details about this invention, see Ref.Tuc-HYP, Ref.Tuc-HYP-PAT, Ref.Tuc-PRISM and references therein. 
       (A) Preferred Embodiment 
       [0052]      FIG. 1  is a block diagram of a classical computer feeding data to a quantum computer. Box  100  represents a classical computer. The Irreps Gen SEO instruction set is generated inside Box  100 . Box  100  comprises sub-boxes  101 ,  102 ,  103 . Box  101  represents input devices, such as a mouse or a keyboard. Box  102  comprises the CPU, internal and external memory units. Box  102  does calculations and stores information. Box  103  represents output devices, such as a printer or a display screen. Box  105  represents a quantum computer, comprising an array of quantum bits and some hardware for manipulating the state of those bits. 
         [0053]    Next consider  FIG. 2 . 
         [0054]    For integers a, b such that a≦b, define Z a,b  by  201 . 
         [0055]    Let N st =d n  be the number of states for n qu(d)its. We will often refer to n as the number of particles or qu(d)its and to d as the number of colors. 
         [0056]    As indicated by  202 , the HYPs H μ  are labeled by the elements of stabs(n, d). Here stabs(n, d) is the set of all standard Young Tableau with n boxes and ≦d rows. stabs(n, d) is also the set of n particle irreps μ of U(d). See Ref.Tuc-HYP for more information about the set stabs(n, d). In this patent, as indicated by  203 , we will often identify the sets stabs(n, d) and Z 1,N     ir   , where N ir  equals the number of irreps (the cardinality of stabs(n, d)). 
         [0057]    Let |e k &gt; for k=1, 2, . . . , N st  denote an orthonormal N st -dimensional basis. Let A be a subset of Z 1,N     st    and A c  the complement of A in Z 1,N     st   . Then J A  and its complement J A   c  are defined by  204  and  205 , respectively. 
         [0058]    We will write M J     A     ,J     B    for the projection  206  of a general N st ×N st  matrix M. 
         [0059]    If J=J A  for some A⊂Z 1,N     st    and M is an N st ×N st  matrix, we define by  207  the “J-block inverse of M”, assuming it exists. Here Ω −1  denotes the usual inverse of a square matrix Ω. Clearly, the J-block inverse of M inverts only the sub-block of M given by its J rows and columns. 
         [0060]    If J=J A  for some A⊂Z 1,N     st    and M is an N st ×N st  matrix, we will often symbolically partition M into the 4 quadrants corresponding to the J and J c  rows and columns of M. We will do so by writing  208 . 
         [0061]    Note that in  208 , [[·]] does not stand for the conventional matrix symbol since all the entries inside the [[·]] are conventional N st ×N st  matrices themselves. As indicated by  208 , the [[·]] symbol is just a convenient way of organizing 4 matrices of the same size and indicating that all 4 should be summed together. For the remainder of this patent, we will be lazy and use [·] to indicate both [[·]] and the conventional [·]. Which one we are referring to should be clear to the reader from context. 
         [0062]    Next consider  FIG. 3 . 
         [0063]    Consider a set {J μ : μ=1, 2, . . . N ir } of matrices (or associated linear operators), all square and of the same size. We will say that such a set satisfies the J-properties if for all μ and ν,  301  is satisfied. 
         [0064]    Consider a set {H μ : μ=1, 2, . . . N ir } of matrices (or associated linear operators), all square and of the same size. We will say that such a set satisfies the H-properties if for all μ and ν,  302  is satisfied. 
         [0065]    We will say that an operator A lives in irrep μ (with respect to a set of J μ , operators that satisfies the J-properties) if  303  is satisfied. We will consider a set of operators D μ  that satisfies  304  for all μ. 
         [0066]    Suppose U is a unitary matrix that can be expressed as  305 , where the H μ  satisfy the H-properties and D μ  lives in μ for all μ. Then we will refer to U as the Irreps Gen (Irreducible representations Generator). In this patent, we will use the letter U exclusively for that transform, except when we use it for U(d), the group of d×d unitary matrices. Note that there is a different U for each (n, d) pair. 
         [0067]    Next consider  FIG. 4 . 
         [0068]    Ref.Kep gives us a method for calculating a set of HYPs H μ  that satisfies the H-properties.  FIG. 4  gives an algorithm such that, given a set of H μ  that satisfies the H-properties, we can do all of the following: compute a set of J μ  that satisfies the J-properties, and a set of D μ , such that for all μ, D μ  lives in μ, and U=Σ μ H μ D μ  is unitary. 
         [0069]    Next we will describe very briefly the algorithm of  FIG. 4 . For a more detailed description of the algorithm, see Ref.Tuc-PRISM. 
         [0070]    Let X μ  be defined by  401 , where L2M( ) is a function that translates Lists to Matrices by taking its list argument and returning the diagonal matrix with that list argument as diagonal. Find as many x k   μ  as possible such that  402  and  403  are satisfied for all μ, ν. It&#39;s convenient to define x k  by  404 , where μ(k) is the single μ for which x k   μ ≠0. Using the information collected so far for the J μ , find a full set of J μ  while being mindful of satisfying the J-properties and the constraint that tr(J μ )=tr(H μ ) for all μ. 
         [0071]    At this point, we should have H μ  and J μ  for all μ. Using that information, one can find the D μ  for each μ via the equations  405  and  406 , where U μ  is unitary and X μ  is defined by  401 . 
         [0072]    Next consider  FIG. 5 . 
         [0073]    In  FIG. 5 , we define a generalization of the conventional Householder Trans-formations (HTs) of Linear Algebra. We will call such generalizations μ-HTs. A conventional HT, when applied to a unitary matrix U, diagonalizes a single column of U. By “diagonalizes” a column of U, we mean that it makes all entries of the column equal to zero except for one of them. A μ-HT, on the other hand, diagonalizes multiple columns of U at once; more precisely, it diagonalizes all columns of U corresponding to the irrep μ. 
         [0074]    Performing Algorithm 2 labeled  502  generates a sequence of μ-HTs Λ μ  such that  501  is satisfied. (We will also refer to Λ μ   554   as a μ-HT). Since the Λ μ  are unitary,  501  can be easily inverted to express the Irreps Gen U as a product of Λ μ   554   (times a trivial phase factor). Note how equation  503  expresses each Λ μ   554   as a matrix partitioned into four quadrants given by the J μ  and J μ   c  rows and columns. We refer the reader to Ref.Tuc-PRISM for more details about the algorithm of  FIG. 5 . 
         [0075]    Next consider  FIG. 6 . 
         [0076]    In the previous figure, we showed how the Irreps Gen U can be expressed as a product of μ-HTs. In this figure, we show how to compile each of these μ-HT factors using the well-known (See Ref.CSD) CS-Decomposition of Linear Algebra. 
         [0077]    The CS decomposition is performed on a unitary matrix which has been partitioned into four quadrants. At the same time, the Λ μ   554   generated by Algorithm 2 of  FIG. 5  are unitary matrices which are in the form  503 , so they are a priori partitioned into four quadrants given by the J μ  and J μ   c  rows and columns. Thus, doing a CS-decomposition of a Λ μ   554   with the predefined partitioning is very natural and it yields  601 . In that figure, the diagonal blocks of            μ  and            μ  are unitary. Furthermore, all quadrants of            μ  are diagonal and satisfy other constraints that are described in full generality in Ref.Tuc-PRISM. See that reference for more details. 
         [0078]    Here is an example. If tr(J μ )=2 and tr(J μ   c )=3, then            μ ,            μ  and            μ  can be found of the form given by Box  602 . If the 2 and 3 for the trace values are swapped, then we get  603  instead of  602 . Note that  604  applies to both cases  602  and  603 . 
         [0079]    For each μ, after doing a CS-Decomposition of Λ μ   554  , one can use the techniques described in Ref.CSD or similar ones to decompose the resulting matrices            μ ,            μ ,            μ  into a SEO (sequence of elementary transformations). 
         [0080]    Next consider  FIG. 7 . 
         [0081]      FIG. 7  describes some possible applications of the invention. This figure is almost the same as  FIG. 6  of Ref.Tuc-HYP-PAT, but it has been adapted so as to apply to arbitrary d instead of to only d=2. 
         [0082]    One important application of the Irreps Gen is that it allows us to create a new kind of CNOT. The usual CNOT is  701  where τ is the target qubit, κ is the control qubit, σ x  is the X Pauli matrix, b∈{0,1} and P b =|b&gt;&lt;b|. By virtue of UJ μ U † =H μ , one can construct the exotic singly controlled qu(d)it rotation given by  702 , where τ is the target qu(d)it, and κ n  are n control qu(d)its. Also, Γ(τ) is an element of U(d) acting on τ and H μ (κ n ) with μ∈stabs(n, d) is a HYP acting on κ n . The U(κ n ) is the Irreps Gen acting on κ n . 
         [0083]    One can also generalize a multiply controlled CNOT given by  703 , where τ is the target qubit, κ l  is a control qubit which is different for different l, and b l ∈{0, 1}, to an exotic multiply controlled qu(d)it rotation given by  704 , where τ is the target qu(d)it and κ l   n     l    are n l  control qu(d l )its which are different particles for different l. Also, Γ(τ) is an element of U(d) acting on τ and H μ     l   (κ l   n     l   ) with μ l ∈stabs(n l , d l ) is a HYP acting on κ l   n     l   . The U(κ l   n     l   ) are the Irreps Gen acting on κ l   n     l   . 
         [0084]    HYPs also lead to a new, fairly simple matrix representation of arbitrary qu(d)it permutations. Next, we will say something about this new representation. See Ref.Tuc-HYP for more details for the case d=2. This new representation was inspired by Ref.NaMi written by Natal and Mila. They too are concerned with finding a convenient matrix representation for arbitrary qu(d)it permutations. Whereas we use HYPs, they use instead something invented by Young called “orthogonal units”. 
         [0085]    Suppose μ∈stabs(n, d). Let |μ,α&gt; where α=1, 2, . . . , dim(μ) be a set of orthonormal eigenvectors with eigenvalue 1 of H μ . Then the states in the set B defined by  705  are orthonormal. Furthermore, if B′ is given by  706 , then the complex span of B equals the complex span of B′. Call B the HYP basis. In the HYP basis, H μ  equals  707 . 
         [0086]    Let  708  denote a qu(d)it-swap of adjacent horizontal lines or qu(d)its j and j+1 in a qu(d)it circuit with horizontal lines labeled from top to bottom 0, 1, 2, . . . , n−1. Using the fact that Σ μ H μ =1, we get  709 . By the Wigner-Eckart theorem, we expect  710 , where f μ, ν   j  is independent of α, and it vanishes if μ         ν (i.e., if μ and ν are not equivalent irreps). 
         [0087]    For all μ,ν∈stabs(n, d), define H μ,ν  by  711 , where θ(μ˜ν) equals 1 if μ and ν are equivalent irreps, and it equals 0 otherwise. If we define ν n  by  712 , then Ref.Tuc-HYP shows that any permutation of n qu(d)its is an element of ν n . 
       (B) Other Embodiments 
       [0088]    The preferred embodiment of this invention is a method for calculating and compiling the Irreps Gen U for arbitrary (n, d). 
         [0089]    It&#39;s important to note that most of the algorithms of this patent do not assume that the set of H μ  is necessarily a set of HYPs; they only assume that it satisfies the H-properties. Thus, the methods of this paper can also be applied to other sets of H μ  operators, as long as they satisfy the H-properties. 
         [0090]    A standard definition in the field of quantum computation is that a qu(d)it is a quantum state that belongs to a d dimensional vector space and a qubit is a qu(d)it with d=2. In quantum error correction (see Ref.Dev for an introduction), one distinguishes between 2 types of qu(d)its, physical and logical. A logical qu(d)it is mapped into a number of physical qu(d)its. It goes without saying that the qu(d)its in the quantum circuit of Irreps Gen proposed in this invention can always be interpreted as logical qu(d)its, and additional gates can be added to that quantum circuit with the purpose of performing error correction. 
         [0091]    By compiling U we mean expressing it as a SEO (sequence of elementary operations) on qubits, not qu(d)its, even in the case when the HYPs are for projecting out irreps of n qu(d)its with d≠2 colors. When d≠2, we will say that the HYP qu(d)its are meta-logical, whereas the qubits into which we compile them are logical. If quantum error correction is added, the logical qubits might themselves be encoded into physical qubits, or else the meta-logical qu(d)its might be encoded directly into physical qubits. 
         [0092]    For convenience, the quantum circuit for the Irreps Gen proposed in this invention may include gates that act on more than 3 qubits at a time. Such “fat” gates might be judged by some not to be elementary gates as defined earlier in this patent. However, such fat gates should be allowed inside the SEO&#39;s covered by this invention for cases in which they are trivially expandable (TE) fat gates. By TE fat gates we mean, fat gates for which there are well known, expanding methods for replacing them by a sequence of gates that are strictly elementary, in the sense that they act on just one or two qubits at a time. Multi-controlled rotations and multiplexors are examples of TE fat gates. In fact, see the Java classes MultiCRotExpander and MultiplexorExpander and related classes available at www.ar-tiste.com and as a computer code appendix to several Tucci patents, for example Ref.TucOpAv. These classes automate such expanding methods for multi-controlled rotations and multiplexors. 
         [0093]    A promising avenue for future research is to modify our exact method for computing U and seek a bounded error approximation for U and for its compilation, some sort of expansion in powers of 1/n useful when n&gt;&gt;1. That such an approximation is likely to exist can be inferred from the fact that for d=2 and large n, what we are dealing with is a system of n&gt;&gt;1 spin ½ quantum states, a system which should behave approximately as if it had classical angular momentum J=n/2. 
         [0094]    So far, we have described some exemplary preferred embodiments of this invention. Those skilled in the art will be able to come up with many modifications to the given embodiments without departing from the present invention. Thus, the inventor wishes that the scope of this invention be determined by the appended claims and their legal equivalents, rather than by the given embodiments.