Abstract:
A virtual parallel computing system and method represents bits with matrices and computes over all input states in parallel through a sequence of matrix operations. The matrix operations relate to logic gate operators to carry out a function implementation that represents a problem to be solved. Initial matrices are prepared to encode the weights of all input states, which can be binary states. Intermediate results can be simplified to decrease computational complexity while maintaining useful approximation results. The final matrices can encode the answer(s) to the problem represented by the function implementation. The system and method are particularly useful in speeding up database searches and in counting solutions of satisfiability problems.

Description:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     This invention was made with Government Support under Contract Numbers CCF-1116590 and CCF-1117241 awarded by the National Science Foundation. The Government has certain rights in the invention. 
    
    
     BACKGROUND 
     The present disclosure relates generally to computational systems and methods, and relates more particularly to the encoding of information in matrices and to computational techniques involving matrix manipulations. 
     Interference and the ability to follow many history paths simultaneously make quantum systems attractive for implementing computations, such as may be possible with quantum computers. Efficient algorithms exploring these properties have been proposed to solve practical problems such as number factoring and unsorted database searches. These algorithms have a number of advantages compared to classically implemented algorithms, especially when quantum computers with thousands of quantum bits become available. Despite recent progress in developing quantum mechanics systems capable of processing information, the number of available quantum bits is somewhat small, e.g., in the tens of bits, making the implementation of a useful quantum computer problematic. Accordingly, a sufficiently large and resilient quantum computer that can take advantage of the above-mentioned algorithms is not yet available. 
     Hard computational problems are those in which the solution expressed as a number of computational steps scales faster than a power of the size of the input data, e.g. ˜O(2 n     q   ). In attempting to find better and more efficient ways to solve hard problems with conventional computers, recent advances in the study of quantum many-body systems provide some guidance. For example, the time evolution of a large class of one-dimensional interacting systems can be efficiently simulated by expressing their wave functions in a matrix product state (MPS) form and by using a time-evolving block decimation (TEBD). Even though many-body interactions tend to increase the rank of the matrices over time, it is possible to use truncation along the evolution to keep the matrices relatively small, such that the resulting wave function approximates quite accurately the exact one without an exponential computation cost. In quantum systems, local interactions do not quickly entangle a one-dimensional many-body state, justifying the matrix truncation. The evaluation of classical probability distributions in the form of an MPS has also been performed in the context of non-equilibrium phenomena of physical systems. 
     SUMMARY 
     In accordance with the present disclosure, a system and a method of computation that utilizes MPS to solve hard computational problems are provided. In particular, the present disclosure can provide computations to organize data to permit solutions to hard computational problems to be obtained through simplified operations involving matrices. When hard computational problems can be mapped onto a search problem, the present disclosure is suitable for obtaining solutions for such search problems. The proposed system and method describe configuration states in terms of weights or a probability distribution written as traces of matrix product states associated with bit configurations. Inputs to a function describing a problem to be solved are provided as one or more matrices, which are manipulated by the implementation of the function to produce MPS&#39;s that contribute to locating solutions to the problem. 
     According to an aspect of the disclosure, an MPS formulation of classical probability distributions is employed to create a virtual parallel machine where all possible outcomes of an algorithm are obtained from all 2 n  inputs of an n-bit register. Information about these outcomes is encoded and compressed in the matrices forming the MPS. This parallelism is useful when a certain problem can use the probability of a single outcome at a time. For example, a search problem that seeks, for a given y, the value of x such that y=ƒ(x) for an algorithmically computable function ƒ can employ parallelism using the probability of the given y. In this case, the focus is not on all values of the output, but on only one corresponding to a given y. In addition, from the probability of y, the method in this invention directly provides the number of input values x satisfying the functional constraint y=ƒ(x). 
     According to an aspect of the present disclosure, there can be parallelism between the steps of the method and those of a logic circuit. Insertion and removal of matrices correspond to insertion and removal of bits in a bit register. Proposed 1-bit and 2-bit gates have matrix operations counterparts. The operations of 2-bit gates rely on a singular value decomposition (SVD) to maintain the MPS form of the probability distribution. Matrices are not restricted to be positive. All these operations preserve the positivity and the overall normalization of the probability. Matrix operations also provide the benefit of permitting direct computation on compressed data, whereby calculations ordinarily performed on uncompressed data, with the attendant compression and decompression processes, can be avoided, thereby leading to greater efficiencies. 
     As an example of a hard computational problem to which the disclosed system and method may be applied, consider the problem of checking which gene combination produces a certain specific feature (e.g., a trait or a genetic disorder). If you have n of these genes, there are 2 n  combinations of having or not having each of the n genes. Checking combinations one-by-one is not feasible if n is very large. Let ƒ(x) be a function that, given a certain gene combination gives you 1 if the combination has the desired feature and gives you 0 otherwise. In this particular application, you would use a software (i.e., a compiler) to transform ƒ(x) into a sequence of gates acting on the binary variables that enumerate x. In practice, these gates are basically a set of instructions for operating on matrices (e.g., at least 2n matrices). The matrices are stored in the computer&#39;s RAM. The method disclosed in this application uses the computer&#39;s processor to manipulate these matrices and find gene combinations with the specific feature. 
     The presently disclosed system and method is applied to evaluating a multivariable Boolean expression for satisfiability, or obtaining and counting the instances satisfying the expression. The application of the disclosure to bit states is unique in the field of computational efforts, unlike known applications for many-body wave functions. The disclosed system and method is also applied to a database search algorithm. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS 
       The present disclosure is described in greater detail below, with reference to the accompanying drawings, in which: 
         FIG. 1  is a block diagram of a computer system capable of implementing the disclosed system and method; 
         FIG. 2  is a block diagram that illustrates matrix operation procedures involved in determining the probability of a certain outcome of a multi-component logic function y=ƒ(x) in accordance with an exemplary embodiment of the present disclosure; 
         FIG. 3  is a block diagram that illustrates a 1-bit matrix operation; 
         FIG. 4  is a block diagram that illustrates a 2-bit matrix operation; and 
         FIG. 5  is a flowchart of an exemplary embodiment of the disclosed system and method for implementing a data base search. 
     
    
    
     DETAILED DESCRIPTION 
     In accordance with the present disclosure, computer operations are performed using matrix product states (MPS) in the realization of a function describing a problem to be solved, and an input to the function. One or more matrices can be used to represent all inputs at once, thereby utilizing parallelism in the computational process. The input matrices are initialized and the matrices evolve according to an applied function. The function itself can be realized using one bit and two bit gates, where the one bit gates are probabilistic gates, and the two bit gates are deterministic gates. 
       FIG. 1  shows a computer system  100  capable of implementing an exemplary embodiment of the system and method of the present disclosure. Matrices used in the disclosed computations can be stored in RAM  102 , while the computer code that can be executed by a CPU  106  to carry out the computations can be stored in memory  104 . 
     Referring now to  FIG. 2 , a block diagram of a system  200  according to an exemplary embodiment of the present disclosure is illustrated. According to an exemplary embodiment, system  200  can be implemented on computer system  100  ( FIG. 1 ). In accordance with system  200 , consider a set of n binary variables {x j =0, 1} j=1, . . . , n  (henceforth named bits), with the vector |x 1 x 2  . . . x n             ≡|x          denoting a particular configuration of this system. Define the vector
                          P   〉     =       ∑       x   n     ,   …   ⁢           ,       x   1     =   0     ,   1       ⁢       P   ⁡     (       x   1     ,   …   ⁢           ,     x   n       )       ⁢            x   1     ⁢           ⁢   …   ⁢           ⁢     x   n       〉           ,           (   1   )               
