Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0701033

Graph identification by quantum walks

Jingbo B. Wang, B. L. Douglas

Published Jan 8, 2007• 1 citation
arXivHTMLPDF

Abstract

This paper has been withdrawn by the authors; replaced by arXiv:0705.2531v2 [quant-ph].
DOI
10.48550/arxiv.quant-ph/0701033

Related papers

Variations on Quantum Oblivious Transfer

Minh-Dung Dang

This paper has been withdrawn by the author, due to the insecurity against attacks received in quant-ph/0605027v5.

arXiv:quant-ph/0506033•Jun 3, 2005•1 citation

Quantum Random Walks and the Graph Isomorphism Problem

Kenneth Rudinger, John King Gamble, M. Wellons +4 more

Bulletin of the American Physical Society•Feb 29, 2012•0 citations

On the relationships between Z-, C-, and H-local unitaries

Cook, Jeremy

Quantum walk algorithms can speed up search of physical regions of space in both the discrete-time [arXiv:quant-ph/0402107] and continuous-time setting [arXiv:quant-ph/0306054], where the physical region of space being searched is modeled as a connected graph. In such a model, Aaronson and Ambainis [arXiv:quant-ph/0303041] provide three different criteria for a unitary matrix to act locally with respect to a graph, called $Z$-local, $C$-local, and $H$-local unitaries, and left the open question of relating these three locality criteria. Using a correspondence between continuous- and discrete-time quantum walks by Childs [arXiv:0810.0312], we provide a way to approximate $N\times N$ $H$-local unitaries with error $δ$ using $O(1/\sqrtδ,\sqrt{N})$ $C$-local unitaries, where the comma denotes the maximum of the two terms.

arXiv:1907.11368•Jul 9, 2019•1 citation

Quantum Walks on Finite Graphs

Renato Portugal

Springer eBooks•Jan 1, 2013•0 citations

Bounds for mixing time of quantum walks on finite graphs

Vladislav Kargin

Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov et al (2002 Proc. 33rd STOC ( 2001 ) (New York: ACM) pp 50–9 arXiv:quant-ph/0012090v2) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speedup in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e. walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.

arXiv:1004.0188•Journal of Physics A Mathematical and Theoretical•Jul 15, 2010•9 citations

On Quantum Walks on Finite Graphs(2) : Some Examples and its Properties

章 根岸, Akira Negishi

•Dec 17, 2013•0 citations
Quantum walk algorithms can speed up search of physical regions of space in both the discrete-time [arXiv:quant-ph/0402107] and continuous-time setting [arXiv:quant-ph/0306054], where the physical region of space being searched is modeled as a connected graph. In such a model, Aaronson and Ambainis [arXiv:quant-ph/0303041] provide three different criteria for a unitary matrix to act locally with respect to a graph, called ZZZ-local, CCC-local, and HHH-local unitaries, and left the open question of relating these three locality criteria. Using a correspondence between continuous- and discrete-time quantum walks by Childs [arXiv:0810.0312], we provide a way to approximate N×NN\times NN×N HHH-local unitaries with error δδδ using O(1/δ,N)O(1/\sqrtδ,\sqrt{N})O(1/δ​,N​) CCC-local unitaries, where the comma denotes the maximum of the two terms.
Several inequalities are proved for the mixing time of discrete-time quantum walks on finite graphs. The mixing time is defined differently than in Aharonov et al (2002 Proc. 33rd STOC ( 2001 ) (New York: ACM) pp 50–9 arXiv:quant-ph/0012090v2) and it is found that for particular examples of walks on a cycle, a hypercube and a complete graph, quantum walks provide no speedup in mixing over the classical counterparts. In addition, non-unitary quantum walks (i.e. walks with decoherence) are considered and a criterion for their convergence to the unique stationary distribution is derived.