Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physics Today

Quantum computer algorithm counts primes

Published Mar 19, 2013• 0 citations
Publisher
DOI
10.1063/pt.5.026853

Related papers

A New Efficient Quantum Algorithm for Computing Primality Measure

Gaurav Saxena, Shilpee Srivastava Saxena

International Journal of Mathematics Trends and Technology•Jun 25, 2021•0 citations

Quantum computation of prime number functions

José Ignacio Latorre, Germán Sierra

We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than $2^n$, where $n$ is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

arXiv:1302.6245•Quantum Information and Computation•May 1, 2014•23 citations

Simulating Factorization with a Quantum Computer

José Luis Rosales

Modern cryptography is largely based on complexity assumptions, for example, the ubiquitous RSA is based on the supposed complexity of the prime factorization problem. Thus, it is of fundamental importance to understand how a quantum computer would eventually weaken these algorithms. In this paper, one follows Feynman's prescription for a computer to simulate the physics corresponding to the algorithm of factoring a large number $N$ into primes. Using Dirac-Jordan transformation theory one translates factorization into the language of quantum hermitical operators, acting on the vectors of the Hilbert space. This leads to obtaining the ensemble of factorization of $N$ in terms of the Euler function $φ(N)$, that is quantized. On the other hand, considering $N$ as a parameter of the computer, a Quantum Mechanical Prime Counting Function $π_{QM}(x)$, where $x$ factorizes $N$, is derived. This function converges to $π(x)$ when $N\gg x$. It has no counterpart in analytic number theory and its derivation relies on semiclassical quantization alone.

arXiv:1505.00642•May 4, 2015•0 citations

Quantum Computer Algorithms

Michele Mosca

APS•Mar 1, 2003•71 citations

Quantum Probabilistic Subroutines and Problems in Number Theory

A. Carlini, Akio Hosoya

We describe a quantum version of the classical probabilistic algorithms à la Rabin. The quantum probabilistic algorithm is fully unitary and reversible, and can be used as a subroutine in larger quantum computations. As an example, we describe a polynomial time algorithm for counting the number of primes smaller than a given integer.

Kluwer Academic Publishers eBooks•Feb 24, 2006•6 citations

Computing prime factors with a Josephson phase qubit quantum processor

Erik A. Lucero, R. Barends, Yulin Chen +11 more

arXiv:1202.5707•Nature Physics•Aug 19, 2012•325 citations
We propose a quantum circuit that creates a pure state corresponding to the quantum superposition of all prime numbers less than 2n2^n2n, where nnn is the number of qubits of the register. This Prime state can be built using Grover's algorithm, whose oracle is a quantum implementation of the classical Miller-Rabin primality test. The Prime state is highly entangled, and its entanglement measures encode number theoretical functions such as the distribution of twin primes or the Chebyshev bias. This algorithm can be further combined with the quantum Fourier transform to yield an estimate of the prime counting function, more efficiently than any classical algorithm and with an error below the bound that allows for the verification of the Riemann hypothesis. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.
Modern cryptography is largely based on complexity assumptions, for example, the ubiquitous RSA is based on the supposed complexity of the prime factorization problem. Thus, it is of fundamental importance to understand how a quantum computer would eventually weaken these algorithms. In this paper, one follows Feynman's prescription for a computer to simulate the physics corresponding to the algorithm of factoring a large number NNN into primes. Using Dirac-Jordan transformation theory one translates factorization into the language of quantum hermitical operators, acting on the vectors of the Hilbert space. This leads to obtaining the ensemble of factorization of NNN in terms of the Euler function φ(N)φ(N)φ(N), that is quantized. On the other hand, considering NNN as a parameter of the computer, a Quantum Mechanical Prime Counting Function πQM(x)π_{QM}(x)πQM​(x), where xxx factorizes NNN, is derived. This function converges to π(x)π(x)π(x) when N≫xN\gg xN≫x. It has no counterpart in analytic number theory and its derivation relies on semiclassical quantization alone.