Patent Publication Number: US-8527437-B1

Title: Method for driving starting quantum state to target one

Description:
CROSS REFERENCES TO RELATED APPLICATIONS 
     Not Applicable 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH AND DEVELOPMENT 
     Not Applicable 
     REFERENCE TO COMPUTER PROGRAM LISTING 
     A computer program listing appendix contained in a single compact disc (CD) is included herewith and incorporated by reference herein. The CD is in IBM-PC format and was burned with a computer running the Windows 98 operating system. The CD contains a single file titled quibbs1-4.txt, in ASCII format, of size 512 KBytes, burnt onto the CD on Oct. 3, 2010. 
     BACKGROUND OF THE INVENTION 
     (A) Field of the Invention 
     The invention relates to a quantum computer; that is, an array of quantum bits (called qubits). More specifically, it relates to methods for using a classical computer to generate a sequence of operations that can be used to operate a quantum computer. 
     (B) Description of Related Art 
     Henceforth, we will allude to certain references by codes. Here is a list of codes and the references they will stand for.
     Ref.GWiki is http://en.wikipedia.org/wiki/Grover&#39;s_algorithm   Ref.GOrig is “Quantum Mechanics Helps in Searching for a Needle in a Haystack”, by Lov. K Grover, in Phys. Rev. Letters Vol. 79, Num. 2, pp. 325-328, published on July of 1997.   Ref.GPat is “Fast Quantum Mechanical Algorithms”, U.S. Pat. No. 6,317,766, by Lov K. Grover   Ref.TexasPat is “Quantum Circuit Design for Grover&#39;s Algorithm”, U.S. Pat. No. 7,028,275, by G. Chen, Z. Diao, M. Zubairy   Ref.GPi/3 is “A Different Kind of Quantum Search” by Lov Grover, arXiv:quant-ph/0503205   Ref.Toy “Multi-phase matching in the Grover algorithm” by F. M. Toyama, W. van Dijk, Y. Nogami, M. Tabuchi, Y. Kimura, arXiv:0801.2956   Ref.TucAfga is “An Adaptive, Fixed-Point Version of Grover&#39;s Algorithm” by R. R. Tucci, arXiv:1001.5200.   Ref.TucQuibbs2 is “Quibbs, a Code Generator for Quantum Gibbs Sampling” by R. R. Tucci, arXiv:1004.2205   

     This invention deals with quantum computing. A quantum computer is an array of quantum bits (qubits) together with some hardware for manipulating those qubits. Quantum computers with several hundred qubits have not been built yet. However, once they are built, it is expected that they will perform certain calculations much faster that classical computers. A quantum computer follows a sequence of elementary operations. The operations are elementary in the sense that they act on only a few qubits (usually 1, 2 or 3) at a time. Henceforth, we will sometimes refer to sequences as products and to operations as operators, instructions, steps or gates. Furthermore, we will abbreviate the phrase “sequence of elementary operations” by “SEO”. SEOs are often represented as quantum circuits. In the quantum computing literature, the term “quantum algorithm” usually means a SEO for quantum computers for performing a desired calculation. Some quantum algorithms have become standard, such as those due to Deutsch-Jozsa, Shor and Grover. One can find on the Internet many excellent expositions on quantum computing. 
     Henceforth, we will abbreviate the phrase “Grover&#39;s Algorithm” by GA. 
     The original GA (first proposed in Ref.GOrig, patented in Ref.GPat, discussed in Ref.GWiki) has turned out to be very useful in quantum computing. Many quantum algorithms rely on it. It drives a starting state towards a target state by performing a sequence of equal steps. By this we mean that each step is a rotation about the same fixed axis and by the same small angle. Because each step is by the same angle, the algorithm overshoots past the target state once it reaches it. 
     About 8 years after Ref.GOrig, Grover proposed in Ref.GPi/3 a “pi/3 fixed-point” algorithm which uses a recursion relation to define an infinite sequence of gradually diminishing steps that drives the starting state to the target state with absolute certainty. 
     Other workers have pursued what they refer to as a phase matching approach to GA. Ref.Toy is a recent contribution to that approach, and has a very complete review of previous related contributions. 
     In this invention, we describe what we call an Adaptive, Fixed-point, Grover&#39;s Algorithm (AFGA, like Afgha-nistan, but without the h). 
     Our AFGA resembles the original GA in that it applies a sequence of rotations about the same fixed axis, but it differs from the original GA in that the angle of successive rotations is different. Thus, unlike the original GA, our AFGA performs a sequence of unequal steps. 
     Our AFGA resembles the pi/3 GA in that it is a fixed-point algorithm that converges to the target, but it differs from the pi/3 GA in its choice of sequence of unequal steps. 
     Our AFGA resembles the phase-matching approach of Ref.Toy, but their algorithm uses only a finite number of distinct “phases”, whereas our AFGA uses an infinite number. Unlike AFGA, the Ref.Toy algorithm is not guaranteed to converge to the target so it is not a true fixed-point algorithm. 
     Many quantum algorithms require a version of GA that works even if there is a large overlap between the starting state and the target state. The original GA only works properly if that overlap is very small. AFGA and the pi/3 GA do not have this small overlap limitation. However, AFGA is significantly more efficient than the pi/3 GA. 
     Previous patents Ref.GPat and Ref.TexasPat are based on the original GA. The inventor Tucci believes that the present invention is an important improvement on those past patents because it is based on AFGA rather than on the original GA. As explained already, contrary to the original GA, AFGA converges with absolute certainty to the target state, and it does not require a small overlap between the starting and target states. 
     The inventor Tucci first published a description of this invention on Jan. 28, 2010, in Ref.TucAfga. Later, Tucci discussed an application of this invention in Ref.TucQuibbs2. 
     BRIEF SUMMARY OF THE INVENTION 
     We refer to the algorithm of Ref.TucAfga as AFGA. A preferred embodiment of this invention is computer program that runs on a classical computer and acts as an AFGA code generator. By this we mean that it generates a SEO (Sequence of Elementary Operations) which implements AFGA, and can be used to operate a quantum computer. The SEO drives as near as desired, in an efficient way, a starting quantum state to a target one. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows a block diagram of a classical computer feeding data to a quantum computer. 
         FIG. 2  shows a quantum circuit generated by an AFGA code generator. 
         FIG. 3  shows Octave/Matlab code for a program called afga.m which calculates the sequence {α j } j=0   ∞ . 
         FIG. 4  shows Octave/Matlab code for functions afga_rot.m and afga_step.m which are called by the program given in  FIG. 3 . 
         FIG. 5  shows a variation of the quantum circuit of  FIG. 2  which uses approximate gates. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     This section describes a preferred embodiment of the invention and other possible embodiments of the invention. 
     A preferred embodiment of this invention is computer program that runs on a classical computer and acts as an AFGA code generator (or, equivalently, as a quantum circuit generator or as a SEO generator). By this we mean that it generates a SEO which implements AFGA and can be used to operate a quantum computer. The SEO drives as near as desired, in an efficient way, a starting quantum state to a target one. 
     This patent includes a Compact Disc with source code for a computer program, written in Java, called Quibbs1.4. Quibbs is described in Ref.TucQuibbs2. Quibbs generates a SEO which can be used to operate a quantum computer and thereby induce it to sample a probability distribution. The Quibbs source code contains a lot of code which is irrelevant to this invention, but it does contain in it an AFGA code generator which can be taken as an example of a useful application of this invention. 
     Henceforth we will say |v&gt; is a unit vector if &lt;v|v&gt;=1. Consider two unit vectors |v 1 &gt; and |v 2 &gt; and let D=∥v 1 &gt;−|v 2 )| 2 . We will say that |v 1 &gt; and |v 2 &gt; are approximately equal to each other if D/4 is significantly smaller than one. We will say that they are equal if D=0. We will say that |v 1 &gt; and |v 2 &gt; are equal (respectively, approximately equal) up to a phase factor if there is some real number a such that |v 1 &gt; and e iα |v 2 &gt; are equal (respectively, approximately equal). We will say that |v 1 &gt; is an approximate eigenvector of an operator Ω if there exists a vector |v 2 &gt; which is an eigenvector of Ω and |v 1 &gt; is approximately equal to |v 2 &gt;. We will say that two unitary operators Ω 1  and Ω 2  acting on the same vector space V of dimension dim(V) are approximately equal if trace[(Ω 1 −Ω 2 )(Ω 1   † −Ω 2   † )]/[4dim(V)] is significantly smaller than one. 
     Consider any operator of the form Ω=exp(iα|v&gt;&lt;v|) where α is a real number and where |v&gt; is a unit vector. Note that Ω has only two distinct eigenvalues, namely exp(iα) and 1. In fact, |v&gt; is an eigenvector of Ω with eigenvalue exp(iα), whereas any vector orthogonal to |v&gt; has eigenvalue 1. The original GA (the one in Ref.GOrig) uses operators of the form Ω, with α equal to π or −π. The pi/3 GA (the one in Ref.GPi/3) uses operators of the form Ω, with α equal to π/3 or −π/3. AFGA, on the other hand, uses operators of the form Ω, with α equal to α j  or Δλ where α j  tends to zero as j tends to infinity. 
       FIG. 1  is a block diagram of a classical computer feeding data to a quantum computer. Box  100  represents a classical computer. This invention includes software that runs inside Box  100 . Box  100  comprises sub-boxes  101 ,  102 ,  103 . Box  101  represents input devices, such as a mouse or a keyboard. Box  102  comprises the CPU, internal and external memory units. Box  102  does calculations and stores information. Box  103  represents output devices, such as a printer or a display screen. Box  105  represents a quantum computer, comprising an array of quantum bits and some hardware for manipulating the state of those qubits. 
     The remainder of this section is divided into 2 subsections. Subsection (A) describes a quantum circuit generated by an AFGA code generator. Subsection (B) discusses other possible embodiments of the invention. 
     (A) Quantum Circuit 
     In this section, we describe a quantum circuit generated by an AFGA code generator. For a more detailed description of the circuit, see Ref.TucAfga. 
       201  in  FIG. 2  is a quantum circuit generated by an AFGA code generator. Let N B  and N ste  be some positive integers. Circuit  201  starts off in an initial state |s′&gt; of N B  qubits. This initial state is then subjected to N ste +1 operators (“ste” stands for steps). We will next proceed to describe the nature of each of these N ste +1 operators. 
     Each of the boxes in circuit  201  is a product of two operators, R beg   (j)  and R tar . “beg” stands for “beginning” and “tar” for “target”. 
     Let Δλ be a real number between 0 and π, and let {α j } j=0   ∞  be a sequence of real numbers. Δλ can be selected by the user. Ref.TucAfga explains how to calculate the angles α j  and  FIG. 3  together with  FIG. 4  show an Octave/Matlab program that calculates them explicitly. 
     Equation  202  defines R beg   (j)  in terms of the state |s′&gt; and the angles α j . Equation  203  defines R tar  in terms of the state |t&gt; and the angle Δλ. Equation  204  defines an angle γ which characterizes the overlap between states |s′&gt; and |t&gt;. γ must be in the interval [0,π]. It cannot be precisely π, or else |s′&gt; and |t&gt; will be exactly orthogonal in which case AFGA won&#39;t work. Equation  205  stipulates that the state |FIN&gt; defined by Equation  201  must be approximately equal (up to a phase factor e iα ) to state |t&gt;. 
       FIG. 3  shows Octave/Matlab code for a program called afga.m.  FIG. 4  shows Octave/Matlab code for functions afga_rot.m and afga_step.m which are called by the program of afga.m. The first 3 lines of afga.m instantiate its 3 input parameters:
     (a) g0_degs=γ in degrees   (b) del_lam_degs=Δλ in degrees   (c) num_steps=N ste      

     Each time afga.m runs successfully, it outputs α 0 ,α 1 , . . . , α N     ste   . It also outputs other quantities. For a detailed description of all the outputs of afga.m, see Ref.TucAfga. 
     (B) Other Embodiments 
     In this section, we describe other possible embodiments of the invention. 
       FIG. 5  shows an embodiment of the invention which is similar to the one in  FIG. 2 . Let c be a positive integer.  201  of embodiment  FIG. 2  applies a sequence of N ste +1 operators to a state |s′&gt; of N B  qubits. On the other hand,  501  of embodiment  FIG. 5  applies a sequence of N ste +1 operators to a state of c+N B  qubits which is a tensor product of state |0&gt; for the top c qubits and state |s′&gt; for the bottom N B  qubits. The extra c auxiliary qubits are used as scratch space. The Quibbs1.4 program (whose source code is in the Compact Disc included with this patent) in fact comprises an implementation of the embodiment of  FIG. 5 . 
     Each of the boxes in circuit  501  is a product of two operators, {tilde over (R)} beg   (j)  and {tilde over (R)} tar . According to equation  502 , {tilde over (R)} beg   (j)  is approximately equal to an operator which acts as the identity on the top c qubits and the operator R beg   (j)  defined in  202  which acts only on the bottom N B  qubits. Likewise, according to Equation  503 , {tilde over (R)} tar  can be approximated by an operator which acts as the identity on the top c qubits and the operator R tar  defined in  203  which acts only on the bottom N B  qubits. Equation  504  stipulates that the state defined by Equation  501  must be approximately equal (up to a phase factor) to a state which is a tensor product of |0&gt; for each of the top c qubits and |t&gt; for the bottom N B  qubits. 
     As is done in Quibbs1.4, the operators {tilde over (R)} beg   (j)  and {tilde over (R)} tar  can be expressed as a SEO. 
     So far, we have described some exemplary preferred embodiments of this invention. Those skilled in the art will be able to come up with many modifications to the given embodiments without departing from the present invention. Thus, the inventor wishes that the scope of this invention be determined by the appended claims and their legal equivalents, rather than by the given embodiments.