Systems and methods for quantum global optimization

This Application claims the benefit of, and priority under 35 U.S.C. § 119(e) to, U.S. Provisional Patent Application No. 62/750,460, entitled “Quantum Walk Enhanced Grover Search Algorithm for Global Optimization on Quantum Computer,” filed Oct. 25, 2018, the contents of which are hereby incorporated by reference herein in their entirety as if fully set forth below.

The presently disclosed subject matter relates generally to systems and methods for quantum global optimization and, more particularly, to systems and methods for enhancing the Grover Search Algorithm through continuous-time quantum walks on a quantum computer.

In the past decade, quantum computation has been used to solve various scientific and engineering problems. Quantum computers have been used to improve both time and space efficiency. One of the significant breakthroughs in quantum computation involves Grover's Search algorithm for unsorted database research, which can improve the computational efficiency by optimizing the number of Grover rotations.

Despite these advantages, there is another aspect of the search efficiency, which is the threshold functional value. The threshold is important in convergence speed because it determines the number of solutions out of a total of possibilities in the discretized solution space.

Accordingly, there is a need for improved systems and methods that improve global optimization, and more specifically involve the threshold functional value in performing a search with Grover Search algorithm.

Aspects of the disclosed technology include systems and methods for predicting survival rates of a prospective organ recipient. Consistent with the disclosed embodiments, the methods may include a quantum computer, a quantum computer emulator, a quantum transistor, a fabric of programmable elements, a support circuitry, a memory, and/or one or more databases. One exemplary method may include receiving a search request comprising an input. The method may include determining an amount of rotations necessary to perform the search request with a Grover Search algorithm. Further, the method may determine that the amount of rotations is less than a predefined amount. Then, the method may generate one or more quantum walks, which the method may be used to replace the rotations in the Grover Search algorithm. Next, the method may include generating a global optimization algorithm based on the Grover search algorithm and the one or more quantum walks. The method may further execute the global optimization algorithm to identify the input.

In some embodiments, identifying the input with the global optimization algorithm may have a first computational cost.

In some embodiments, the method may further include estimating a second computational cost for identifying the input using the Grover Search algorithm.

According to some embodiments, the first computational cost is less than the second computational cost.

In some embodiments, generating the one or more quantum walks may involve determining a functional integral by applying an equation (9) of:

F n , 0 = ∑ l = 0 ∞ [ dq n , 0 ( l ) ⁢ e - i ⁢ r ⁡ ( 1 + i ) ⁢ b / Δ 2 - V n ⁢ r ( - 1 ) l ⁢ i n ] = ∑ l = 0 ∞ e - b ⁢ r / Δ 2 ⁢ ( b ⁢ r 2 ⁢ Δ 2 ) 2 ⁢ l + n l ! ⁢ ( n + l ) ! ⁢ e - i ⁢ τr ⁡ ( 1 + i ) ⁢ b / Δ 2 - V n ⁢ r ( - 1 ) l ⁢ i n = i n ⁢ e - ib ⁢ r / Δ 2 - V n ⁢ r ⁢ ∑ l = 0 ∞ ( - 1 ) l ⁢ ( b ⁢ r 2 ⁢ Δ 2 ) 2 ⁢ l + n l ! ⁢ ( n + l ) ! = i n ⁢ e - ib ⁢ r / Δ 2 - V n ⁢ r ⁢ J n ( b ⁢ r Δ 2 ) ,

where a unitary quantum walk operator (U) is represented as u jk =F (j−l),0 for a given space resolution Δ and a time resolution r.

In some embodiments, generating the one or more quantum walks may involve applying an equation of:

ψ j ( t + r ) = ∑ k F ( j - k ) , 0 ⁢ ψ k ( t ) ,

where t is a time, Ψ(t) is an amplitude associated with the time t, a first quantum walk from the one or more quantum walks is Ψ(t+r), and a j th element is represented as (j=1, . . . , N).

According to some embodiments, updating the j th element by applying the equation of:

ψ j ( t + r ) = F ( j - K ) , 0 = i ( j - K ) ⁢ e - ibr / Δ 2 - V j ⁢ r ⁢ J ( j - K ) ( b ⁢ r Δ 2 ) ,

