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

arXiv:1302.6245 · Quantum Information and Computation

Quantum computation of prime number functions

José Ignacio Latorre, Germán Sierra

Published May 1, 2014• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic14.7-8-3

Related papers

There is entanglement in the primes

José Ignacio Latorre, Germán Sierra

Large series of prime numbers can be superposed on a single quantum register and then analyzed in full parallelism. The construction of this Prime state is efficient, as it hinges on the use of a quantum version of any efficient primality test. We show that the Prime state turns out to be very entangled as shown by the scaling properties of purity, Renyi entropy and von Neumann entropy. An analytical approximation to these measures of entanglement can be obtained from the detailed analysis of the entanglement spectrum of the Prime state, which in turn produces new insights in the Hardy-Littlewood conjecture for the pairwise distribution of primes. The extension of these ideas to a Twin Prime state shows that this new state is even more entangled than the Prime state, obeying majorization relations. We further discuss the construction of quantum states that encompass relevant series of numbers and opens the possibility of applying quantum computation to Arithmetics in novel ways.

arXiv:1403.4765•Quantum Information and Computation•May 1, 2015•25 citations

Identification of prime numbers with quantum computers

Victor Penchel Alvarenga Balthar dos Santos

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.

•Sep 30, 2024•0 citations

Quantum Versions of Classical Randomized Algorithms

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.

Progress of Theoretical Physics Supplement•Jan 1, 2000•0 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

Quantum probabilistic subroutines and problems in number theory

A. Carlini, Akio Hosoya

We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.

arXiv:quant-ph/9907020•Physical Review A•Aug 18, 2000•12 citations

Efficient state preparation for a register of quantum bits

Andrei N. Soklakov, Rüdiger Schack

We describe a quantum algorithm to prepare an arbitrary pure state of a register of a quantum computer with fidelity arbitrarily close to 1. Our algorithm is based on Grover's quantum search algorithm. For sequences of states with suitably bounded amplitudes, the algorithm requires resources that are polynomial in the number of qubits. Such sequences of states occur naturally in the problem of encoding a classical probability distribution in a quantum register.

arXiv:quant-ph/0408045•Physical Review A•Jan 9, 2006•125 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.
Large series of prime numbers can be superposed on a single quantum register and then analyzed in full parallelism. The construction of this Prime state is efficient, as it hinges on the use of a quantum version of any efficient primality test. We show that the Prime state turns out to be very entangled as shown by the scaling properties of purity, Renyi entropy and von Neumann entropy. An analytical approximation to these measures of entanglement can be obtained from the detailed analysis of the entanglement spectrum of the Prime state, which in turn produces new insights in the Hardy-Littlewood conjecture for the pairwise distribution of primes. The extension of these ideas to a Twin Prime state shows that this new state is even more entangled than the Prime state, obeying majorization relations. We further discuss the construction of quantum states that encompass relevant series of numbers and opens the possibility of applying quantum computation to Arithmetics in novel ways.
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.
We present a quantum version of the classical probabilistic algorithms a' la Rabin for the test of primality of a given integer. Our quantum algorithm is based on the use of Grover's unitary operator for searching an unstructured database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the quantum counting algorithm by Brassard et al. Our quantum probabilistic algorithm is fully unitary and reversible, and can be used as part of larger and more complicated quantum networks. Polynomial time algorithms for testing the primality of an integer, the ‘prime number theorem’ and a conjecture about the asymptotic number of representations of an even integer as a sum of two primes are also discussed.
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.
We present a quantum version of the classical probabilistic algorithms as studied by Rabin. The quantum algorithm is based on the essential use of Grover's operator for the quantum search of a database and of Shor's Fourier transform for extracting the periodicity of a function, and their combined use in the counting algorithm originally introduced by Brassard et al. One of the main features of our quantum probabilistic algorithm is its full unitarity and reversibility, which would make its use possible as part of larger and more complicated networks in quantum computers. As an example of this we describe polynomial time algorithms for studying some important problems in number theory, such as the test of the primality of an integer, the so called prime number theorem, and Hardy and Littlewood's conjecture about the asymptotic number of representations of an even integer as a sum of two primes.