Classical and quantum algorithms for exponential congruences

Wim Van Dam*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

17 Citations (Scopus)

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 . 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.

Original languageEnglish
Title of host publicationTheory of Quantum Computation, Communication, and Cryptography
Subtitle of host publicationThird Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers
EditorsYasuhito Kawano, Michele Mosca
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages1-10
Number of pages10
ISBN (Electronic)9783540893042
ISBN (Print)9783540893035
DOIs
Publication statusPublished - 2008
Event3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008 - Tokyo, Japan
Duration: 30 Jan 20081 Feb 2008

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume5106
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008
Country/TerritoryJapan
CityTokyo
Period30/01/081/02/08

Fingerprint

Dive into the research topics of 'Classical and quantum algorithms for exponential congruences'. Together they form a unique fingerprint.

Cite this