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:0809.1538

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

Published Sep 9, 2008• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0809.1538

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 search simulation with Wolfram Mathematica

Alexander N. Prokopenya

We consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Sep 28, 2016•0 citations

Solving mathematical problems with quantum search algorithm

Rubens Viana Ramos, Paulo Benicio Melo de Sousa, David Sena Oliveira

Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of algorithms.

arXiv:quant-ph/0605003•Apr 29, 2006•4 citations

A Quantum Diophantine Equation Solution Finder

Lara Tatli, P. D. Stevenson

Diophantine equations are multivariate equations, usually polynomial, in which only integer solutions are admitted. A brute force method for finding solutions would be to systematically substitute possible integer values for the unknown variables and check for equality. Grover’s algorithm is a quantum search algorithm which can find marked indices in a list very efficiently. By treating the indices as the integer variables in the Diophantine equation, Grover’s algorithm can be used to find solutions in a brute force way more efficiently than classical methods. We present a hand-coded example for the simplest possible Diophantine equation, and results for a more complicated, but still simulable, equation encoded with a high-level quantum language.

arXiv:2408.11606•Mathematical Problems of Computer Science•Jun 1, 2025•0 citations

Lower bounds of a quantum search for an extreme point

Yuri Ozhigov

We show that Durr and Hoyer's quantum algorithm of searching for an extreme point of an integer function cannot be sped up for functions that are chosen randomly. Any other algorithm acting in a substantially shorter time o(√2n) (n →α) gives an incorrect answer for the functions phi with the single point of maximum chosen randomly with probability Perr →1. The lower bound as Ω(√2n /b) is established for the quantum search for solution of the equation f (x) = 1, where f is a Boolean function with b such solutions chosen at random with asymptotic probability 1 (n→α).

arXiv:quant-ph/9806001•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jun 8, 1999•5 citations

QUANTUM ALGORITHMS FOR OPTIMIZATION USING ASYMPTOTIC QUANTUM SEARCH

Rubens Viana Ramos, Paulo Benicio Melo de Sousa

Problems of optimization are very common in several areas like engineering, physics, economics and mathematics and usually, they are very difficult to solve. Basically, one has to find the minimum or maximum of an objective function. In this work, we chose two optimization problems and we present quantum algorithms to solve them. The problems are: (1) to find the best decomposition of a unitary operation achievable by a programmable quantum circuit; (2) to find the minimal distance of a linear code. The quantum algorithms used are asymptotic quantum search and their main property is the fact that only one measurement is required.

International Journal of Quantum Information•Aug 1, 2008•0 citations
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.
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 consider Grover's algorithm of quantum search for one or several integers out of N = 2n, where n is a number of quantum bits in the memory register. There is a black-box or subroutine containing information about hidden integers and it can easily recognize these integers but we do not know which ones out of N they are. To find the hidden items we can do no better with a classical computer than to apply the subroutine repeatedly to all possible integers until we hit on the special one and in the worst case we have to repeat this procedure N times. We have analyzed the Grover algorithm carefully and showed that it enables to speed up this search quadratically, although its realization requires to know a number of hidden items. The lower bound for the probability of successful solving the search problem has been obtained. The validity of the results was demonstrated by simulation of the Grover search algorithm using the package QuantumCircuit written in the Wolfram Mathematica language.
Quantum computation has attracted much attention since it was shown by Shor and Grover the possibility to implement quantum algorithms able to realize, respectively, factoring and searching in a faster way than any other known classical algorithm. It is possible to use Grover algorithm, taking profit of its ability to find a specific value in a unordered database, to find, for example, the zero of a logical function; the minimal or maximal value in a database or to recognize if an odd number is prime or not. Here we show quantum algorithms to solve those cited mathematical problems. The solution requires the use of a quantum bit string comparator being used as oracle. This quantum circuit compares two quantum states and identifies if they are equal or, otherwise, which of them is the largest. Moreover, we also show the quantum bit string comparator allow us to implement conditional statements in quantum computation, a fundamental structure for designing of algorithms.
Diophantine equations are multivariate equations, usually polynomial, in which only integer solutions are admitted. A brute force method for finding solutions would be to systematically substitute possible integer values for the unknown variables and check for equality. Grover’s algorithm is a quantum search algorithm which can find marked indices in a list very efficiently. By treating the indices as the integer variables in the Diophantine equation, Grover’s algorithm can be used to find solutions in a brute force way more efficiently than classical methods. We present a hand-coded example for the simplest possible Diophantine equation, and results for a more complicated, but still simulable, equation encoded with a high-level quantum language.
We show that Durr and Hoyer's quantum algorithm of searching for an extreme point of an integer function cannot be sped up for functions that are chosen randomly. Any other algorithm acting in a substantially shorter time o(√2n) (n →α) gives an incorrect answer for the functions phi with the single point of maximum chosen randomly with probability Perr →1. The lower bound as Ω(√2n /b) is established for the quantum search for solution of the equation f (x) = 1, where f is a Boolean function with b such solutions chosen at random with asymptotic probability 1 (n→α).
Problems of optimization are very common in several areas like engineering, physics, economics and mathematics and usually, they are very difficult to solve. Basically, one has to find the minimum or maximum of an objective function. In this work, we chose two optimization problems and we present quantum algorithms to solve them. The problems are: (1) to find the best decomposition of a unitary operation achievable by a programmable quantum circuit; (2) to find the minimal distance of a linear code. The quantum algorithms used are asymptotic quantum search and their main property is the fact that only one measurement is required.