Spatial search by continuous-time quantum walk with multiple marked vertices

Thomas G. Wong

doi:10.1007/s11128-015-1239-y

Spatial search by continuous-time quantum walk with multiple marked vertices

Thomas G. Wong

Research output: Contribution to journal › Article › peer-review

25 Scopus citations

Abstract

In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of (Formula presented.) complete graphs” with all configurations of two marked vertices, two configurations of (Formula presented.) marked vertices, and two configurations of (Formula presented.) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration’s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.

Original language	English (US)
Pages (from-to)	1411-1443
Number of pages	33
Journal	Quantum Information Processing
Volume	15
Issue number	4
DOIs	https://doi.org/10.1007/s11128-015-1239-y
State	Published - Apr 1 2016
Externally published	Yes

All Science Journal Classification (ASJC) codes

Electronic, Optical and Magnetic Materials
Statistical and Nonlinear Physics
Theoretical Computer Science
Signal Processing
Modeling and Simulation
Electrical and Electronic Engineering

Access to Document

10.1007/s11128-015-1239-y

Cite this

@article{6b82001115ed45958a09edb02747e074,

title = "Spatial search by continuous-time quantum walk with multiple marked vertices",

abstract = "In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of (Formula presented.) complete graphs” with all configurations of two marked vertices, two configurations of (Formula presented.) marked vertices, and two configurations of (Formula presented.) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration{\textquoteright}s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.",

author = "Wong, {Thomas G.}",

note = "Funding Information: Thanks to Andris Ambainis for useful discussions. This work was supported by the European Union Seventh Framework Programme (FP7/2007–2013) under the QALGO (Grant Agreement No. 600700) project, and the ERC Advanced Grant MQC. Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2016",

month = apr,

day = "1",

doi = "10.1007/s11128-015-1239-y",

language = "English (US)",

volume = "15",

pages = "1411--1443",

journal = "Quantum Information Processing",

issn = "1570-0755",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Spatial search by continuous-time quantum walk with multiple marked vertices

AU - Wong, Thomas G.

N1 - Funding Information: Thanks to Andris Ambainis for useful discussions. This work was supported by the European Union Seventh Framework Programme (FP7/2007–2013) under the QALGO (Grant Agreement No. 600700) project, and the ERC Advanced Grant MQC. Publisher Copyright: © 2016, Springer Science+Business Media New York.

PY - 2016/4/1

Y1 - 2016/4/1

N2 - In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of (Formula presented.) complete graphs” with all configurations of two marked vertices, two configurations of (Formula presented.) marked vertices, and two configurations of (Formula presented.) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration’s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.

AB - In the typical spatial search problems solved by continuous-time quantum walk, changing the location of the marked vertices does not alter the search problem. In this paper, we consider search when this is no longer true. In particular, we analytically solve search on the “simplex of (Formula presented.) complete graphs” with all configurations of two marked vertices, two configurations of (Formula presented.) marked vertices, and two configurations of (Formula presented.) marked vertices, showing that the location of the marked vertices can dramatically influence the required jumping rate of the quantum walk, such that using the wrong configuration’s value can cause the search to fail. This sensitivity to the jumping rate is an issue unique to continuous-time quantum walks that does not affect discrete-time ones.

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

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

U2 - 10.1007/s11128-015-1239-y

DO - 10.1007/s11128-015-1239-y

M3 - Article

AN - SCOPUS:84955328322

SN - 1570-0755

VL - 15

SP - 1411

EP - 1443

JO - Quantum Information Processing

JF - Quantum Information Processing

IS - 4

ER -

Spatial search by continuous-time quantum walk with multiple marked vertices

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this