Discrete quantum walks hit exponentially faster

Julia Kempe

doi:10.1007/978-3-540-45198-3_30

Discrete quantum walks hit exponentially faster

Julia Kempe

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one comer to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Sanjeev Asora, Amit Sahai, Klaus Jansen, Jose D.P. Rolim
Publisher	Springer Verlag
Pages	354-369
Number of pages	16
ISBN (Print)	3540407707, 9783540407706
DOIs	https://doi.org/10.1007/978-3-540-45198-3_30
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2764
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45198-3_30

Cite this

Kempe, J. (2003). Discrete quantum walks hit exponentially faster. In S. Asora, A. Sahai, K. Jansen, & J. D. P. Rolim (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 354-369). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764). Springer Verlag. https://doi.org/10.1007/978-3-540-45198-3_30

Discrete quantum walks hit exponentially faster. / Kempe, Julia.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Sanjeev Asora; Amit Sahai; Klaus Jansen; Jose D.P. Rolim. Springer Verlag, 2003. p. 354-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2764).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Kempe, J 2003, Discrete quantum walks hit exponentially faster. in S Asora, A Sahai, K Jansen & JDP Rolim (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2764, Springer Verlag, pp. 354-369. https://doi.org/10.1007/978-3-540-45198-3_30

Kempe J. Discrete quantum walks hit exponentially faster. In Asora S, Sahai A, Jansen K, Rolim JDP, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 354-369. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45198-3_30

Kempe, Julia. / Discrete quantum walks hit exponentially faster. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Sanjeev Asora ; Amit Sahai ; Klaus Jansen ; Jose D.P. Rolim. Springer Verlag, 2003. pp. 354-369 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{fd27987d5b994b5ab22c203d7a37788f,

title = "Discrete quantum walks hit exponentially faster",

abstract = "This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one comer to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.",

author = "Julia Kempe",

year = "2003",

doi = "10.1007/978-3-540-45198-3_30",

language = "English (US)",

isbn = "3540407707",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "354--369",

editor = "Sanjeev Asora and Amit Sahai and Klaus Jansen and Rolim, {Jose D.P.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - Discrete quantum walks hit exponentially faster

AU - Kempe, Julia

PY - 2003

Y1 - 2003

N2 - This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one comer to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.

AB - This paper addresses the question: what processes take polynomial time on a quantum computer that require exponential time classically? We show that the hitting time of the discrete time quantum random walk on the n-bit hypercube from one comer to its opposite is polynomial in n. This gives the first exponential quantum-classical gap in the hitting time of discrete quantum walks. We provide the basic framework for quantum hitting time and give two alternative definitions to set the ground for its study on general graphs. We outline a possible application to sequential packet routing.

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

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

U2 - 10.1007/978-3-540-45198-3_30

DO - 10.1007/978-3-540-45198-3_30

M3 - Chapter

AN - SCOPUS:35248893912

SN - 3540407707

SN - 9783540407706

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 354

EP - 369

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Asora, Sanjeev

A2 - Sahai, Amit

A2 - Jansen, Klaus

A2 - Rolim, Jose D.P.

PB - Springer Verlag

ER -

Discrete quantum walks hit exponentially faster

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this