© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Identification of prime numbers with quantum computers

Victor Penchel Alvarenga Balthar dos Santos

Published Sep 30, 2024• 0 citations

Abstract

The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.

Related papers

Using quantum computers to identify prime numbers via entanglement dynamics

Victor F. dos Santos, Jonas Maziero

Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.

arXiv:2403.14703•Physical Review A•Aug 2, 2024•2 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.

Quantum Information and Computation•May 1, 2014•14 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. We also propose a Twin Prime state to measure the number of twin primes and another state to test the Goldbach conjecture. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

arXiv:1302.6245•Feb 25, 2013•0 citations

Prime Number Identification Demonstrated with Quantum Processors Using a New Rescaling-Based Noise Mitigation Technique

Victor F. dos Santos, Victor P. Brasil, Pedro A. S. Contri +1 more

We implement a quantum protocol for prime number identification based on entanglement dynamics, using IBM quantum processors. The method links the primality of an integer to specific Fourier components extracted from the time evolution of entanglement in a bipartite quantum system. To mitigate experimental noise, we introduce a noise-mitigation method based on a global rescaling factor, which is calibrated on a subset of circuits and extrapolated across different configurations. Theoretical support is provided by a new analytical bound for the Fourier modes derived assuming an initial uniform superposition state. This new bound enhances the separation between prime and composite numbers under moderate experimental deviations. These results represent a step toward practical number-theoretic applications on noisy intermediate-scale quantum (NISQ) devices.

quant-pharXiv:2605.28964•Advanced Quantum Technologies•May 29, 2026•0 citations

Identifying primes from entanglement dynamics

A. L. M. Southier, Léa Ferreira dos Santos, P. H. Souto Ribeiro +1 more

The distribution of primes over the set of natural numbers is a fascinating subject closely related to topics that range from the fundamental problem of factorization to applications in cryptography. Despite numerous efforts, efficient methods to locate huge primes are still under investigation. Here, we present an alternative approach to identifying prime numbers that is based on the evolution of the linear entanglement entropy. Specifically, we show that a singular behavior in the amplitudes of the Fourier series of this entropy is associated with prime numbers. We also discuss how this intriguing connection between primes and entanglement could be experimentally implemented using existing optical devices, and examine a possible relationship between our results and the zeros of the Riemann zeta function.

arXiv:2303.10157•Physical Review A•Oct 4, 2023•5 citations

Prime Number Primality Testing via Quantum Lattice-Based Search

Jincheng Zhang

This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.

•Aug 31, 2026•0 citations

The identification of prime numbers is an ancient area of study with applications in cryptography and fundamental mathematical problems, such as the Riemann Hypothesis (RH). Classical algorithms, like the Sieve of Eratosthenes and the AKS Primality Test, are efficient examples for this purpose. However, quantum computing (QC), with its superior theoretical capacity, has inspired the development of quantum algorithms, many of which are probabilistic or rely on the RH. In this dissertation, we propose a deterministic and efficient quantum algorithm that generalizes a recent method from quantum optics to identify prime numbers through entanglement dynamics. We adapted this method for QC, removing several constraints from the original work, and showed that discrete bipartite quantum systems prepared in certain initial states can be used to identify prime numbers through the Fourier modes of the reduced purity of one of the subsystems. The proposed algorithm is viable for implementation in future fault-tolerant QC systems. The initial steps involve encoding the system in qubits and preparing a maximally superposed state. In the state evolution step, we use Walsh matrices to efficiently prepare diagonal unitary gates. The reduced purity is measured using a modified controlled-SWAP test, and the Fourier modes are obtained via the numerical calculation of a one-dimensional integral. Subsequently, we present the simulations performed in Qiskit, which demonstrate the validity of the algorithm in all its stages. Finally, we discuss the computational cost, quantifying the number of elementary gates as a function of the number of qubits and speculating the total computational complexity of the algorithm.

Recently, the entanglement dynamics of two harmonic oscillators initially prepared in a separable-coherent state was demonstrated to offer a pathway for prime number identification. This article presents a generalized approach and outlines a deterministic algorithm making possible the implementation of this theoretical concept on scalable fault-tolerant qubit-based quantum computers. We prove that the diagonal unitary operations employed in our algorithm exhibit a polynomial-time complexity of degree two, contrasting with the previously reported exponential complexity of general diagonal unitaries.

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.

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. We also propose a Twin Prime state to measure the number of twin primes and another state to test the Goldbach conjecture. Arithmetic properties of prime numbers are then, in principle, amenable to experimental verifications on quantum systems.

We implement a quantum protocol for prime number identification based on entanglement dynamics, using IBM quantum processors. The method links the primality of an integer to specific Fourier components extracted from the time evolution of entanglement in a bipartite quantum system. To mitigate experimental noise, we introduce a noise-mitigation method based on a global rescaling factor, which is calibrated on a subset of circuits and extrapolated across different configurations. Theoretical support is provided by a new analytical bound for the Fourier modes derived assuming an initial uniform superposition state. This new bound enhances the separation between prime and composite numbers under moderate experimental deviations. These results represent a step toward practical number-theoretic applications on noisy intermediate-scale quantum (NISQ) devices.

The distribution of primes over the set of natural numbers is a fascinating subject closely related to topics that range from the fundamental problem of factorization to applications in cryptography. Despite numerous efforts, efficient methods to locate huge primes are still under investigation. Here, we present an alternative approach to identifying prime numbers that is based on the evolution of the linear entanglement entropy. Specifically, we show that a singular behavior in the amplitudes of the Fourier series of this entropy is associated with prime numbers. We also discuss how this intriguing connection between primes and entanglement could be experimentally implemented using existing optical devices, and examine a possible relationship between our results and the zeros of the Riemann zeta function.

This paper introduces a novel quantum algorithm for efficient primality testing, aiming to surpass the limitations of classical methods through the application of lattice-based search. We detail the design of a quantum circuit that explores the prime number space, leveraging superposition and entanglement to achieve significantly reduced computational complexity. The core mechanism centers around quantum search, allowing for parallel exploration of the vast space of possible prime factors. We present a comprehensive analysis of the algorithm's performance, including a detailed mathematical justification of its efficiency gains compared to established techniques. The paper concludes with a discussion of the potential implications of this quantum approach for cryptography and other applications requiring prime number verification.