量子随机行走的基本性质及应用研究
|
摘要
量子随机行走作为经典随机行走的量子推广,自1993年被提出后,就受到广泛的关注,近年来,吸引了许多数学家,计算机科学家,物理学家及工程师等的注意。量子随机行走已经成为量子算法的一个重要工具,一系列基于量子随机行走的量子算法被提出,其中一些到达问题相对于经典算法具有指数加速,搜索问题也达到了O(√N)这一最佳效率,且量子随机行走已被证明可以用于普适量子计算。为了更好的发挥量子随机行走的潜力,我们需要对量子随机行走的各种基本性质有更深的了解,包括方差,熵,到达时间,混合时间,平均位置等有更精确的结果,还有更多情形下量子随机行走需要得到研究。
本文主要研究量子随机行走的一些基本性质及应用,包括：
1.介绍量子随机行走的的定义,及量子随机行走和经典随机行走的区别。介绍了两种研究一维量子随机行走的方法：Fourier变换方法和排列组合方法,还有利用3变量幺正算UξθS作为硬币,来控制离散量子随机行走的演化,最后还介绍了基于量子随机行走的一些量子算法和普适量子计算的方案,以及多粒子纠缠在量子随机行走中的表现。
2.研究使用任意幺正算符作为硬币的离散量子随机行走,我们发现当初始态为平衡态1/(?)(|OL>+i|OR>)时,其平均位置满足
Quantum random walks (QWs), as the quantum version of classical random walks, since was introduced in1993, have been widespread concerned. Recently, QWs have attracted great attention from mathematicians, computer scientists, physicists, and engineers. Quantum walks have been exploited as an useful tool for quantum algorithms in quantum computing. A list of quantum algorithms based on QWs have already been proposed. QWs can be used to perform an oracle search on a database of N items with O((?)N) was proved, and in some problems, the hitting time is exponential faster than its corresponding classical random walk, QWs can also be used for universal computation.
In order to use the quantum walk to its fullest potential, we need to have a deeper understanding of the basic nature, including standard deviation, entropy, hitting time, mixing time and average position etc., we need more precise results about them and QWs in more situations need to be discussed.
In this dissertation, we mainly concentrated some basic properties and appli-cations of QWs. It contains,
1. We give the definition of quantum random walk, and the basic difference between classical random walk and quantum random walk. Two methods for computing one-dimensional QWs:Fourier transform method and per-mutations method were introduced. Using3parameters unitary operation to control the evolution of QWs, some algorithms, the solution of universal quantum computing and the evolution of multi-particles in QWs were also introduced,
2. We investigated discrete-time quantum walks with an arbitary unitary coin. Here we discover that the average position (x)=max((x))sin(α+γ), while the initial state is1/(?)2(|OL)+i|OR)). We prove the result and get some symmetry properties of quantum walks with a U(2) coin with|OL) and|OR) as the initial state.
3. We investigated the discrete-time quantum random walks on a line in peri-odic potential. The probability distribution with periodic potential is more complex compared to the normal quantum walks, and the standard devia-tion a has interesting behaviors for different period q and parameter θ. We studied the behavior of standard deviation with variation in walk steps, pe-riod, and θ. The standard deviation increases approximately linear with θ and decreases with1/q for θ∈(0, π/4), and increases approximately linear with1/q for θ∈[π/4, π/2). For θ∈(π/4, π/2), it means the transmission is larger than the reflection, and become larger, with sensibility, the diffussion will be accelerated, and when θ∈(π/2,3π/4), the transmission becomes smaller and reflection becomes larger, with sensibility, the diffusion will be decelerated, but when θ∈(π/4,3π/4) and q=2, the standard deviations are nearly the same, and when and q>2, the standard deviation will decrease.
4. We construct a Parrondo's game using discrete time quantum walks. Two lossing games are represented by two different coin operators. By mixing the two coin operators UA(αA,βA,γA) and UB(αB,βB.γB), we may win the game. Here we mix the two games correlated to the positions instead of time. With a number of selections of the parameters, we can win the game with sequences ABB, ABBB, etc.. If we set βA=45°,γA=0, αB=0,βB=88°, we find the game1with Uas=Us(-51°,45°,0), UBS=Us(0,88°,-16°) will win and get the most profit. If we set αA=0,βA=45°, αB=0,βB=88°and the game2with UAS=Us(0,45°,-51°), UBS=Us(0,88°,-67°), will win most. And game1is equivalent to the game2with the changes of sequences and steps. But at a large enough steps, the game will loss at last.
本文主要研究量子随机行走的一些基本性质及应用,包括：
1.介绍量子随机行走的的定义,及量子随机行走和经典随机行走的区别。介绍了两种研究一维量子随机行走的方法：Fourier变换方法和排列组合方法,还有利用3变量幺正算UξθS作为硬币,来控制离散量子随机行走的演化,最后还介绍了基于量子随机行走的一些量子算法和普适量子计算的方案,以及多粒子纠缠在量子随机行走中的表现。
2.研究使用任意幺正算符作为硬币的离散量子随机行走,我们发现当初始态为平衡态1/(?)(|OL>+i|OR>)时,其平均位置满足
Quantum random walks (QWs), as the quantum version of classical random walks, since was introduced in1993, have been widespread concerned. Recently, QWs have attracted great attention from mathematicians, computer scientists, physicists, and engineers. Quantum walks have been exploited as an useful tool for quantum algorithms in quantum computing. A list of quantum algorithms based on QWs have already been proposed. QWs can be used to perform an oracle search on a database of N items with O((?)N) was proved, and in some problems, the hitting time is exponential faster than its corresponding classical random walk, QWs can also be used for universal computation.
In order to use the quantum walk to its fullest potential, we need to have a deeper understanding of the basic nature, including standard deviation, entropy, hitting time, mixing time and average position etc., we need more precise results about them and QWs in more situations need to be discussed.
In this dissertation, we mainly concentrated some basic properties and appli-cations of QWs. It contains,
1. We give the definition of quantum random walk, and the basic difference between classical random walk and quantum random walk. Two methods for computing one-dimensional QWs:Fourier transform method and per-mutations method were introduced. Using3parameters unitary operation to control the evolution of QWs, some algorithms, the solution of universal quantum computing and the evolution of multi-particles in QWs were also introduced,
2. We investigated discrete-time quantum walks with an arbitary unitary coin. Here we discover that the average position (x)=max((x))sin(α+γ), while the initial state is1/(?)2(|OL)+i|OR)). We prove the result and get some symmetry properties of quantum walks with a U(2) coin with|OL) and|OR) as the initial state.
3. We investigated the discrete-time quantum random walks on a line in peri-odic potential. The probability distribution with periodic potential is more complex compared to the normal quantum walks, and the standard devia-tion a has interesting behaviors for different period q and parameter θ. We studied the behavior of standard deviation with variation in walk steps, pe-riod, and θ. The standard deviation increases approximately linear with θ and decreases with1/q for θ∈(0, π/4), and increases approximately linear with1/q for θ∈[π/4, π/2). For θ∈(π/4, π/2), it means the transmission is larger than the reflection, and become larger, with sensibility, the diffussion will be accelerated, and when θ∈(π/2,3π/4), the transmission becomes smaller and reflection becomes larger, with sensibility, the diffusion will be decelerated, but when θ∈(π/4,3π/4) and q=2, the standard deviations are nearly the same, and when and q>2, the standard deviation will decrease.
4. We construct a Parrondo's game using discrete time quantum walks. Two lossing games are represented by two different coin operators. By mixing the two coin operators UA(αA,βA,γA) and UB(αB,βB.γB), we may win the game. Here we mix the two games correlated to the positions instead of time. With a number of selections of the parameters, we can win the game with sequences ABB, ABBB, etc.. If we set βA=45°,γA=0, αB=0,βB=88°, we find the game1with Uas=Us(-51°,45°,0), UBS=Us(0,88°,-16°) will win and get the most profit. If we set αA=0,βA=45°, αB=0,βB=88°and the game2with UAS=Us(0,45°,-51°), UBS=Us(0,88°,-67°), will win most. And game1is equivalent to the game2with the changes of sequences and steps. But at a large enough steps, the game will loss at last.
引文
[1]A. Ambainis, E. Bach, A. Nayak, A. Vishwanath and J. Watrous, One Di-mensional Quantum Walk, In: Proceeding of the 33th ACM Symposium on The Theory of Computation (STOC'01) ACM pp.60-69 (2001).
[2]A. Nayak and A. Vishwanath, Quantum Walk on the line, Technical Report, Center for Discrete Mathematics & Theoretical Computer Science (2000).
[3]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[4]E. Farhi, Quantum computation and decision trees, Phys. Rev. A 58,915 (1998).
[5]J. Watrous, Quantum simulations of classical random walks and undirected graph connectively, Journal of Computer and System Sciences 62, pp.376-391 (2001).
[6]N. Shenvi, J. Kempe and K. B. Whaley, Quantum random-walk search algo-rithm, Phys. Rev. A 67,052307 (2003).
[7]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[8]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Proceedings of the 16th ACM-SIAM symposium on Discrete algorithms, pp.1099-1108, (2005).
[9]S. Aaronson and A. Ambainis, Quantum search'of spatial regions, Theory of Computing (Also FOCS'03),1, pp.47-79, (2005).
[10]F. Magniez, A. Nayak, J. Roland and M. Santha, Search via quantum walk, Proceedings of the 39th ACM Symposium on Theory of Computing, pp. 575-584 (2007).
[11]N. B. Lovett, M. Everitt, M. Trevers, D. Mosby, D. Stockton and V. Kendon, Spatial search using the discrete time quantum walk, Nat. Comput.11:23-35 (2012).
[12]A. M. Childs, E. Farhi and S. Gutmann, An Example of the Difference Be-tween Quantum and Classical Random Walks, Quantum Information Process-ing.1, pp.35-43 (2002).
[13]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, Exponential algorithmic speedup by quantum walk, In:Proceedings of the 35th ACM Symposium on The Theory of Computation (STOC'03) ACM, pp.59-68 (2003).
[14]A. Ambainis, Quantum walk algorithm for element distinctness, SIAM Jour-nal on Computing,37(1),210-239, (2007).
[15]A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett.102, 180501 (2009).
[16]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[17]A. M. Childs, D. Gosset and Z. Webb, Universal computation by multi-particle quantum walk, arXiv:quant-ph/1205.3782 (2012); Science 39,791 (2013).
[18]D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, Proceeding STOC'01 Proceedings of the 33th annual ACM symposium on Theory of computing, pp.50-59 (2001).
[19]L. C. Kwek and Setiawan, One-dimensional quantum walk with a moving boundary, Phy. Rev. A 84,032319 (2011).
[20]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[21]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum random walks with decoherent coins, Phys. Rev. A 67,032304 (2003).
[22]J. Du, H. Li, X. Xu, M. Shi, J. Wu, X. Zhou, and R. Han, Experimental implementation of the quantum random-walk algorithm, Phys. Rev. A 67, 042316, (2003).
[23]C. A. Ryan, M. Laforest, J. C. Boileau, and R. Laflamme, Experimental implementation of discrete time quantum random walk on an NMR quantum information processor, Phys. Rev. A 72,062317, (2005).
[24]J. M. Grossman, D. Ciampini, M. D. Arcy, K. Helmerson, P. D. Lett, W. D. Phillips, A. Vaziri and S. L. Rolston, Implementation of a quantum random walk with a sodium Bose-Einstein condensate, The 35th Meeting of the Di-vision of Atomic, Molecular and Optical Physics, Tuscon, AZ, (DAMOP04), (2004).
[25]H. B. Perets, Y. Lahini, F. Pozzi, M. Sorel, R. Morandotti and Y. Silberberg, Realization of quantum walks with negligible decoherence in waveguide lattices, Phys. Rev. Lett.100,170506 (2008).
[26]B. C. Travaglione and G. J. Milburn, Implementing the quantum random walk, Phys. Rev. A 65,032310 (2002)
[27]W. Dur, R. Raussendorf, V. M. Kendon, and H. J. Briegel, Quantum walks in optical lattice, Phys. Rev. A 66,052319, (2002).
[28]K. Eckert, J. Mompart, G. Birkl, and M. Lewenstein. One-and two-dimen-sional walks in arrays of optical traps, Phys. Rev. A 72,012327 (2005).
[29]C. M. Chandrashekar. Implementing the one-dimensional quantum (Hadamard) walk using Bose-Einstein condensate., Phys. Rev. A 74, 032307 (2006).
[30]K. Manouchehri and J. B. Wang, Quantum walks in an array of quantum dots, J. Phys. A: Math. Theor.41,065304 (2008).
[31]Z. Y. Ma, K. Burnett, M. A. d'Arcy, and S. A. Gardiner, Quantum random walk using quantum accelerator modes, Phys. Rev. A 73,013401 (2006).
[32]Y. Bromberg, Y. Lahini, R. Morandotti and Y. Silberberg, Quantum and Classical Correlations in Waveguide Lattices, Phys. Rev. Lett.102,253904 (2009).
[33]Y. Lahini, M. Verbin, S. D. Huber, Y. Bromberg, R. Pugatch and Y. Siber-berg, Quantum walk of two interacting bosons, Phys. Rev. A 86,011603 (2012).
[34]L. Sansoni, F. Sciarrino, g. Vallone, P. Mataloni, A. Crespi, R. Ramponi adn R. Osellame, Two-Particle Bosonic-Fermionic Quantum Walk via Integrated Photonics, Phys. Rev. Lett.108,010502 (2012).
[35]B. C. Sanders, S. D. Bartlett, B. Tragenna and P. L. Knight, Quantum quin-cunx in cavity quantum electrodynamics., Phys. Rev. A 67,042305 (2003).
[36]M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Infor-mation, section 10.5.4, The Gottesman-Knill Theorem, Cambridge University Press, Cambridge (2000).
[37]D. A. Meyer and N. R. Wallach, From quantum cellular automata to quantum lattice gases, J. Stat. Phys.85,551-574 (1996).
[38]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU(2) coin, Phy. Rev. A 77,032326 (2008).
[39]E. Feldman and M. Hillery, Scattering theory and discrete-time quantum walks, Phys. Lett. A 324,277 (2004).
[40]M. Hillery, J. Bergou, and E. Feldman, Quantum walks based on an interfer-ometric analogy, Phys. Rev. A 68,032314 (2003).
[41]L. K. Grover, A fast quantum mechanical algorithm for database search, In: Proceedings of the 28th Annual ACM Symposium on the Theory of Comput-ing. pp.212-219 (1996).
[42]F. Magniez, A. Nayak, P. Richter and M. Santha, On the hitting times of quantum versus random walks, In:Proceedings of the 20th annual ACM-SIAM SODA, ACM, New York, pp.86-95 (2009).
[43]P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury and F. Vatan, A new universal and fault-tolerant quantum basis, Inf. Proc. Lett.75,101 (2000).
[44]A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin and H. Weinfurter, Elementary gates for quantum computation, Phys. Rev. A 52,3457 (1995).
[45]Y. Omar, N. Paunkovic, L. Sheridan and S. Bose, Quantum walk on a line with two entangled particles, Phys. Rev. A 74,042304 (2006).
[46]M. Stefanak, S. M. Barnett, B. Kollar, T. Kiss and I. Jex, Directional cor-relations in quantum walks with two particles, New Journal of Physics 13, 033029 (2011).
[47]J. Kempe, Quantum random walks: an introductory overview, Contemporary Physics,44(4),307 (2003).
[48]S. E. Venegas-Andraca, Quantum walks: a comprehensive review, Quantum Inf. Process 11,1015-1106 (2012).
[49]量子线路的交换,看起来不可实现,但是这里只是提出理论的逻辑模型,而不是研究基于量子随机行走的实际实现。
[1]A. P. Flitney, D. Abbott, Quantum models of Parrondo's games, Phys. A 324 (2003) 152-156.
[2]A. P. Flitney and D. Abbott, Quantum walks with history depen-dence, J. Phys. A: Math. Gen.37,7581 (2004).
[3]A. P. Flitney, Quantum Parrondo's games using quantum walks, arXiv:quant-ph/1209.2252 (2012).
[4]A. Nayak and A. Vishwanath, Quantum Walk on the line, Technical Report, Center for Discrete Mathematics & Theoretical Computer Science (2000).
[5]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU(2) coin, Phy. Rev. A 77, 032326 (2008).
[1]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[2]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the 35th ACM symposium on Theory of computing (ACM Press, New York), (2003), pp.59-68.
[3]N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67,052307 (2003).
[4]A. M. Childs, E. Farhi, and S. Gutmann, An Example of the Dif-ference Between Quantum and Classical Random Walks, Quantum Information Processing,1,35 (2002).
[5]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[6]A. Ambainis, Quantum walks and their algorithmic applications, arXiv:quant-ph/0403120; Int. J. Quantum Inf.01,507 (2003).
[7]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Proceedings of the 16th ACM-SIAM symposium on Discrete algo-rithms, pp.1099-1108, (2005).
[8]A. M. Childs, Universal Computation by Quantum Walk, Phys. Rev. Lett.102,180501 (2009).
[9]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Uni-versal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[10]D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, Proceeding STOC'01 Proceedings of the 33th annual ACM symposium on Theory of computing, pp.50-59 (2001).
[11]L. C. Kwek and Setiawan, One-dimensional quantum walk with a moving boundary, Phy. Rev. A 84,032319 (2011).
[12]J. Sebby-Strabley, M. Anderlini, P. S. Jessen, and J. V. Porto, Lattice of double wells for manipulating pairs of cold atoms, Phys. Rev. A 73,033605 (2006).
[13]H. B. Perets, Y. Lahini, F. Pozzi, M. Sorel, R. Morandotti, and Y. Silberberg, Phys. Realization of Quantum Walks with Negligible Decoherence in Waveguide Lattices, Rev. Lett.100,170506 (2008).
[14]K. Mayer, M. C. Tichy, F. Mintert, T. Konrad, and A. Buchleitner, Counting statistics of many-particle quantum walks, Phys. Rev. A 83,062307 (2011).
[15]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[16]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum random walks with decoherent coins, Phys. Rev. A 67,032304 (2003).
[17]B. C. Travaglione and G. J. Milburn, Implementing the quantum random walk, Phys. Rev. A 65,032310 (2002).
[18]E. Feldman and M. Hillery, Scattering theory and discrete-time quan-tum walks, Phys. Lett. A 324,277 (2004).
[19]M. Hillery, J. Bergou, and E. Feldman, Quantum walks based on an interferometric analogy, Phys. Rev. A 68,032314 (2003).
[20]P. Ribeiro, P. Milman and R. Mosseril, Aperiodic Quantum Random Walks, Phys. Rev. Lett.93,190503 (2004)
[21]A. Wojcikl, T.z Luczak2, P. Kurzynskil, A. Grudkal, and M. Bed-narska2, Quasiperiodic Dynamics of a Quantum Walk on the Line, Phys. Rev. Lett.93,180601 (2004).
[22]Y. Shikanol and H. Katsura, Localization and fractality in inhomo-geneous quantum walks with self-duality, Phys. Rev. E 82,031122 (2010).
[23]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU (2) coin, Phy. Rev. A 77, 032306 (2008).
[1]G. P. Harmer, D. Abbott, P. G. Taylor and J. M. R. Parrondo, Random Fluctuations:unsolved Problems of Noise, in Proc.2nd int. Conf. on Un-solvedProblems of Noise and Fluctuations (UPoN'99), Adelaide, Australia, 511,189 (1999).
[2]G. P. Harmer and, D. Abbott, Losing strategies can win by Parrondo's para-dox, Nature 402,864(1999).
[3]J. M. R. Parrondo, G. P. Harmer, and D. Abbott, New Paradoxical Games Based on Brownian Ratchets, Phys. Rev. Lett.85,5226-5229 (2000).
[4]G. P. Harmer, D. Abbott, P. G. Taylor and J. M. R. Parrondo, Brownian ratchets and Parrondo's games, Chaos 11,705 (2001).
[5]A. Allison, D. Abbott, Control systems with stochastic feedback, Chaos 11 (2001) 715.
[6]J. Ng and D. Abbott, Introduction to Quantum Games and a Quantum Parrondo Game,9th Internation Symposium on Dynamic Games and Ap-plications held in Adelaide, South Australia, Dec 18-21, (2000).
[7]A. P. Flitney, J. Ng, and D. Abbott, Quantum Parrondo's games, Physica A 314,35 (2002).
[8]D. A. Meyer and H. Blumer, Parrondo games as lattice gas automata,J. Stat. Phys.107,225 (2002).
[9]C. F. Lee and N. Johnson, Parrondo Games and Quantum Algorithms, Phys. Lett. A 301,343 (2002); also arXiv:quant-ph/0203043 (2002).
[10]A. P. Flitney, D. Abbott, Quantum models of Parrondo's games, Phys. A 324,152-156 (2003).
[11]A. P. Flitney and D. Abbott, Quantum walks with history dependence, J. Phys. A: Math. Gen.37,7581 (2004).
[12]P. Gawron, J. A. Miszczak, Quantum Implementation of Parrondo's Para-dox, Fluct. Noise Lett.05, L471 (2005); also arXiv:quant-ph/0502185 (2005).
[13]J. Kosik, J. A. Miszczak and V. Buzek, Quantum Parrondo's game with random strategies, J. Mod. Opt.54,2275 (2007); also arXiv:quant-ph/0704.2937 (2007).
[14]S. Khan, M. Ramzan,M. K. Khan, Quantum Parrondo's Games Under Decoherence, Int. J. Theor. Phys.49,31-41 (2010).
[15]L. Chen, C. F. Li, M. Gong, G. C. Guo, Quantum Parrondo game based on a quantum ratchet effect, Phys. A 389,4071-4074 (2010).
[16]C. Ampadu, A quantum analogue of parrondo's game, arXiv:quant-ph/1104.5275 (2011).
[17]C. M. Chandrashekar, S. Banerjee, Parrondo's game using a discrete-time quantum walk, Physics Lett. A 375,1553 (2011).
[18]A. P. Flitney, Quantum Parrondo's games using quantum walks, arXiv:quant-ph/1209.2252 (2012).
[19]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[20]J. Kempe, Quantum random walks: an introductory overview, Contempo-rary Physics,44(4),307 (2003).
[21]S. E. Venegas-Andraca, Quantum walks:a comprehensive review, Quantum Inf. Process (2012) 11:1015-1106.
[22]E. Farhi and S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58,915 (1998).
[23]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spiel-man, Exponential algorithmic speedup by a quantum walk, Proceedings of the 35th ACM symposium on Theory of computing (ACM Press, New York), (2003), pp.59-68.
[24]N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search al-gorithm, Phys. Rev. A 67,052307 (2003).
[25]A. M. Childs, E. Farhi, and S. Gutmann, An Example of the Difference Be-tween Quantum and Classical Random Walks, Quantum Information Pro-cessing,1,35 (2002).
[26]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[27]A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quanum Inform.01,507 (2003).
[28]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Pro-ceedings of the 16th ACM-SIAM symposium on Discrete algorithms, pp. 1099-1108, (2005).
[29]A. M. Childs, Universal Computation by Quantum Walk, Phys. Rev. Lett. 102,180501 (2009).
[30]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[31]A. M. Childs, D. Gosset and Z. Webb, Universal computation by multi-particle quantum walk, arXiv:quant-ph/1205.3782 (2012); Science 39,791 (2013).
[32]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[33]M. Li, Y. S. Zhang and G. C. Guo, Quantum random walk in periodic po-tential on a line, Chin. Phys. Lett.30,020304 (2013).
[34]M. Li, Y. S. Zhang and G. C. Guo, Average position in quantum walks with a U(2) coin, Chin. Phys. B 22,030310 (2013).
[2]A. Nayak and A. Vishwanath, Quantum Walk on the line, Technical Report, Center for Discrete Mathematics & Theoretical Computer Science (2000).
[3]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[4]E. Farhi, Quantum computation and decision trees, Phys. Rev. A 58,915 (1998).
[5]J. Watrous, Quantum simulations of classical random walks and undirected graph connectively, Journal of Computer and System Sciences 62, pp.376-391 (2001).
[6]N. Shenvi, J. Kempe and K. B. Whaley, Quantum random-walk search algo-rithm, Phys. Rev. A 67,052307 (2003).
[7]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[8]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Proceedings of the 16th ACM-SIAM symposium on Discrete algorithms, pp.1099-1108, (2005).
[9]S. Aaronson and A. Ambainis, Quantum search'of spatial regions, Theory of Computing (Also FOCS'03),1, pp.47-79, (2005).
[10]F. Magniez, A. Nayak, J. Roland and M. Santha, Search via quantum walk, Proceedings of the 39th ACM Symposium on Theory of Computing, pp. 575-584 (2007).
[11]N. B. Lovett, M. Everitt, M. Trevers, D. Mosby, D. Stockton and V. Kendon, Spatial search using the discrete time quantum walk, Nat. Comput.11:23-35 (2012).
[12]A. M. Childs, E. Farhi and S. Gutmann, An Example of the Difference Be-tween Quantum and Classical Random Walks, Quantum Information Process-ing.1, pp.35-43 (2002).
[13]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, Exponential algorithmic speedup by quantum walk, In:Proceedings of the 35th ACM Symposium on The Theory of Computation (STOC'03) ACM, pp.59-68 (2003).
[14]A. Ambainis, Quantum walk algorithm for element distinctness, SIAM Jour-nal on Computing,37(1),210-239, (2007).
[15]A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett.102, 180501 (2009).
[16]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[17]A. M. Childs, D. Gosset and Z. Webb, Universal computation by multi-particle quantum walk, arXiv:quant-ph/1205.3782 (2012); Science 39,791 (2013).
[18]D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, Proceeding STOC'01 Proceedings of the 33th annual ACM symposium on Theory of computing, pp.50-59 (2001).
[19]L. C. Kwek and Setiawan, One-dimensional quantum walk with a moving boundary, Phy. Rev. A 84,032319 (2011).
[20]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[21]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum random walks with decoherent coins, Phys. Rev. A 67,032304 (2003).
[22]J. Du, H. Li, X. Xu, M. Shi, J. Wu, X. Zhou, and R. Han, Experimental implementation of the quantum random-walk algorithm, Phys. Rev. A 67, 042316, (2003).
[23]C. A. Ryan, M. Laforest, J. C. Boileau, and R. Laflamme, Experimental implementation of discrete time quantum random walk on an NMR quantum information processor, Phys. Rev. A 72,062317, (2005).
[24]J. M. Grossman, D. Ciampini, M. D. Arcy, K. Helmerson, P. D. Lett, W. D. Phillips, A. Vaziri and S. L. Rolston, Implementation of a quantum random walk with a sodium Bose-Einstein condensate, The 35th Meeting of the Di-vision of Atomic, Molecular and Optical Physics, Tuscon, AZ, (DAMOP04), (2004).
[25]H. B. Perets, Y. Lahini, F. Pozzi, M. Sorel, R. Morandotti and Y. Silberberg, Realization of quantum walks with negligible decoherence in waveguide lattices, Phys. Rev. Lett.100,170506 (2008).
[26]B. C. Travaglione and G. J. Milburn, Implementing the quantum random walk, Phys. Rev. A 65,032310 (2002)
[27]W. Dur, R. Raussendorf, V. M. Kendon, and H. J. Briegel, Quantum walks in optical lattice, Phys. Rev. A 66,052319, (2002).
[28]K. Eckert, J. Mompart, G. Birkl, and M. Lewenstein. One-and two-dimen-sional walks in arrays of optical traps, Phys. Rev. A 72,012327 (2005).
[29]C. M. Chandrashekar. Implementing the one-dimensional quantum (Hadamard) walk using Bose-Einstein condensate., Phys. Rev. A 74, 032307 (2006).
[30]K. Manouchehri and J. B. Wang, Quantum walks in an array of quantum dots, J. Phys. A: Math. Theor.41,065304 (2008).
[31]Z. Y. Ma, K. Burnett, M. A. d'Arcy, and S. A. Gardiner, Quantum random walk using quantum accelerator modes, Phys. Rev. A 73,013401 (2006).
[32]Y. Bromberg, Y. Lahini, R. Morandotti and Y. Silberberg, Quantum and Classical Correlations in Waveguide Lattices, Phys. Rev. Lett.102,253904 (2009).
[33]Y. Lahini, M. Verbin, S. D. Huber, Y. Bromberg, R. Pugatch and Y. Siber-berg, Quantum walk of two interacting bosons, Phys. Rev. A 86,011603 (2012).
[34]L. Sansoni, F. Sciarrino, g. Vallone, P. Mataloni, A. Crespi, R. Ramponi adn R. Osellame, Two-Particle Bosonic-Fermionic Quantum Walk via Integrated Photonics, Phys. Rev. Lett.108,010502 (2012).
[35]B. C. Sanders, S. D. Bartlett, B. Tragenna and P. L. Knight, Quantum quin-cunx in cavity quantum electrodynamics., Phys. Rev. A 67,042305 (2003).
[36]M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Infor-mation, section 10.5.4, The Gottesman-Knill Theorem, Cambridge University Press, Cambridge (2000).
[37]D. A. Meyer and N. R. Wallach, From quantum cellular automata to quantum lattice gases, J. Stat. Phys.85,551-574 (1996).
[38]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU(2) coin, Phy. Rev. A 77,032326 (2008).
[39]E. Feldman and M. Hillery, Scattering theory and discrete-time quantum walks, Phys. Lett. A 324,277 (2004).
[40]M. Hillery, J. Bergou, and E. Feldman, Quantum walks based on an interfer-ometric analogy, Phys. Rev. A 68,032314 (2003).
[41]L. K. Grover, A fast quantum mechanical algorithm for database search, In: Proceedings of the 28th Annual ACM Symposium on the Theory of Comput-ing. pp.212-219 (1996).
[42]F. Magniez, A. Nayak, P. Richter and M. Santha, On the hitting times of quantum versus random walks, In:Proceedings of the 20th annual ACM-SIAM SODA, ACM, New York, pp.86-95 (2009).
[43]P. O. Boykin, T. Mor, M. Pulver, V. Roychowdhury and F. Vatan, A new universal and fault-tolerant quantum basis, Inf. Proc. Lett.75,101 (2000).
[44]A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin and H. Weinfurter, Elementary gates for quantum computation, Phys. Rev. A 52,3457 (1995).
[45]Y. Omar, N. Paunkovic, L. Sheridan and S. Bose, Quantum walk on a line with two entangled particles, Phys. Rev. A 74,042304 (2006).
[46]M. Stefanak, S. M. Barnett, B. Kollar, T. Kiss and I. Jex, Directional cor-relations in quantum walks with two particles, New Journal of Physics 13, 033029 (2011).
[47]J. Kempe, Quantum random walks: an introductory overview, Contemporary Physics,44(4),307 (2003).
[48]S. E. Venegas-Andraca, Quantum walks: a comprehensive review, Quantum Inf. Process 11,1015-1106 (2012).
[49]量子线路的交换,看起来不可实现,但是这里只是提出理论的逻辑模型,而不是研究基于量子随机行走的实际实现。
[1]A. P. Flitney, D. Abbott, Quantum models of Parrondo's games, Phys. A 324 (2003) 152-156.
[2]A. P. Flitney and D. Abbott, Quantum walks with history depen-dence, J. Phys. A: Math. Gen.37,7581 (2004).
[3]A. P. Flitney, Quantum Parrondo's games using quantum walks, arXiv:quant-ph/1209.2252 (2012).
[4]A. Nayak and A. Vishwanath, Quantum Walk on the line, Technical Report, Center for Discrete Mathematics & Theoretical Computer Science (2000).
[5]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU(2) coin, Phy. Rev. A 77, 032326 (2008).
[1]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[2]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the 35th ACM symposium on Theory of computing (ACM Press, New York), (2003), pp.59-68.
[3]N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67,052307 (2003).
[4]A. M. Childs, E. Farhi, and S. Gutmann, An Example of the Dif-ference Between Quantum and Classical Random Walks, Quantum Information Processing,1,35 (2002).
[5]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[6]A. Ambainis, Quantum walks and their algorithmic applications, arXiv:quant-ph/0403120; Int. J. Quantum Inf.01,507 (2003).
[7]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Proceedings of the 16th ACM-SIAM symposium on Discrete algo-rithms, pp.1099-1108, (2005).
[8]A. M. Childs, Universal Computation by Quantum Walk, Phys. Rev. Lett.102,180501 (2009).
[9]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Uni-versal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[10]D. Aharonov, A. Ambainis, J. Kempe, U. Vazirani, Quantum walks on graphs, Proceeding STOC'01 Proceedings of the 33th annual ACM symposium on Theory of computing, pp.50-59 (2001).
[11]L. C. Kwek and Setiawan, One-dimensional quantum walk with a moving boundary, Phy. Rev. A 84,032319 (2011).
[12]J. Sebby-Strabley, M. Anderlini, P. S. Jessen, and J. V. Porto, Lattice of double wells for manipulating pairs of cold atoms, Phys. Rev. A 73,033605 (2006).
[13]H. B. Perets, Y. Lahini, F. Pozzi, M. Sorel, R. Morandotti, and Y. Silberberg, Phys. Realization of Quantum Walks with Negligible Decoherence in Waveguide Lattices, Rev. Lett.100,170506 (2008).
[14]K. Mayer, M. C. Tichy, F. Mintert, T. Konrad, and A. Buchleitner, Counting statistics of many-particle quantum walks, Phys. Rev. A 83,062307 (2011).
[15]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[16]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum random walks with decoherent coins, Phys. Rev. A 67,032304 (2003).
[17]B. C. Travaglione and G. J. Milburn, Implementing the quantum random walk, Phys. Rev. A 65,032310 (2002).
[18]E. Feldman and M. Hillery, Scattering theory and discrete-time quan-tum walks, Phys. Lett. A 324,277 (2004).
[19]M. Hillery, J. Bergou, and E. Feldman, Quantum walks based on an interferometric analogy, Phys. Rev. A 68,032314 (2003).
[20]P. Ribeiro, P. Milman and R. Mosseril, Aperiodic Quantum Random Walks, Phys. Rev. Lett.93,190503 (2004)
[21]A. Wojcikl, T.z Luczak2, P. Kurzynskil, A. Grudkal, and M. Bed-narska2, Quasiperiodic Dynamics of a Quantum Walk on the Line, Phys. Rev. Lett.93,180601 (2004).
[22]Y. Shikanol and H. Katsura, Localization and fractality in inhomo-geneous quantum walks with self-duality, Phys. Rev. E 82,031122 (2010).
[23]C. M. Chandrashekar, R. Srikanth, and R. Laflamme, Optimizing the discrete time quantum walk using a SU (2) coin, Phy. Rev. A 77, 032306 (2008).
[1]G. P. Harmer, D. Abbott, P. G. Taylor and J. M. R. Parrondo, Random Fluctuations:unsolved Problems of Noise, in Proc.2nd int. Conf. on Un-solvedProblems of Noise and Fluctuations (UPoN'99), Adelaide, Australia, 511,189 (1999).
[2]G. P. Harmer and, D. Abbott, Losing strategies can win by Parrondo's para-dox, Nature 402,864(1999).
[3]J. M. R. Parrondo, G. P. Harmer, and D. Abbott, New Paradoxical Games Based on Brownian Ratchets, Phys. Rev. Lett.85,5226-5229 (2000).
[4]G. P. Harmer, D. Abbott, P. G. Taylor and J. M. R. Parrondo, Brownian ratchets and Parrondo's games, Chaos 11,705 (2001).
[5]A. Allison, D. Abbott, Control systems with stochastic feedback, Chaos 11 (2001) 715.
[6]J. Ng and D. Abbott, Introduction to Quantum Games and a Quantum Parrondo Game,9th Internation Symposium on Dynamic Games and Ap-plications held in Adelaide, South Australia, Dec 18-21, (2000).
[7]A. P. Flitney, J. Ng, and D. Abbott, Quantum Parrondo's games, Physica A 314,35 (2002).
[8]D. A. Meyer and H. Blumer, Parrondo games as lattice gas automata,J. Stat. Phys.107,225 (2002).
[9]C. F. Lee and N. Johnson, Parrondo Games and Quantum Algorithms, Phys. Lett. A 301,343 (2002); also arXiv:quant-ph/0203043 (2002).
[10]A. P. Flitney, D. Abbott, Quantum models of Parrondo's games, Phys. A 324,152-156 (2003).
[11]A. P. Flitney and D. Abbott, Quantum walks with history dependence, J. Phys. A: Math. Gen.37,7581 (2004).
[12]P. Gawron, J. A. Miszczak, Quantum Implementation of Parrondo's Para-dox, Fluct. Noise Lett.05, L471 (2005); also arXiv:quant-ph/0502185 (2005).
[13]J. Kosik, J. A. Miszczak and V. Buzek, Quantum Parrondo's game with random strategies, J. Mod. Opt.54,2275 (2007); also arXiv:quant-ph/0704.2937 (2007).
[14]S. Khan, M. Ramzan,M. K. Khan, Quantum Parrondo's Games Under Decoherence, Int. J. Theor. Phys.49,31-41 (2010).
[15]L. Chen, C. F. Li, M. Gong, G. C. Guo, Quantum Parrondo game based on a quantum ratchet effect, Phys. A 389,4071-4074 (2010).
[16]C. Ampadu, A quantum analogue of parrondo's game, arXiv:quant-ph/1104.5275 (2011).
[17]C. M. Chandrashekar, S. Banerjee, Parrondo's game using a discrete-time quantum walk, Physics Lett. A 375,1553 (2011).
[18]A. P. Flitney, Quantum Parrondo's games using quantum walks, arXiv:quant-ph/1209.2252 (2012).
[19]Y. Aharonov, L. Davidovich, and N. Zagury, Quantum random walks, Phys. Rev. A 48,1687 (1993).
[20]J. Kempe, Quantum random walks: an introductory overview, Contempo-rary Physics,44(4),307 (2003).
[21]S. E. Venegas-Andraca, Quantum walks:a comprehensive review, Quantum Inf. Process (2012) 11:1015-1106.
[22]E. Farhi and S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58,915 (1998).
[23]A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spiel-man, Exponential algorithmic speedup by a quantum walk, Proceedings of the 35th ACM symposium on Theory of computing (ACM Press, New York), (2003), pp.59-68.
[24]N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search al-gorithm, Phys. Rev. A 67,052307 (2003).
[25]A. M. Childs, E. Farhi, and S. Gutmann, An Example of the Difference Be-tween Quantum and Classical Random Walks, Quantum Information Pro-cessing,1,35 (2002).
[26]A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70,022314 (2004).
[27]A. Ambainis, Quantum walks and their algorithmic applications, Int. J. Quanum Inform.01,507 (2003).
[28]A. Ambainis and J. Kempe, Coins make quantum walks faster, In Pro-ceedings of the 16th ACM-SIAM symposium on Discrete algorithms, pp. 1099-1108, (2005).
[29]A. M. Childs, Universal Computation by Quantum Walk, Phys. Rev. Lett. 102,180501 (2009).
[30]N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A 81,042330 (2010).
[31]A. M. Childs, D. Gosset and Z. Webb, Universal computation by multi-particle quantum walk, arXiv:quant-ph/1205.3782 (2012); Science 39,791 (2013).
[32]T. A. Brun, H. A. Carteret, and A. Ambainis, Quantum walks driven by many coins, Phys. Rev. A 67,052317 (2003).
[33]M. Li, Y. S. Zhang and G. C. Guo, Quantum random walk in periodic po-tential on a line, Chin. Phys. Lett.30,020304 (2013).
[34]M. Li, Y. S. Zhang and G. C. Guo, Average position in quantum walks with a U(2) coin, Chin. Phys. B 22,030310 (2013).