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

Kluwer Academic Publishers eBooks

Quantum Probabilistic Subroutines and Problems in Number Theory

A. Carlini, Akio Hosoya

Published Feb 24, 2006• 6 citations
Publisher

Abstract

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.
DOI
10.1007/0-306-47114-0_33

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•12 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

Carmichael Numbers on a Quantum Computer

A. Carlini, Akio Hosoya

We present a quantum probabilistic algorithm which tests with a polynomial computational complexity whether a given composite number is of the Carmichael type. We also suggest a quantum algorithm which could verify a conjecture by Pomerance, Selfridge and Wagstaff concerning the asymptotic distribution of Carmichael numbers smaller than a given integer.

arXiv:quant-ph/9908022•Aug 5, 1999•1 citation

Asymptotic Quantum Search and a Quantum Algorithm for Calculation of a Lower Bound of the Probability of Finding a Diophantine Equation That Accepts Integer Solutions

Rubens Viana Ramos, Juliana Loureiro de Oliveira

Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed and all of them use the quantum search algorithm as a subroutine and several intermediate measurements are realized. In this work, it is proposed a new quantum algorithm for finding the minimum of a function in which quantum search is not used as a subroutine and only one measurement is needed. This is also named asymptotic quantum search. As an example, we propose a quantum algorithm based on asymptotic quantum search and quantum counting able to calculate a lower bound of the probability of finding a Diophantine equation with integer solution.

arXiv:0809.1538•Sep 9, 2008•0 citations

A quantum algorithm for computing multiplicative order of integers modulo a prime

Maheswara Rao Valluri

One of the challenging problems in number theory is to compute efficiently multiplicative order of integers modulo a prime. This problem was listed under open problems in the number theoretic complexity II proposed by Leonard M. Adleman and Kevin S.McCurley in 1994. This paper offers a polynomial-time quantum algorithm for computing the order k = min {x|x∈, ax ≡ 1(modp)}, if p∈ Primes and gcd(a,p) = 1, where a, p∈, and it requires 2 (1) 2 ((log p) +O )  quantum operations.

Journal of Discrete Mathematical Sciences and Cryptography•Jan 1, 2023•0 citations

Quantum Computers Can Find Quadratic Nonresidues in Deterministic Polynomial Time

Thomas G. Draper

An integer $a$ is a quadratic nonresidue for a prime $p$ if $x^2 \equiv a \bmod p$ has no solution. Quadratic nonresidues may be found by probabilistic methods in polynomial time. However, without assuming the Generalized Riemann Hypothesis, no deterministic polynomial-time algorithm is known. We present a quantum algorithm which generates a random quadratic nonresidue in deterministic polynomial time.

arXiv:2106.03991•Jun 7, 2021•1 citation
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 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.
Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed and all of them use the quantum search algorithm as a subroutine and several intermediate measurements are realized. In this work, it is proposed a new quantum algorithm for finding the minimum of a function in which quantum search is not used as a subroutine and only one measurement is needed. This is also named asymptotic quantum search. As an example, we propose a quantum algorithm based on asymptotic quantum search and quantum counting able to calculate a lower bound of the probability of finding a Diophantine equation with integer solution.
An integer aaa is a quadratic nonresidue for a prime ppp if x2≡a mod px^2 \equiv a \bmod px2≡amodp has no solution. Quadratic nonresidues may be found by probabilistic methods in polynomial time. However, without assuming the Generalized Riemann Hypothesis, no deterministic polynomial-time algorithm is known. We present a quantum algorithm which generates a random quadratic nonresidue in deterministic polynomial time.