where K is an index between 1 and N, Ψ K (t)=1.0, and Ψ k≠K (t)=0.0.

In some embodiments, determining a probability that j is observed by applying the equation of:

Pr ⁡ ( x = j ) = ψ j * ( t + r ) ⁢ ψ j ( t + r ) = C 0 ⁢ e - 2 ⁢ V j ⁢ r ⁢ J ( j - K ) 2 ( b ⁢ r Δ 2 ) ,

where C 0 is a

normalization factor that ensures that Σ j=1 N Pr(x=j)=1.

In some embodiments.

Rc= [0,0,0,0,1,1,0,1,1,2,1,2,3,1,4,5,1,6,2,7,9,11,13,16,5,20,24,23,31,2,41,49,4,60,72,9,88,105,125,3,149,22,133,219]

is the amount of rotations necessary to perform the search request with the Grover Search algorithm.

In some embodiments, the global optimization algorithm is represented by:

In some embodiments, the global optimization algorithm may be executed by a quantum computer.

In some embodiments, the global optimization algorithm may be executed by a quantum computer emulator.

Another exemplary method may include receiving a search request comprising an input. The method may further include determining a plurality of rotations necessary to perform the search request with a Grover Search algorithm. Next, the method may generate one or more quantum walks based on the plurality of rotations. Then, the plurality of rotations in the Grover Search algorithm may be replaced with the one or more quantum walks. Further, the method may include generating a global optimization algorithm based on the Grover search algorithm and the one or more quantum walks. Then, the global optimization algorithm may be executed to identify the input

Further features of the disclosed design, and the advantages offered thereby, are explained in greater detail hereinafter with reference to specific embodiments illustrated in the accompanying drawings, wherein like elements are indicated be like reference designators.

Reference will now be made to the accompanying drawings, which are not necessarily drawn to scale, are incorporated into and constitute a portion of this disclosure, illustrate various implementations and aspects of the disclosed technology, and, together with the description, serve to explain the principles of the disclosed technology. In the drawings:

FIG. 1 is an example flow chart of a method for global optimization, in accordance with some examples of the present disclosure;

FIG. 2 is another example flow chart of a method for global optimization, in accordance with some examples of the present disclosure;

FIGS. 3A-B are graphs illustrating an average Probability Density Function (PDF) by blocked weighted bootstrap quantum walk (BBW-QW) algorithm and a blocked weighted bootstrap (BBW) algorithm, respectively, in accordance with some examples of the present disclosure;

FIGS. 4A-B are graphs illustrating typical PDF by a BBW-QW algorithm and typical BBW algorithm, respectively, in accordance with some examples of the present disclosure;

FIG. 5A is a graph illustrating the probability of success of with respect to the iterations, in accordance with some examples of the present disclosure;

FIG. 5B is a graph illustrating the probability of success of functional evaluations, in accordance with some examples of the present disclosure;

FIG. 5C is a graph illustrating the effect of domain size with respect to functional evaluations, in accordance with some examples of the present disclosure;

FIG. 6 is a graph illustrating the efficiency of various algorithms, in accordance with some examples of the present disclosure;

FIGS. 7A-B are graphs illustrating the average PDF by the BBW-QW algorithm and the average PDF by the BBW algorithm, respectively, in accordance with some examples of the present disclosure;

FIGS. 8A-B are graphs illustrating the probability of success of with respect to iterations and the probability of success of functional evaluations, respectively, in accordance with some examples of the present disclosure;

FIG. 9 is another graph illustrating the efficiency of various algorithms, in accordance with some examples of the present disclosure; and

FIGS. 10A-B are examples of a quantum computer in accordance with some examples of the present disclosure, in accordance with some examples of the present disclosure.

Some implementations of the disclosed technology will be described more fully with reference to the accompanying drawings. This disclosed technology can be embodied in many different forms, however, and should not be construed as limited to the implementations set forth herein. The components described hereinafter as making up various elements of the disclosed technology are intended to be illustrative and not restrictive. Many suitable components that would perform the same or similar functions as components described herein are intended to be embraced within the scope of the disclosed electronic devices and methods. Such other components not described herein can include, but are not limited to, for example, components developed after development of the disclosed technology.

