Abstract:
The invention comprises a classical computer that runs a special computer program. The program takes as input an initial data-set that comprises probabilistic information and returns as output a sequence of elementary operations (SEO). The initial data-set helps determine a classical Bayesian (CB) net. A program called “Q-Embedder” embeds the CB net within a quantum Bayesian (QB) net. A program called “Qubiter” (a quantum compiler) then translates the QB net into an equivalent SEO. The SEO outputted by the classical computer can be used to manipulate an array of qubits in a quantum computer. Application of the SEO to the array, followed by a measurement of the array, yields the value of certain conditional probabilities that we wish to know. The main goal of the invention is to provide a method for performing classical Bayesian net calculations on a quantum computer. Such calculations can be done on a classical computer; the hope is that they can be done much faster on a quantum computer.

Description:
CROSS REFERENCES TO RELATED APPLICATIONS  
       [0001]     Not Applicable  
       STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT  
       [0002]     Not Applicable  
       BACKGROUND OF THE INVENTION  
       [0003]     (A) Field of the Invention  
         [0004]     The invention relates to an array of quantum bits (qubits) commonly known as a quantum computer. More specifically, it relates to methods for translating an input data-set into a sequence of operations that can be used to manipulate said array. The invention also relates to classical probabilistic networks (classical Bayesian nets) and their quantum counterparts.  
         [0005]     (B) Description of Related Art  
         [0006]     This invention deals with Quantum Computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating these 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 qubit 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. For a detailed discussion of quantum computing, see the books Gru99: J. Gruska,  Quantum Computing , (Osborne McGraw-Hill, 1999), and NieChu00: M. Nielsen, I. Chuang,  Quantum Computation and Quantum Information , (Cambridge University Press, 2000). Also, one can find on the Internet some excellent, free introductions to quantum computing.  
         [0007]     This invention also deals with Classical Bayesian (CB) and Quantum Bayesian (QB) nets. (Most of the literature to date deals only with CB nets and refers to them simply as Bayesian nets (or networks), without the adjective “classical”.)  
         [0008]     A CB net comprises a graph (i.e., a diagram) and a matrix (with probabilities as entries) associated with each node of the graph. CB nets organize large amounts of probabilistic information and represent complicated probabilistic relationships. They do this in a way that is graphical, highly intuitive, and easily scalable. From the data contained within a CB net, one can derive many other conditional probabilities. Knowing such conditional probabilities is useful in applications of Decision Theory and Artificial Intelligence, wherein inferences are made based on uncertain knowledge. CB nets have been used in many areas, including pattern recognition, speech recognition, data mining, search engines, spam filters, expert systems, medical diagnosis, computer games with AI capabilities, etc. Companies which actively support the development and deployment of CB net technology include Microsoft, Intel, Google, etc. CB nets are also used in Defense (e.g., Star Wars missile discrimination). For a detailed discussion of CB nets, see the books Jen01: Finn V. Jensen,  Bayesian Networks and Decision Graphs  (Springer Verlag, 2001), and Pea88: Judea Pearl,  Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference  (Morgan Kaufmann, Palo Alto, 1988). Also, one can find on the Internet some excellent, free introductions to CB nets.  
         [0009]     QB nets are a generalization of CB nets to quantum mechanics. A QB net comprises a graph and a matrix (with complex numbers called probability amplitudes or just amplitudes as entries) associated with each node of the graph. QB nets have been proposed as a graphical method for analyzing the behavior of quantum systems, in QFogPat: U.S. Pat. No. 5,787,236 by R. R. Tucci. QB net diagrams may be viewed as an alternative to qubit circuits. For an introduction to QB nets, see QFogPat and Tuc99QIT: R. R. Tucci, “Quantum Information Theory—A Quantum Bayesian Nets Perspective”, ArXiv eprint quant-ph/9909039.  
         [0010]     The method proposed in this invention is based on an earlier method proposed by Fredkin-Toffoli (F-T) in Tof80: T. Toffoli,  Automata, Languages and Programming,  7 th Coll . (Springer Verlag, 1980) pg. 632, and in EreTof82: E. Fredkin, T. Toffoli, Int. Jour. of Th. Phys. (1982) Vol. 21, pg. 219. The F-T method is used in the field of (classical) reversible computing. F-T showed how, given any binary gate ƒ (i.e., a function ƒ: {0, 1} r →{0, 1} s , for some integers r, s), one can construct another binary gate {overscore (ƒ)} such that {overscore (ƒ)} can be used to perform the same calculations as ƒ, but in a reversible manner. We will call {overscore (ƒ)} a deterministic reversible extension (DRE) of ƒ. Binary gates ƒ and {overscore (ƒ)} can be represented as binary deterministic circuits. In this patent, we show how, given any CB net K C , one can construct a QB net K Q  which is a “q-embedding” of K C . (“q-” stands for “quantum-”) By running K Q  on a quantum computer, one can calculate any conditional probability that one would be interested in calculating for the CB net K C . Such conditional probabilities can be calculated with classical computers; the hope is that they can be calculated much faster with a quantum computer. Our method for constructing a q-embedding for a CB net is a generalization of the F-T method for constructing a DRE of a binary deterministic circuit. Thus, we generalize their method to the embedding of any classical stochastic circuit, not just binary deterministic ones.  
         [0011]     Grover&#39;s algorithm is a quantum algorithm proposed in GroPat: U.S. Pat. No. 6,317,766, by Lov K. Grover. Our method of embedding a CB net K C  within a QB net K Q  can sometimes be used in combination with Grover&#39;s algorithm to great advantage. In certain cases, the target states that we wish to detect have probabilities that are too small to be measurable by running K Q  on a quantum computer. However, we will show that sometimes one can construct a new QB net, call it K Q ′, that magnifies to measurable values the target probabilities that were unmeasurable using K Q  alone. We will refer to K Q ′ as Grover&#39;s Microscope for K Q , because K Q ′ is closely related to Grover&#39;s algorithm, and it magnifies some of the probabilities found with K Q .  
         [0012]     The independent claims of GroPat are 1 and 12. Claim 1 of GroPat refers to an “arrangement”, presumably meaning quantum hardware such as a quantum computer. The claims of the present patent that pertain to Grover&#39;s algorithm require a classical computer that generates a sequence of operations; they do not require the actual application of said sequence of operations to a quantum computer. Claim 12 of GroPat refers to “A method for moving a quantum mechanical physical system which exists in a superposition of a plurality of states”. Again, this seems to require quantum hardware to be manipulated according to the method. Even if it were judged that an embodiment of claim 12 of GroPat did not require quantum hardware, the present patent claims a Grover-like algorithm only if used as a post-processor to a special, classical computer program of which a preferred embodiment called “Q-Embedder” is described below.  
         [0013]     A quantum compiler is a computer program that one runs on classical computers. It can “compile” a unitary matrix; i.e., it can express a unitary matrix as a SEO that a quantum computer can follow. An early type of quantum compiler is discussed in Bar95: A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. H. Smolin, H. Weinfurter, ArXiv eprint quant-ph/9503016. A different type of quantum compiler is discussed in QbtrPat: U.S. Pat. No. 6,456,994 B1, by R. R. Tucci, and in Tuc99Qbtr: R. R. Tucci, “A Rudimentary Quantum Compiler (2cnd ed.)”, ArXiv eprint quant-ph/9902062.  
         [0014]     To run a QB net on a quantum computer, as is proposed in this invention, we need to translate the QB net into an equivalent SEO. This can be done with the help of a quantum compiler. A possible method of accomplishing this is discussed in QbtrPat and in Tuc98: R. R. Tucci, “How to Compile a Quantum Bayesian Net”, ArXiv eprint quant-ph/9805016. Thus, the method of this invention promises to be fertile ground for the use of quantum compilers.  
         [0015]     A precursor to this invention was first published in TucV1: R. R. Tucci, “Quantum Computer as an Inference Engine”, ArXiv eprint quant-ph/0004028 Version 1, submitted on 6 Apr. 2000. After TucV1 was published, Tucci realized that the method of TucV1 was flawed in some important respects. A new method, which is a substantial modification and correction of the method of TucV1, was published by Tucci in TucV2: R. R. Tucci, “Quantum Computer as a Probabilistic Inference Engine”, ArXiv eprint quant-ph/0004028 Version 2, submitted on 19 Apr. 2004. We emphasize that TucV1 is now considered obsolete and flawed by Tucci. On the other hand, Tucci currently views TucV2 as essentially correct and in agreement with this invention. TucV1 and TucV2 differ as follows. Contrary to TucV2, TucV1 does not q-embed the root nodes of the CB net that it is trying to q-embed. More importantly, Section 6.3 of TucV1 incorrectly claims that calculating a conditional probability for a CB net K C  using its q-embedding K Q  requires measurements of all internal nodes of K Q . TucV2 shows that only some of the external nodes of K Q  need to be measured.  
         [0016]     JaePat: U.S. Pat. No. 6,675,154, by G. S. Jaeger, proposes the use of a quantum computer for performing Fuzzy Logic. (Fuzzy Logic is a field that started with the paper Zad65: Lotfi Zadeh, “Fuzzy Sets”, Information and Control Vol 8 (1965) pgs. 338-353). Although it might at first appear that there is some overlap between the claims of JaePat and those of the present patent, careful reflection shows that this is not the case. Indeed, the independent claims of JaePat are 1, 2, 6 and 11. Claim 1 of JaePat requires the use of F1: “at least one fuzzy proposition”. Claim 2 of JaePat requires the use of F2: “fuzzy logic operations”. Claims 6 and 11 both require “fuzzy control”, which presumably requires F1 or F2. The claims of the present patent do not require F1 or F2. It is also of interest to note that many scientists and engineers are highly critical of Fuzzy Logic, and consider Bayesian Nets a far better method for dealing with situations involving uncertain knowledge.  
         [0017]     To summarize, the present invention has the following advantages over prior art: 
        It merges ideas from various subjects (quantum computers, CB nets, QB nets, quantum compilers and Grover&#39;s algorithm) in a new way.     It generalizes ideas of F-T used in classical reversible computing.     It gives a method for performing CB net calculations on a quantum computer. Such calculations can be done on a classical computer. The hope is that they can be done much faster on a quantum computer.     It uses ideas from TucV2, and avoids mistakes of TucV1. TucV1 and TucV2 were both written by the inventor of this patent.     It shuns ideas from Fuzzy Logic in favor of Bayesian nets.        
 
       BRIEF SUMMARY OF THE INVENTION  
       [0023]     A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating these qubits. A classical Bayesian (CB) net (or network) comprises a graph (i.e., a diagram) and a matrix (with probabilities as entries) associated with each node of the graph. A quantum Bayesian (QB) net comprises a graph and a matrix (with complex numbers called probability amplitudes or just amplitudes as entries) associated with each node of the graph.  
         [0024]     A preferred embodiment of the invention comprises a classical computer that runs a special computer program. The program takes as input an initial data-set that contains probabilistic information and returns as output a sequence of elementary operations (SEO). The initial data-set helps determine a CB net K C . A program called “Q-Embedder” q-embeds K C  within a QB net K Q . (“q-” stands for “quantum-). A program called “Qubiter” then translates K Q  into an equivalent SEO. Qubiter is an example of a type of program called a quantum compiler.  
         [0025]     The SEO outputted by the classical computer can be used to manipulate an array of qubits in a quantum computer. Application of the SEO to the array, followed by a measurement of the array, yields the value of certain conditional probabilities that we wish to know.  
         [0026]     A probability matrix is any matrix such that each column of the matrix constitutes a discrete probability distribution. Given a probability matrix P, this patent defines a unitary matrix U called a q-embedding of P. U carries all information contained in P. This patent describes a method for constructing one q-embedding U (out of many possible ones) for an arbitrary probability matrix P.  
         [0027]     Given a CB net K C , this patent defines a QB net K Q  called a q-embedding of K C . By running K Q  on a quantum computer, one can calculate any conditional probability that one would be interested in calculating for the original CB net K C . This patent describes a method for constructing one q-embedding K Q  (out of many possible ones) for an arbitrary CB net K C . The method involves replacing each node matrix of K C  by a q-embedding. Doing this replacement of node matrices requires adding to the graph of K C  new nodes called marginalizer and ancilla nodes.  
         [0028]     This patent also shows how to use a version of Grover&#39;s algorithm in combination with Q-Embedder and Qubiter.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0029]      FIG. 1  shows a labelled graph and the four node matrices associated with the four nodes of the graph. The A j  are complex amplitudes. This figure illustrates a QB net. Suppose we replaced A j  everywhere in this figure by probabilities P j . Then the figure would be an illustration of a CB net.  
         [0030]      FIG. 2  shows how to construct a q-embedding of an arbitrary probability matrix P(y/x). For definiteness, we assume in this figure that x∈{0, 1, 2} and y∈{0, 1, 2, 3}. Shaded columns can be filled using the Gram-Schmidt algorithm.  
         [0031]      FIG. 3  shows a CB net for 2-body scattering. The figure includes the net&#39;s graph and a table of its node probabilities. We use this net to illustrate how one can construct a q-embedding of an arbitrary CB net.  
         [0032]      FIG. 4  shows a CB net (defined by a graph and a table of node probabilities) obtained by adding marginalizer nodes to the CB net of  FIG. 3 .  
         [0033]      FIG. 5  shows, for the scattering QB net, its graph.  
         [0034]      FIG. 6  shows, for the scattering QB net, a table of its node amplitudes.  
         [0035]      FIG. 7  shows, for the scattering QB net, the probability amplitude of its external nodes.  
         [0036]      FIG. 8  shows, for the lung-disease-diagnosis CB net, its graph, and a table of its node probabilities.  
         [0037]      FIG. 9  shows, for the lung-disease-diagnosis QB net, its graph.  
         [0038]      FIG. 10  shows, for the lung-disease-diagnosis QB net, a table of its node amplitudes.  
         [0039]      FIG. 11  shows, for the voting CB net, its graph and a table of its node probabilities.  
         [0040]      FIG. 12  shows, for the voting QB net, its graph, a table of its node amplitudes and the amplitude of its external nodes.  
         [0041]      FIG. 13  shows various vectors relevant to the algorithm that we call “Grover&#39;s Microscope”.  
         [0042]      FIG. 14  shows two boxes, each representing a text file. Together, these two text files fully specify a QB net.  
         [0043]      FIG. 15  shows a block diagram of a classical computer feeding data to a quantum computer. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0000]     (A) Theory Behind New Method  
         [0000]     Henceforth, we use the following notation.  
         [0044]     We will use the word “ditto” as follows. If we say “A (ditto, X) is smaller than B (ditto, Y)”, we mean “A is smaller than B” and “X is smaller than Y”.  
         [0045]     The prefix “q-” will to stand for “quantum-” (as in “q-embedding”) and the prefix “c-” will stand for “classical-”.  
         [0046]     Let Bool={0, 1}. Let Z a,b ={a, a+1, a+2, . . . , b−1, b} for arbitrary integers a and b such that a≦b. For any finite set S, |S| will denote the cardinality of S (i.e., the number of elements in S).  
         [0047]     δ(x, y) will denote the Kronecker delta function; it equals one if x=y and zero otherwise. For any statement St, we define the truth function θ(St) to equal 1 if St is true and 0 if St is false. For example, δ(x, y)=θ(x=y).  
         [0048]     ⊕ will denote addition mod 2. Suppose {right arrow over (x)}=(x 0 , x 1 , x 2 , . . . )∈Bool ∞ . We will call  
       x   =       ∑     α   =   0     ∞     ⁢       x   α     ⁢     2   α             
 
 the decimal representation of {right arrow over (x)} and denote it by dec({right arrow over (x)}). 
 
         [0049]     We will use the symbol Σ. to denote a sum of whatever is on the right hand side of this symbol, where we sum over those indices with a dot underneath them. For example, Σ.ƒ(α)=Σ α ƒ(α)  
         [0050]     Suppose function ƒ maps set S into the complex numbers. We will use ƒ(x)/(Σ x  numerator) to represent ƒ(x)/(Σ x∈S ƒ(x)). Thus, “numerator” stands for the numerator of the fraction.  
         [0051]     Henceforth, we will either underline or put a caret over random variables. (ArXiv publications by Tucci (e.g., TucV2) indicate random variables by underlining them.) For example, P(â=a)=P â (a) will denote the probability that the random variable â assumes value a. P(â=a) will often be abbreviated by P(a) when no confusion will arise. S â  will denote the set of values which the random variable â may assume, and N â  will denote the number of elements in S â . pd(B|A) will stand for the set of probability distributions P(•|•) such that P(b|a)≧0 and Σ b′∈B P(b′|a)=1 for all a∈A and b∈B.  
         H   1     =     (         1         1   ⁢                 1           -   1     ⁢               )         
 
 is the one bit Hadamard matrix. H N     B   =H 1   {circle over (×)}N     B    (the n-fold tensor product of H 1 ) is the N B  bit Hadamard matrix. 
 
         [0052]     Let {right arrow over (κ)}=(κ 0 , κ 1 , κ N     B     −1 ) label N B  bits. Assume all κ i  are distinct. We will often use N S =2 N     B   , where N B  stands for number of bits and N S  for number of states. If|φ           κ     i   =|φ(κ i )          is a ket for qubit κ i , define |φ           {right arrow over (κ)} =|φ({right arrow over (κ)})         =Π i=0   N     B     −1 |φ)κ i )         . For example, if  
                   ❘   0     〉       κ   i       =     (         1           0         )             (   1   )             
 
 for all i, then  
                         ❘   0     〉       κ   -&gt;       =       ⁢       ∏     i   =   0         N   B     -   1       ⁢       ❘     ⁢   0   ⁢       〉       κ   i                       =       ⁢       (         1           0         )     ⊗     (         1           0         )     ⊗   …   ⊗     (         1           0         )                   =       ⁢         [     1   ,   0   ,   0   ,   …   ⁢           ,   0     ]     T     .                   (   2   )             
 
 Likewise, if Ω(κ i ) is an operator acting on qubit κ i , define  
         Ω   ⁢     (     ⁢     κ   -&gt;     ⁢     )       =       ∏     i   =   0         N   B     -   1       ⁢       Ω   ⁡     (     κ   i     )       .           
 
 For example,  
           H   1     ⁢     (     ⁢     κ   -&gt;     ⁢     )       =       ∏     i   =   0         N   B     -   1       ⁢       H   1     ⁡     (     κ   i     )             
 
 is the N B  bit Hadamard matrix. 
 
         [0053]     Suppose φ is a normalized (φ † φ=1) complex vector. Define the projection and reflection operators for φ by 
 
