Compiler for a quantum computer

Abstract

A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating these qubits. Quantum Bayesian (QB) nets are a method of modeling quantum systems graphically in terms of network diagrams. This invention comprises a classical computer running a computer program that expresses the information contained in a QB net as a sequence of elementary operations (SEO). One can then run these sequences on a quantum computer. We show how to reduce a QB net into a SEO by a two step process. First, express the information contained in the QB net as a sequence of unitary operators. Second, express each of those unitary operators as a SEO. An appendix to this document contains the C++ source code of a computer program called “Qubiter1.0”, which is a preferred embodiment of the invention.

1. A method of operating a classical computer, wherein said method must be stored in a computer readable medium which said classical computer can read, , wherein said method must be stored in the external or internal memory units of said classical computer, to calculate a sequence of operations with the purpose of applying said sequence of operations to a quantum computer comprising an array of qubits, to induce said quantum computer to execute a desired calculation, said method comprising the steps of:
 storing in said classical computer a QB net (Quantum Bayesian net) data-set comprising: 
 (a) graph information comprising a node label for each node of a plurality of N nodes, and also comprising a plurality of directed lines, wherein a directed line comprises an ordered pair of said node labels, wherein one member of the label pair labels the source node and the other member labels the destination node of the directed line,  
 (b) state information comprising, for each jε{1, 2, . . . N}, a finite set Σ j  containing labels for the states that the j'th node {circumflex over (x)} j  may assume  assumes, and  
 (c) amplitude information comprising, for each jε{1, 2, . . . N}, a representation of a complex number 
         A   j     ⁡     [         x   j     ❘     x     k   ⁢           ⁢   1         ,     x     k   ⁢           ⁢   2       ,   …   ,     x     k   ⁢           ⁢          S   j                ]         
 
 
 
       for each vector 
       (       x   j     ,     x     k   ⁢           ⁢   1       ,     x     k   ⁢           ⁢   2       ,   …   ,     x     k   ⁢           ⁢          S   j                )       
 
       such that x j εΣ j , x k     1   εΣ k     1   , x k     2   εΣ k     2   , . . . , and 
           x     k   ⁢           ⁢          S   j              ∈     Σ     k   ⁢           ⁢          S   j                ,       
 
       wherein 
       (         x   ^       k   ⁢           ⁢   1       ,       x   ^       k   ⁢           ⁢   2       ,   …   ,       x   ^       k   ⁢           ⁢          S   j                )       
 
       are the |S j | nodes connected to {circumflex over (x)} j  by directed lines entering {circumflex over (x)} j , wherein said directed lines entering {circumflex over (x)} j  transmit the state of their source node, wherein said |S j | is an integer greater or equal to zero,
 composing with said classical computer and using said QB net data-set, a data-set that specifies  yields a unitary matrix V in , wherein V in    is equivalent to the unitary matrix U   |T|    . . . U   3   U   2    of Eq.  (   20   ) , and V   in    describes the quantum - state evolution for the situation described by said QB net data - set,   
 calculating said sequence of operations using said classical computer, wherein said sequence of operations and said V in  both would, if applied to an  said array of qubits, produce equivalent transformations of the array of qubits.  
 
     
     
       2. The method of  claim 1 , wherein said sequence of operations comprises c-not operations  elementary operations on said array of qubits. 
     
     
       3. The method of  claim 1 , wherein said sequence of operations comprises qubit rotation operations  is a sequence of elementary operations on said array of qubits. 
     
     
       4. The method of  claim 1 , further  also utilizing a quantum computer, comprising the additional step of:
 manipulating said quantum computer largely according to said sequence of operations.  
 
     
     
       5. The method of  claim 1 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequence of operations, wherein if the decomposer is given data that fairly directly specifies a   specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies  specifies a represetation of three unitary matrices: L, D, R, such that the following matrix equation holds: U=LDR. 
     
     
       6. The method of  claim 1 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequence of operations, wherein if the decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies eight unitary matrices:   specifies a represetation of four matrices D 00 , D 01 , D 10 , D 11 , and four unitary matrices L 0 , L 1 , R 0 , R 1 , such that if one partitions said U into four blocks U 00 , U 01 , U 10 , U 11 , then the following four matrix equations hold: U ij =L i D ij R j  for iεBool and jεBool. 
     
     
       7. The method of  claim 1 , comprising the additional step of:
 calculating with said classical computer and using said QB net data-set, a tree data-set that comprises data that can be represented as a tree-node matrix for each node contained in a subset of the nodes of a tree, wherein the product, in some order defined by the  determined in accordance with said tree, of all said tree-node matrices is equivalent to said V in .  
 
     
     
       8. A method of operating a classical computer having display, storage and calculation means, wherein said method must be stored in a computer readable medium which said classical computer can read, , wherein said method must be stored in the external or internal memory units of said classical computer, to analyze a quantum  physical system that exhibits quantum mechanical behavior  comprising an array of qubits, said method comprising the steps of:
 displaying on said display means a graph comprising a plurality of N nodes, and a plurality of directed lines connecting certain pairs of said nodes,  
 storing in said storage means a QB net (Quantum Bayesian net) data-set comprising: 
 (a) graph information comprising a node label for each of said N nodes, and also comprising, for each said directed line, said node label for the source node and for the destination node of the directed line,  
 (b) state information comprising, for each jε{1, 2, . . . N}, a finite set Σ j  containing labels for the states that the j'th node {circumflex over (x)} j  may assume  assumes, and  
 (c) amplitude information comprising, for each jε{1, 2, . . . N}, a representation of a complex number 
         A   j     ⁡     [         x   j     ❘     x     k   ⁢           ⁢   1         ,     x     k   ⁢           ⁢   2       ,   …   ,     x     k   ⁢           ⁢          S   j                ]         
 
 
 
       for each vector 
       (       x   j     ,     x     k   ⁢           ⁢   1       ,     x     k   ⁢           ⁢   2       ,   …   ,     x     k   ⁢           ⁢          S   j                )       
 
       such that x j εΣ j , x k     1   εΣ k     1   , x k     2   εΣ k     2   , . . . , and 
           x     k   ⁢           ⁢          S   j              ∈     Σ     k   ⁢           ⁢          S   j                ,       
 
       wherein 
       (         x   ^       k   ⁢           ⁢   1       ,       x   ^       k   ⁢           ⁢   2       ,   …   ,       x   ^       k   ⁢           ⁢          S   j                )       
 
       are the |S j | nodes connected to {circumflex over (x)} j  by directed lines entering {circumflex over (x)} j , wherein said directed lines entering {circumflex over (x)} j  transmit the state of their source node, wherein said |S j | is an integer greater or equal to zero,
 composing with said calculation means and using said QB net data-set, a data-set that specifies  yields a unitary matrix V in , wherein V in    is equivalent to the unitary matrix U   |T|   . . . U   3   U   2    of Eq.  (   20   ) 1    and V   in    describes the quantum - state evolution for the situation described by said QB net data - set,   
 calculating with said calculation means and using said QB net data-set, a sequence of operations on said array of qubits, wherein said sequence of operations and said V in  both would, if applied to an  said array of qubits, produce equivalent transformations of the array of qubits.  
 
     
     
       9. The method of  claim 8 , wherein said sequence of operations comprises c-not operations  elementary operations on said array of qubits. 
     
     
       10. The method of  claim 8 , wherein said sequence of operations comprises qubit rotation operations  is a sequence of elementary operations on said array of qubits. 
     
     
       11. The method of  claim 8 , further  also utilizing a quantum computer, comprising the additional step of:
 manipulating said quantum computer largely according to said sequence of operations.  
 
     
     
       12. The method of  claim 8 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequence of operations, wherein if the decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies  specifies a represetation of three unitary matrices: L, D, R, such that the following matrix equation holds: U=LDR. 
     
     
       13. The method of  claim 8 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequences  sequence of operations, wherein if the decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies eight unitary matrices;  specifies a represetation of four matrices D 00 , D 01 , D 10 , D 11 , and four unitary matrices L 0 , L 1 , R 0 , R 1 , such that if one partitions said U into four blocks U 00 , U 01 , U 10 , U 11 , then the following four matrix equations hold: U ij =L i D ij R j  for iεBool and jεBool. 
     
     
       14. The method of  claim 8 , comprising the additional step of:
 calculating with said classical computer and using said QB net data-set, a tree data-set that comprises data that can be represented as a tree-node matrix for each node contained in a subset of the nodes of a tree, wherein the product, in some order defined by the  determined in accordance with said tree, of all said tree-node matrices is equivalent to said V in .  
 
     
     
       15. A method of operating a classical computer, wherein said method must be stored in a computer readable medium which said classical computer can read, , wherein said method must be stored in the external or internal memory units of said classical computer, to calculate a sequence of operations with the purpose of applying said sequence of operations to a quantum computer comprising an array of qubits, to induce said quantum computer to execute a desired calculation, wherein said classical computer comprises a unitary matrix decomposer, wherein if said unitary matrix decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U of dimension greater than 2, then the decomposer will calculate a data-set that fairly directly specifies  specifies a represetation of three unitary matrices: L, D, R, such that the following matrix equation holds: U=LDR, wherein L and R each yields unitary matrices whose dimension is smaller than that of U, said method comprising the steps of:
 storing in said classical computer an input data-set that fairly directly specifies  specifies a represetation of a unitary matrix V in , wherein at least one row of V in  has 3 or more non-zero entries and at least one column of V in  has 3 or more non-zero entries,  
 applying said unitary matrix decomposer to decompose the initial unitary matrix U=V in   ,    
   applying said unitary matrix decomposer repeatedly to decompose initial unitary matrices obtained from the output of a previous application of said unitary matrix decomposer,   
 calculating with said classical computer, using said input data-set and data obtained by applying said unitary matrix decomposer, said sequence of operations on said array of qubits, wherein said sequence of operations and said V in  both would, if applied to an  said array of qubits, produce equivalent transformations of the array of qubits.  
 
     
     
       16. The method of  claim 15 , wherein if said unitary matrix decomposer is given data that fairly directly specifies a unitary matrix U of dimension greater than  2   species a represetation of said initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies eight unitary matrices:  specifies a represetation of four matrices D 00 , D 01 , D 10 , D 11 , and four unitary matrices L 0 , L 1 , R 0 , R 1 , such that if one partitions said U into four blocks U 00 , U 01 , U 10 , U 11 , then the following four matrix equations hold: U ij =L i D ij R j  for iεBool and jεBool. 
     
     
       17. The method of  claim 15 , wherein said sequence of operations comprises c-not operations. 
     
     
       18. The method of  claim 15 , wherein said sequence of operations comprises qubit rotation operations  elementary operations on said array of qubits. 
     
     
       19. The method of  claim 15 , wherein some of said sequences of operations comprise qubit rotations and c-nots  said sequence of operations is a sequence of elementary operations on said array of qubits. 
     
     
       20. The method of  claim 15 , further  also utilizing a quantum computer, comprising the additional step of:
 manipulating said quantum computer largely according to said sequence of operations.  
 
     
     
       21. A method of operating a classical computer, wherein said method must be stored in a computer readable medium which said classical computer can read, , wherein said method must be stored in the external or internal memory units of said classical computer, to calculate a sequence of operations with the purpose of applying said sequence of operations to a quantum computer comprising an array of qubits, to induce said quantum computer to execute a desired calculation, said method comprising the steps of:
 storing in said classical computer an input data-set that fairly directly specifies  specifies a represetation of a unitary matrix V in , wherein at least one row of V in  has 3 or more non-zero entries and at least one column of V in  has 3 or more non-zero entries,  
 calculating with said classical computer and using said input data-set, a tree data-set that comprises data that can be represented as a node matrix M j  for each node j contained in a subset J of the nodes of a tree, wherein the product, in some order defined by the  determined in accordance with said tree, of all said node matrices is equivalent to said V in ,  
 calculating with said classical computer and using said tree data-set, for each of the node matrices M, a string of operations on qubits, wherein said string of operations and said M both would,  for each jεJ, a product π j    of operations on said array of qubits, wherein M   j    and π   j    both would,  if applied to an  said array of qubits, produce equivalent transformations of the array of qubits.  
 
     
     
       22. The method of  claim 21 , wherein some of said sequences of operations comprise  for some jεJ, π j    comprises  c-not operations. 
     
     
       23. The method of  claim 21 , wherein some of said sequences of operations comprise  for some jεJ, π j    comprises  qubit rotation operations. 
     
     
       24. The method of  claim 21 , wherein some of said sequences of operations comprise qubit rotations and c-nots  for some jεJ, π j    comprises elementary operations on said array of qubits . 
     
     
       25. The method of  claim 21 , wherein said sequences of operations are sequences of elementary operations  for all jεJ, π j    is a sequence of elementary operations on said array of qubits . 
     
     
       26. The method of  claim 21 , further  also utilizing a quantum computer, comprising the additional step of:
 manipulating said quantum computer largely according to said sequence of operations.  
 
     
     
       27. The method of  claim 21 , wherein if said V in  is a square matrix with N rows, then said node matrices are also square matrices with N rows and with at most two non-zero entries in each row and in each column. 
     
     
       28. The method of  claim 21 , wherein if said V in  is a square matrix with N rows, then said node matrices are also square matrices with N rows and with about two non-zero entries in each row and in each column. 
     
     
       29. The method of  claim 21 , wherein if said V in  is a square matrix with N rows, then said node matrices have theoretically a number of nonzero real parameters which grows linearly with N or slower, for large N  grows, for large N 1    linearly with N or slower . 
     
     
       30. The method of  claim 21 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequences  sequence of operations, wherein if said unitary matrix decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies  specifies a represetation of three unitary matrices: L, D, R, such that the following matrix equation holds: U=LDR. 
     
     
       31. The method of  claim 21 , wherein said tree is a binary tree in which each node branches out into two nodes. 
     
     
       32. The method of claim  31    21 , wherein said classical computer includes a unitary matrix decomposer which is used in the calculation of said sequences  sequence of operations, wherein if the decomposer is given data that fairly directly specifies a  specifies a represetation of an initial unitary matrix U, then the decomposer will calculate a data-set that fairly directly specifies eight unitary matrices:  specifies a represetation of four matrices D 00 , D 01 , D 10 , D 11 , and four unitary matrices L 0 , L 1 , R 0 , R 1 , such that if one partitions said U into four blocks U 00 , U 01 , U 10 , U 11 , then the following four matrix equations hold: U ij =L i D ij R j  for iεBool and jεBool. 
     
     
       33. The method of  claim 32 , wherein some of said sequences of operations comprise  for some jεJ, π j    comprises  c-not operations. 
     
     
       34. The method of  claim 32 , wherein some of said sequences of operations comprise  for some jεJ, π j    comprises  qubit rotation operations. 
     
     
       35. The method of  claim 32 , wherein some of said sequences of operations comprise qubit rotations and c-nots  for some jεJ, π j    comprises elementary operations on said array of qubits . 
     
     
       36. The method of  claim 32 , wherein said sequences of operations are sequences of elementary operations  for all jεJ, π j    is a sequence of elementary operations on said array of qubits . 
     
     
       37. The method of  claim 32 , further  also utilizing a quantum computer, comprising the additional step of:
 manipulating said quantum computer largely according to said sequence of operations.