Journal or Publication Title:
Date of publication:
Volume:
Additional Information:
Title:
A Quantum Diophantine Equation Solution Finder
Creator:
Subject:
Uncontrolled Keywords:
Grover’s algorithm ; Diophantine equations
Coverage:
Abstract:
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.