Π φ =φφ †   , R   φ =1−2Π φ .  (3) 
 
 Note that Π φ   2 =Π φ . If x′=R φ x, then x′ is the reflection of x with respect to the plane perpendicular to φ. For example, R φ φ=−φ. 
 
         [0054]     Next we will present a brief review of CB and QB nets. For more information about CB nets see Jen01 or Pea88 or the internet. For more information about QB nets, see QFogPat or Tuc99QIT. First, we will discuss QB nets. Then we will point out how CB nets differ from QB nets.  
         [0055]     We call a graph (or a diagram) a collection of nodes with arrows connecting some pairs of these nodes. The arrows of the graph must satisfy certain constraints. We call a labelled graph a graph whose nodes are labelled. A QB net consists of two parts: a labelled graph with each node labelled by a random variable, and a collection of node matrices, one matrix for each node. These two parts must satisfy certain constraints.  
         [0056]     An internal arrow is an arrow that has a starting (source) node and a different ending (destination) one. We will use only internal arrows. We define two types of nodes: an internal or non-leaf node is a node that has one or more internal arrows leaving it, and an external or leaf node is a node that has no internal arrows leaving it. It is also common to use the terms root node or prior probability node for a node that has no incoming arrows (if any arrows touch it, they are outgoing ones).  
         [0057]     We restrict our attention to acyclic graphs; that is, graphs that do not contain cycles. (A cycle is a closed path of arrows with the arrows all pointing in the same sense.)  
         [0058]     We assign a random variable to each node of the QB net. Suppose the random variables assigned to the N nodes are x 1 , x 2 , x N . For each j∈Z 1,N , the random variable {circumflex over (x)} j  will be assumed to take on values within a finite set S j  called the set of possible states of {circumflex over (x)} j .  
         [0059]     For example, consider the net of  FIG. 1 . Nodes  11 ,  12  and  13  are internal and node  14  is external. Node  11  is a root node. There are four nodes so N=4. We will assume that the four nodes must lie in one of two states: either no or si. Thus, S 1 =S 2 =S 3 =S 4 ={no, si}.  
         [0060]     If Γ={k 1 , k 2 , . . . , k |Γ| }⊂Z 1,N , and k 1 &lt;k 2 &lt; . . . &lt;k |Γ| , define (x.) Γ =(x k     1   , x k     2   , . . . , x k     |Γ|   ) and ({circumflex over (x)}.) Γ =({circumflex over (x)} k     1   , {circumflex over (x)} k     2   , . . . , {circumflex over (x)} k     |Γ|   ). Sometimes, we also abbreviate (x.) Z     1,N    (i.e., the vector that includes all the possible x j  components) by just x., and ({circumflex over (x)}.) Z     1,N    by just {circumflex over (x)}.  
         [0061]     For example, suppose N=4. One has Z 1,4 ={1, 2, 3, 4}. If Γ={1, 3}, then |Γ|=2. Furthermore, (x.) Γ =(x 1 , x 3 ) and ({circumflex over (x)}.) Γ =({circumflex over (x)} 1 , {circumflex over (x)} 3 ). One defines x.=(x.) Z     1,4   =(x 1 , x 2 , x 3 , x 4 ) and {circumflex over (x)}.=({circumflex over (x)}.) Z     1,4   =({circumflex over (x)} 1 , {circumflex over (x)} 2 , {circumflex over (x)} 3 , {circumflex over (x)} 4 ).  
         [0062]     Let Z ext  be the set of all j∈Z 1,N  such that {circumflex over (x)} j  is an external node, and let Z int  be the set of all j∈Z 1,N  such that {circumflex over (x)} j  is an internal node. Clearly, Z ext  and Z int  are disjoint and their union is Z 1,N .  
         [0063]     For example, for  FIG. 1 , Z ext ={4} and Z int ={1, 2, 3}.  
         [0064]     Each possible value x. of {circumflex over (x)}. defines a different net story. For any net story x., we call (x.) Z     int    the internal state of the story and (x.) Z     ext    its external state.  
         [0065]     For example, a possible story for the net of  FIG. 1  is the case when {circumflex over (x)} 1 ={circumflex over (x)} 2 =si and {circumflex over (x)} 3 ={circumflex over (x)} 4 =no. This net story may also be represented by {circumflex over (x)}.=(si, si, no, no). Since we are assuming that each of the four nodes of  FIG. 1  can assume two states, there are total of 2 4 =16 stories possible for the net of  FIG. 1 . For story {circumflex over (x)}.=(si, si, no, no), the internal state is (x 1 , x 2 , x 3 )=(si, si, no) and the external state is x 4 =no.  
         [0066]     For each net story, we may assign an amplitude to each node. Define Γ j  to be the set of all k such that an arrow labelled x k  (i.e., an arrow whose source node is {circumflex over (x)} k ) enters node {circumflex over (x)} j . We say nodes ({circumflex over (x)}.) Γ     j    are parents of node {circumflex over (x)} j , and {circumflex over (x)} j  is a child of nodes ({circumflex over (x)}.) γ     j   . We assign a complex number A j [x j |(x.) Γ     j   ] to node {circumflex over (x)} j . We call A j [x j |(x.) Γ     j   ] the amplitude of node {circumflex over (x)} j  within net story x..  
         [0067]     For example, consider an arbitrary net story, call it (x 1 , x 2 , x 3 , x 4 ), of  FIG. 1 . No arrow enters node {circumflex over (x)} 1  so both Γ 1  and (x.) Γ     1    are empty. Node {circumflex over (x)} 2  is entered by an arrow from node {circumflex over (x)} 1  so Γ 2 ={1} and (x.) Γ     2   =(x 1 ). Likewise, Γ 3 ={1} and (x.) Γ     3   =(x 1 ). Finally, Γ 4 ={2, 3} and (x.) Γ     4   =(x 2 , x 3 ). We assign the complex number A 1 [x 1 ] to node {circumflex over (x)} 1 , A 2 [x 2 |x 1 ] to node {circumflex over (x)} 2 , A 3 [x 3 |x 1 ] to node {circumflex over (x)} 3 , and A 4 [x 4 |x 2 , x 3 ] to node x 4 .  
         [0068]     The amplitude of net story x., call it A(x.), is defined to be the product of all the node amplitudes A j [x j |(x.) Γ     j   ] for j∈Z 1,N . Thus,  
               A   ⁡     (     x   .     )       =       ∏     j   ∈     Z     1   ,   N           ⁢         A   j     ⁡     [       x   j     ❘       (     x   .     )       Γ   j         ]       .               (   4   )             
 
         [0069]     For example, consider an arbitrary net story, call it (x 1 , x 2 , x 3 , x 4 ), of  FIG. 1 . One has that 
 
 A ( x   1   , x   2   , x   3   , x   4 )= A   1   [x   1   ]A   2   [x   2   |x   1   ]A   3   [x   3   |x   1   ]A   4   [x   4   |x   2   , x   3 ].  (5) 
 
         [0070]     The function A j  with values A j [x j |(x.) Γ     j   ] determines a matrix that we will call the node matrix of node {circumflex over (x)} j , and denote by Q j . x j  is the matrix&#39;s row index and (x.) Γ     j    is its column index.  
         [0071]     For example,  FIG. 1  gives the four node matrices Q 1 , Q 2 , Q 3 , Q 4  associated with the four nodes of the graph shown there.  
         [0072]     This concludes our brief review of QB nets. CB nets are the same a QB nets except that complex numbers (node amplitudes) A j [x j |(x.) Γ     j   ], are replaced by non-negative numbers (node probabilities) P j [x j |(x.) Γ     j   ]. In analogy to Eq. (4), the probability of net story x., call it P(x.), is defined as  
               P   ⁡     (     x   .     )       =       ∏     j   ∈     Z     1   ,   N           ⁢         P   j     ⁡     [       x   j     ❘       (     x   .     )       Γ   j         ]       .               (   6   )             
 
 Whereas the node amplitudes of a QB net satisfy (usually)  
                   ∑       x   j     ∈     S   j         ⁢              A   j     ⁡     [       x   j     ❘       (     x   .     )       Γ   j         ]            2       =   1     ,           (   7   )             
 
 the node probabilities of a CB net satisfy (usually)  
                 ∑       x   j     ∈     S   j         ⁢       P   j     ⁡     [       x   j     ❘       (     x   .     )       Γ   j         ]         =   1.           (   8   )             
 
 (We say “usually” because sometimes it might be convenient to use un-normalized P j  or A j . Within the specification of this patent, we assume that node probabilities P j  and node amplitudes A j  are normalized. This should be interpreted as a preferred embodiment, not a necessity, of the invention.) 
 
         [0073]     Refs.QbtrPat (see, for example, Eq. (20) of QbtrPat) and Tuc98 show that given any QB net, one can find a (non-unique) unitary matrix, call it U net , and an initial state vector, call it Ψ 0 , so that U net  and Ψ 0  describe the state evolution for the situation captured by the QB net. One has 
 
