Abstract
The famous Goldbach conjecture states that any even natural number N greater than 2 can be written as the sum of two prime numbers p^(I) and p^(II). In this article we propose a quantum analogue device that solves the following problem: given a small prime p^(I), identify a member N of a N-strong set even numbers for which N-p^(I) is also a prime. A table of suitable large primes p^(II) is assumed to be known a priori. The device realizes the Grover quantum search protocol and as such ensures a √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 {\bf 83}, 2033 (2013)]. For a given small prime number p^(I)=223, it took our quantum algorithm 5 steps to identify the number N=4× 10¹⁸+14 as featuring a Goldbach partition involving 223 and another prime, namely p^(II)=4× 10¹⁸-239. Currently, our algorithm limits the number of evens to be tested simultaneously to N ∼ ln(N): larger samples will typically contain more than one even that can be partitioned with the help of a given p^(I), thus leading to a departure from the Grover paradigm.