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

Progress of Theoretical Physics Supplement

Quantum Versions of Classical Randomized Algorithms

A. Carlini, Akio Hosoya

Published Jan 1, 2000• 0 citations
Publisher

Abstract

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.

DOI
10.1143/ptps.138.495

Related papers

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•11 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•5 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

Early quantum algorithms

Riccardo Manenti, Mário Motta

Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.

•Aug 25, 2023•0 citations

How to detect whether Shor’s algorithm succeeds against large integers without a quantum computer

Daniel Chicayban Bastos, Luis Antônio Brasil Kowada

Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.

Procedia Computer Science•Jan 1, 2021•6 citations
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.
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.
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.
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.
Abstract This chapter presents early quantum algorithms. We first describe Deutsch’s and Bernstein-Vazirani, some of the first quantum algorithms that showed a query advantage over their classical counterparts. We then present Grover’s algorithm, a quantum algorithm that finds an item in an unstructured database with a quadratic speed-up over classical algorithms. We explain the quantum Fourier transform, an important subroutine in various quantum algorithms. The chapter concludes with a detailed presentation of two of the most prominent applications of the quantum Fourier transform: the period finding algorithm and Shor’s algorithm for prime factorization.
Shor’s algorithm is a well-known probabilistic method for factoring large composite integers in polynomial-time on a quantum computer. The method computes the order r of a random element x in the group Z∗N and uses that information for splitting N with an application of the greatest common divisor algorithm. However, being probabilistic, the success of Shor’s algorithm relies on some special properties of N. If r is even and xr/2 £ -1 mod N, then gcd(xr/2 - 1, N) reveals a nontrivial factor of N and the method succeeds. But even assuming that r is even and being given the complete prime factorization of N it is not obvious whether xr/2 £ -1 mod N and, therefore, it is not easy to assert whether Shor’s algorithm would split N without running it and looking at its answer. We present a strategy for detecting whether the splitting occurs without any need for running the quantum order-finding algorithm, but we must be given the prime factorization of N. This has allowed us to produce the first direct evidence of the probability of success of Shor’s method. The composites chosen were the product of two randomly-generated probable primes of similar sizes that pass the Miller-Rabin test.