Achieving quantum advantage in a search for a violations of the Goldbach conjecture, with driven atoms in tailored potentials

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 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×1018+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.