Achieving quantum advantage in a search for a minimal Goldbach partition with driven atoms in tailored potentials

• URL: http://arxiv.org/abs/2404.00517v2
• Date: Tue, 30 Jul 2024 02:14:00 GMT
• Title: Achieving quantum advantage in a search for a minimal Goldbach partition with driven atoms in tailored potentials
• Authors: Oleksandr V. Marchukov, Andrea Trombettoni, Giuseppe Mussardo, Maxim Olshanii,
• Abstract summary: 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'$. 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'$.
• Score: 15.236546465767026
• License: http://creativecommons.org/licenses/by/4.0/
• 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$ 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.

Related papers

• Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
  Estimating the trace of powers of identical $k$ density matrices is a crucial subroutine for many applications. Inspired by the Newton-Girard method, we developed an algorithm that uses only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates.
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• A generic quantum Wielandt's inequality [0.9975341265604578]
  It is conjectured that $k$ should be of order $mathcalO(n2)$ in general. We provide a generic version of quantum Wielandt's inequality, which gives the optimal length with probability one. We shed new light on a long-standing open problem for Projected Entangled Pair State.
  arXiv  Detail & Related papers  (2023-01-19T18:57:32Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  Given a quantum state $varrho$ and a quantifier $cal E(varrho), it is a hard task to determine $cal E(varrhootimes N)$. We show that the one shot distillable entanglement of certain spherically symmetric states can be quantitatively approximated by such an augmented additivity.
  arXiv  Detail & Related papers  (2022-07-31T00:23:10Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Divide-and-conquer verification method for noisy intermediate-scale quantum computation [0.0]
  noisy intermediate-scale quantum computations can be regarded as logarithmic-depth quantum circuits on a sparse quantum computing chip. We propose a method to efficiently verify such noisy intermediate-scale quantum computation.
  arXiv  Detail & Related papers  (2021-09-30T08:56:30Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Tight Quantum Time-Space Tradeoffs for Function Inversion [7.895232155155041]
  We show that even with quantum advice, $ST + T2 = tildeOmega(N)$ is required for an algorithm to invert random functions. We also prove quantum time-space lower bounds for Yao's box problem and salted cryptography.
  arXiv  Detail & Related papers  (2020-06-10T04:23:26Z)
• Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
  We study the problem of finding $K$ collision pairs in a random function $f : [N] rightarrow [N]$ by using a quantum computer. We prove that the number of queries to the function must increase significantly when the size of the available memory is limited.
  arXiv  Detail & Related papers  (2020-02-20T18:48:51Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.