SciPost Submission Page

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

by Oleksandr V. Marchukov, Andrea Trombettoni, Giuseppe Mussardo, Maxim Olshanii

Submission summary

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^{\text{(I)}}$ and $p^{\text{(II)}}$. In this article we propose a quantum analogue device that solves the following problem: given a small prime $p^{\text{(I)}}$, identify a member $N$ of a $\mathcal{N}$-strong set even numbers for which $N-p^{\text{(I)}}$ is also a prime. A table of suitable large primes $p^{\text{(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 {\bf 83}, 2033 (2013)]. For a given small prime number $p^{\text{(I)}}=223$, it took our quantum algorithm 5 steps to identify the number $N=4\times 10^{18}+14$ as featuring a Goldbach partition involving $223$ and another prime, namely $p^{\text{(II)}}=4\times 10^{18}-239$. Currently, our algorithm limits the number of evens to be tested simultaneously to $\mathcal{N} \sim \ln(N)$: larger samples will typically contain more than one even that can be partitioned with the help of a given $p^{\text{(I)}}$, thus leading to a departure from the Grover paradigm.

Author comments upon resubmission

List of changes