Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.14/149776
37 Visitors37 Hits0 Downloads
Classical and quantum algorithms for exponential congruences
Workshop on Theory of Quantum Computation, Communication, and Cryptography (TQC) (3rd : 2008) (30 January - 1 February 2008 : Tokyo)
Kawano, Yasuhito and Mosca, Michele. Theory of quantum computation, communication, and cryptography : third workshop, TQC 2008, Tokyo, Japan, January 30-February 1, 2008 : revised selected papers, p.1-10
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 Fq. A quantum algorithm with time complexity q 3/8 (logq) O(1) is presented. While still superpolynomial in logq, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q 9/8 (logq) O(1). Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones.