Quantum Algorithms II

Peter J. Love, Bruce M. Boghosian

Masanori Ohya, Igor Vasil'evich Volovich

Gerardo G. Fogel

This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.

Masanori Ohya, Igor Vasil'evich Volovich

Oleksandr V. Marchukov, Andrea Trombettoni, Giuseppe Mussardo +1 more

The famous Goldbach conjecture states that any even natural number N N greater than 2 2 can be written as the sum of two prime numbers p^{\text{(I)}} p (I) and p^{\text{(II)}} p (II) . In this article we propose a quantum analogue device that solves the following problem: given a small prime p^{\text{(I)}} p (I) , identify a member N N of a \mathcal{N} 𝒩 -strong set even numbers for which N-p^{\text{(I)}} N − p (I) is also a prime. A table of suitable large primes p^{\text{(II)}} p (II) is assumed to be known a priori. The device realizes the Grover quantum search protocol and as such ensures a \sqrt{\mathcal{N}} 𝒩 quantum advantage. Our numerical example involves a set of 51 even numbers just above the highest even classical-numerically explored so far [T. O. e Silva, S. Herzog, and S. Pardi, Mathematics of Computation 83, 2033 (2013)]. For a given small prime number p^{\text{(I)}}=223 p (I) = 223 , it took our quantum algorithm 5 steps to identify the number N=4× 10^{18}+14 N = 4 × 10 18 + 14 as featuring a Goldbach partition involving 223 223 and another prime, namely p^{\text{(II)}}=4× 10^{18}-239 p (II) = 4 × 10 18 − 239 . Currently, our algorithm limits the number of evens to be tested simultaneously to \mathcal{N} \sim \ln(N) <