The Prime state and its quantum relatives

D. García-Martín; E. Ribas; S. Carrazza; J.I. Latorre; G. Sierra

doi:10.22331/q-2020-12-11-371

The Prime state and its quantum relatives

D. García-Martín^1,2,3, E. Ribas², S. Carrazza^4,5, J.I. Latorre^2,5,6, and G. Sierra³

¹Barcelona Supercomputing Center (BSC), Barcelona, Spain.
²Dept. Física Quàntica i Astrofísica, Universitat de Barcelona, Barcelona, Spain.
³Instituto de Física Teórica, UAM-CSIC, Madrid, Spain.
⁴TIF Lab, Dipartimento di Fisica, Università degli Studi di Milano and INFN Milan, Milan, Italy.
⁵Quantum Research Centre, Technology Innovation Institute, Abu Dhabi, UAE.
⁶Center for Quantum Technologies, National University of Singapore, Singapore.

Published:	2020-12-11, volume 4, page 371
Eprint:	arXiv:2005.02422v3
Doi:	https://doi.org/10.22331/q-2020-12-11-371
Citation:	Quantum 4, 371 (2020).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The Prime state of $n$ qubits, ${|\mathbb{P}_n{\rangle}}$, is defined as the uniform superposition of all the computational-basis states corresponding to prime numbers smaller than $2^n$. This state encodes, quantum mechanically, arithmetic properties of the primes. We first show that the Quantum Fourier Transform of the Prime state provides a direct access to Chebyshev-like biases in the distribution of prime numbers. We next study the entanglement entropy of ${|\mathbb{P}_n{\rangle}}$ up to $n=30$ qubits, and find a relation between its scaling and the Shannon entropy of the density of square-free integers. This relation also holds when the Prime state is constructed using a qudit basis, showing that this property is intrinsic to the distribution of primes. The same feature is found when considering states built from the superposition of primes in arithmetic progressions. Finally, we explore the properties of other number-theoretical quantum states, such as those defined from odd composite numbers, square-free integers and starry primes. For this study, we have developed an open-source library that diagonalizes matrices using floats of arbitrary precision.

► BibTeX data

