  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$ and $p'$,
with $p \, , p'$ referred to as a Goldbach pair. In this article we present a
quantum analogue protocol for detecting -- given a even number $N$ -- the
existence of a so-called minimal Goldbach partition $N=p+p'$ with $p\equiv
p_{\rm min}(N)$ being the so-called minimal Goldbach prime, i.e. the least
possible value for $p$ among all the Goldbach pairs of $N$. The proposed
protocol is effectively a quantum Grover algorithm with a modified final stage.
Assuming that an approximate smooth upper bound $\mathcal{N}(N)$ for the number
of primes less than or equal to $ p_{\rm min}(N)$ is known, our protocol will
identify if the set of $\mathcal{N}(N)$ lowest primes contains the minimal
Goldbach prime in approximately $\sqrt{\mathcal{N}(N)}$ steps, against the
corresponding classical value $\mathcal{N}(N)$. In the larger context of a
search for violations of Goldbach's conjecture, the quantum advantage provided
by our scheme appears to be potentially convenient. E.g., referring to the
current state-of-art numerical search for violations of the Goldbach conjecture
among all even numbers up to $N_{\text{max}} = 4\times 10^{18}$ [T. O. e Silva,
S. Herzog, and S. Pardi, Mathematics of Computation 83, 2033 (2013)], a quantum
realization of the search would deliver a quantum advantage factor of
$\sqrt{\mathcal{N}(N_{\text{max}})} \approx 37$ and it will require a Hilbert
space spanning $\mathcal{N}(N_{\text{max}}) \approx 1376$ basis states.
