{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T17:08:42Z","timestamp":1781197722247,"version":"3.54.1"},"reference-count":52,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T00:00:00Z","timestamp":1607644800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>The Prime state of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> qubits, <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo stretchy=\"false\">|<\/mml:mo><\/mml:mrow><mml:msub><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">P<\/mml:mi><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msub><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo fence=\"false\" stretchy=\"false\">\u27e9<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math>, is defined as the uniform superposition of all the computational-basis states corresponding to prime numbers smaller than <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mn>2<\/mml:mn><mml:mi>n<\/mml:mi><\/mml:msup><\/mml:math>. 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 <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo stretchy=\"false\">|<\/mml:mo><\/mml:mrow><mml:msub><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"double-struck\">P<\/mml:mi><\/mml:mrow><mml:mi>n<\/mml:mi><\/mml:msub><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo fence=\"false\" stretchy=\"false\">\u27e9<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math> up to <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><mml:mo>=<\/mml:mo><mml:mn>30<\/mml:mn><\/mml:math> 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.<\/jats:p>","DOI":"10.22331\/q-2020-12-11-371","type":"journal-article","created":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T11:08:36Z","timestamp":1607684916000},"page":"371","source":"Crossref","is-referenced-by-count":7,"title":["The Prime state and its quantum relatives"],"prefix":"10.22331","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0693-1952","authenticated-orcid":false,"given":"D.","family":"Garc\u00eda-Mart\u00edn","sequence":"first","affiliation":[{"name":"Barcelona Supercomputing Center (BSC), Barcelona, Spain."},{"name":"Dept. F\u00edsica Qu\u00e0ntica i Astrof\u00edsica, Universitat de Barcelona, Barcelona, Spain."},{"name":"Instituto de F\u00edsica Te\u00f3rica, UAM-CSIC, Madrid, Spain."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"E.","family":"Ribas","sequence":"additional","affiliation":[{"name":"Dept. F\u00edsica Qu\u00e0ntica i Astrof\u00edsica, Universitat de Barcelona, Barcelona, Spain."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0079-6753","authenticated-orcid":false,"given":"S.","family":"Carrazza","sequence":"additional","affiliation":[{"name":"TIF Lab, Dipartimento di Fisica, Universit\u00e0 degli Studi di Milano and INFN Milan, Milan, Italy."},{"name":"Quantum Research Centre, Technology Innovation Institute, Abu Dhabi, UAE."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1702-7018","authenticated-orcid":false,"given":"J.I.","family":"Latorre","sequence":"additional","affiliation":[{"name":"Dept. F\u00edsica Qu\u00e0ntica i Astrof\u00edsica, Universitat de Barcelona, Barcelona, Spain."},{"name":"Quantum Research Centre, Technology Innovation Institute, Abu Dhabi, UAE."},{"name":"Center for Quantum Technologies, National University of Singapore, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3408-5682","authenticated-orcid":false,"given":"G.","family":"Sierra","sequence":"additional","affiliation":[{"name":"Instituto de F\u00edsica Te\u00f3rica, UAM-CSIC, Madrid, Spain."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2020,12,11]]},"reference":[{"key":"0","unstructured":"J.I. Latorre and G. Sierra, ``Quantum computation of prime number functions'', Quant. Inf. Comput. 14, 577 (2014)."},{"key":"1","doi-asserted-by":"publisher","unstructured":"L.K. Grover, ``A fast quantum mechanical algorithm for database search'', Proc. STOC. May 1996, 212 (1996).","DOI":"10.1145\/237814.237866"},{"key":"2","unstructured":"B. Riemann, ``On the Number of Prime Numbers less than a Given Quantity'', Monatsberichte der Berliner Akademie November 1859, 671 (1859),."},{"key":"3","unstructured":"K. Walisch and D. Baugh, ``New confirmed $\\pi(10^{27}$) prime counting function record'', Mersenne Forum (2015), https:\/\/github.com\/kimwalisch\/primecount."},{"key":"4","doi-asserted-by":"publisher","unstructured":"G. Brassard, P. H\u00f8yer and A. Tapp, ``Quantum Counting'', Proc. 25th ICALP, LNCS 1443, Springer-Verlag, 820 (1998).","DOI":"10.1007\/BFb0055105"},{"key":"5","doi-asserted-by":"publisher","unstructured":"M. Rubinstein and P. Sarnak, ``Chebyshev\u2019s Bias'', Exp. Math. 3, 173 (1994).","DOI":"10.1080\/10586458.1994.10504289"},{"key":"6","unstructured":"J.I. Latorre and G. Sierra, ``There is entanglement in the primes'', Quant. Inf. Comput. 15, 622 (2015)."},{"key":"7","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1007\/BF02403921"},{"key":"8","unstructured":"We consider natural bi-partitions those that separate the first $m$ qubits and the remainder $n-m$ qubits, without any reordering."},{"key":"9","doi-asserted-by":"publisher","unstructured":"G. Mussardo, H. Giudici and J. Viti, ``The Coprime Quantum Chain\", J. Stat. Mech. Theory Exp. 2017, 033104 (2017).","DOI":"10.1088\/1742-5468\/aa5bb4"},{"key":"10","doi-asserted-by":"crossref","unstructured":"G. Mussardo, A. Trombettoni and Zhaon Zhang, ``Prime suspects in a Quantum Ladder'', arXiv:2005.01758 (2020).","DOI":"10.1103\/PhysRevLett.125.240603"},{"key":"11","unstructured":"F.V. Mendes and R.V. Ramos, ``Quantum Sequence States'', arXiv:1408.4838 (2014)."},{"key":"12","doi-asserted-by":"publisher","unstructured":"S. Carrazza, D. Garc\u00eda-Mart\u00edn and J.I. Latorre, Quantum-TII\/qprime: Qprime v1.0.0 (May 2020). https:\/\/doi.org\/10.5281\/zenodo.3787043.","DOI":"10.5281\/zenodo.3787043"},{"key":"13","doi-asserted-by":"publisher","unstructured":"L. Miller. ``Riemann\u2019s 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).","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"14","doi-asserted-by":"publisher","unstructured":"M. Agrawal, N. Kayal and N. Saxena, ``Primes is in P'', Ann. Math. 160, 781 (2004).","DOI":"10.4007\/annals.2004.160.781"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1080\/00107510903184414"},{"key":"16","doi-asserted-by":"publisher","unstructured":"M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, New York (2011).","DOI":"10.1017\/CBO9780511976667"},{"key":"17","unstructured":"https:\/\/www.claymath.org\/millennium-problems."},{"key":"18","doi-asserted-by":"publisher","unstructured":"L. Schoenfeld, ``Sharper bounds for the Chebyshev functions $\\theta(x)$ and $\\psi(x)$. II\", Math. Comput. 30, 337 (1976).","DOI":"10.2307\/2005976"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1098\/rspa.1998.0164"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/1.9781611976014.5"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Meissel, ``\u00dcber die Bestimmung der Primzahlenmenge innerhalb gegebener Grenzen'', Math. Ann. 2, 636 (1870).","DOI":"10.1007\/BF01444045"},{"key":"22","doi-asserted-by":"publisher","unstructured":"D.H. Lehmer, ``On the exact number of primes less than a given limit'', Illinois J. Math. 3, 381 (1959).","DOI":"10.1215\/ijm\/1255455259"},{"key":"23","doi-asserted-by":"publisher","unstructured":"J.C. Lagarias, V.S. Miller and A.M. Odlyzko, ``Computing $\\pi(x)$: the Meissel-Lehmer method'', Math. Comp. 44, 573 (1985).","DOI":"10.2307\/2007973"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M. Del\u00e9glise and J. Rivat, ``Computing $\\pi(x)$: the Meissel, Lehmer, Lagarias, Miller, Odlyzko method'', Math. Comp. 65, 235 (1996).","DOI":"10.1090\/S0025-5718-96-00674-6"},{"key":"25","unstructured":"X. Gourdon, ``Computation of $\\pi(x)$: improvements to the Meissel, Lehmer, Lagarias, Miller, Odllyzko, Del\u00e9glise and Rivat method'', unpublished (2001). As cited in Ref. pi(x)."},{"key":"26","doi-asserted-by":"publisher","unstructured":"J.C. Lagarias and A.M. Odlyzko, ``Computing $\\pi(x)$: an Analytic Method'', J. Algorithms 8, 173 (1987).","DOI":"10.1016\/0196-6774(87)90037-X"},{"key":"27","doi-asserted-by":"publisher","unstructured":"P. Shor, ``Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer'', SIAM J. Sci. Statist. Comput. 26, 1484 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/ncomms5213"},{"key":"29","unstructured":"E. Farhi, J. Goldstone and S. Guttman, ``A Quantum Approximate Optimization Algorithm'', arXiv:1411.4028 (2014)."},{"key":"30","unstructured":"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$."},{"key":"31","doi-asserted-by":"publisher","unstructured":"G. Brassard, P. H\u00f8yer, M. Mosca and A. Tapp, ``Quantum Amplitude Amplification and Estimation'', Contemp. Math. 305, 53 (2002).","DOI":"10.1090\/conm\/305"},{"key":"32","doi-asserted-by":"publisher","unstructured":"A. Montanaro, ``Quantum speedup of Monte Carlo methods'', Proc. R. Soc. A 471, 20150301 (2015).","DOI":"10.1098\/rspa.2015.0301"},{"key":"33","doi-asserted-by":"publisher","unstructured":"M. Del\u00e9glise, P. Dusart and X.F. Roblot, ``Counting primes in residue classes'', Math. Comp. 73, 1565 (2004).","DOI":"10.1090\/S0025-5718-04-01649-7"},{"key":"34","unstructured":"http:\/\/mathworld.wolfram.com\/ ModularPrimeCountingFunction.html."},{"key":"35","doi-asserted-by":"publisher","unstructured":"I. Bengtsson and K. Zyczkowski, Geometry of quantum states: an introduction to quantum entanglement, Cambridge University Press, New York (2018).","DOI":"10.1017\/CBO9780511535048"},{"key":"36","unstructured":"We thank Alonso Botero for noticing this fact."},{"key":"37","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088%2F1751-8121%2Fab3521"},{"key":"38","doi-asserted-by":"publisher","unstructured":"E. B. Bogomolny and J. P. Keating, ``Gutzwiller's trace formula and spectral statistics: beyond the diagonal approximation\", Phys. Rev. Lett. 77, 1472 (1996).","DOI":"10.1103\/PhysRevLett.77.1472"},{"key":"39","doi-asserted-by":"publisher","unstructured":"M. V. Berry and J. P. Keating, ``The Riemann zeros and eigenvalue asymptotics\", SIAM Rev. 41, 236 (1999).","DOI":"10.1137\/S0036144598347497"},{"key":"40","doi-asserted-by":"publisher","unstructured":"H.G. Gadiyar and R. Padma, ``Ramanujan-Fourier series, the Wiener-Khintchine formula and the distribution of prime pairs'', Phys. A 269, 503 (1999).","DOI":"10.1016\/S0378-4371(99)00171-5"},{"key":"41","unstructured":"H. G. Gadiyar and R. Padma, ``Linking the circle and the sieve: Ramanujan-Fourier series\", arXiv:math\/0601574 (2006)."},{"key":"42","unstructured":"A. R\u00e9nyi, ``On measures of information and entropy\", Proceedings of the fourth Berkeley Symposium on Mathematics, Statistics and Probability 1960, 547 (1961)."},{"key":"43","doi-asserted-by":"publisher","unstructured":"D.N. Page, ``Average entropy of a subsystem'', Phys. Rev. Lett. 71, 129 (1993).","DOI":"10.1103\/PhysRevLett.71.1291"},{"key":"44","doi-asserted-by":"publisher","unstructured":"T. Grover and M.P.A. Fisher, ``Entanglement and the Sign Structure of Quantum States'', Phys. Rev. A 92, 042308 (2015).","DOI":"10.1103\/PhysRevA.92.042308"},{"key":"45","doi-asserted-by":"publisher","unstructured":"J.I. Latorre, ``Entanglement entropy and the simulation of quantum mechanics'', J. Phys. A: Math. Theor. 40, 6689 (2007).","DOI":"10.1088%2F1751-8113%2F40%2F25%2Fs13"},{"key":"46","unstructured":"P. Sarnak, ``Three lectures on the M\u00f6bius function, randomness, and dynamics'', online notes (2011), http:\/\/publications.ias.edu\/sarnak\/paper\/512."},{"key":"47","unstructured":"F. Cellarosi and Y. G. Sinai, ``Ergodic Properties of Square-Free Numbers\", arXiv:1112.4691 (2011)."},{"key":"48","doi-asserted-by":"publisher","unstructured":"L. Amico, R. Fazio, A. Osterloh and V. Vedral, ``Entanglement in Many-Body Systems'', Rev. Mod. Phys. 80, 517 (2008).","DOI":"10.1103\/RevModPhys.80.517"},{"key":"49","doi-asserted-by":"publisher","unstructured":"E. Grosswald and F. J. Schnitzer, ``A class of modified $\\zeta$ and L-functions'', Pacific. Jour. Math. 74, 357 (1978).","DOI":"10.2140\/pjm.1978.74.357"},{"key":"50","doi-asserted-by":"publisher","unstructured":"D. R. Ward, ``Some Series Involving Euler's Function'', J. London Math. Soc. 2, 210 (1927).","DOI":"10.1112\/jlms\/s1-2.4.210"},{"key":"51","unstructured":"J. H. van Lint and H.E. Richert, ``\u00dcber die Summe $\\sum_n \\mu^2(n)\/ \\varphi(n)$'', Nederl. Akad. Wetensch.` Proc. Ser. A 67, Indag. Math. 26, 582 (1964)."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-12-11-371\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,12,11]],"date-time":"2020-12-11T11:10:03Z","timestamp":1607685003000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-12-11-371\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,11]]},"references-count":52,"URL":"https:\/\/doi.org\/10.22331\/q-2020-12-11-371","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,11]]},"article-number":"371"}}