@article{GarciaMartin2020primestateits,
  doi = {10.22331/q-2020-12-11-371},
  url = {https://doi.org/10.22331/q-2020-12-11-371},
  title = {The {P}rime state and its quantum relatives},
  author = {Garc{\'{i}}a-Mart{\'{i}}n, D. and Ribas, E. and Carrazza, S. and Latorre, J.I. and Sierra, G.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {371},
  month = dec,
  year = {2020}
}

► References

[1] J.I. Latorre and G. Sierra, ``Quantum computation of prime number functions'', Quant. Inf. Comput. 14, 577 (2014).
https://dl.acm.org/doi/10.5555/2638682.2638685

[2] L.K. Grover, ``A fast quantum mechanical algorithm for database search'', Proc. STOC. May 1996, 212 (1996).
https://doi.org/10.1145/237814.237866

[3] B. Riemann, ``On the Number of Prime Numbers less than a Given Quantity'', Monatsberichte der Berliner Akademie November 1859, 671 (1859),.
https://www.claymath.org/sites/default/files/ezeta.pdf

[4] K. Walisch and D. Baugh, ``New confirmed $\pi(10^{27}$) prime counting function record'', Mersenne Forum (2015), https://github.com/kimwalisch/primecount.
https://github.com/kimwalisch/primecount

[5] G. Brassard, P. Høyer and A. Tapp, ``Quantum Counting'', Proc. 25th ICALP, LNCS 1443, Springer-Verlag, 820 (1998).
https://doi.org/10.1007/BFb0055105

[6] M. Rubinstein and P. Sarnak, ``Chebyshev’s Bias'', Exp. Math. 3, 173 (1994).
https://doi.org/10.1080/10586458.1994.10504289

[7] J.I. Latorre and G. Sierra, ``There is entanglement in the primes'', Quant. Inf. Comput. 15, 622 (2015).

[8] G.H. Hardy and J.E. Littlewood, ``Some Problems of 'Partitio Numerorum.' III. On the Expression of a Number as a Sum of Primes", Acta Math. 44, 1 (1923).
https://doi.org/10.1007/BF02403921

[9] We consider natural bi-partitions those that separate the first $m$ qubits and the remainder $n-m$ qubits, without any reordering.

[10] G. Mussardo, H. Giudici and J. Viti, ``The Coprime Quantum Chain", J. Stat. Mech. Theory Exp. 2017, 033104 (2017).
https://doi.org/10.1088/1742-5468/aa5bb4

[11] G. Mussardo, A. Trombettoni and Zhaon Zhang, ``Prime suspects in a Quantum Ladder'', arXiv:2005.01758 (2020).
arXiv:2005.01758

[12] F.V. Mendes and R.V. Ramos, ``Quantum Sequence States'', arXiv:1408.4838 (2014).
arXiv:1408.4838

[13] S. Carrazza, D. García-Martín and J.I. Latorre, Quantum-TII/qprime: Qprime v1.0.0 (May 2020). https://doi.org/10.5281/zenodo.3787043.
https://doi.org/10.5281/zenodo.3787043

[14] L. Miller. ``Riemann’s hypothesis and tests for primality'', J. Comput. Sys. Sci. 13, 300 (1976); M. O. Rabin. ``Probabilistic algorithm for testing primality'', J. Number Theory 12, 128 (1980).
https://doi.org/10.1016/0022-314X(80)90084-0

[15] M. Agrawal, N. Kayal and N. Saxena, ``Primes is in P'', Ann. Math. 160, 781 (2004).
https://doi.org/10.4007/annals.2004.160.781

[16] T.M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, New York (1976); G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers, Oxford Universiy Press, Oxford (1938).
https://doi.org/10.1080/00107510903184414

[17] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, New York (2011).
https://doi.org/10.1017/CBO9780511976667

[18] https://www.claymath.org/millennium-problems.
https://www.claymath.org/millennium-problems

[19] L. Schoenfeld, ``Sharper bounds for the Chebyshev functions $\theta(x)$ and $\psi(x)$. II", Math. Comput. 30, 337 (1976).
https://doi.org/10.2307/2005976

[20] A. Kitaev, ``Quantum measurements and the Abelian stabilizer problem'', arXiv:quant-ph/9511026 (1995); R. Cleve, A. Ekert, C. Macchiavello and M.Mosca, ``Quantum algorithms revisited'', Proc. R. Soc. London A 454, 339 (1998).
https://doi.org/10.1098/rspa.1998.0164
arXiv:quant-ph/9511026

[21] S. Aaronson, ``Quantum Lower Bound for Approximate Counting Via Laurent Polynomials'', arXiv:1808.02420 (2018); S. Aaronson and P. Rall, ``Quantum Approximate Counting, Simplified'', SOSA20, 24 (2020).
https://doi.org/10.1137/1.9781611976014.5
arXiv:1808.02420

[22] Meissel, ``Über die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen'', Math. Ann. 2, 636 (1870).
https://doi.org/10.1007/BF01444045

[23] D.H. Lehmer, ``On the exact number of primes less than a given limit'', Illinois J. Math. 3, 381 (1959).
https://doi.org/10.1215/ijm/1255455259

[24] J.C. Lagarias, V.S. Miller and A.M. Odlyzko, ``Computing $\pi(x)$: the Meissel-Lehmer method'', Math. Comp. 44, 573 (1985).
https://doi.org/10.2307/2007973

[25] M. Deléglise and J. Rivat, ``Computing $\pi(x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method'', Math. Comp. 65, 235 (1996).
https://doi.org/10.1090/S0025-5718-96-00674-6

[26] X. Gourdon, ``Computation of $\pi(x)$: improvements to the Meissel, Lehmer, Lagarias, Miller, Odllyzko, Deléglise and Rivat method'', unpublished (2001). As cited in Ref. pi(x).

[27] J.C. Lagarias and A.M. Odlyzko, ``Computing $\pi(x)$: an Analytic Method'', J. Algorithms 8, 173 (1987).
https://doi.org/10.1016/0196-6774(87)90037-X

[28] P. Shor, ``Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer'', SIAM J. Sci. Statist. Comput. 26, 1484 (1997).
https://doi.org/10.1137/S0097539795293172

[29] A. Peruzzo, J. McClean, P. Shadbolt, M.H. Yung, X.Q. Zhou, P.J. Love, A. Aspuru-Guzik and J. L. O'Brien, ``A variational eigenvalue solver on a quantum processor'', Nat. Commun. 5, 4213 (2013).
https://doi.org/10.1038/ncomms5213

[30] E. Farhi, J. Goldstone and S. Guttman, ``A Quantum Approximate Optimization Algorithm'', arXiv:1411.4028 (2014).
arXiv:1411.4028

[31] If $p_i$ is the exact probability, and $\hat{p}_i$ the estimate of it, the statistical additive error is defined as $p_i=\hat{p}_i+\epsilon_i$, and the multiplicative error as $\hat{p}_i=(1+\varepsilon_i) p_i$.

[32] G. Brassard, P. Høyer, M. Mosca and A. Tapp, ``Quantum Amplitude Amplification and Estimation'', Contemp. Math. 305, 53 (2002).
https://doi.org/10.1090/conm/305

[33] A. Montanaro, ``Quantum speedup of Monte Carlo methods'', Proc. R. Soc. A 471, 20150301 (2015).
https://doi.org/10.1098/rspa.2015.0301

[34] M. Deléglise, P. Dusart and X.F. Roblot, ``Counting primes in residue classes'', Math. Comp. 73, 1565 (2004).
https://doi.org/10.1090/S0025-5718-04-01649-7

[35] http://mathworld.wolfram.com/ ModularPrimeCountingFunction.html.
http://mathworld.wolfram.com/ModularPrimeCountingFunction.html

[36] I. Bengtsson and K. Zyczkowski, Geometry of quantum states: an introduction to quantum entanglement, Cambridge University Press, New York (2018).
https://doi.org/10.1017/CBO9780511535048

[37] We thank Alonso Botero for noticing this fact.

[38] J.P. Keating and D.J. Smith, ``Twin prime correlations from the pair correlation of Riemann zeros'', J. Phys. A: Math. Theor. 52, 365201 (2019).

[39] E. B. Bogomolny and J. P. Keating, ``Gutzwiller's trace formula and spectral statistics: beyond the diagonal approximation", Phys. Rev. Lett. 77, 1472 (1996).
https://doi.org/10.1103/PhysRevLett.77.1472

[40] M. V. Berry and J. P. Keating, ``The Riemann zeros and eigenvalue asymptotics", SIAM Rev. 41, 236 (1999).
https://doi.org/10.1137/S0036144598347497

[41] H.G. Gadiyar and R. Padma, ``Ramanujan-Fourier series, the Wiener-Khintchine formula and the distribution of prime pairs'', Phys. A 269, 503 (1999).
https://doi.org/10.1016/S0378-4371(99)00171-5

[42] H. G. Gadiyar and R. Padma, ``Linking the circle and the sieve: Ramanujan-Fourier series", arXiv:math/0601574 (2006).
arXiv:math/0601574

[43] A. Rényi, ``On measures of information and entropy", Proceedings of the fourth Berkeley Symposium on Mathematics, Statistics and Probability 1960, 547 (1961).

[44] D.N. Page, ``Average entropy of a subsystem'', Phys. Rev. Lett. 71, 129 (1993).
https://doi.org/10.1103/PhysRevLett.71.1291

[45] T. Grover and M.P.A. Fisher, ``Entanglement and the Sign Structure of Quantum States'', Phys. Rev. A 92, 042308 (2015).
https://doi.org/10.1103/PhysRevA.92.042308

[46] J.I. Latorre, ``Entanglement entropy and the simulation of quantum mechanics'', J. Phys. A: Math. Theor. 40, 6689 (2007).

[47] P. Sarnak, ``Three lectures on the Möbius function, randomness, and dynamics'', online notes (2011), http://publications.ias.edu/sarnak/paper/512.
http://publications.ias.edu/sarnak/paper/512

[48] F. Cellarosi and Y. G. Sinai, ``Ergodic Properties of Square-Free Numbers", arXiv:1112.4691 (2011).
arXiv:1112.4691

[49] L. Amico, R. Fazio, A. Osterloh and V. Vedral, ``Entanglement in Many-Body Systems'', Rev. Mod. Phys. 80, 517 (2008).
https://doi.org/10.1103/RevModPhys.80.517

[50] E. Grosswald and F. J. Schnitzer, ``A class of modified $\zeta$ and L-functions'', Pacific. Jour. Math. 74, 357 (1978).
https://doi.org/10.2140/pjm.1978.74.357

[51] D. R. Ward, ``Some Series Involving Euler's Function'', J. London Math. Soc. 2, 210 (1927).
https://doi.org/10.1112/jlms/s1-2.4.210

[52] J. H. van Lint and H.E. Richert, ``Über die Summe $\sum_n \mu^2(n)/ \varphi(n)$'', Nederl. Akad. Wetensch.` Proc. Ser. A 67, Indag. Math. 26, 582 (1964).

Cited by

[1] V. Marić, S. M. Giampaolo, and Fabio Franchini, "Fate of local order in topologically frustrated spin chains", Physical Review B 105 6, 064408 (2022).

[2] A. L. M. Southier, Lea F. Santos, P. H. Souto Ribeiro, and A. D. Ribeiro, "Identifying primes from entanglement dynamics", Physical Review A 108 4, 042404 (2023).

[3] Giuseppe Mussardo, Andrea Trombettoni, and Zhao Zhang, "Prime Suspects in a Quantum Ladder", Physical Review Letters 125 24, 240603 (2020).

The above citations are from Crossref's cited-by service (last updated successfully 2023-11-29 19:09:51) and SAO/NASA ADS (last updated successfully 2023-11-29 19:09:52). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.