Abstract:
We describe a method for using a classical computer to generate a sequence of elementary operation (SEO) that can be used to operate a quantum computer, thereby inducing the quantum computer to sample an arbitrary probability distribution. The probability distribution being sampled is specified in the form of a Bayesian network.

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
     Not Applicable 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT 
     Not Applicable 
     REFERENCE TO COMPUTER PROGRAM LISTING 
     A computer program listing appendix contained in a single compact disc (CD) is included herewith and incorporated by reference herein. The CD is in IBM-PC format and was burned with a computer running the Windows 98 operating system. The CD contains a single file titled quibbs1-4.txt, in ASCII format, of size 512 KBytes, burnt onto the CD on Sep. 27, 2010. 
     BACKGROUND OF THE INVENTION 
     (A) Field of the Invention 
     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. The invention also relates to methods for sampling a probability distribution and classical probabilistic networks (called classical Bayesian networks). 
     (B) Description of Related Art 
     Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.
     Ref.BNets is http://en.wikipedia.org/wiki/Bayesian_network   Ref.GSamp is “Rapid Sampling Through Quantum Computing” by Lov Grover, ariv:quant-ph/9912001   Ref.GPat is “Fast Quantum Mechanical Algorithms”, U.S. Pat. No. 6,317,766, by Lov K. Grover   Ref.GWiki is http://en.wikipedia.org/wiki/Grover&#39;s_algorithm   Ref.TexasPat is “Quantum Circuit Design for Grover&#39;s Algorithm”, U.S. Pat. No. 7,028,275, by G. Chen, Z. Diao, M. Zubairy   Ref.Som is “Quantum Simulated Annealing” by R. Somma, S. Boixo, H. Barnum, arXiv:0712.1008   Ref.Woc is “Speed-up via Quantum Sampling” by Pawel Wocjan, Anura Abeyesinghe, arXiv:0804.4259   Ref.GPi/3 is “A Different Kind of Quantum Search” by Lov Grover, arXiv:quant-ph/0503205   Ref.TucQusann is “Code Generator for Quantum Simulated Annealing” by R. R. Tucci, arXiv:0908.1633   Ref.TucQuibbs1 is “Quantum Gibbs Sampling Using Szegedy Operators” by R. R. Tucci, arXiv:0910.1647   Ref.TucAfga is “An Adaptive, Fixed-Point Version of Grover&#39;s Algorithm” by R. R. Tucci, arXiv:1001.5200.   Ref.TucQuibbs2 is “Quibbs, a Code Generator for Quantum Gibbs Sampling” by R. R. Tucci, arXiv:1004.2205   

     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, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs are often represented as 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. 
     This invention also deals with sampling a probability distribution. Given a probability distribution P   x   ( ) defined for all points x in some domain val( x ), sampling P   x   ( ) means obtaining a collection {x (1) ,x (2) , . . . , x (N     sam     ) } of points in val( x ) which are distributed according to P   x   ( ). If one can obtain such a collection of points, one can use it to evaluate approximately the expected value of any function defined on val( x ). Hence, sampling a probability distribution is very useful. If the points x∈val( x ) have dim( x ) components, and dim( x ) is very high, then sampling P   x   ( ) becomes very difficult. The reason is that the majority of the sample points x (j)  will come from those regions of val( x ) where P   x   ( ) is high, but finding those regions requires that we explore the entire set val( x ). When dim( x ) is high, set val( x ) is huge, because its volume grows exponentially with dim( x ). 
     The preferred embodiment of this invention uses a Bayesian network to specify P   x   ( ). Bayesian networks are described, for example, in Ref.BNets. 
     There are several standard techniques for sampling probability distributions using a classical computer (for instance, Monte Carlo techniques like Gibbs sampling and Metropolis-Hastings sampling). This invention differs from those standard techniques in that we propose using a quantum computer to generate the sample of points. This is an exciting possibility to the inventor Tucci for the following reasons. Quantum computers use quantum mechanics, which has probabilities built into it, so doing Monte Carlo tricks should come natural to a quantum computer. Furthermore, systems in a quantum mechanical state have a knack for being in many places at once, so one suspects that quantum computers can explore large spaces like val( x ) much faster than classical computers can. 
     Grover in Ref.GSamp seems to have been the first to propose a method for sampling probability distributions using a quantum computer. Let us call his method GSamp for short. In a nutshell, GSamp applies the so called Grover&#39;s “search” Algorithm (the one discussed in Ref.GPat and Ref.GWiki) to N B +1 qubits, using the starting state
 
| s′               =| 0 N     B                       |0         
 
