A Quantum Diophantine Equation Solution Finder

Authors

  • Lara Tatli University of Durham, Durham, DH1 3LE
  • Paul Stevenson University of Surrey, Guildford, Surrey, GU2 7XH

Keywords:

Quantum computing, Grover’s algorithm, Diophantine equations

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.

References

B.Grechuk, “Diophantine equations: a systematic approach”, arxiv:2108.08705, 2022. https://doi.org/10.48550/arXiv.2108.08705

R.E. Frye, “Finding 958004 + 2175194 + 4145604 = 4224814 on the connection machine”, Supercomputing 88:Proceedings of the 1988 ACM/IEEE Conference on Supercomputing, Science and Applications, vol. 2, pp. 1061162, 1988. DOI: 10.1109/SUPERC.1988.74138

L.K. Grover, “A fast quantum mechanical algorithm for database search”, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. STOC 96, Association for Computing Machinery, New York, NY, USA, pp. 212219, 1996. https://doi.org/10.1145/237814.237866

A. Roy, J.L. Pachuau, G. Krishna and A.K. Saha, “Applying Grovers algorithm to implement various numerical and comparison operations”, Quantum Studies: Mathematics and Foundations, vol. 11, pp. 291306, 2024. https://doi.org/10.1007/s40509-024-00323-w

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, Cambridge, UK, 2010. https://doi.org/10.1017/CBO9780511976667

F. Orts, G. Ortega, E. F. Combarro, and E. M. Garzón, A review on reversible quantum adders, Journal of Network and Computer Applications, vol. 170, 102810, 2020. https://doi.org/10.1016/j.jnca.2020.102810

Classiq: Classiq Platform. https://platform.classiq.io/ Accessed 2024-11-13.

I. Abdurrahman, Enhancing Grover's search algorithm: a modified approach to increase the probability of good states, The Journal of Supercomputing, vol. 80, pp. 18048–18061, 2024. https://doi.org/10.1007/s11227-024-06142-5

S. Aaronson and P. Rall, Quantum approximate counting, simplified, Proceedings of the 2020 Symposium on Simplicity in Algorithms (SOSA), Society for Industrial and Applied Mathematics, Philadelphia, PA, pp. 24–32, 2020. https://doi.org/10.51137/1.9781611976014

Downloads

Published

2025-06-01

How to Cite

Tatli, L., & Stevenson, P. (2025). A Quantum Diophantine Equation Solution Finder. Mathematical Problems of Computer Science, 63, 60–70. Retrieved from https://mpcs.sci.am/index.php/mpcs/article/view/885