Abstract:
A system and method efficiently prepare the initial state of q quantum computer required by the eigenvalue approximation method of Abrams and Lloyd. The system and method can be applied when solving continuous Hermitian eigenproblems, e.g. the Schrodinger equation, on a discrete gird, and allows for efficient calculation of their eigenvalues with quantum computers. A system and method efficiently prepare an approximate initial state (not limited to eigenvectors) of a quantum computer required by a quantum algorithm as input.

Description:
GOVERNMENT INTERESTS 
       [0001]    This application discloses an invention made with government support under Contract No. F30602-01-0523 awarded by US Air Force, Air Force Material Command Air Force Research Laboratory/IFKF. The government may have certain rights in the invention. 
     
    
     FIELD OF THE INVENTION 
       [0002]    This invention relates to quantum computing and to methods and systems to efficiently calculate eigenvalues and eigenvectors Hermitian operators and quantum mechanical evolution operators with quantum computers and methods and systems to efficiently calculate an approximate quantum state to be used as an input in a quantum mechanical system. 
       BACKGROUND 
       [0003]    Intuitively, quantum mechanical problems offer great potential for quantum computers to achieve large speedups over classical machines. An important problem of this kind is the approximation of an eigenvalue of a quantum mechanical operator. In a recent paper published in 1999 in Physical Review Letters (Vol 83, p. 5162) and hereby incorporated by reference, Abrams and Lloyd present a quantum method for doing this. Their method is exponentially faster than the best classical method, but requires a good approximation of the corresponding eigenvector as an input. 
         [0004]    There is currently a continuing need for a method and system for efficiently computing a good approximation of the eigenvector as an input to the Abrams and Lloyd quantum method. 
         [0005]    There is also a continuing need for a method and system for efficiently computing a good approximation of a quantum state (not limited to eigenvectors) as an input to a quantum mechanical computer or computation. For example, one would like to compute an approximate input to the quantum simulation algorithm. The quantum simulation algorithm is described in the book Quantum Computation and Quantum Information, by M. A. Nielsen and I. L. Chuang, Cambridge University Press, Cambridge UK (2000). 
       SUMMARY OF THE INVENTION 
       [0006]    The present invention is a system and method for use on a quantum computer to efficiently prepare the initial quantum state required by Abrams and Lloyd&#39;s eigenvalue approximation method. The system and method of the present invention is used to prepare a quantum register with an approximation of the eigenvector that is guaranteed to be sufficiently good to be used as input to the Abrams and Lloyd method. The present invention can be used when solving continuous Hermitian eigenproblems, e.g. the Schrodinger equation, on a discrete grid. 
         [0007]    Beginning with an eigenvector for a problem discretized on a coarse grid, the system of the present invention efficiently constructs, quantum mechanically, an approximation of the same eigenvector on a finer grid. This eigenvector approximation is suitable as the initial state for the eigenvalue estimation method of Abrams and Lloyd. 
         [0008]    Similarly beginning with a vector (i.e., a quantum state) for a continuous problem discretized on a coarse grid, the system of the present invention efficiently constructs, quantum mechanically, a vector (i.e., a state), which is an approximation to the corresponding vector on a finer grid. Our system efficiently extends a vector of low dimension to one of high dimension, which is then presented as input to some quantum computation method, e.g., the quantum simulation algorithm. 
         [0009]    The features and advantages of the present invention will be more readily apparent and understood from the following detailed description of the invention, which should be understood in conjunction with the accompanying drawings appended to the end of the detailed description. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0010]      FIG. 1  is a chart illustrating the steps performed on the various quantum registers according to an embodiment of the present invention. 
           [0011]      FIG. 2  is a chart illustrating the steps performed on the various quantum registers according to another embodiment of the invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]    For purposes of illustration only, and not to limit the scope of the present invention, the invention will be explained with reference to the embodiments of the invention indicated in the drawings. One skilled in the art would understand that the present invention is not limited to the specific examples disclosed and can be more generally applied to other initial state preparation methods and systems than those disclosed. 
         [0013]    The key component in the Abrams and Lloyd method is quantum phase estimation, which is a method for approximating an eigenvalue of a unitary matrix. Quantum phase estimation is also described in the above referenced book of Nielsen and Chuang. We give a brief outline of this method below. 
         [0014]    Let Q denote a 2 m ×2 m  unitary matrix. We want to approximate a specific eigenvalue of Q. Phase estimation does this using the corresponding eigenvector as input. The Abrams and Lloyd method deals with the case when this eigenvector is not known exactly. Referring to  FIG. 1 , consider a quantum computer consisting of three registers  140 ,  150 , and  160  with a total of b+m+w qubits. The first b qubits in register  150  are all initially in the state |0         . The second register  140  with m qubits is initialized to some state |ψ         , which must approximate the eigenvector in question sufficiently well, as will be seen. The last w qubits in register  160  are work qubits for temporary storage. The w qubits are not important in our discussion here, and we generally omit discussion of them below. 
         [0015]    Since Q is unitary and therefore normal, the state |ψ          can be expanded with respect to eigenvectors of Q. Omitting discussion of the work qubits in register  160 , the initial state of the algorithm is 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       | 
                       
                         0 
                          
                         
                             
                         
                          
                       
                       | 
                       
                         ψ 
                          
                       
                     
                     = 
                     
                       
                         | 
                       
                        
                       0 
                        
                       
                           
                       
                        
                        
                       
                         
                           ∑ 
                           u 
                         
                          
                         
                           
                             d 
                             u 
                           
                            
                           
                             | 
                           
                            
                           u 
                            
                           
                               
                           
                            
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where |u          are the eigenvectors of Q. Placing the first register  150  in an equal superposition, using b Hadamard gates in step  170 , transforms this state into 
         [0000]    
       
         
           
             
               
                 
                   
                     1 
                     
                       
                         2 
                         b 
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         
                           2 
                           b 
                         
                         - 
                         1 
                       
                     
                      
                     
                       
                         | 
                       
                        
                       j 
                        
                       
                           
                       
                        
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Next, powers of Q are applied in step  170  to create the state 
         [0000]    
       
         
           
             
               
                 
                   
                     1 
                     
                       
                         2 
                         b 
                       
                     
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         
                           2 
                           b 
                         
                         - 
                         1 
                       
                     
                      
                     
                       
                         | 
                       
                        
                       j 
                        
                       
                           
                       
                        
                        
                       
                         Q 
                         i 
                       
                        
                       
                         
                           ∑ 
                           u 
                         
                          
                         
                           
                             d 
                             u 
                           
                            
                           
                             | 
                           
                            
                           u 
                            
                           
                               
                           
                            
                           
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0016]    Since Q is unitary, its eigenvalues can be written as e 2πiφ     u   , where φ u ∈R. We can assume that φ u ∈[0,1) and consider the approximation of one of these phases instead of the approximation of one of the eigenvalues. Equation (3) is equal to 
         [0000]    
       
         
           
             
               
                 
                   
                     1 
                     
                       
                         2 
                         b 
                       
                     
                   
                    
                   
                     
                       ∑ 
                       u 
                     
                      
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           
                             2 
                             b 
                           
                           - 
                           1 
                         
                       
                        
                       
                         
                           d 
                           u 
                         
                          
                         
                            
                           
                             2 
                              
                             
                               πjϕ 
                               u 
                             
                           
                         
                          
                         
                           | 
                         
                          
                         j 
                          
                         
                             
                         
                          
                          
                         
                           | 
                         
                          
                         u 
                          
                         
                             
                         
                          
                         
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0000]    It is easily seen that the inverse Fourier transform performed in step  170  on the first register  150  creates the state 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∑ 
                       u 
                     
                      
                     
                       
                         
                           d 
                           u 
                         
                          
                         
                           ( 
                           
                             
                               ∑ 
                               
                                 j 
                                 = 
                                 0 
                               
                               
                                 
                                   2 
                                   b 
                                 
                                 - 
                                 1 
                               
                             
                              
                             
                               
                                 g 
                                  
                                 
                                   ( 
                                   
                                     
                                       ϕ 
                                       u 
                                     
                                     , 
                                     j 
                                   
                                   ) 
                                 
                               
                                
                               
                                 | 
                               
                                
                               j 
                                
                               
                                   
                               
                                
                             
                           
                           ) 
                         
                       
                        
                       
                           
                       
                        
                       
                         | 
                       
                        
                       u 
                        
                       
                           
                       
                        
                     
                   
                   , 
                   
                     
 
                   
                    
                   where 
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
             
               
                 
                   
                     g 
                      
                     
                       ( 
                       
                         
                           ϕ 
                           u 
                         
                         , 
                         j 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   sin 
                                    
                                   
                                     ( 
                                     
                                       π 
                                        
                                       
                                         ( 
                                         
                                           
                                             
                                               2 
                                               b 
                                             
                                              
                                             
                                               ϕ 
                                               u 
                                             
                                           
                                           - 
                                           j 
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                  
                                 
                                    
                                   
                                     
                                       π 
                                        
                                       
                                         ( 
                                         
                                           
                                             ϕ 
                                             u 
                                           
                                           - 
                                           
                                             j 
                                              
                                             
                                                 
                                             
                                              
                                             
                                               2 
                                               
                                                 - 
                                                 b 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           2 
                                           b 
                                         
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                   
                                 
                               
                               
                                 
                                   2 
                                   b 
                                 
                                  
                                 
                                   sin 
                                    
                                   
                                     ( 
                                     
                                       π 
                                        
                                       
                                         ( 
                                         
                                           
                                             ϕ 
                                             u 
                                           
                                           - 
                                           
                                             j2 
                                             
                                               - 
                                               b 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               
                                 2 
                                 b 
                               
                                
                               
                                 ϕ 
                                 u 
                               
                             
                             ≠ 
                             j 
                           
                         
                       
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                             
                               
                                 2 
                                 b 
                               
                                
                               
                                 ϕ 
                                 u 
                               
                             
                             = 
                             
                               j 
                               . 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    In step  180 , a measurement of the first register  150  produces outcome j  190  with probability 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       p 
                       j 
                     
                     = 
                     
                       
                         ∑ 
                         u 
                       
                        
                       
                         
                           
                              
                             
                               d 
                               u 
                             
                              
                           
                           2 
                         
                          
                         
                           
                              
                             
                               g 
                                
                               
                                 ( 
                                 
                                   
                                     ϕ 
                                     u 
                                   
                                   , 
                                   j 
                                 
                                 ) 
                               
                             
                              
                           
                           2 
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and the second register  140  will collapse to the state 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     u 
                   
                    
                   
                     
                       
                         
                           d 
                           u 
                         
                          
                         
                           g 
                            
                           
                             ( 
                             
                               
                                 ϕ 
                                 u 
                               
                               , 
                               j 
                             
                             ) 
                           
                         
                       
                       
                         
                           p 
                           j 
                         
                       
                     
                      
                     
                         
                     
                      
                     
                       | 
                     
                      
                     u 
                      
                     
                         
                     
                      
                     
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
     
         [0000]    represented by the register  200 ; register  210  contains the work qubits after the measurement  180  as known to one skilled in the art. 
         [0017]    We remark that for special case when the eigenvalues φ u  can be represented exactly with b-bits (i.e., 2 b φ u  is an integer), equation (5) simplifies to 
         [0000]    
       
         
           
             
               
                 
                   
                     ∑ 
                     u 
                   
                    
                   
                     
                       d 
                       u 
                     
                      
                     
                       | 
                     
                      
                     
                       ϕ 
                       u 
                     
                      
                     
                         
                     
                      
                      
                     
                       | 
                     
                      
                     u 
                      
                     
                         
                     
                      
                     
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0000]    When the eigenvalues are of this form and are distinct, a measurement in step  180  of the first register  150  will cause the second register  140  to collapse exactly onto the corresponding eigenvector in register  200 . 
         [0018]    Recall that the system and method of the present invention are to achieve an approximation of the phase that corresponds to an eigenvector |u″          using a quantum computer, that the state |ψ          is an approximation of this eigenvector, and that the eigenvalue is obtained from the value of the outcome j  190  by e 2πij/2̂b  is of the form and approximates e 2πiφ     u   . For instance, one is often interested in the eigenvalue corresponding to the ground state or in low order eigenvalues. We define Δ(φ 0 , φ 1 )=min x ∈ z {|x+φ 1 −φ 0 |}, φ 0 ,φ 1 ∈R (i.e., the fractional part of the distance between φ 0  and φ 1 ) Then a measurement of the first register produces an outcome from the set G={j:Δ(j/2 b , φ u′ )≦k/2 b ,k&gt;1} with probability 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           Pr 
                            
                           
                             ( 
                             G 
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             ∑ 
                             
                               j 
                               ∈ 
                               G 
                             
                           
                            
                           
                             
                               ∑ 
                               u 
                             
                              
                             
                               
                                  
                                 
                                   
                                     d 
                                     u 
                                   
                                    
                                   
                                     g 
                                      
                                     
                                       ( 
                                       
                                         
                                           ϕ 
                                           u 
                                         
                                         , 
                                         j 
                                       
                                       ) 
                                     
                                   
                                 
                                  
                               
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         ≥ 
                           
                          
                         
                           
                             ∑ 
                             
                               j 
                               ∈ 
                               G 
                             
                           
                            
                           
                             
                                
                               
                                 
                                   d 
                                   
                                     u 
                                     ′ 
                                   
                                 
                                  
                                 
                                   g 
                                    
                                   
                                     ( 
                                     
                                       
                                         ϕ 
                                         
                                           u 
                                           ′ 
                                         
                                       
                                       , 
                                       j 
                                     
                                     ) 
                                   
                                 
                               
                                
                             
                             2 
                           
                         
                       
                     
                   
                   
                     
                       
                         
                           ≥ 
                             
                            
                           
                             
                               
                                  
                                 
                                   d 
                                   
                                     u 
                                     ′ 
                                   
                                 
                                  
                               
                               2 
                             
                             - 
                             
                               
                                 
                                    
                                   
                                     d 
                                     
                                       u 
                                       ′ 
                                     
                                   
                                    
                                 
                                 2 
                               
                               
                                 2 
                                  
                                 
                                   ( 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         , 
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0000]    and when k=1 the probability to obtain j such that Δ(j/2 b , φ u′ )≦2 −b  is bounded from below by 
         [0000]    
       
         
           
             
               8 
               
                 π 
                 2 
               
             
              
             
               
                 
                    
                   
                     d 
                     
                       u 
                       ′ 
                     
                   
                    
                 
                 2 
               
               · 
               
                  
                 
                   ψ 
                    
                 
               
             
           
         
       
     
         [0000]    must be chosen in a way that this probability is large or preferably greater than ½, which implies that |d u′ | has to be sufficiently large. For one embodiment of the present invention to obtain an approximation of φ u′  with accuracy 2 −n  and probability at least |d u′|   2 (1−ε), equation (10) shows that the number of qubits b in the first register  150  must be 
         [0000]    
       
         
           
             
               
                 
                   b 
                   = 
                   
                     n 
                     + 
                     
                       
                         ⌈ 
                         
                           log 
                            
                           
                             ( 
                             
                               1 
                               + 
                               
                                 1 
                                 
                                   2 
                                    
                                   ε 
                                 
                               
                             
                             ) 
                           
                         
                         ⌉ 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0019]    Quantum phase estimation can be used as an efficient subroutine to find eigenvalues. Consider a Hermitian operator H. The operator G(t)=e −iHt  is unitary and has the same eigenvectors as H. We assume that G can be implemented efficiently and, therefore, can be used as the unitary operator in the phase estimation algorithm. For example, when H is local, i.e., it can be written in the form ΣH j , where each H j  acts only on a small number of qubits, then G can be implemented efficiently. However, locality is not a necessary condition for efficient implementation. Indeed, G can be efficiently implemented for a many-particle quantum mechanical system with a non-local H. One skilled in the art will understand that it is possible to implement G for a wide class of non-local Hamiltonians. 
         [0020]    The Hermitian eigenproblem described above is solved on a discrete grid. One embodiment of the present invention addresses the case in which the grid is extremely fine. Clearly, a fine grid requires a large vector for the representation of the initial state of the algorithm. In general, it may not be possible to efficiently prepare an arbitrary quantum state in a space with a large number of qubits. However, the present invention includes a method for the efficient preparation of an initial state. 
         [0021]    In one embodiment of the invention, the operator possesses an eigenvector for a coarse grid discretization of the problem, which was most likely obtained classically since the size of the problem is small, although one skilled in the art will understand an eigenvector obtained by any coarse method can be employed without diverging from the scope of the invention. Using this eigenvector, we efficiently construct an approximation to the corresponding eigenvector for a fine grid discretization of the problem. We use this approximation as the initial state of the eigenvalue approximation algorithm. We describe our method for a one-dimensional continuous problem on the interval [0,1]. 
         [0022]    Let H be a positive Hermitian operator, defined on a Hilbert space of smooth functions on [0,1]. Let v k (·), k=1,2, . . . , denote the eigenfunctions of H, ordered according to the magnitude of the corresponding eigenvalues; and without loss of generality we assume that 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       ∫ 
                       0 
                       1 
                     
                      
                     
                       
                         
                            
                           
                             
                               v 
                               k 
                             
                              
                             
                               ( 
                               x 
                               ) 
                             
                           
                            
                         
                         2 
                       
                        
                       
                          
                         x 
                       
                     
                   
                   = 
                   1. 
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Suppose that H N  is a discretization of H with grid size h N =1/(1+N). Let |U k   (N)           k=0,1, . . . ,N−1, denote the normalized eigenvectors of H N , ordered according to the magnitude of the corresponding eigenvalues. The expansion of the k-th eigenvector in the computational basis can be written as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                     
                      
                     
                       U 
                       k 
                       
                         ( 
                         N 
                         ) 
                       
                     
                      
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                      
                     
                       
                         u 
                         
                           k 
                           , 
                           j 
                         
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                       
                          
                       
                        
                       j 
                        
                       
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0000]    
       
         
           
             Let 
              
             
                 
             
              
             
                
               
                 
                   
                     V 
                     k 
                     
                       ( 
                       N 
                       ) 
                     
                   
                    
                 
                 = 
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       0 
                     
                     
                       N 
                       - 
                       1 
                     
                   
                    
                   
                     
                       v 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           ( 
                           
                             j 
                             + 
                             1 
                           
                           ) 
                         
                          
                         
                           h 
                           N 
                         
                       
                       ) 
                     
                   
                 
               
                
             
              
             j 
              
           
         
       
     
         [0000]    be the sampled version of v k (·) at the discretization points. Consider problems such that the eigenvector of interest satisfies ∥v′ k ∥ ∞ =sup 0≦x≦1 |v′ k (x)|=O(1) and 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                       
                         
                           
                              
                           
                            
                           
                             U 
                             k 
                             
                               ( 
                               N 
                               ) 
                             
                           
                            
                         
                         - 
                         
                           
                             
                                
                             
                              
                             
                               V 
                               k 
                               
                                 ( 
                                 N 
                                 ) 
                               
                             
                              
                           
                           
                              
                             
                               
                                  
                               
                                
                               
                                 V 
                                 k 
                                 
                                   ( 
                                   N 
                                   ) 
                                 
                               
                                
                             
                              
                           
                         
                       
                        
                     
                     = 
                     
                       O 
                        
                       
                         ( 
                         
                           h 
                           N 
                           g 
                         
                         ) 
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where q&gt;0 is the order of convergence and 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                       
                         
                            
                         
                          
                         X 
                          
                       
                        
                     
                     2 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         
                           
                              
                             
                               x 
                               j 
                             
                              
                           
                           2 
                         
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         
                            
                         
                          
                         X 
                          
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           j 
                           = 
                           
                             N 
                             - 
                             1 
                           
                         
                       
                        
                       
                         
                           x 
                           j 
                         
                          
                         
                            
                         
                          
                         j 
                          
                         
                           . 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
         [0000]    for 
         [0000]    
       
         
           
             
                
               
                 
                   X 
                    
                 
                 = 
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       0 
                     
                     
                       j 
                       = 
                       
                         N 
                         - 
                         1 
                       
                     
                   
                    
                   
                     x 
                     j 
                   
                 
               
                
             
              
             j 
              
             
               . 
             
           
         
       
     
         [0000]    For example, these conditions are satisfied when, for example, we are dealing with second order elliptic operators. 
         [0023]    Now, assume that the eigenvector |U k   (N     0     )            of H N     0    has been obtained classically. This vector is placed in a log NO qubit register  110  (see  FIG. 1 ). For N=2 s N 0 , we construct an approximation |Ũ k   (N)            of |U k   (N)            by appending s qubits in register  120 , each qubit in the state |0         , to |U k   (N)            and then performing in step  130  a Hadamard transformation on each one of these s qubits in register  120 , i.e. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                          
                       
                        
                       
                         
                           U 
                           ~ 
                         
                         k 
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                     
                     = 
                     
                       
                         
                            
                         
                          
                         
                           
                             U 
                             ~ 
                           
                           k 
                           
                             ( 
                             
                               N 
                               0 
                             
                             ) 
                           
                         
                          
                          
                         
                           
                             ( 
                             
                               
                                 
                                   
                                      
                                   
                                    
                                   0 
                                    
                                 
                                 + 
                                 
                                   
                                      
                                   
                                    
                                   1 
                                    
                                 
                               
                               
                                 2 
                               
                             
                             ) 
                           
                           
                             ⊗ 
                             s 
                           
                         
                       
                       = 
                       
                         
                           1 
                           
                             
                               2 
                               s 
                             
                           
                         
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               1 
                             
                           
                            
                           
                             
                               u 
                               
                                 k 
                                 , 
                                 
                                   j 
                                    
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                               
                               
                                 ( 
                                 
                                   N 
                                   0 
                                 
                                 ) 
                               
                             
                              
                             
                                
                             
                              
                             j 
                              
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where ƒ(j)=└j/ 2   s ┘. The effect of ƒ is to replicate the coordinates of |U k   (N     0     )           2 s  times. According to the present invention, |Ũ k   (N)            is used as input to the eigenvalue and eigenvector approximation method. When the result of the method is measured |Ũ k   (N)            will collapse onto a superposition of eigenvectors according to equation (8). The magnitude of the coefficient of |U k   (N)            in this superposition can be made arbitrarily close to one by appropriately choosing N 0 . 
         [0024]    Consider two different expansions of |Ũ k   (N)           : 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                     
                      
                     
                       
                         U 
                         ~ 
                       
                       k 
                       
                         ( 
                         N 
                         ) 
                       
                     
                      
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                      
                     
                       
                         u 
                         
                           k 
                           , 
                           j 
                         
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                       
                          
                       
                        
                       j 
                        
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   
                     
                        
                     
                      
                     
                       
                         U 
                         ~ 
                       
                       k 
                       
                         ( 
                         N 
                         ) 
                       
                     
                      
                   
                   = 
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                      
                     
                       
                         d 
                         
                           k 
                           , 
                           l 
                         
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                       
                          
                       
                        
                       
                         
                           U 
                           ~ 
                         
                         l 
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                       
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The first expansion is in the computational basis and the second is with respect to the eigenvectors H N . We call |d k,k   (N) | 2  the probability of success. Equation (17) can be rewritten as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                          
                       
                        
                       
                         
                           U 
                           ~ 
                         
                         k 
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                     
                     - 
                     
                       
                          
                       
                        
                       
                         U 
                         k 
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                     
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             d 
                             
                               k 
                               , 
                               k 
                             
                             
                               ( 
                               N 
                               ) 
                             
                           
                           - 
                           1 
                         
                         ) 
                       
                        
                       
                          
                       
                        
                       
                         
                           U 
                           ~ 
                         
                         k 
                         
                           ( 
                           N 
                           ) 
                         
                       
                        
                     
                     + 
                     
                       
                         ∑ 
                         
                           l 
                           ≠ 
                           k 
                         
                       
                        
                       
                         
                           d 
                           
                             k 
                             , 
                             l 
                           
                           
                             ( 
                             N 
                             ) 
                           
                         
                          
                         
                            
                         
                          
                         
                           U 
                           l 
                           
                             ( 
                             N 
                             ) 
                           
                         
                          
                         
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Taking norms on both sides and using (13) and (16) gives the inequality 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                              
                             
                               
                                 
                                   | 
                                 
                                  
                                 
                                   U 
                                   k 
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                  
                               
                               - 
                               
                                 
                                   | 
                                 
                                  
                                 
                                   
                                     U 
                                     ~ 
                                   
                                   k 
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                  
                               
                             
                              
                           
                           2 
                         
                         = 
                           
                          
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               r 
                             
                           
                            
                           
                             
                                
                               
                                 
                                   u 
                                   
                                     k 
                                     , 
                                     j 
                                   
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     u 
                                     ~ 
                                   
                                   
                                     k 
                                     , 
                                     j 
                                   
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                               
                                
                             
                             2 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             
                                
                               
                                 
                                   d 
                                   
                                     k 
                                     , 
                                     k 
                                   
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                 - 
                                 1 
                               
                                
                             
                             2 
                           
                           + 
                           
                             
                               ∑ 
                               
                                 l 
                                 ≠ 
                                 k 
                               
                             
                              
                             
                               
                                  
                                 
                                   d 
                                   
                                     k 
                                     , 
                                     l 
                                   
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                  
                               
                               2 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         ≥ 
                           
                          
                         
                           
                             ∑ 
                             
                               l 
                               ≠ 
                               k 
                             
                           
                            
                           
                             
                                
                               
                                 d 
                                 
                                   k 
                                   , 
                                   l 
                                 
                                 
                                   ( 
                                   N 
                                   ) 
                                 
                               
                                
                             
                             2 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           1 
                           - 
                           
                             
                               
                                  
                                 
                                   d 
                                   
                                     k 
                                     , 
                                     k 
                                   
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                 
                                  
                               
                               2 
                             
                             . 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0025]    We will now bound ( 19 ) from above, and thus the probability of failure. The definition of |Ũ k   (N)            implies 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                          
                         
                           
                             
                               | 
                             
                              
                             
                               U 
                               k 
                               
                                 ( 
                                 N 
                                 ) 
                               
                             
                              
                           
                           - 
                           
                             
                               | 
                             
                              
                             
                               
                                 U 
                                 ~ 
                               
                               k 
                               
                                 ( 
                                 N 
                                 ) 
                               
                             
                              
                           
                         
                          
                       
                       2 
                     
                     = 
                     
                       
                         ∑ 
                         
                           j 
                           = 
                           0 
                         
                         
                           N 
                           - 
                           1 
                         
                       
                        
                       
                         
                            
                           
                             
                               
                                 
                                   
                                     
                                       
                                         v 
                                         k 
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             ( 
                                             
                                               j 
                                               + 
                                               1 
                                             
                                             ) 
                                           
                                            
                                           
                                             h 
                                             N 
                                           
                                         
                                         ) 
                                       
                                     
                                     
                                        
                                       
                                         | 
                                         
                                           
                                             V 
                                             k 
                                             
                                               ( 
                                               N 
                                               ) 
                                             
                                           
                                            
                                         
                                       
                                        
                                     
                                   
                                   - 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       
                                         v 
                                         k 
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             ( 
                                             
                                               
                                                 f 
                                                  
                                                 
                                                   ( 
                                                   j 
                                                   ) 
                                                 
                                               
                                               + 
                                               1 
                                             
                                             ) 
                                           
                                            
                                           
                                             h 
                                             
                                               N 
                                               0 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     
                                       
                                         ? 
                                       
                                        
                                       
                                          
                                         
                                            
                                           
                                             V 
                                             k 
                                             
                                               ( 
                                               
                                                 N 
                                                 0 
                                               
                                               ) 
                                             
                                           
                                           〉 
                                         
                                          
                                       
                                     
                                   
                                   + 
                                 
                               
                             
                             
                               
                                 
                                   
                                     Δ 
                                     
                                       k 
                                       , 
                                       j 
                                     
                                     
                                       ( 
                                       N 
                                       ) 
                                     
                                   
                                   - 
                                   
                                     
                                       Δ 
                                       
                                         k 
                                         , 
                                         
                                           f 
                                            
                                           
                                             ( 
                                             j 
                                             ) 
                                           
                                         
                                       
                                       
                                         ( 
                                         
                                           N 
                                           0 
                                         
                                         ) 
                                       
                                     
                                     
                                       ? 
                                     
                                   
                                 
                               
                             
                           
                            
                         
                         2 
                       
                     
                   
                   , 
                   
                     
 
                   
                    
                   
                     
                       ? 
                     
                      
                     
                       indicates text missing or illegible when filed 
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 
         [0000]    
       
         
           
             
               
                 ∑ 
                 
                   j 
                   = 
                   0 
                 
                 
                   N 
                   - 
                   1 
                 
               
                
               
                 
                    
                   
                     Δ 
                     
                       k 
                       , 
                       j 
                     
                     
                       ( 
                       N 
                       ) 
                     
                   
                    
                 
                 2 
               
             
             = 
             
               
                 
                   O 
                    
                   
                     ( 
                     
                       h 
                       N 
                       
                         2 
                          
                         q 
                       
                     
                     ) 
                   
                 
                  
                 
                     
                 
                  
                 and 
                  
                 
                     
                 
                  
                 
                   
                     ∑ 
                     
                       j 
                       = 
                       0 
                     
                     
                       N 
                       - 
                       1 
                     
                   
                    
                   
                     
                        
                       
                         Δ 
                         
                           k 
                           , 
                           
                             f 
                              
                             
                               ( 
                               j 
                               ) 
                             
                           
                         
                         
                           ( 
                           
                             N 
                             0 
                           
                           ) 
                         
                       
                        
                     
                     2 
                   
                 
               
               = 
               
                 
                   2 
                   s 
                 
                  
                 
                   O 
                    
                   
                     ( 
                     
                       h 
                       
                         N 
                         0 
                       
                       
                         2 
                          
                         q 
                       
                     
                     ) 
                   
                 
                  
                 
                     
                 
                  
                 by 
                  
                 
                     
                 
                  
                 
                   
                     ( 
                     14 
                     ) 
                   
                   . 
                 
               
             
           
         
       
     
         [0000]    Applying the triangle inequality, we get 
         [0000]    
       
         
           
             
               
                 
                   
                      
                     
                       
                         
                           | 
                         
                          
                         
                           U 
                           k 
                           
                             ( 
                             N 
                             ) 
                           
                         
                          
                       
                       - 
                       
                         
                           | 
                         
                          
                         
                           
                             U 
                             ~ 
                           
                           k 
                           
                             ( 
                             N 
                             ) 
                           
                         
                          
                       
                     
                      
                   
                   ≤ 
                   
                     
                       
                         ( 
                         
                           
                             ∑ 
                             
                               j 
                               = 
                               0 
                             
                             
                               N 
                               - 
                               1 
                             
                           
                            
                           
                             
                                
                               
                                 
                                   
                                     
                                       
                                         
                                           
                                             v 
                                             k 
                                           
                                            
                                           
                                             ( 
                                             
                                               
                                                 ( 
                                                 
                                                   j 
                                                   + 
                                                   1 
                                                 
                                                 ) 
                                               
                                                
                                               
                                                 h 
                                                 N 
                                               
                                             
                                             ) 
                                           
                                         
                                         
                                            
                                           
                                             | 
                                             
                                               
                                                 V 
                                                 k 
                                                 
                                                   ( 
                                                   N 
                                                   ) 
                                                 
                                               
                                                
                                             
                                           
                                            
                                         
                                       
                                       - 
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         
                                           v 
                                           k 
                                         
                                          
                                         
                                           ( 
                                           
                                             
                                               ( 
                                               
                                                 
                                                   f 
                                                    
                                                   
                                                     ( 
                                                     j 
                                                     ) 
                                                   
                                                 
                                                 + 
                                                 1 
                                               
                                               ) 
                                             
                                              
                                             
                                               h 
                                               
                                                 N 
                                                 0 
                                               
                                             
                                           
                                           ) 
                                         
                                       
                                       
                                         
                                           ? 
                                         
                                          
                                         
                                            
                                           
                                              
                                             
                                               V 
                                               k 
                                               
                                                 ( 
                                                 
                                                   N 
                                                   0 
                                                 
                                                 ) 
                                               
                                             
                                             〉 
                                           
                                            
                                         
                                       
                                     
                                   
                                 
                               
                                
                             
                             2 
                           
                         
                         ) 
                       
                       
                         1 
                         / 
                         2 
                       
                     
                     + 
                     
                       
                         
                           O 
                            
                           
                             ( 
                             
                               h 
                               
                                 N 
                                 0 
                               
                               q 
                             
                             ) 
                           
                         
                         . 
                         
                           
 
                         
                          
                         
                           ? 
                         
                       
                        
                       
                         indicates text missing or illegible when filed 
                       
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
           
         
       
     
         [0000]    The definition of |V k   (N)            and the fact that ∥v′ k ∥ ∞ =O(1) imply that ∥V k   (N)           ∥=√{square root over (N)}(1+O(h N )). Hence, the sum above is equal to 
         [0000]    
       
         
           
             
               
                 
                   
                     1 
                     N 
                   
                    
                   
                     
                       ∑ 
                       
                         j 
                         = 
                         0 
                       
                       
                         N 
                         - 
                         1 
                       
                     
                      
                     
                       
                         
                            
                           
                             
                               
                                 
                                   
                                     
                                       
                                         v 
                                         k 
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             ( 
                                             
                                               j 
                                               + 
                                               1 
                                             
                                             ) 
                                           
                                            
                                           
                                             h 
                                             N 
                                           
                                         
                                         ) 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         1 
                                         + 
                                         
                                           O 
                                            
                                           
                                             ( 
                                             
                                               h 
                                               N 
                                             
                                             ) 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                   - 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       v 
                                       k 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           ( 
                                           
                                             
                                               f 
                                                
                                               
                                                 ( 
                                                 j 
                                                 ) 
                                               
                                             
                                             + 
                                             1 
                                           
                                           ) 
                                         
                                          
                                         
                                           h 
                                           
                                             N 
                                             0 
                                           
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       1 
                                       + 
                                       
                                         O 
                                          
                                         
                                           ( 
                                           
                                             h 
                                             
                                               N 
                                               0 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                            
                         
                         2 
                       
                       . 
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Since v k (·) is continuous with a bounded first derivative, we have that 
         [0000]        u   k ( x   2,j )= u   k ( x   1,j )+ O (| x   2,j   −x   1,j |),  (123) 
         [0000]    where x 1,j =(j+1)h N  and x 2,j =(ƒ(j)+1)h N     0   ,j=0, . . . ,N−1. Clearly |x 2,j −x 1,j |=O(h N     0   ). Using (22), (23) and the triangle inequality, we obtain from (21) that 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             
                                
                               
                                 
                                   
                                     | 
                                   
                                    
                                   
                                     U 
                                     k 
                                     
                                       ( 
                                       N 
                                       ) 
                                     
                                   
                                    
                                 
                                 - 
                                 
                                   
                                     | 
                                   
                                    
                                   
                                     
                                       U 
                                       ~ 
                                     
                                     k 
                                     
                                       ( 
                                       N 
                                       ) 
                                     
                                   
                                    
                                 
                               
                                
                             
                             2 
                           
                           ≤ 
                           
                             
                               
                                 O 
                                  
                                 
                                   ( 
                                   
                                     h 
                                     
                                       N 
                                       0 
                                     
                                   
                                   ) 
                                 
                               
                                
                               
                                 
                                    
                                   
                                     
                                       | 
                                     
                                      
                                     
                                       V 
                                       k 
                                       
                                         ( 
                                         N 
                                         ) 
                                       
                                     
                                      
                                   
                                    
                                 
                                 
                                   N 
                                 
                               
                             
                             + 
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               O 
                                
                               
                                 ( 
                                 
                                   h 
                                   
                                     N 
                                     0 
                                   
                                 
                                 ) 
                               
                             
                             + 
                             
                               O 
                                
                               
                                 ( 
                                 
                                   h 
                                   
                                     N 
                                     0 
                                   
                                 
                                 ) 
                               
                             
                           
                           = 
                           
                             
                               O 
                                
                               
                                 ( 
                                 
                                   h 
                                   
                                     N 
                                     0 
                                   
                                   
                                     min 
                                      
                                     
                                       { 
                                       
                                         1 
                                         , 
                                         q 
                                       
                                       } 
                                     
                                   
                                 
                                 ) 
                               
                             
                             . 
                           
                         
                       
                     
                   
                    
                   
                       
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
           
         
       
     
         [0026]    Hence, the probability of failure is bounded from above by O(N 0   −min{2,2q} ). It depends only on the order of convergence to the continuous problem and the number of points in the classically solved small problem. We can select an N 0  such that the probability of failure is less than ½, no matter how much larger N is. By choosing a large N, we can make the discretization error arbitrarily small. Equation (24) implies that the probability of obtaining the eigenvalue e 2πiφ     k    with accuracy 2 −b  is at least 
         [0000]    
       
         
           
             
               8 
               
                 π 
                 2 
               
             
              
             
               
                 ( 
                 
                   1 
                   - 
                   
                     O 
                      
                     
                       ( 
                       
                         N 
                         0 
                         
                           
                             - 
                             min 
                           
                            
                           
                             { 
                             
                               2 
                               , 
                               
                                 2 
                                  
                                 q 
                               
                             
                             } 
                           
                         
                       
                       ) 
                     
                   
                 
                 ) 
               
               . 
             
           
         
       
     
         [0027]    We remark that any classical numerical algorithm that computes an eigenvalue, satisfying a specific (nontrivial) property, of a N×N unitary matrix takes time Ω(N). For example, one may want to find the eigenvalue that corresponds to the ground state. This is true even if a matrix is sparse and regardless of whether the algorithm is deterministic or randomized. It is merely a consequence of the fact that the algorithm needs to consider all the (nonzero) elements of the matrix, and there are at least Ω(N) such elements. Alternatively, in the restricted case when the matrix is diagonal finding one of its elements is a problem at least as hard as searching an unordered list. The lower bound for searching yields the lower bound in our case. 
         [0028]    In conclusion, our method provides a highly efficient preparation of initial states for eigenvalue approximation, requiring only a small number of Hadamard gates. Thus the method of Abrams and Lloyd, using the initial state prepared by the system and method of the present invention, computes the eigenvalue exponentially faster than any classical algorithm. The method of the invention can be generalized to higher dimensional continuous problems. 
         [0029]    In another embodiment of the invention, if we possess a vector that corresponds to a coarse discetization of a continuous problem then, under suitable conditions, we can efficiently extend it to a vector that approximates the corresponding vector (i.e., a state) of a fine discretization. Referring to  FIG. 2 , we first place the original or given vector in register  310 . Assuming that the vector has dimension N 0  this register has log N 0  qubits. For a N=2 s N 0 , we append to register  310  s qubits, in the state |0         , in register  320 . Then in step  330  we apply the Hadamard transform to the appended qubits. See Equation (15) and the explanation of the effect of the replicating function ƒ. In register  340  we have the combination of the two registers  310 ,  320 , register  340  containing the approximation corresponding to a vector (i.e., state) of dimension N=2 s N 0 . This requires log N=log N 0 +s qubits for its quantum mechanical representation. Step  350  represents a quantum mechanical system using the approximation obtained in register  340 . Step  360  represents the final state of the system  350 . 
         [0030]    Having described the embodiments of the invention, it should be apparent that various combinations of embodiments may be made or modifications added thereto as is known to those skilled in the art without departing from the spirit and scope of the invention.