Classical and Quantum Algorithms for Exponential Congruences

2008/04/07 by van Dam, Wim, Shparlinski, Igor E. · 1 citation
#FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.0804.1109

Abstract

We discuss classical and quantum algorithms for solvability testing and finding integer solutions x,y of equations of the form af^x + bg^y = c over finite fields GF(q). A quantum algorithm with time complexity q^(3/8) (log q)^O(1) is presented. While still superpolynomial in log q, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q^(9/8) (log q)^O(1). Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones.

Cited by

• The Grand Challenge of Quantum Applications

Related

• Quantum speedup to some types of polynomial equations
• Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
• On the Existence of certain Quantum Algorithms
• Quantum and Classical Algorithms for Bounded Distance Decoding
• Basic Quantum Algorithms