SciPost logo

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

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

SciPost Phys. Core 8, 074 (2025) · published 28 October 2025

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 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× 10^{18}+14$ as featuring a Goldbach partition involving $223$ and another prime, namely $p^{\text{(II)}}=4× 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.

Authors / Affiliations: mappings to Contributors and Organizations

See all Organizations.
Funders for the research work leading to this publication