Optimal computation with non-unitary quantum walks

被引:15
作者
Kendon, Viv [1 ]
Maloyer, Olivier [2 ]
机构
[1] Univ Leeds, Sch Phys & Astron, Leeds LS2 9JT, W Yorkshire, England
[2] Univ Paris 11, Orsay, France
关键词
quantum computing; quantum walks; quantum algorithms;
D O I
10.1016/j.tcs.2007.12.011
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Quantum versions of random walks on the line and the cycle show a quadratic improvement over classical random walks in their spreading rates and mixing times, respectively. Non-unitary quantum walks can provide a useful optimisation of these properties, producing a more uniform distribution on the line, and faster mixing times on the cycle. We investigate the interplay between quantum and random dynamics by comparing the resources required, and examining numerically how the level of quantum correlations varies during the walk. We show numerically that the optimal non-unitary quantum walk proceeds such that the quantum correlations are nearly all removed at the point of the final measurement. This requires only O(log T) random bits for a quantum walk of T steps. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:187 / 196
页数:10
相关论文
共 34 条
[1]  
Aharonov Dorit, 2001, arXiv: quant-ph/0012090, P50
[2]   QUANTUM RANDOM-WALKS [J].
AHARONOV, Y ;
DAVIDOVICH, L ;
ZAGURY, N .
PHYSICAL REVIEW A, 1993, 48 (02) :1687-1690
[3]   Quantum walk algorithm for element distinctness [J].
Ambainis, A .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :22-31
[4]  
AMBAINIS A, 2001, P 33 ACM S THEOR COM, P60, DOI DOI 10.1145/380752.380757
[5]   One-dimensional quantum walks with absorbing boundaries [J].
Bach, E ;
Coppersmith, S ;
Goldschen, MP ;
Joynt, R ;
Watrous, J .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (04) :562-592
[6]   Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem [J].
Bennett, CH ;
Shor, PW ;
Smolin, JA ;
Thapliyal, AV .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2002, 48 (10) :2637-2655
[7]   Quantum random walks with decoherent coins [J].
Brun, TA ;
Carteret, HA ;
Ambainis, A .
PHYSICAL REVIEW A, 2003, 67 (03) :9
[8]   Entanglement in coined quantum walks on regular graphs [J].
Carneiro, I ;
Loo, M ;
Xu, XB ;
Girerd, M ;
Kendon, V ;
Knight, PL .
NEW JOURNAL OF PHYSICS, 2005, 7
[9]  
CARNEIRO I, QUANTPH0504042
[10]  
Childs A.M., 2003, STOC'03: 35th Annual ACM Symposium on Theory of Computing, P59, DOI [DOI 10.1145/780542.780552, 10.1145/780542.780552]