Discrete quantum walks hit exponentially faster
成果类型：
Article
署名作者：
Kempe, J
署名单位：
Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); University of California System; University of California Berkeley; University of California System; University of California Berkeley
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-004-0423-2
发表日期：
2005
页码：
215-235
关键词：
摘要：
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 walk on the n-bit hypercube from one corner 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.
来源URL：