Classical and quantum algorithms for exponential congruences

Wim Van Dam; Igor E. Shparlinski

doi:10.1007/978-3-540-89304-2_1

Classical and quantum algorithms for exponential congruences

Wim Van Dam^*, Igor E. Shparlinski

^*Corresponding author for this work

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

18 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 language	English
Title of host publication	Theory of Quantum Computation, Communication, and Cryptography
Subtitle of host publication	Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers
Editors	Yasuhito Kawano, Michele Mosca
Place of Publication	Berlin
Publisher	Springer, Springer Nature
Pages	1-10
Number of pages	10
ISBN (Electronic)	9783540893042
ISBN (Print)	9783540893035
DOIs	https://doi.org/10.1007/978-3-540-89304-2_1
Publication status	Published - 2008
Event	3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008 - Tokyo, Japan Duration: 30 Jan 2008 → 1 Feb 2008

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	5106
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008
Country/Territory	Japan
City	Tokyo
Period	30/01/08 → 1/02/08

Access to Document

10.1007/978-3-540-89304-2_1

Cite this

Van Dam, W., & Shparlinski, I. E. (2008). Classical and quantum algorithms for exponential congruences. In Y. Kawano, & M. Mosca (Eds.), Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers (pp. 1-10). (Lecture Notes in Computer Science; Vol. 5106). Springer, Springer Nature. https://doi.org/10.1007/978-3-540-89304-2_1

Van Dam, Wim ; Shparlinski, Igor E. / Classical and quantum algorithms for exponential congruences. Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers. editor / Yasuhito Kawano ; Michele Mosca. Berlin : Springer, Springer Nature, 2008. pp. 1-10 (Lecture Notes in Computer Science).

@inproceedings{b89f4daf2caa456a96eb8278993e28fa,

title = "Classical and quantum algorithms for exponential congruences",

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

author = "{Van Dam}, Wim and Shparlinski, {Igor E.}",

year = "2008",

doi = "10.1007/978-3-540-89304-2_1",

language = "English",

isbn = "9783540893035",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "1--10",

editor = "Yasuhito Kawano and Michele Mosca",

booktitle = "Theory of Quantum Computation, Communication, and Cryptography",

address = "United States",

note = "3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008 ; Conference date: 30-01-2008 Through 01-02-2008",

}

Van Dam, W & Shparlinski, IE 2008, Classical and quantum algorithms for exponential congruences. in Y Kawano & M Mosca (eds), Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers. Lecture Notes in Computer Science, vol. 5106, Springer, Springer Nature, Berlin, pp. 1-10, 3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008, Tokyo, Japan, 30/01/08. https://doi.org/10.1007/978-3-540-89304-2_1

Classical and quantum algorithms for exponential congruences. / Van Dam, Wim; Shparlinski, Igor E.
Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers. ed. / Yasuhito Kawano; Michele Mosca. Berlin: Springer, Springer Nature, 2008. p. 1-10 (Lecture Notes in Computer Science; Vol. 5106).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Classical and quantum algorithms for exponential congruences

AU - Van Dam, Wim

AU - Shparlinski, Igor E.

PY - 2008

Y1 - 2008

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

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

UR - http://www.scopus.com/inward/record.url?scp=58049123672&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-89304-2_1

DO - 10.1007/978-3-540-89304-2_1

M3 - Conference proceeding contribution

AN - SCOPUS:58049123672

SN - 9783540893035

T3 - Lecture Notes in Computer Science

SP - 1

EP - 10

BT - Theory of Quantum Computation, Communication, and Cryptography

A2 - Kawano, Yasuhito

A2 - Mosca, Michele

PB - Springer, Springer Nature

CY - Berlin

T2 - 3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008

Y2 - 30 January 2008 through 1 February 2008

ER -

Van Dam W, Shparlinski IE. Classical and quantum algorithms for exponential congruences. In Kawano Y, Mosca M, editors, Theory of Quantum Computation, Communication, and Cryptography: Third Workshop, TQC 2008 Tokyo, Japan, January 30 - February 1, 2008. Revised Selected Papers. Berlin: Springer, Springer Nature. 2008. p. 1-10. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-89304-2_1

Classical and quantum algorithms for exponential congruences

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this