It is also to be understood that the mention of one or more method steps does not imply that the methods steps must be performed in a particular order or preclude the presence of additional method steps or intervening method steps between the steps expressly identified.

Reference will now be made in detail to exemplary embodiments of the disclosed technology, examples of which are illustrated in the accompanying drawings and disclosed herein. Wherever convenient, the same references numbers will be used throughout the drawings to refer to the same or like parts.

FIG. 1 shows an example flow chart of a method 100 for global optimization that may be performed by a quantum computer and/or a quantum computer emulator. At 110 , the method may receive a search request that may include an input. At 120 , the amount of rotations necessary to perform the search request with a Grover Search algorithm may be determined. Further, at 130 , the method may determine that the amount of rotations is less than a predefined amount. After this determination, at 140 , one or more quantum walks may be generated. Then, at 150 , the rotations associated with the Grover search algorithm may be replaced with the one or more quantum walks. At 160 , the global optimization algorithm may be generated based on the Grover Search algorithm and the one or more quantum walks. At 170 , the global optimization algorithm may be executed by, for example, a quantum computer to identify the input.

FIG. 2 shows another example flow chart of a method 200 for global optimization that may also be performed by a quantum computer and/or a quantum computer emulator. At 210 , the method may receive a search request that may include an input. At 220 , a plurality of rotations necessary to perform the search request with a Grover Search algorithm may be determined. Further, at 230 , the method may generate one or more quantum walks based on the plurality of rotations. Then, at 240 , the rotations associated with the Grover search algorithm may be replaced with the one or more quantum walks. At 250 , the global optimization algorithm may be generated based on the Grover Search algorithm and the one or more quantum walks. At 260 , the global optimization algorithm may be executed by, for example, a quantum computer to identify the input.

FIGS. 3A-B illustrate an average Probability Density Function (PDF) by blocked weighted bootstrap quantum walk (BBW-QW) algorithm and a blocked weighted bootstrap (BBW) algorithm, respectively. As shown, the average PDF's over 20 runs of search may be compared between the proposed quantum walk Grover Search algorithm and the BBW algorithm, where the rotation threshold R 0 is 2. The typical PDF's for only one run of search by the two algorithms may be compared in FIGS. 4A-B . It may be shown that the PDF's are flat and close to the uniform distribution for few rotations in the BBW algorithm. In the proposed BBW-QW algorithm, they may be replaced by a sharper distribution after one step of quantum walk.

FIGS. 5A-B are graphs illustrating the differences between the BBW and the BBW-QW algorithms. FIG. 5C is a graph illustrating the efficiencies of the BBW and the BBW-Qw algorithm when the domain size varies. At the initial stage of search with few iterations, quantum walk may provide higher probabilities of success. For example, it may be shown that when R 0 =2, the difference between the BBW-QW and the BBW algorithms may be most significant. Further, the benefit of functional evaluations may also be seen at later stages of the search. It can also be seen that the efficiency of the BBW algorithms slightly decreases at the early stage as the domain size increases, whereas it may not change for the BBW-QW algorithm. Further, with about 50 evaluations, both BBW and BBW-QW algorithms may increase the probability of success to about 90%.

FIG. 6 is a graph illustrating the efficiency of various algorithms. More specifically, FIG. 6 illustrates how the quantum search algorithms may compare with traditional global optimization methods, the probabilities of successful search with respect to the number of functional evaluations in the BBW, BBW-QW, simulated annealing, and genetic algorithms (GA) for Rastrigin function. The results from the genetic algorithms with different populations sizes (e.g., 5, 25, and 50) and simulated annealing with different initial temperature (e.g., 100 and 1000) are shown. The optimal solution may be known at x=0. Further, when the distance between a located solution and the known optimum solution is less than a threshold value of 1.0×10 −4 , the search may be deemed a success. The threshold may be chosen to be compatible with the resolution used in the quantum algorithms as a result of the number of available qubits. Moreover, the number of iterations may affect the probability of success. Among the three population sizes, the population size of 25 is the best. Yet, it may be much less efficient than the quantum search algorithms. Similarly, the simulated annealing is not as efficient as the quantum search algorithms.