and the target state

                                    t   〉     =       1       2     N   B           ⁢     ∑   x              ⁢   x     〉     ⊗     (           P     x   _       ⁡     (   x   )         |   0     〉       +       1   -       P     x   _       ⁡     (   x   )             ❘   1     〉     )     ,         
where the sum is over all x∈{0,1} N     B   . Once this starting state is driven into this target state, one measures the target state to sample P   x   (x). A serious defect of GSamp is that its target state is useless for sampling P   x   (x), because it has a vanishingly small amplitude of size O(1/√{square root over (2 N     B   )}) for all x. The preferred embodiment of this invention, which we call Quibbs, does not suffer from this defect because its target state is
 
                                t   〉     =       ∑   x     ⁢         P     x   _       ⁡     (   x   )                  ⁢   x     〉     ⊗     |   0     〉     .         
Thus, Quibbs&#39; target state has a finite amplitude at those x for which P   x   (x) is finite.
 
     Some previous patents (see Ref.GPat and Ref.TexasPat) use Grover&#39;s search algorithm, but they do not mention in their claims or specification its use for sampling a probability distribution. 
     Beside Ref.GSamp, Ref.Som and Ref.Woc have also given methods for sampling probability distributions with a quantum computer. Ref.Som uses the quantum Zeno effect, whereas Ref.Woc uses Grover&#39;s pi/3 algorithm (the one in Ref.GPi/3). The present invention uses neither the quantum Zeno effect, nor Grover&#39;s pi/3 algorithm. It uses more efficient techniques instead. 
     Ref.Som and Ref.Woc are both concerned with optimization (via simulated annealing) of a non-negative function E(x) defined for all x, whereas the present invention is concerned with sampling an arbitrary probability distribution P   x   (x). Even though optimization and sampling are related and share some common techniques, they are not the same thing. For instance, sampling allows you to find the expected value of any function of x, whereas optimization doesn&#39;t. Optimization allows you to find a good minimum of E(x) whereas sampling alone doesn&#39;t. 
     The inventor Tucci first published a description of this invention on Oct. 9, 2009, in Ref.TucQuibbs1. Later, he added further details in Ref.TucAfga and Ref.TucQuibbs2. 
     BRIEF SUMMARY OF THE INVENTION 
     A preferred embodiment of the invention is Quibbs, a computer program written in Java. Source code for Quibbs1.4 is included with this patent. Quibbs is a “code generator” for quantum sampling: after the user inputs some files that specify a classical Bayesian network, Quibbs outputs a quantum circuit for sampling, using a quantum computer, the probability distribution which characterizes the Bayesian network. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a block diagram of a classical computer feeding data to a quantum computer. 
         FIG. 2  shows the quantum circuit generated by Quibbs. 
         FIG. 3  shows insides of parts in  FIG. 2   
         FIG. 4  shows insides of parts in  FIG. 3   
         FIG. 5  shows insides of parts in  FIG. 4   
         FIG. 6  shows Control Panel of Quibbs. 
         FIG. 7  shows the Parents File for a Bayesian net with graph A→B←C. 
         FIG. 8  shows a States File for a Bayesian net with 3 nodes called A, B and C. 
         FIG. 9  shows a Probabilities File for a Bayesian net with Parents File given by  FIG. 7  and States File given by  FIG. 8 . 
         FIG. 10  shows an example of a Log File. 
         FIG. 11  shows an example of an English File. 
         FIG. 12  shows an example of a Picture File. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     This section describes in detail a preferred embodiment of the invention called Quibbs and other possible embodiments of the invention. 
     Quibbs is a computer program written in Java. Source code for Quibbs1.4 is included with this patent. Quibbs is a “code generator” for quantum sampling: after the user inputs some files that specify a classical Bayesian network, Quibbs outputs a quantum circuit for sampling, using a quantum computer, the probability distribution which characterizes the Bayesian network. 
     The Bayesian network being considered will be characterized by a random variable  x  that can take on values in a set val( x ) and has a full probability distribution P   x   ( ). (val( x ) is often called the sample space of  x ). If the Bayesian network has N nds  nodes, then  x =( x   1 , x   2 , . . . ,  x   N     nds   ), where random variable  x   j ∈val( x   j ) corresponds to the j&#39;th node. Without loss of generality, we will take val( x   j )={0,1} N     Bj    for some positive integer N Bj , and val( x )={0,1} N     B   , where N B =Σ j N Bj . 
     Henceforth we will say |v            is a unit vector if          v|v         =1. Consider two unit vectors |v 1            and |v 2            and let D=∥v i           −|v 2           | 2 . We will say that |v 1            and |v 2            are approximately equal to each other if D is significantly smaller than one. We will say that they are equal if D=0. We will say that |v 1            and |v 2            are equal (respectively, approximately equal) up to a phase factor if there is some real number α such that |v 1            and e iα |v 2            are equal (respectively, approximately equal). We will say that |v 1            is an approximate eigenvector of an operator Ω if there exist a vector |v 2            which is an eigenvector of Ω and |v 1            is approximately equal to |v 2           .
     Henceforth, we will use the acronym AFGA (Adaptive Fixed-point Grover&#39;s Algorithm) for the algorithm described in Ref.TucAfga. 
     Consider any operator of the form Ω=exp(iα|v                     v|) where α is a real number and where |v          is a unit vector. Note that Ω has only two distinct eigenvalues, namely exp(iα) and 1. In fact, |v          is an eigenvector of Ω with eigenvalue exp(iα), whereas any vector orthogonal to |v          has eigenvalue 1. The original Grover&#39;s algorithm (the one in Ref.GWiki) uses operators of the form Ω, with α equal to π or −π. Grover&#39;s pi/3 algorithm (the one in Ref.GPi/3) uses operators of the form Ω, with α equal to π/3 or −π/3. AFGA, on the other hand, uses operators of the form Ω, with α equal to α j  or Δλ where α j  tends to zero as j tends to infinity.
       FIG. 1  is a block diagram of a classical computer feeding data to a quantum computer. Box  100  represents a classical computer. Quibbs1.4 software runs 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. The inputs and outputs of Quibbs can be rendered on the display screen. Box  105  represents a quantum computer, comprising an array of quantum bits and some hardware for manipulating the state of those bits. 
     The remainder of this section is divided into 3 subsections. Subsection (A) describes the quantum circuit generated by Quibbs. Subsection (B) describes Quibbs&#39; user interface. Subsection (C) discusses other possible embodiments of the invention. 
     (A) Quibbs: Quantum Circuit 
     In this section, we describe the quantum circuit generated by Quibbs. For a more detailed description of the circuit, see Ref.TucQuibbs1 and Ref.TucAfga. 
       201  in  FIG. 2  is the quantum circuit generated by Quibbs. Let a, c, N B  and N ste  be some positive integers, and let x 0  be an element of {0,1} N     B   . Circuit  201  operates on ac+2N B  qubits. Circuit  201  starts off in an initial state which is a tensor product state of the ac+2N B  qubits, with the top ac+N B  qubits in state |0            and the bottom N B  qubits in state |x 0           . This initial state is then subjected to N ste +1 operators (“ste” stands for step). We will next proceed to describe the nature of each of these N ste +1 operators.
     Each of the boxes in circuit  201  is a product of two operators, {tilde over (R)} beg   (j)  and {tilde over (R)} tar . “beg” stands for “beginning” and “tar” for “target”. Note that {tilde over (R)} beg   (j)  depends on the step number j (an integer which ranges from 0 to N ste ), whereas {tilde over (R)} tar  doesn&#39;t depend on it. According to equation  202 , even though {tilde over (R)} beg   (j)  acts on all the ac+2N B  qubits, it can be expressed exactly as operator which acts as the identity on the top ac qubits and another operator R beg   (j)  which acts only on the bottom 2N B  qubits.  FIG. 3 , which will be discussed in more detail later, gives an exact circuit equivalent, namely circuit  301 , for {tilde over (R)} tar . We see that {tilde over (R)} tar  cannot be expressed exactly in terms of an operator which acts as the identity on the top ac qubits. However, according to equation  203 , {tilde over (R)} tar  can be approximated by an operator which acts as the identity on the top ac qubits and another operator {tilde over (R)} tar  which acts only on the bottom 2N B  qubits. 
     Let Δλ be a real number between 0 and π, and let {α j } j=0   ∞  be a sequence of real numbers. Δλ can be selected by the user. Ref.TucAfga explains how to calculate the angles α j  and gives an Octave/Matlab program called afga.m that calculates them explicitly. 
     Equation  204  defines R beg   (j)  in terms of the state |s′            and the angles α j . Equation  205  defines R tar  in terms of the state |t          and the angle Δλ. State |s′          is defined by equation  206 , and state |t          is defined by equation  207 . Equation  208  defines the state |√{square root over (π)}         , where π( )=P   x   ( ). Equation  209  stipulates that the state |FIN          defined by Equation  201  must be approximately equal (up to a phase factor e iα ) to a state which is a tensor product of |0          for each of the top ac+N B  qubits and |√{square root over (π)}          for the bottom N B  qubits.
     {tilde over (R)} tar  is defined exactly by the quantum circuit  301  in  FIG. 3 . Circuit  301  uses two operators called V and Q. These are defined explicitly by equations  302  and  303 . In equation  303 , H is the 1-qubit Hadamard matrix. Equation  303  also uses various powers of an operator W that will be defined explicitly in the next figure. 
     W is a so called Szegedy quantum walk operator. Equation  401  in  FIG. 4  defines W in terms of operators U, {circumflex over (π)} and {hacek over (π)}. The projection operators {circumflex over (π)} and {hacek over (π)} are defined by equations  402  and  403 , respectively. The operator U can be defined in various ways, as long as it satisfies equation  404 . One particular way of defining U is described in Ref.TucQuibbs1, and implemented explicitly in the Quibbs source code included with this patent. But what are the eigenvectors |m j              and eigenvalues m j  alluded to in equation  404 ? As stated in equation  405 , they are the eigenvectors and eigenvalues of an operator M hyb  that will be defined in the next figure.
     Equation  501  in  FIG. 5  defines the operator M hyb . (“hyb” stands for “hybrid”). Equation  501  uses two operators called Λ 1  and Λ 2 . The matrix elements of Λ 1  and Λ 2  are defined by equation  502 , in terms of the matrix elements of two operators called M 1  and M 2 . The matrix elements of M 1  and M 2  are defined in terms of certain conditional probabilities of P   x   (x). Suppose x=(x 1 ,x 2 , . . . , x N     nds   ). When N nds =3, the matrix elements of M 1  and M 2  are defined by equations  503  and  504 . For arbitrary N nds , the matrix elements of M 1  and M 2  are defined using the same pattern as in this N nds =3 example. 
     (B) Quibbs: User Interface 
     In this section, we describe Quibbs&#39; user interface. For more a more detailed description of the interface, see Ref.TucQuibbs2. 
     (B1) The Control Panel 
       FIG. 6  shows the Control Panel for Quibbs. This is the main and only window of Quibbs (except for the occasional error message window). This window is open if and only if Quibbs is running. 
     The Control Panel allows the user to enter the following inputs: 
     I/O Folder: The user enters in this text box the name of a folder. The folder will contain Quibbs&#39; input and output files for the particular Bayesian network that the user is currently considering. 
     To generate a quantum circuit, the I/O folder must contain the following 3 input files: 
     (In1) parents.txt 
     (In2) states.txt 
     (In3) probs.txt 
     Examples of In1, In2 and In3 will be presented later. For this section, all the reader needs to know is that: The parents.txt file lists the parent nodes of each node of the Bayesian net being considered. The states.txt file lists the names of the states of each node of the Bayesian net. And the probs.txt file gives the probability matrix for each node of the Bayesian net. Together, the In1, In2 and In3 files fully specify the Bayesian network being considered. 
     In the example of  FIG. 6 , “3nodes” is entered in the I/O Folder text box. A folder called “3nodes” comes with the distribution of Quibbs. It contains, among other things, In1, In2, In3 files that specify one possible Bayesian network with 3 nodes. 
     When the user presses the Read Bayesian Net button, Quibbs reads files In1, In2 and In3. The program then creates data structures that contain complete information about the Bayesian network. Furthermore, Quibbs fills the scrollable list in the Starting State grouping with information that specifies “the starting state”. The starting state is one particular instantiation (i.e., a particular state for each node) of the Bayesian network  x . The point x 0  introduced before can be calculated from the starting state. Each row of the scrollable list names a different node, and a particular state of that node. For example,  FIG. 6  shows the Quibbs Control Panel immediately after pressing the Read Bayesian Net button. In this example, the Bayesian net read in has 3 nodes called A, B and C, and the starting state has node A in state a1, node B in state b1 and node C in state c1. 
     If the user presses the Random Start button, the starting state inside the scrollable list is changed to a randomly generated one. Alternative, the user can choose a specific state for each node of the Bayesian net by using the Node State Menu, the menu immediately to the left of the Random Start button. 
     Number of Probe Bits (for each PE step): This is the parameter a=1,2,3, . . . for the operator V. 
     Number of Phase Estimation (PE) Steps: This is the parameter c=1,2,3, . . . : for the operator V. 
     Maximum Number of Grover Steps: Quibbs will stop iterating the AFGA if it reaches this number of iterations. 
     Gamma Tolerance (degs): This is an angle given in degrees. Quibbs will stop iterating the AFGA if the absolute value of γ j  becomes smaller than this tolerance. (γ j  is an angle in AFGA that tends to zero as the step index j tends to infinity. γ j  quantifies how close the AFGA is to reaching the target state). 
     Delta Lambda (degs): This is the angle Δλ of AFGA, given in degrees. 
     Once Quibbs has successfully read files In1, In2 and In3, and once the user has filled all the text boxes in the Inputs grouping, the user can successfully press the Write Q. Circuit Files button. This will cause Quibbs to write the following output files within the I/O folder: 
     (Out1) quibbs_log.txt 
     (Out2) quibbs_eng.txt 
     (Out3) quibbs_pic.txt 
     Examples of these 3 output files will be given later. For now, all the reader needs to know is that: The quibbs_log.txt file records all the input and output parameters that the user entered into the Control Panel, so the user won&#39;t forget them. The quibbs_eng.txt file is an “in English” description of a quantum circuit. And the quibbs_pic.txt file translates, line for line, the English description found in quibbs_eng.txt into a “pictorial” description. 
     The Control Panel displays the following output text boxes. (The Starting Gamma (degs) output text box and the Prob. of Starting State output text box are both filled as soon as a starting state is given in the inputs. The other output text boxes are filled when the user presses the Write Q. Circuit Files button.) 
     Starting Gamma (degs): This is γ∈[0,π], defined to satisfy cos(γ/2)=           s′|t         =√{square root over (P   x   (x 0 ))}, where P   x   (x 0 ) is called the Prob. of Starting State.
     Prob. of Starting State: This is the probability P   x   (x 0 ), which must be nonzero for AFGA to work. The probability distribution P   x   ( ), and point x 0  were introduced before. 
     Number of Qubits: This is the total number of qubits used by the quantum circuit, equal to ac+2N B . 
     Number of Elementary Operations: This is the number of elementary operations in the output quantum circuit. 
     (B2) Input Files 
     As explained earlier, for Quibbs to generate quantum circuit files, it needs to first read 3 input files: the Parents File called parents.txt, the States File called states.txt, and the Probabilities File called probs.txt. These 3 input files must be placed inside the I/O folder. Next we give examples of these 3 input files. 
       FIG. 7  shows the Parents File for a Bayesian net with graph A→B←C. In this example, nodes A and C have no parents and node B has parents A and C. 
       FIG. 8  shows a States File for a Bayesian net with 3 nodes called A, B and C. In this example, node A has 3 states called a1, a2 and a3, node B has 2 states called b1 and b2, and node C has 2 states called c1 and c2. 
       FIG. 9  shows a Probabilities File for a Bayesian net with Parents File given by  FIG. 7  and States File given by  FIG. 8 . In this example, P A (a1)=0.2, P B|A,C (b1|a1,c1)=0.7, etc. 
     (B3) Output Files 
     As explained earlier, when the user presses the Write Q. Circuit Files button, Quibbs writes 3 output files within the I/O folder: a Log File called quibbs_log.txt, an English File called quibbs_eng.txt, and a Picture File called quibbs_pic.txt. Next we give examples of these 3 output files. 
       FIG. 10  is an example a Log File. A Log File records all the information found in the Control Panel. 
       FIG. 11  is an example of an English File. An English File completely specifies the output SEO. It does so “in English”, thus its name. Each line represents one elementary operation, and time increases as we move downwards. Ref.TucQuibbs2 explains in detail how to interpret an English File. 
       FIG. 12  is an example of a Picture File. A Picture File partially specifies the output SEO. It gives an ASCII picture of the quantum circuit. Each line represents one elementary operation, and time increases as we move downwards. There is a one-to-one onto correspondence between the rows of the English and Picture Files. Ref.TucQuibbs2 explains in detail how to interpret a Picture File. 
     (C) Other Embodiments 
     In this section, we describe other possible embodiments of the invention. 
     Of course, Quibbs could have been written in a computer language other than Java. 
     The quantum circuit generated by Quibbs includes some quantum multiplexors. The Java application Multiplexor Expander (see Ref.TucQusann) allows the user to replace each of those multiplexors by a sequence of more elementary gates such as multiply controlled NOTs and qubit rotations. Multiplexor Expander source code is included with this patent. Another perhaps more efficient variation would be if Quibbs didn&#39;t write a given multiplexor in the English File, but rather wrote instead a SEO that was either exactly or approximately equal to the multiplexor. 
     The quantum circuit generated by Quibbs includes some multiply controlled NOTs. The Java application MultiCNot Expander, whose source code is included with this patent, allows the user to replace each of those multiply controlled NOTs by a sequence of more elementary gates such as singly controlled NOTs and qubit rotations. 
     A version of Quibbs could forgo writing the English or Picture Files and feed the SEO directly to the quantum computer. 
     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.