Ψ=U net Ψ 0 ,  (9) 
 
 where information about the root nodes of the QB net is encoded in the initial state vector Ψ 0 , and information about the leaf nodes of the QB net is encoded in the final state vector Ψ. 
 
         [0074]     Next we will define the q-embedding of a probability matrix and of a CB net.  
         [0075]     A probability matrix P(y|x) is a rectangular (not necessarily square) matrix with row index y∈S ŷ  and column index x∈S {circumflex over (x)}  such that P(y|x)≧0 for all x, y, and Σ y P(y|x)=1 for all x. The set of all probability matrices P(y|x) where x∈S {circumflex over (x)}  and y∈S ŷ  will be denoted by pd(S ŷ |S {circumflex over (x)} ) (pd=probability distribution). A probability matrix is assigned to each node of a CB net. A probability matrix P(y|x) is deterministic if for each column x, there exists a single row y, call it ƒ(x), such that P(y|x)=δ(ƒ(x), y). Any map ƒ: S {circumflex over (x)} →S ŷ  uniquely specifies (and is uniquely specified) by the deterministic probability matrix P with matrix elements P(y|x)=δ(y, ƒ(x)) for all x∈S {circumflex over (x)}  and y∈S ŷ . We often talk about a map ƒ and its associated probability matrix P(y|x) as if they were the same thing.  
         [0076]     A unitary matrix A(y, {tilde over (x)}|x, {tilde over (y)}) (with rows labelled by y, {tilde over (x)} and columns by x, {tilde over (y)}) is a q-embedding of probability matrix P(y|x) if  
                 ∑     x   ~       ⁢            A   ⁢     (     y   ,       x   ~     ❘   x     ,       y   ~     =   0       )            2       =     P   ⁡     (     y   ❘   x     )               (   10   )             
 
 for all possible values of y and x. We say {tilde over (y)} is a source index and {tilde over (x)} is a sink index. We also refer to {tilde over (x)} and {tilde over (y)} collectively as ancilla indices. If a q-embedding satisfies A(y, {tilde over (x)}|x, {tilde over (y)})∈Bool for all y, {tilde over (x)}, x, {tilde over (y)}, we say that it is a deterministic q-embedding. Examples of the q-embedding of a probability matrix will be given below. 
 
         [0077]     Given a QB net K Q , let  
               P   ⁡     [       (     x   .     )     L     ]       =                ∑       (     x   .     )       not   ⁡     (   L   )           ⁢     A   ⁡     (     x   .     )              2     .             (   11   )             
 
 On the right hand side of Eq. (11), A(x.) is the amplitude of story (x.), not(L)=Z Q −L, where Z Q  is the set of indices of all the nodes of K Q , and L is the set of indices of all external (leaf) nodes of K Q . In other words, not (L) is the set of internal (non-leaf) nodes of K Q . We say K Q  is a q-embedding of CB net K C  if P[(x.) L ] defined by Eq. (11) satisfies  
                 P   ⁡     [       (     x   .     )       Z   C       ]       =       ∑       (     x   .     )       L   1         ⁢     P   ⁡     [       (     x   .     )     L     ]           ,           (   12   )             
 
 where L 1 ⊂L, and Z C  is the set of indices of all nodes of K C . Thus, the probability distribution associated with all nodes of K C  can be obtained from the probability distribution associated with the external nodes of K Q . Examples of the q-embedding of a CB net will be given below. 
 
         [0078]     Next we will prove that any probability matrix has a q-embedding. Suppose that we are given a probability matrix P(y|x) where x∈S {circumflex over (x)}  and y∈S ŷ . Let N {circumflex over (x)} =|S {circumflex over (x)} | and N ŷ =|S ŷ . Let ξ (x)  for x∈S {circumflex over (x)}  be any orthonormal basis of the complex N {circumflex over (x)}  dimensional vector space. The components of ξ (x)  will be denoted by ξ {circumflex over (x)}   (x) , where {tilde over (x)}∈S {circumflex over (x)} . If the ξ (x) &#39;s are the standard basis, then ξ {tilde over (x)}   (x) =δ(x, {tilde over (x)}). Define matrix A by  
               A   ⁡     (     y   ,       x   ~     ❘   x     ,     y   ~       )       =     {                 ⁢         P   ⁡     (     y   ❘   x     )         ⁢     ξ     x   ~       (   x   )                   if   ⁢           ⁢     y   ~       =   0                   ⁢     obtained   ⁢           ⁢   by   ⁢           ⁢   Gram   ⁢     -     ⁢   Schmidt   ⁢           ⁢   method               if   ⁢           ⁢     y   ~       ≠   0           .               (   13   )             
 
         [0079]     To understand the last equation, consider  FIG. 2 . In that figure we have assumed for definiteness that S {circumflex over (x)} ={0, 1, 2} and S ŷ ={0, 1, 2, 3}. The shaded (ditto, unshaded) columns have {tilde over (y)}≠0 (ditto, {tilde over (y)}=0). It is easy to see that the unshaded columns are orthonormal because the vectors ξ (x)  are orthonormal and  
           ∑   y     ⁢           ⁢     P   ⁡     (     y   ❘   x     )         =   1.       
Since the unshaded columns are orthonormal, one can use the Gram-Schmidt method to fill the shaded columns so that all the columns of A are orthonormal and therefore A is unitary. The Gram Schmidt method is covered in most Linear Algebra books. See, for example, the book NobDan88: B. Noble and J. W. Daniels,  Applied Linear Algebra , Third Edition (Prentice Hall, 1988). Note that by virtue of Eq. (13),  
                       ∑     x   ~       ⁢            A   ⁡     (     y   ,       x   ~     ❘   x     ,       y   ~     =   0       )            2       =       ⁢       ∑     x   ~       ⁢       P   ⁡     (     y   ❘   x     )       ⁢     ξ     x   ~         (   x   )     *       ⁢     ξ     x   ~       (   x   )                       =       ⁢     P   ⁡     (     y   ❘   x     )                     (   14   )             
 
 so that the A defined by Eq. (13) does indeed satisfy Eq. (10). 
 
         [0080]     Note that the matrix A defined by Eq. (13) will have real entries if the ξ (x)  basis is chosen to lie in the real N {circumflex over (x)}  dimensional vector space and the Gram-Schmidt process is carried out in that same space. Thus, one can always find a q-embedding A for a probability matrix such that A is not merely unitary, but also orthogonal. However, if A is destined to become a node matrix in a QB net, it may be counterproductive to constrain A to be real, since this constraint may cause SEO decompositions of A to be longer.  
         [0081]     Note that the matrix A defined by Eq. (13) has dimensions N {circumflex over (x)} N ŷ ×N {circumflex over (x)} N ŷ . It is sometimes possible to find a smaller q-embedding of an N ŷ ×N {circumflex over (x)}  probability matrix P(y|x). For example, suppose 
 
 P ( y|x   1   , x   2 )=δ( y, x   1   ⊕x   2 ),  (15) 
 
 for y, x 1 , x 2 ∈Bool. Then define  
                 A   ⁡     (     y   ,     e   ❘     x   1       ,     x   2       )       =           (     -   1     )         x   1     ⁢   e         2       ⁢     δ   ⁡     (     y   ,       x   1     ⊕     x   2         )           ,           (   16   )             
 
 for y, e, x 1 , x 2 ∈Bool. It is easy to check that matrix A is unitary. Furthermore,  
                 ∑   e     ⁢            A   ⁡     (     y   ,     e   ❘     x   1       ,     x   2       )            2       =       δ   ⁡     (     y   ,       x   1     ⊕     x   2         )       .             (   17   )             
 
         [0082]     Next we will show that any CB net has a q-embedding. So far we&#39;ve shown how to construct a q-embedding for any probability matrix. Remember that each node of a CB net K C  has a probability matrix assigned to it. The main step in constructing a q-embedding of K C  is to replace each node matrix of K C  by a q-embedding of it.  
         [0083]     Before describing our construction method, we need some definitions. We say a node {circumflex over (m)} is a marginalizer node if it has a single input arrow and a single output arrow. Furthermore, the parent node of {circumflex over (m)}, call it {circumflex over (x)}, has states x=(x 1 , x 2 , . . . . x n ), where x i ∈S {circumflex over (x)}     i    for each i∈Z 1,n . Furthermore, for some particular integer i 0 ∈Z 1,n , the set of possible states of {circumflex over (m)} is S {circumflex over (m)} =S  
           S     m   ^       =     S         x   ^     i     0         ,       
 
 , and the node matrix of {circumflex over (m)} is P[{circumflex over (m)}=m|{circumflex over (x)}=(x 1 , x 2 , . . . , x n )]=δ(m, x i     0   ). 
 
         [0084]     Let K C  be a CB net for which we want to obtain a q-embedding. Our construction has two steps:  
         [0000]     (Step 1) Add Marginalizer Nodes.  
         [0085]     More specifically, replace K C  by a modified CB net K C   mod  obtained as follows. For each node {circumflex over (x)} of K C , add a marginalizer node between {circumflex over (x)} and every child of {circumflex over (x)}. If {circumflex over (x)} has no children, add a child to it.  
         [0086]     As an example of this step, consider the net K C  (“two body scattering net”) defined by  FIG. 3 .  FIG. 3  consists of two parts: a graph, and a table giving the probability matrices associated with each node of the graph.  
         [0087]     Applying Step 1 to K C  defined by  FIG. 3  yields K C   mod  defined by  FIG. 4 . Note that in  FIG. 4 , black circles denote all the marginalizer nodes added in Step 1, whereas white circles denote the original nodes of K C .  
         [0000]     (Step 2) Replace Node Probability Matrices by Their Q-Embeddings. Add Ancilla Nodes.  
         [0088]     More specifically, replace K C   mod  by a QB net K Q  obtained as follows. For each node of K C   mod , except for the marginalizer nodes that were added in the previous step, replace its node matrix by a new node matrix which is a q-embedding of the original node matrix. Add a new node for each ancilla index of each new node matrix. These new nodes will be called ancilla nodes (of either the source or sink kind) because they correspond to ancilla indices.  
         [0089]     Applying Step 2 to net K C   mod  for two body scattering yields K Q  defined by the graph shown in  FIG. 5  and the table of node amplitudes shown in  FIG. 6 . Note that in  FIG. 5 , black circles denote all the marginalizer and ancilla nodes added in Steps 1 and 2, whereas white circles denote the original nodes of K C .  
         [0090]     K Q  looks much more complicated than K C , but it really isn&#39;t, since most of its node matrices are delta functions which quickly disappear when summing over node states.  
         [0091]     According to the table of  FIG. 6 , the probability amplitude for the external (aka leaf) nodes is given by the equation of  FIG. 7 , where we have summed over all internal (non-leaf) nodes. The equation of  FIG. 7  shows that the net K Q  that we constructed from the net K C  by following Steps 1 and 2 satisfies the definition Eq. (12) that we gave earlier for a q-embedding of K C . The probability distribution of the states of the external nodes of the QB net K Q  contains all the probabilistic information of the original CB net K C . Hurray! 
         [0092]     The q-embedding of a CB net, as defined by Eq. (12), is not unique. For example, we could have defined the graph of  FIG. 5  without the nodes â 3  and {circumflex over (b)} 3 . We chose to include such nodes for pedagogical reasons.  
         [0093]     As another example of q-embedding a CB net, consider the CB net (“lung-disease-diagnosis net”) defined by  FIG. 8 . The figure includes the net&#39;s graph and a table of its node probabilities. After applying Steps 1 and 2 to the CB net of  FIG. 8 , one obtains the QB net defined by the graph of  FIG. 9  and the table of  FIG. 10 .  
         [0094]     Next we will first present a CB net, call it K C , that describes voting. Then we will find a QB net K Q  that is a q-embedding of K C . In certain cases, the target states that we wish to detect have probabilities that are too small to be measurable by running K Q  on a quantum computer. However, we will show that sometimes one can construct a new QB net, call it K Q ′, that magnifies to measurable values the target probabilities that were unmeasurable using K Q  alone. We will refer to K Q ′ as Grover&#39;s Microscope for K Q , because K Q ′ is closely related to Grover&#39;s algorithm, and it magnifies some of the probabilities found with K Q .  
         [0095]     Suppose y∈Bool and {right arrow over (x)}=(x 0 , x 1 , . . . , x N     B     −1 )∈Bool N     B   . Let ƒ: Bool N     B   →Bool.  
         [0096]     We will say that ƒ is AND-like if ƒ({right arrow over (x)})=θ({right arrow over (x)}={right arrow over (x)} targ ) for some target vector {right arrow over (x)} targ ∈Bool N     B   . An AND-like ƒ maps all {right arrow over (x)} into zero except for {right arrow over (x)} targ  which it maps into one. Thus, |ƒ −1 (1)|=1. An example of an AND-like ƒ is the multiple AND gate ƒ({right arrow over (x)})=x 0           x 1            . . .          x N     B     −1 , which can also be expressed as ƒ({right arrow over (x)})=θ[{right arrow over (x)}=(1, 1, . . . , 1)].  
         [0097]     We will say that ƒ is OR-like if ƒ({right arrow over (x)})=θ({right arrow over (x)}≠{right arrow over (x)} targ ) for some target vector {right arrow over (x)} targ ∈Bool N     B   . An OR-like ƒ maps all {right arrow over (x)} into one except for {right arrow over (x)} targ  which it maps into zero. Thus, |ƒ −1 (0)|=1. An example of an OR-like ƒ is the multiple OR gate ƒ({right arrow over (x)})=x 0           x 1            . . .          x N     B     −1 , which can also be expressed as ƒ({right arrow over (x)})=θ[{right arrow over (x)}≠(0, 0, . . . , 0)].  
         [0098]     We will say that ƒ has a single target if it is either AND-like or OR-like. If ƒ has more than one target (i.e., if |ƒ −1 (0)| and |ƒ −1 (1)|are both greater than one), then we will say that ƒ has multiple targets.  
         [0099]     Suppose y∈Bool and {right arrow over (x)}=(x 0 , x 1 , . . . , x N     B     −1 )∈Bool N     B   . Consider the CB net (“voting net”) defined by  FIG. 11 .  
         [0100]     Henceforth, we will abbreviate P(y=0|{right arrow over (x)})=p i  and P(y=1|{right arrow over (x)})=q i , where i=dec({right arrow over (x)})∈Z 0,N     S     −1 . Hence p i +q i =1 for all i∈Z 0,N     S     −1 . In general, the probability matrix P(y|{right arrow over (x)}) has 2 N     B    free parameters (namely, p i  for all i∈Z 0,N     S     −1 ). This number of parameters is forbiddingly large for large N B . To ease the task of specifying P(y|{right arrow over (x)}), it is common to impose additional constraints on P(y|{right arrow over (x)}). An interesting special type of P(y|{right arrow over (x)}) is deterministic pd(Bool|BOOl N     B   ) matrices; that is, those that can be expressed in the form 
 
 P ( y|{right arrow over (x)})=δ(   y , ƒ( {right arrow over (x)} )),  (18) 
 
 where ƒ: Bool N     B   →Bool. In this case, the voting net can be used to pose the satisfiability problem (SAT): given y=0, find the most likely {right arrow over (x)}∈Bool N     B   ; in other words, find those {right arrow over (x)} for which ƒ({right arrow over (x)})=0. If ƒ is OR-like then all p i  equal zero except for one p i  which equals one. For example, for N B =2, if ƒ is an OR gate, then  
                   P   ⁢     (     ⁢   y     ❘       x   -&gt;     ⁢       )     OR         =     (         1       0       0       0           0       1       1       1         )       ,           (   19   )             
 
 where the row indices are y=0, 1 and the column indices are {right arrow over (x)}=00, 01, 10, 11 in that order. A slightly more general type of P(y|{right arrow over (x)}) is quasi-deterministic pd(Bool|Bool N     B   ) matrices; that is, those that can be expressed in the form  
                   P   ⁢     (     ⁢   y     ❘       x   -&gt;     ⁢     )         =       ∑     t   -&gt;       ⁢     δ   ⁢     (     ⁢   y         ,     f   ⁢     (     ⁢     t   -&gt;     ⁢     )     ⁢     )     ⁢     P   ⁡     (       t   0     ❘     x   0       )       ⁢     P   ⁡     (       t   1     ❘     x   1       )       ⁢           ⁢   …   ⁢           ⁢     P   ⁡     (       t       N   B     -   1       ❘     x       N   B     -   1         )         ,           (   20   )             
 
 where ƒ: Bool N     B   →Bool and we sum over all to {right arrow over (t)}=(t 0 , t 1 , . . . , t N     B     −1 ) Bool N     B   . When ƒ({right arrow over (t)})=t 0           t 1            . . .          t N     B     −1 , P(y|{right arrow over (x)}) is called a noisy-OR. TucV2 discusses how to q-embed deterministic and quasi-deterministic pd(Bool|BOOl N     B   ) matrices, and how to express their q-embeddings as a SEO. 
 
         [0101]     A q-embedding for the CB net defined by  FIG. 11  is given by the QB net defined by  FIG. 12 .  
         [0102]     According to table 122 of  FIG. 12 , the probability amplitude for the external (leaf) nodes is given by equation 123 of  FIG. 12 .  
         [0103]     To fully specify the QB net for voting, we need to extend A({right arrow over (x)} 2 |{right arrow over (x)} 1 =0) and A({right arrow over (x)} 3 , y 2 |{right arrow over (x)} 2 , y 1 =0) into unitary matrices by adding columns to them. This can always be accomplished by applying the Gram-Schmidt algorithm. But sometimes one can guess a matrix extension, and this makes application of the Gram-Schmidt method unnecessary. If P({right arrow over (x)}) is uniform (i.e., P({right arrow over (x)})=1/N S  for all {right arrow over (x)}, which means there is no a priori information about {right arrow over (x)}), then A({right arrow over (x)} 2 |{right arrow over (x)} 1 =0)=1/{square root}{square root over (N S )}. In this case, we can extend A({right arrow over (x)} 2 |{right arrow over (x)} 1 =0) into the N B  bit Hadamard matrix H N     B   : 
 
[ A ( {right arrow over (x)}   2   |{right arrow over (x)}   1 )]=H N     B     /{square root}{square root over (N     S     )}.   (21) 
 
 (This works because all entries of the first column of H N     B    are equal to 1.) As to extending A({right arrow over (x)} 3 , y 2 |{right arrow over (x)} 2 , y 1 =0), this can be done as follows. Define 
 
Δ p   =diag ({square root}{square root over ( p   0 )}, {square root}{square root over ( p   1 )}, . . . , {square root}{square root over ( p   N     S     −1 )}),  (22) 
 
and 
 
Δ q   =diag ({square root}{square root over ( q   0 )}, {square root}{square root over ( q   1 )}, . . . , {square root}{square root over ( q   N     S     −1 )}).  (23) 
 
 A possible way of extending A({right arrow over (x)} 3 , y 2 |{right arrow over (x)} 2 , y 1 =0) into a unitary matrix is  
               [       A   ⁢     (     ⁢       x   -&gt;     3       ,       y   2     ❘       x   -&gt;     2       ,       y   1     ⁢     )         ]     =       (           Δ   p           -     Δ   q                 Δ   q           Δ   p           )     .             (   24   )             
 
 Unitary matrices of this kind are called D-matrices in QbtrPat. QbtrPat shows how to decompose any D-matrix into a SEO. 
 
         [0104]     Next we will discuss Grover&#39;s Microscope for the voting QB net defined by  FIG. 12 . For simplicity, we will assume that P({right arrow over (x)}) is uniform.  
         [0105]     Let is {right arrow over (κ)}=(κ 0 , κ 1 , . . . , κ N     B     −1 ) label N B  bits and let τ label another bit. Assume that τ and all the κ i  are distinct. Define 
 
φ p =({square root}{square root over ( p   0 )}, {square root}{square root over ( p   1 )}, . . . , {square root}{square root over ( p   N     S     −1 )}) T ,  (25) 
 
φ q =({square root}{square root over ( q   0 )}, {square root}{square root over ( q   1 )}, . . . {square root}{square root over ( q   N     S     −1 )}) T ,  (26) 
 
 and  
                 ❘   Ψ     〉     =     Ψ   =       1       N   S         ⁢       (           ϕ   p               ϕ   q           )     .                 (   27   )             
 
 Since p i +q i =1 for all i, φ p   T φ p +φ p   T φ q =N S . According to equation 123 of  FIG. 12 , when P({right arrow over (x)}) is uniform, the voting QB net fully specifies a unitary matrix U net  such that 
 
|Ψ         = U   net |0           {right arrow over (κ)} |0           τ .  (28) 
 
 (The last equation is an example of Eq. (9).) 
 
         [0106]     Define orthonormal vectors e 0  and e 1  by  
                 e   0     =     (             ϕ   p     /          ϕ   p                    0         )       ,           ⁢       e   1     =       (         0               ϕ   q     /          ϕ   q                  )     .               (   29   )             
 
 If P(y|{right arrow over (x)}) is deterministic with OR-like ƒ, then all components of e 0  are zero except for the one at the target state j targ . 
 
         [0107]     Ψ can be expressed in terms of e 0 , e 1  as  
             Ψ   =       1       N   S         ⁢       (              ϕ   p          ⁢     e   0       +            ϕ   q          ⁢     e   1         )     .               (   30   )             
 
 It is convenient to define a vector Ψ ⊥  orthogonal to Ψ:  
               Ψ   ⊥     =       1       N   S         ⁢       (              ϕ   q          ⁢     e   0       -            ϕ   p          ⁢     e   1         )     .               (   31   )             
 
 If P(y|{right arrow over (x)}) is deterministic with OR-like ƒ, then |φ p |=1 and |φ q |={square root}{square root over (N S −1)}so, for large N S , Ψ≈e 1  and Ψ ⊥ ≈e 0 . For an arbitrary angle α, let  
                 Ψ   ⊥   ′     =       1       N   S         ⁡     [         (         c     α   2       ⁢          ϕ   q            +       s     α   2       ⁢          ϕ   p              )     ⁢     e   0       +       (         s     α   2       ⁢          ϕ   q            -       c     α   2       ⁢          ϕ   p              )     ⁢     e   1         ]         ,           (   32   )             
 
 where s A =sin A and c A =cos A for any angle A. Note that the angle between Ψ′ ⊥  and Ψ ⊥  is α/2. Also, the angle between e 1  and Ψ is θ/2. 
 
         [0108]      FIG. 13  portrays various vectors that arise in explaining Grover&#39;s Microscope. Note that Ψ′ ⊥ =e 0  when α=θ.  
         [0109]     Since we plan to stay within the two dimensional vector space with orthonormal basis e 0 , e 1 , it is convenient to switch matrix representations. Within span(e 0 , e 1 ), e 0 , e 1  can be represented more simply by:  
                 e   0     =     (         1           0         )       ,           ⁢       e   1     =       (         0           1         )     .               (   33   )             
 
 If e 0 , e 1  are represented in this way, then  
               Ψ   =       1       N   S         ⁢     (                ϕ   p                         ϕ   q                )         ,           (   34   )                   Ψ   ⊥     =       1       N   S         ⁢     (                  ϕ   q          ⁢                     -          ϕ   p            ⁢               )         ,           (   35   )             
 
 and 
 
Ψ′ ⊥   =WΨ,   (36) 
 
 where  
             W   =       (           c     α   2             -     s     α   2                   s     α   2             c     α   2             )     ⁢       (           0   ⁢             1               -   1     ⁢             0         )     .               (   37   )             
 
 The matrix  
         (           0   ⁢             1               -   1     ⁢             0         )             
 
 is a clockwise rotation by π/2 in space span(e 0 , e 1 ). Thus, W equals a clockwise rotation by π/2 followed by a counter-clockwise rotation by α/2. 
 
         [0110]     Define the following reflection operators 
 
 R   0 =1−2Π |0     {right arrow over (κ)}   Π |0     τ   ,  (38) 
 
 R   Ψ   =U   net   R   0   U   net   † ,  (39) 
 
 R   Ψ′     ⊥     =WR   Ψ   W   † .  (40) 
 
 It follows that 
 
− R   Ψ   R   Ψ′     ⊥     =c   α ΨΨ T   −s   α ΨΨ ⊥   T   +s   α Ψ ⊥ Ψ T   +c   α Ψ ⊥ Ψ ⊥   T .  (41) 
 
 Thus, −R Ψ R Ψ′     ⊥    rotates vectors in span(e 0 , e 1 ), clockwise by an angle α. 
 
         [0111]     Grover&#39;s Microscope can be summarized by the following equation 
 
(− R   105    R   Ψ′     ⊥   ) r Ψ≈e 0 ,  (42) 
 
 for some integer r to be determined, where “≈” means approximation at large N S . What this means is that our system starts in state Ψ and is rotated consecutively r times, each time by a small angle α, until it arrives at the state e 0 . If P(y|{right arrow over (x)}) is deterministic with OR-like ƒ, then measuring state e 0  yields the target state j targ . 
 
         [0112]     The optimum number r of iterations is  
               r   ⁢           ⁢   α     ≈       π   2     ⁢     (     1   +     2   ⁢   k       )               (   43   )             
 
 for some integer k. Note that cos(θ/2)=         Ψ|e 1           =|φ q |/{square root}{square root over (N S )}. Hence, in general, θ depends on |φ p | (or on |φ q |={square root}{square root over (N S −|φ p | 2 )}). If P(y|{right arrow over (x)}) is deterministic with OR-like ƒ, then |φ p |=1 and |φ q |={square root}{square root over (N S −1)}. In this case, it is convenient to choose α=θ, so that Ψ′ ⊥ =e 0 . Then the optimum number r of iterations for Grover&#39;s original algorithm and for Grover&#39;s Microscope are equal. If we don&#39;t know ahead of time the value of |φ p |, then setting θ=α will make both r and α depend on the unknown |φ p |, although the product rα will still be independent of it. 
 
         [0113]     Let  
                     U   Gscope     =     (         0       1             -   1         0         )                 =         -     e   1       ⁢     e   0   T       +       e   0     ⁢     e   1   T                     =       -     ψψ   ⊥   T       +       ψ   ⊥     ⁢       ψ   T     .                       (   44   )             
 
 Note that 
 
 U   Gscope Ψ=Ψ ⊥ .  (45) 
 
 From the point of view of quantum compiling, Grover&#39;s Microscope approximates the π/2 rotation U Gscope  by the r-fold product of −R Ψ R Ψ′     ⊥   , where we assume that −R Ψ R Ψ′     ⊥    can be shown to have a SEO of low (polynomial in N B ) complexity. (If such a low complexity SEO cannot be found, then it is pointless to divide U Gscope  into r iterations of −R Ψ R Ψ′     ⊥   , and we might be better off compiling U Gscope  all at once.) 
 
 (B) Computer Implementation of Theory 
 
         [0114]     In Section (A), we described a mathematical algorithm for q-embedding any CB net within a QB net. Next we describe a particular implementation of this algorithm, a computer program called Q-Embedder that can be run on a classical computer.  
         [0115]     To understand the input and output data of Q-Embedder, one must first understand the convention Q-Embedder uses for specifying CB and QB nets. Q-Embedder uses two text files to specify a QB net. An example is shown in  FIG. 14 . In this figure, boxes  140  and  145  each represents a text file.  
         [0116]     From text file  140  we learn that the QB net has 3 nodes called A, B and X. We also learn the possible states of each node. For example, node A has two possible states, a1 and a2. The hash symbol in line  141  indicates that a new node will follow. Line  142  names the node A being considered. Lines  143  list the two possible states, a1, a2, of A.  
         [0117]     From text file  145 , we learn that nodes A, B, X are connected by two arrows: (1) from A to X, (2) from B to X. We also learn the node matrix for each of the nodes. For example, we learn that node A is a root node, and the amplitudes of its two states a1 and a2 are, respectively, 0.707+0i and 0+0.707i. Node X has four parent states: (B, A)=(b1, a1), (b2, a1), (b1, a2) and (b2, a2). For the parent state (B, A)=(b1, a1), the amplitudes of the two states x1 and x2 of X are, respectively, 1+0i and 0+0i. The hash symbol in line  146  indicates that a new parent state will follow. Line  147  names the node X being considered. Lines  148  give the parent state (B, A)=(b1, a1). Lines  149  give the amplitude of the states x1, x2.  
         [0118]     There are many equivalent ways of specifying a QB net. In earlier examples, we specified a QB net by giving a graph (diagram) and a table specifying the amplitudes for each node. On the other hand, Q-Embedder specifies QB nets by means of two text files exemplified by  FIG. 14 .  
         [0119]     To specify a CB net instead of a QB net, Q-Embedder also uses two text files, almost identical to those exemplified by  FIG. 14 . The only difference is that wherever QB net files list two real numbers separated by white space to represent a complex number (a node amplitude), CB net files list a single real number, from the interval [0,1], to represent a probability.  
         [0120]     Now that we understand how Q-Embedder specifies CB nets and QB nets, it is easy to describe the input and output data for Q-Embedder. Q-Embedder takes as input two text files that specify a CB net K C , and it returns as output two text files that specify a QB net K Q  that is a q-embedding of K C . For example, if the two input text files specify the CB net defined by  FIG. 3 , then the two output text files will specify that QB net defined by  FIG. 5  and  FIG. 6 .  
         [0121]     We will not present source code for Q-Embedder in this patent. Those skilled in the art of programming will find it a straightforward exercise to write a computer program like Q-Embedder that performs Steps 1 and 2. These steps were carefully described and illustrated with two detailed examples, two body scattering and lung disease diagnosis.  
         [0122]     Next we will discuss how to combine Q-Embedder, Qubiter, and a quantum computer.  
         [0123]     QbtrPat proposes a computer program for translating a QB net into an equivalent SEO. QbtrPat gives source code for a computer program called Qubiter-1.0 that can accomplish such translations partially, for two node QB nets. Then QbtrPat gives careful instructions on how to augment Qubiter-1.0 so that it can translate any QB net. Assume henceforth a computer program called Qubiter that can translate any QB net into a SEO.  
         [0124]     Q-Embedder can be used in tandem with Qubiter. In such a configuration, Q-Embedder takes as input 2 text that specify a CB net, and it returns as output 2 text files that specify a QB net. Then Qubiter takes as input the 2 output files of Q-Embedder, and it returns as output an equivalent SEO.  
         [0125]     Note that it may suffice to find a SEO that is only approximately (within a certain precision) equivalent instead of exactly equivalent to the QB net. This may be true if, for example, the probabilities associated with the CB net that was q-embedded were not specified too precisely to begin with.  
         [0126]     A classical computer running Q-Embedder and Qubiter in tandem can feed the SEO produced by Qubiter to a quantum computer.  
         [0127]      FIG. 15  is a block diagram of a classical computer feeding data to a quantum computer. Box  150  represents a classical computer. It comprises sub-boxes  151 ,  152 ,  153 . Box  151  represents input devices, such as a mouse or a keyboard. Box  152  represents the CPU, internal and external memory units. Box  152  does calculations and stores information. Box  153  represents output devices, such as a printer or a display screen. The graph (e.g.,  FIG. 3 ) of a CB net, or the graph (e.g.,  FIG. 5 ) of a QB net, can be rendered on the display screen. Box  155  represents a quantum computer, comprising an array of quantum bits and some hardware for manipulating the state of those bits. For more information about the organization of a present day classical computer, see CPP: J. Adams, S. Leestma, L. Nyhoff, “C++, an Introduction to Computing”, (Prentice Hall, 1995) pages 19-20.  
         [0128]     Next we describe how to calculate probabilities with a quantum computer. Consider the example of the CB net K C  given by  FIG. 3  and its q-embedding, the QB net K Q  given by  FIG. 5  and  FIG. 6 . From the equation of  FIG. 7 , it is clear that by running K Q  on a quantum computer, we can calculate any conditional probability that one would want to calculate for K C . For example, suppose we wanted to calculate P â,{circumflex over (d)}|{circumflex over (x)} . Run K Q  on the quantum computer several times, each time measuring nodes â 5 , {circumflex over (d)} 3  and {circumflex over (x)} 5d  and not measuring all other external nodes. The resulting measurements will be distributed according to the probability distribution P â,{circumflex over (d)},{circumflex over (x)} . Nature will automatically take the magnitude squared of the amplitude A(a 5 , b 5 , c 3 , d 3 , x 5c , x 5d ) and sum the result over the states of the un-measured external nodes. The laws of quantum mechanics guarantee it. Proceed in the same way to calculate P {circumflex over (x)} . Run K Q  on the quantum computer several times, each time measuring node {circumflex over (x)} 5d  and not measuring all other external nodes. Finally divide P â,{circumflex over (d)},{circumflex over (x)}  by P {circumflex over (x)}  on a classical (or quantum) computer. This procedure works if we assign an integer number of qubits to each external node of K Q , and if different external nodes are assigned different qubits. This way, when we say that we measured or did not measure an external node, we mean that we measured or did not measure the qubits assigned to that node. To implement this idea, it is convenient to extend the set of possible states of each node of K C  so that the cardinality of the extended set equals a power of two. For example, for the CB net of  FIG. 3 , let N â =|S â|. Then let  
 
 {overscore (N)}   â =min{2 n   : n∈Z   0,∞ , N â ≦2 n }.  (46) 
 
 We extend S â  to a larger set {overscore (S)} â  which contains S â  and has |{overscore (S)} â |={overscore (N)} â . We also define P(a)=0 for a∈{overscore (S)} â −S â . In an analogous way, we extend S {circumflex over (b)} , S {circumflex over (x)} , S ĉ  and S {circumflex over (d)}  so that each has a cardinality which is a power of two. We also extend the functions P(b), P(x|a, b), P(c|x) and P(d|x) so that they take the same values on the old elements of the domain and vanish on the new ones. 
 
         [0129]     Suppose samples a 1 , a 2 , . . . a ν , belong to a finite set S â , and suppose that they are distributed according to a probability distribution P â . What number ν of samples a i  is necessary to estimate P â  within a given precision? This question is directly relevant to our method for estimating probabilities by running a QB net on a quantum computer. We will not give a detailed answer to this question here. For an answer, the reader can consult any book on the mathematical theory of Statistics. An imprecise rule of thumb is that if the support of P â  has ν 0  elements, then ν should be at least as large as ν 0 ; i.e., one needs at least “one data point per bin” to estimate P â  with any decent accuracy.  
         [0130]     We&#39;ve explained how to estimate a conditional probability for a CB net by running a QB net ν times on a quantum computer. If we wanted to find P(y|x 0 , x 1 ) for the voting CB net, then the number of runs ν required to estimate P(y|x 0 , x 1 ) with moderate accuracy would not be too onerous, because the domain of P(y|x 0 , x 1 ) is Bool 3 , which contains only 8 points. But what if we wanted to estimate P(y|{right arrow over (x)})? For large N B , the domain of P(y|{right arrow over (x)}) is very large (2 N     B     +1  points). If the support of P(y|{right arrow over (x)}) occupies a large fraction of this domain, then the number of runs ν required to estimate P(y|{right arrow over (x)}) with moderate accuracy is forbiddingly large. However, there are some cases in which “Grover&#39;s Microscope” can come to the rescue, by allowing us to amplify certain salient features of P(y|{right arrow over (x)}) so that they become measurable in only a few runs.  
         [0131]     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.