where the probability of a configuration |x           
 
 P ( x   1   , . . . , x   n )= tr ( M   1   x     1      . . . M   n   x     n   ).  (2)
 
Here, each M j   x     j    is a real matrix of dimensions D j−1 ×D j  representing a bit j with a state x j . The trace can be dropped if we consider the first and last matrices to be row and column vectors, i.e., D 0 =D n =1. The vector |P          is normalized in the following sense: define a vector |Σ         =Σ x     1     , . . . , x     n     =0, 1 |x 1  . . . x n           , then a normalization constant Z=         Σ|P         =1 since Σ x P(x)=1. Consider the bits laid orderly along a straight line, referred to as the bit string. The matrix dimension D j  is referred to as the bond dimension between adjacent bits j and j+1.

     Starting from an initial probability distribution P 0 (x 1 , . . . , x n ) the vector |P            evolves as a sequence of 1-bit and 2-bit operations on adjacent bits is applied to the matrices M j   x     j   . These operations follow a Boolean function ƒ(x), analogous to a logic circuit, which is designed according to the particular computational problem of interest. It has been shown that, for a Boolean function ƒ(x), the function can be completely realized using a sequence of 1-bit and 2-bit gates. Bit operations are implemented on the matrices as follows.
     1-Bit Gates: 
     A probabilistic 1-bit gate takes states 0, 1 into states 0, 1 with probabilities p,1−p and q, 1−q: 
             0   ⁢     ⟶   p     ⁢   0             or             0   ⁢     ⟶     1   -   p       ⁢   1               1   ⁢     ⟶     1   -   q       ⁢   0             or             1   ⁢     ⟶   q     ⁢   1.         