FIGS. 7A-B illustrate the results of the BBW-QW algorithm and the BBW algorithm is searching for Schwefel function where R 0 =0. Further, the efficiencies of the BBW and BBW-QW algorithms with different R 0 values are compared in FIGS. 8A-B . As shown by the graphs, the quantum research algorithms may perform more efficiently for the Schwefel function than for the Rastrigin function. The optimum solution may be found with the probability of one with only few iterations. As a result, the difference between the two algorithms may be relatively small.

FIG. 9 is another graph illustrating the efficiency of various algorithms. In particular, FIG. 9 compares the efficiencies of the BBW and BBW-QW algorithms for the Ackley function. Similar to the Rastrigin function, R 0 =2 may provide an improvement for the Schwefel function and the Ackley function. It should be noted that the rotational threshold R 0 may play a key role of efficiency for the BBW-QW algorithm compared to the BBW algorithm. For example, if R 0 is too large, more quantum walks (with additional functional evaluations) are applied during the search, which may decrease the efficiency of the search algorithm. The test results indicate that a threshold value of R 0 <2 may be good for the test functions. In general, the selection of the value R 0 may depend on the complexity of the objective function. If the function has more local optima or wells in the search domain, more quantum walks may be necessary. Therefore, a larger value of R 0 may need to be chosen.

FIGS. 10A-B are examples of a quantum computer in accordance with some examples of the present disclosure. The example architectures 1000 A and/or 1000 B may implement some or all aspects of the embodiments described herein. For example, the architectures 1000 A and/or 1000 B may perform the methods 100 and/or 200 . The architectures 1000 A and 1000 B may be a quantum computer or a quantum computer emulator. Therefore, the architectures 1000 A and/or 1000 B may include a quantum transistor, a fabric of programmable elements that may include a plurality of couplers and/or a plurality of qubits, a support circuitry, and/or a memory.

Throughout the specification and the claims, the following terms take at least the meanings explicitly associated herein, unless the context clearly dictates otherwise. The term “or” is intended to mean an inclusive “or.” Further, the terms “a,” “an,” and “the” are intended to mean one or more unless specified otherwise or clear from the context to be directed to a singular form.

In this description, numerous specific details have been set forth. It is to be understood, however, that implementations of the disclosed technology can be practiced without these specific details. In other instances, well-known methods, structures and techniques have not been shown in detail in order not to obscure an understanding of this description. References to “one embodiment,” “an embodiment,” “some embodiments,” “example embodiment,” “various embodiments,” “one implementation,” “an implementation,” “example implementation,” “various implementations,” “some implementations,” etc., indicate that the implementation(s) of the disclosed technology so described can include a particular feature, structure, or characteristic, but not every implementation necessarily includes the particular feature, structure, or characteristic. Further, repeated use of the phrase “in one implementation” does not necessarily refer to the same implementation, although it can.

As used herein, unless otherwise specified the use of the ordinal adjectives “first,” “second,” “third,” etc., to describe a common object, merely indicate that different instances of like objects are being referred to, and are not intended to imply that the objects so described must be in a given sequence, either temporally, spatially, in ranking, or in any other manner.

While certain implementations of the disclosed technology have been described in connection with what is presently considered to be the most practical and various implementations, it is to be understood that the disclosed technology is not to be limited to the disclosed implementations, but on the contrary, is intended to cover various modifications and equivalent arrangements included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.

This written description uses examples to disclose certain implementations of the disclosed technology, including the best mode, and also to enable any person skilled in the art to practice certain implementations of the disclosed technology, including making and using any devices or systems and performing any incorporated methods. The patentable scope of certain implementations of the disclosed technology is defined in the claims, and can include other examples that occur to those skilled in the art. Such other examples are intended to be within the scope of the claims if they have structural elements that do not differ from the literal language of the claims, or if they include equivalent structural elements with insubstantial differences from the literal language of the claims.