The probabilities p and q are encoded into a transfer function t ũ, u  that takes a logic input a=0, 1 into a logic output ã=0, 1. Explicitly: t 0, 0 =p, t 1, 0 =1−p, t 0, 1 =1−q, t 1, 1 =q.  FIG. 3  illustrates a 1-bit gate acting on the matrices corresponding to bit j, namely, M j   x     j   , which yields new matrices according to the expression
 
                       M   ~     j     x   j       =       ∑         x   j   ′     =   0     ,   1       ⁢       t       x   j     ,     x   j   ′         ⁢       M   j     x   j   ′       .                 (   3   )               
The transfer function t x     j     , x′     j    satisfies the sum rule Σ ã=0.1 t ã, a =1, which ensures that the normalization Z=1 is maintained along the computation. Examples of 1-bit gates are: (a) Deterministic NOT, with p=0 and q=0, (b) RAND, with p=½ and q=½, which randomizes the bit, (c) RST, with p=1 and q=0, which resets the bit to 0. 1-bit gates preserve matrix dimensions, for example by carrying the input to the output, in conjunction with providing the processed output.
 
     2-Bit Gates: 
     Given two logical functions A(a, b) and B(a, b), we construct the deterministic 2-bit transfer function T ã, {tilde over (b)}; a, b  in the following way: 
                     T       a   ~     ,       b   ~     ;   a     ,   b       =     {           1   ,               a   ~     =         A   ⁡     (     a   ,   b     )       ⁢   and   ⁢           ⁢     b   ~       =     B   ⁡     (     a   ,   b     )           ,               0   ,           otherwise   .                     (   4   )               
This transfer function takes bits from states a and b to states ã and {tilde over (b)}, respectively. Similarly to 1-bit gates, the normalization after 2-bit gates is preserved since the transfer matrix satisfies the sum rule Σ ã, {tilde over (b)}=0.1 T ã, {tilde over (b)}; a, b =1. A 2-bit gate acting on adjacent bits j−1 and j takes their matrix product M j−1   x     j−1    M j   x     j    into a larger single matrix according to the expression
 
                     Q       j   -   1     ,   j         x     j   -   1       ,     x   j         =       ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T         x     j   -   1       ⁢     x   j       ,     x     j   -   1     ′     ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢       M   j     x   j   ′       .                 (   5   )               
While the input matrices M j−1   x     j−1    and M j   x     j    have D j−2 ×D j−1  and D j− ×D j  matrix elements, respectively, the resulting matrix Q j−1, j  has a total of 2D j−2 ×2D j  matrix elements. In order to bring the result of Eq. (5) back to a matrix product form, a singular value decomposition (SVD) of the matrix Q j−1, j   x     j−1′     x     j    is performed. For this purpose, the matrix is organized in the following block form:
 
                     Q       j   -   1     ,   j       =       (             ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T     0   ,     0   ;     x     j   -   1     ′       ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢     M   j     x   j   ′                   ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T     0   ,     1   ;     x     j   -   1     ′       ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢     M   j     x   j   ′                       ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T     1   ,     0   ;     x     j   -   1     ′       ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢     M   j     x   j   ′                   ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T     1   ,     1   ;     x     j   -   1     ′       ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢     M   j     x   j   ′                 )     .             (   6   )               
The singular value decomposition can be carried out using standard linear algebra techniques. After the decomposition, Q j−1, j =UΛV, where U and V are orthogonal matrices of dimensions 2D j−2 ×2D j−2  and 2D j ×2D j , respectively, and Λ is a diagonal rectangular matrix of dimensions 2D j−2 ×2D j  containing the singular values. More explicitly, Λ αα =λ α &gt;0, where a=1, . . . , r, with r≦min(2D j−2 , 2D j ), and Λ αβ =0 for α≠β. Here, r denotes the rank of the matrix Q j−1, j .
 
     The resulting matrices for the bits j−1 and j are obtained through the expressions
 
[{tilde over ( M )} j−1   0 ] αβ   =[U]   αβ √{square root over (λ β )}, α1, . . . ,  D   j−2 , β=1, . . . ,  r   (7)
 
[ {tilde over (M)}   j−1   1 ] αβ   =[U]   αβ √{square root over (λ β )}, α=D j−2 +1, . . . , 2D j−2 , β=1, . . . ,  r   (8)
 
[{tilde over ( M )} j   0 ] αβ =√{square root over (λ α )}[V] αβ , α=1, . . . ,  r, β= 1, . . . ,  D   j   (9)
 
[{tilde over ( M )} j   1 ] αβ =√{square root over (λ α )}[V] αβ, α= 1, . . . ,  r, β=D   j +1, . . . , 2 D   j .  (10)
 
Using these matrices, Eq. (5) can be rewritten as
 
                         M   ~       j   -   1       x     j   -   1         ⁢       M   ~     j     x   j         =       ∑       x     j   -   1     ′     ,       x   j   ′     =   0     ,   1       ⁢       T       x     j   -   1       ,       x   j     ;     x     j   -   1     ′       ,     x   j   ′         ⁢     M     j   -   1       x     j   -   1     ′       ⁢       M   j     x   j   ′       .                 (   11   )               
These are the resulting matrices illustrated in  FIG. 4  following the 2-bit gate operation. One consequence of the 2-bit gate operation is a change in the bond dimension between bits j−1 and j, namely, D j−1 , becomes {tilde over (D)} j−1 =r. The other matrix dimensions remain unchanged.
 
     Below, block forms of the matrix Q j−1, j  for five common 2-bit gates used in applications of the invention are presented: AND, NAND, OR, XOR, SWAP, and COPY. For logic operations, the first bit carries forward its state, while the result of the operation is stored in the second bit. 
     AND gate: A AND (a, b)=a and B AND (a, b)=a           b. In this case, T 0, 0; 0, 0 =T 0, 0; 0, 1 T 1, 1; 1, 1 =1, with all other elements set to zero.
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     AND 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                               + 
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   1 
                                 
                               
                             
                           
                           
                             0 
                           
                         
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     NAND gate: A NAND (a, b)=a and B NAND (a, b)=           (a         b). In this case, T 0, 1; 0, 0 =T 0, 1; 0, 1 =T 1, 1; 1, 0 =T 1, 0; 1, 1 =1, with all other elements set to zero.
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     AND 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             0 
                           
                           
                             
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                               + 
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   1 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
     OR gate: A OR (a, b)=a and B OR (a, b)=a           b. In this case, T 0, 0; 0, 0 =T 0, 1; 0, 1 =T 1, 1; 1, 0 T 1, 1; 1, 1 =1, with all other elements set to zero.
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     OR 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                         
                           
                             0 
                           
                           
                             
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                               + 
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   1 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     XOR gate: Λ XOR (a, b)=a and B XOR (a, b)=a⊕b. In this case, T 0, 0; 0, 0 =T 0, 1; 0, 1 =T 1, 1; 1, 0 =T 1, 0; 1, 1 =1, with all other elements set to zero. 
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     XOR 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
     SWAP gate: A SWAP =(a, b)=b and B SWAP (a, b)=a. In this case, T 0, 0; 0, 0 T 1, 0; 0, 1 =T 0, 1, 1, 0 =T 1, 1, 1, 1 =1, with all other elements set to zero. 
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     SWAP 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                         
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
           
         
       
     
     COPY gate: A COPY (a, b)=a and B COPY (a, b)=a. In this case, T 0, 0; 0, 0 =T 0, 0; 0, 1 =T 1, 1, 1, 0 =T 1, 1, 1, 1 =1, with all other elements set to zero. 
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     COPY 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                               + 
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   1 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                             
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   0 
                                 
                               
                               + 
                               
                                 
                                   M 
                                   
                                     j 
                                     - 
                                     1 
                                   
                                   0 
                                 
                                 ⁢ 
                                 
                                   M 
                                   j 
                                   1 
                                 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     IDENTITY gate: A IDENTITY (a, b)=a and B IDENTITY (a, b)=b. In this case, T 0, 0; 0, 0 =T 0, 1; 0, 1 =T 1, 0, 1, 0 =T 1, 1, 1, 1 =1, with all other elements set to zero. 
     
       
         
           
             
               
                 
                   
                     Q 
                     
                       
                         j 
                         - 
                         1 
                       
                       , 
                       j 
                     
                     IDENTIFY 
                   
                   = 
                   
                     
                       ( 
                       
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 0 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                         
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 0 
                               
                             
                           
                           
                             
                               
                                 M 
                                 
                                   j 
                                   - 
                                   1 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 M 
                                 j 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
     Filters: 
     Given a set of matrices defining a matrix product state, it is possible to filter out certain bit configurations by resorting to a sequence of 2-bit gates which do not preserve probability. These gates differ from those described earlier in the sense that their transfer matrices T ã, {tilde over (b)}; a, b  do not satisfy the sum rule Σ ã, {tilde over (b)}=0, 1 T ã, {tilde over (b)}; a, b =1. All other aspects, such as singular value decomposition, are the same as for the probability preserving 2-bit gates. Consider for example a situation where it is desired to remove all configurations where the bits j and j−1 are different, irrespective of the other bits, namely, configurations where x j =0, x j−1 =1 or x j =1, x j−1 =0. This operation can be implemented by a filter of the logic form (x j ⊕x j−1 ), which can be realized by a transfer matrix of the form T 0, 0; 0, 0 =T 1, 1; 1, 1 =1 and with all other elements set to zero. Given that two bits span 4 possible states (00, 01, 10, 11), there are 14 nontrivial 2-bit filter gates (out of 16): 4 that block 3 out of 4 possible states; 6 that block 2 out of 4 possible states; and 4 that block 1 out of the 4 possible states. The other filter gates, which may be considered trivial, are those that block all or block none of the 4 possible states. 
     Bit Insertions and Removals: Insertion of a new bit (say, initially set to 0) in between bits j−1 and j amounts to replacing M j−1   x     j−1   M j   x     j    with M j−1   x     j−1   M α   x     α   M j   x     j   , where M α   1  and M α   0  are D j−1 ×D j−1  null and identity matrices, respectively, and the total sum over bit configurations in the vector |P            [see Eq. (1)] now includes the binary variable x α =0, 1. Removal of a bit is done by absorbing its matrix into the one of an adjacent bit, namely, by tracing it out. For example, the operation expressed as Σ x     j     =0, 1 M j   x     j   M j+1   x     j+1   ={tilde over (M)} j+1   x     j+1    is used to remove bit j.
     Application: Search algorithm. 
     Consider the search problem where, given a function y=ƒ(x) that can be computed algorithmically with O(n d ) gates and a certain value for y, search for an input x that yields as output y=ƒ(x). 
     Matrix product states can express the probability values of all possible m-bit outputs y≡y 1 y 2  . . . y m  if one starts with a product state encoding all possible n-bit inputs x≡x 1 x 2  . . . x n , namely, P(x)=2 −n  for all x. The problem can be solved by computing P(y). The following steps illustrate an exemplary embodiment.
         1. Start with all bits x i , i=1, . . . , n, randomized with equal probabilities of ½ for being 0 or 1. Compute final output matrices M j   y     j   , j=1, . . . , m, resulting from the action of the circuit that evaluates ƒ(x).   2. Compute the probability P(y) for the given y of interest. If P(y)≧2 −n , then there is at least one value of x such that y=ƒ(x).   3. Fix one of the input bits, say x 1 , to be 0, instead of randomizing it. Recompute the output matrices M j   y     j   , j=1, . . . , m, and the new probability P(y). Again test if the probability is above the threshold, P(y)≧2 −n+1  in this case. If the probability fell below the threshold, reset x 1  to 1.   4. Repeat step 3 fixing now input bit x 2  to be 0 and calculating the output matrices and the new probability. Continue repeating step 3, fixing input bit x 3  to be 0, and so on until input bit x n  is fixed to be 0. At the end of n steps, having fixed all the n bits of the input, we have arrived at one value for x such that y=ƒ(x).       

     Notice that since there may be more than one x for a given y, P(y) being above the corresponding threshold does not mean that fixing each input bit to be 1 is necessarily forbidden. Accordingly, the computational process can be run again with the input bits being fixed to different values than in the initial run(s), and additional solutions can be determined where P(y) is determined to be above the corresponding threshold. 
     In additional to finding solutions, the above described system and method can be used to count the total number of possible solutions. For this purpose, P(y) is multiplied by 2 n  after step 2 above. The result is the number of possible solutions x such that ƒ(x)=y for a given y. 
     Referring now to  FIG. 5 , an exemplary embodiment of the disclosed system and method is illustrated in a flowchart  500 . Flowchart  500  illustrates a database search application using the presently disclosed system and method. The computational process illustrated in flowchart  500  begins with a counter k being set to zero as illustrated in a block  512 . Counter k is used to represent the number of bits for which the process will be performed. In a block  514 , the initialization of the matrices representing all bits is undertaken, as well as the application of 1-bit gates used to randomize the inputs. For example, example, all bits x i , i=1, . . . , n, are assigned random probabilities that, in this exemplary embodiment, are equal, meaning a probability of 0.5 for each of the bits being 0 or 1. Although a randomizing function is illustrated in block  514  for setting uniform probabilities for bit states, the probability can set to any useful value for each of the input bit states. For example, a priori knowledge of the function ƒ(x) or solutions can be used to condition the initial probabilities of the input bit states. Alternatively, the initial matrices or input states can be obtained from a database  502 , which can also store the randomized probability matrices resulting from the application of the 1-bit gates used to set the initial probabilities of the input state. 
     A block  516  illustrates the determination of y=ƒ(x) with the implementation of the logic function in a block  518  and the computation of the resulting probabilities in a block  520 . Block  518  illustrates the implementation of the function using 1-bit and/or 2-gates that define the logic function used to calculate the final output matrices M j   y     j   , j=1, . . . , m. The final output matrices are used to compute the probability of the output state represented by the final output matrices, as illustrated in block  520 . 
     The particular output state can have a probability of zero, meaning that there is not a solution. The determination of whether the probability of the output state is zero is illustrated in decision block  522 , where zero probability causes the “yes” branch to be taken, while non-zero probability causes the “no” branch to be taken. If the “yes” branch of decision block  522  is taken, counter k is checked to see if it is a zero value, as illustrated in decision block  524 . If counter k is equal to zero, none of the input bits have been set to a fixed value, and no solution exists to the problem implemented as the logic function illustrated in block  518 . At that point, the process illustrated in flow chart  500  stops, as illustrated by the “yes” branch of decision block  524 . 
     If k is not equal to zero in decision block  524 , a non-initial state has been processed with a probability of P(y)=0, where at least one of the input bits is fixed to a value. In this case, additional output probabilities can be processed, as illustrated with the “no” branch of decision block  524  being taken to a block  532 . Block  532  illustrates an input bit x; being set to 1, and its input matrices being reset accordingly. By fixing the input bit to a certain value, the process illustrated in flowchart  500  moves closer to a solution to the problem. The value of counter k is then compared to the number of bits n, as illustrated in a decision block  530 . If counter k=n, the process is complete with at least one solution being found, as illustrated with the “yes” branch of decision block  530 . If the value of counter k is not yet equal to n, as illustrated by the “no” branch of decision block  530 , counter k is incremented, as illustrated in a block  534 . 
     When the probability of the output state is non-zero, a potential solution has been determined, which is illustrated with the “no” branch of decision block  522  being taken to decision block  530 . The “no” branch being taken from decision block  522  means that, for example, P(y)≧2 −n+k , and that there is at least one value of x such that y=ƒ(x). Note that the threshold for the computed probability depends on a value of counter k, and thus changes with each pass through the process, as more input bits are fixed in value. However, each input state with a non-zero probability can potentially be a solution, which is why the probability is checked for being non-zero, as illustrated in decision block  522 . Decision block  530  illustrates the determination of whether all bits have been processed, and if so, indicates that the solution(s) has(have) been found, as illustrated with the “yes” branch of decision block  530 . If all bits have not been processed, counter k is incremented, as illustrated with the “no” branch of decision block  530  directed to block  534 . 
     After counter k is incremented, as illustrated in block  534 , a new input state is formed as illustrated in a block  536 . For example, block  536  illustrates input bit x, being set to be 0 on the first pass through, instead of being randomized, and 1-bit randomizing gates are applied to the n-k remaining input matrices, as illustrated in a block  538 . The process in block  516  is then reiterated and the logic function operations are applied to the input matrices. Output matrices M j   y     j   , j=1, . . . , m, and the new probability P(y) are then recomputed as illustrated in blocks  518  and  520 . The newly calculated probability is tested to see if it is equal to zero to determine if the new configuration of input states is a solution to the logic function, as illustrated in decision block  522 . If the probability is zero, then the input bit state is not a solution, which is illustrated by the “yes” branch of decision block  522 . If this is not the first pass through the process, meaning that counter k is not 0, the input bit that was set to a fixed value of 0, as illustrated in block  536 , is reset to 1, as illustrated in block  532  being reached by the “no” branch of decision block  524 . Again, counter k is checked for being equal to n, and if so, the process terminates with a solution, as illustrated with the “yes” branch in decision block  530 . Otherwise, the steps of flowchart  500  are repeated with k being incremented with each iteration, as is illustrated in block  534 . With each iteration, a new bit is fixed to determine the probability of the input state. For example, input bit x 2  is fixed to a value and the matrices and probabilities are then recalculated, followed by input bit x 3  being set to a fixed value, and so on until we finally fix input bit x n . At the end of n steps, having fixed all the n bits of the input, we have arrived at one value for x such that y=ƒ(x). 
     In additional to finding solutions, the method illustrated in flowchart  500  can be used to count the total number of possible solutions. For this purpose, P(y) is multiplied by 2 n  after being computed. The result is the number of possible solutions x such that ƒ(x)=y for a given y. 
     The computational cost of the search algorithm discussed above is one of the advantages attained in accordance with the present disclosure. According to an exemplary embodiment, a determination of the computational cost can be stated in terms of the largest matrix dimension D in the computations, which is related to the number n g  of gates involved in the computation of the function ƒ(x). All SVD steps involve matrices with rank smaller or equal to D; therefore, the cost associate to gate operations is no more than O(n g ×D 3 ). Computing the trace of the matrix products for a fixed y yields the probability P(y), which takes time no more than O(n×D 3 ). Also, the procedure is repeated for each iteration in which the input bits x, i=1, . . . , n are each fixed in turn. Therefore, in the worst case, the time is O(n×max{n g , n}×D 3 ) to find x. 
     The method can be further sped up by retaining only the largest singular values during the SVD steps. The number of singular values that are kept can be varied according to the particular function being computed. 
     The number of solutions of a search problem can be found by multiplying the probability P(y*) in block  520  by 2 n . If the result is equal to s, s solutions exist. After the first solution has been found, additional solutions can be obtained one-by-one by repeating the same procedure but including the following extension to the method. To find one more solution, one builds a filter function that blocks input configurations that correspond to previously found solutions. The filter functions can be broken down using the 2-bit filter gates. The search algorithm can then be used again, but now applying the gates encoding the filter function in conjunction with the gates encoding the function ƒ(x). 
     Generalizations: 
     Although one-dimensional bit arrays have been presented, the present disclosure is not so limited, and can be extended to higher dimension tensor products. The presently disclosed system and method can be generalized to consider non-normalized weights W(x) instead of probabilities P(x) in Eq. (1). In such a case one can use 1-bit and 2-bit gates with arbitrary transfer matrices t ã, a  in Eq. (3) and T ã, {tilde over (b)}; a, b  in Eq. (5), respectively. Alternatively, or in addition, non-normalized weights W(x) and/or probabilities P(x) can be used initially and/or in describing the matrices that represent one or more output states. 
     According to aspects of the present disclosure, the system and method can be generalized to encode a database as a matrix product state. The matrices are constructed so as to encode weights W(x), where x is an n-bit number, and such that W(x)=1 if x belongs to the database, and W(x)=0 if otherwise. This feature permits database information to be distributed into matrix form, where the matrices can be efficiently processed to analyze the data. 
     Example: 
     As an example of a matrix computation according to aspects of the present disclosure, consider the following multi-component Boolean expression of the type y=ƒ(x), with y=(y 1 , y 2 ) and x=(x 1 , x 2 , x 3 , x 4 ):
 
ƒ 1 ( x   1   , x   2   , x   3   , x   4 )= x   1             ( x   2           (           x   3              x   4 ))  (19)
 
ƒ 2 ( x   1   , x   2   , x   3   , x   4 )=(           x   2              x   3 )         (           x   1           ( x   2             x   4 )).  (20)
 
These expressions satisfy the truth table shown below. Notice that P(0, 0)=0, while P(0, 1)= 5/16, P(1, 0)= 9/16, and P(1, 0)= 1/16.

     
       
         
               
               
               
               
               
               
               
             
           
               
                   
                   
               
               
                   
                 x 1   
                 x 2   
                 x 3   
                 x 4   
                 f 1   
                 f 2   
               
               
                   
                   
               
             
             
               
                   
                 0 
                 0 
                 0 
                 0 
                 0 
                 1 
               
               
                   
                 0 
                 0 
                 0 
                 1 
                 0 
                 1 
               
               
                   
                 0 
                 0 
                 1 
                 0 
                 0 
                 1 
               
               
                   
                 0 
                 0 
                 1 
                 1 
                 0 
                 1 
               
               
                   
                 0 
                 1 
                 0 
                 0 
                 1 
                 0 
               
               
                   
                 0 
                 1 
                 0 
                 1 
                 1 
                 0 
               
               
                   
                 0 
                 1 
                 1 
                 0 
                 0 
                 1 
               
               
                   
                 0 
                 1 
                 1 
                 1 
                 1 
                 1 
               
               
                   
                 1 
                 0 
                 0 
                 0 
                 1 
                 0 
               
               
                   
                 1 
                 0 
                 0 
                 1 
                 1 
                 0 
               
               
                   
                 1 
                 0 
                 1 
                 0 
                 1 
                 0 
               
               
                   
                 1 
                 0 
                 1 
                 1 
                 1 
                 0 
               
               
                   
                 1 
                 1 
                 0 
                 0 
                 1 
                 0 
               
               
                   
                 1 
                 1 
                 0 
                 1 
                 1 
                 0 
               
               
                   
                 1 
                 1 
                 1 
                 0 
                 1 
                 0 
               
               
                   
                 1 
                 1 
                 1 
                 1 
                 1 
                 1 
               
               
                   
                   
               
             
          
         
       
     
     The following sequence of matrix operations can be used to compute ƒ 1  and ƒ 2 : in the above truth table. 
     Initialize 1×1 matrices M 1   0 , M 1   1 , M 2   0 , M 2   1 , M 3   0 , M 3   1 , M 4   0 , and M 4   1  to ½. 
     INSERT bit  5   
     COPY bit  4  bit  5   
     SWAP bits  4 ,  5   
     NOT on bit  3   
     OR on bits  3 ,  4   
     NOT on bit  3   
     SWAP bits  3 ,  4   
     AND on bits  2 ,  3   
     SWAP bits  2 ,  3   
     OR on bits  1 ,  2   
     SWAP bits  1 ,  2   
     (result of ƒ 1  in bit  1 , all others shifted to the right by one) 
     SWAP bits  4 ,  5   
     AND on bits  3 ,  4   
     SWAP bits  3 ,  4   
     NOT on bit  2   
     OR on bits  2 ,  3   
     NOT on bit  4   
     OR on bits  4 ,  5   
     SWAP bits  4 ,  5   
     AND on bits  3 ,  4   
     SWAP bits  3 ,  4   
     SWAP bits  2 ,  3   
     (result of ƒ 2  in bit  2 ) 
     TRACE OUT bit  5   
     TRACE OUT bit  4   
     TRACE OUT bit  3   
     The above matrix operations result in 1×2 matrices M 1   0  and M 1   1  and 2×1 matrices M 2   0  and M 2   1 . The probabilities are then given by P(0, 0)=M 1   0 M 2   0 , P(0, 1)=M 1   0 M 2   1 , P(1, 0)=M 1   1 M 2   0 , and P(1, 1)=M 1   1 M 2   1 . 
     The operations herein depicted and/or described herein are purely exemplary and imply no particular order. Further, the operations can be used in any sequence when appropriate and can be partially used. With the above embodiments in mind, it should be understood that they can employ various computer-implemented operations involving data transferred or stored in computer systems. These operations are those requiring physical manipulation of physical quantities. Usually, though not necessarily, these quantities take the form of electrical, magnetic, or optical signals capable of being stored, transferred, combined, compared and otherwise manipulated. 
     Any of the operations depicted and/or described herein that form part of the embodiments are useful machine operations. The embodiments also relate to a device or an apparatus for performing these operations. The apparatus can be specially constructed for the required purpose, or the apparatus can be a general-purpose computer selectively activated or configured by a computer program stored in the computer. In particular, various general-purpose machines employing one or more processors coupled to one or more computer readable medium, described below, can be used with computer programs written in accordance with the teachings herein, or it may be more convenient to construct a more specialized apparatus to perform the required operations. 
     The disclosed systems and methods can also be embodied as computer readable code on a computer readable medium. The computer readable medium is any data storage device that can store data, which can thereafter be read by a computer system. Examples of the computer readable medium include hard drives, read-only memory, random-access memory, CD-ROMs, CD-Rs, CD-RWs, magnetic tapes and other optical and non-optical data storage devices. The computer readable medium can also be distributed over a network-coupled computer system so that the computer readable code is stored and executed in a distributed fashion. 
     The foregoing description has been directed to particular embodiments of this disclosure. It will be apparent, however, that other variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages. The procedures, processes and/or modules described herein may be implemented in hardware, software, embodied as a computer-readable medium having program instructions, firmware, or a combination thereof. For example, the function described herein may be performed by a processor executing program instructions out of a memory or other storage device. Therefore, it is the object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the disclosure.