One‑Dimensional Discrete Time Quantum Walk: Path Analysis Approach, Probability Distribution and Symmetry

LIN Yun-guo

doi:10.12263/DZXB.20200709

您当前的位置：

首页 >

文章列表页 >

One‑Dimensional Discrete Time Quantum Walk: Path Analysis Approach, Probability Distribution and Symmetry

PAPERS | 更新时间：2025-12-08

- One‑Dimensional Discrete Time Quantum Walk: Path Analysis Approach, Probability Distribution and Symmetry
- ACTA ELECTRONICA SINICA Vol. 49, Issue 7, Pages: 1323-1330(2021)
- 作者机构：
  
  1.福建农林大学计算机与信息学院，福建福州350002
  2.南威软件集团博士后科研工作站，福建泉州362000
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20200709
  CLC： TP301.6
- Received：14 July 2020，
  
  Revised：2021-01-05，
  
  Published：25 July 2021
- 稿件说明：
移动端阅览
林运国.一维离散时间量子行走的路径分析法、概率分布与对称性[J].电子学报,2021,49(07):1323-1330.

LIN Yun-guo.One‑Dimensional Discrete Time Quantum Walk: Path Analysis Approach, Probability Distribution and Symmetry[J].ACTA ELECTRONICA SINICA,2021,49(07):1323-1330.
林运国.一维离散时间量子行走的路径分析法、概率分布与对称性[J].电子学报,2021,49(07):1323-1330. DOI： 10.12263/DZXB.20200709.

LIN Yun-guo.One‑Dimensional Discrete Time Quantum Walk: Path Analysis Approach, Probability Distribution and Symmetry[J].ACTA ELECTRONICA SINICA,2021,49(07):1323-1330. DOI： 10.12263/DZXB.20200709.

摘要

为了模拟长程的一维离散时间量子行走的演化过程以及降低计算复杂性，提出一种路径分析方法.首先分析系统到达某个位置的路径分块和路径数，将系统移位到某个位置演化算子进行分解，表示成二阶矩阵线性空间的一组基的线性组合；然后用超几何级数进行化简，给出概率分布的计算方法；最后分析产生对称式概率分布的充分条件，表明对称性只与量子初态有关.实验结果表明，该方法能够有效模拟系统的长时间演化过程.相关结果可以推广到更一般类型的离散时间量子行走.

Abstract

In order to simulate one‑dimensional discrete time quantum walks after a long time of evolution and reduce the computational complexity

we propose a path analysis approach. Dividing every path of a discrete time quantum walk into a set of blocks and counting number of paths starting from an initial qubit state

we give an expression for some evolution operator in form of a linear combination of a fixed set of basis in a 2‑dimensional matrix space. As a consequence

we present a calculating formula of probability distribution in terms of hypergeometric polynomial and give a sufficient condition on symmetry of probability distribution which is only determined by initial qubit states. Our experimental results reveal that this method can well simulate the evolution process in a long time scale. We also briefly extend these studies to more general discrete time quantum walks.

关键词

Keywords

references

Aharonov Y ， Davidovich L ， Zagury N . Quantum random walks ［J］. Physical Review A ， 1993 ， 48 （ 2 ）： 1687 - 1690 .

Shenvi N ， Kempe J ， Whaley K B . Quantum random walk search algorithm ［J］. Physical Review A ， 2003 ， 67 （ 5 ）： 052307 .

Ambainis A . Quantum walk algorithm for element distinctness ［J］. SIAM Journal on Computing ， 2007 ， 37 （ 1 ）： 210 - 239 .

Kempe J . Quantum Random Walks Hit Exponentially Faster ［EB/OL］. https：//arxiv.org/abs/quant-ph/0205083v1 https://arxiv.org/abs/quant-ph/0205083v1 ， 2002 .

Ambainis A . Quantum walks and their algorithmic applications ［J］. International Journal of Quantum Information ， 2003 ， 01 （ 04 ）： 507 - 518 .

Andraca V ， Elías S . Quantum Walks for Computer Scientists ［M］. USA ， Vermont： Morgan & Claypool ， 2008 . 61 - 87 .

Farhi E ， Gutmann S . Quantum computation and decision trees ［J］. Physical Review A ， 1998 ， 58 （ 2 ）： 915 - 928 .

Watrous J . Quantum simulations of classical random walks and undirected graph connectivity ［J］. Journal of Computer System Sciences ， 2001 ， 62 （ 2 ）： 376 - 391 .

Kendon ， Viv . Quantum walks on general graphs ［J］. International Journal of Quantum Information ， 2008 ， 04 （ 05 ）： 791 - 805 .

Mackay T D ， Bartlett S D ， Stephenson L T ， et al . Quantum walks in higher dimensions ［J］. Journal of Physics A ， 2002 ， 35 （ 12 ）： 2745 - 2753 .

Brun T A ， Carteret H A ， Ambainis A . Quantum walks driven by many coins ［J］. Physical Review A ， 2003 ， 67 （ 5 ）： 052317 .

Ribeiro P ， Milman P ， Mossed R . Aperiodic quantum random walks ［J］. Physical Review Letters ， 2004 ， 93 （ 19 ）： 190503 .

Ambainis A ， Bach E ， Nayak A ， et al . One‑dimensional quantum walks ［A］. Proceedings of the Thirty‑Third Annual ACM Symposium on Theory of Computing ［C］. New York， USA ： ACM ， 2001 . 37 - 49 .

Chandrashekar C M ， Srikanth R ， Laflamme R ， et al . Optimizing the discrete time quantum walk using a SU（2） coin ［J］. Physical Review A ， 2008 ， 77 （ 3 ）： 032326 .

Rousseva J ， Kovchegov Y . On alternating quantum walks ［J］. Physica A： Statistical Mechanics and Its Applications ， 2017 ， 470 ： 309 - 320 .

Ahmad R ， Bibi S ， Sajjad U . Randomizing Quantum Walk ［EB/OL］. https：//arxiv.org/abs/2003.00440 https://arxiv.org/abs/2003.00440 ， 2020 .

Wang F ， Zhang P ， Wang Y ， et al . Quantum walk with one variable absorbing boundary ［J］. Physics Letters A ， 2017 ， 381 （ 2 ）： 65 - 69 .

Schuhmacher P K ， Govia L C G ， Taketani B G ， et al . Quantum Simulation of a Discrete‑Time Quantum Stochastic Walk ［EB/OL］. https：//arxiv.org/abs/2004.06151 https://arxiv.org/abs/2004.06151 ， 2020 .

Venegasandraca S E . Quantum walks： a comprehendsive review ［J］. Quantum Information Processing ， 2012 ， 11 （ 5 ）： 1015 - 1106 .

Higuchi Y ， Konno N ， Sato I ， et al . Periodicity of the discrete‑time quantum walk on a finite graph ［J］. Interdisciplinary Information Sciences ， 2017 ， 23 ： 75 - 86 .

Krovi H ， Brun T A . Hitting time for quantum walks on the hypercube ［J］. Physical Review A ， 2006 ， 73 （ 3 ）： 501 - 507 .

Konno N ， Namiki T ， Soshi T . Symmetry of distribution for the one‑dimensional Hadamard walk ［J］. Interdisciplinary Information Sciences ， 2002 ， 10 （ 1 ）： 11 - 22 .

Konno N . A new type of limit theorems for the on e‑dimensional quantum random walk ［J］. Journal of The Mathematical Society of Japan ， 2005 ， 57 （ 4 ）： 1179 - 1195 .

韩琦，陈芷禾，殷世德，等 . 基于Hadamard算子的二维离散量子行走的概率测度估计［J］. 应用数学学报， 2020 ， 43 （ 1 ）： 49 - 61 .

Han Qi ， Chen Zhi‑he ， Yin Shi‑de ， et al . Estimation of probability measure for 2‑D discrete quantum walk based on Hadamard operator ［J］. Acta Mathematicae Applicatae Sinica ， 2020 ， 43 （ 1 ）： 49 - 61 . （in Chinese）

Ashwin N ， Ashvin V . Quantum Walk on the Line ［EB/OL］. https：//arxiv.org/abs/quant-ph/0010117 https://arxiv.org/abs/quant-ph/0010117 ， 2000 .

Carteret H A ， Ismail M E H ， Richmond B . Three routes to the exact asymptotics for the one‑dimensional quantum walk ［J］. Journal of Physics A ， 2003 ， 36 （ 33 ）： 8775 - 8795 .

Xu X ， Ide Y . Exact solutions and symmetry analysis for the limiting probability distribution of quantum walks ［J］. Annals of Physics ， 2016 ， 373 ： 682 - 693 .

Rodrigues J ， Paunković N ， Mateus P . A simulator for discrete quantum walks on lattices ［J］. International Journal of Modern Physics C ， 2017 ， 28 （ 04 ）： 1750055 .

Yuwana L ， Purwanto A ， Endarko E ， et al . Matlab programming to implement quantum walk algorithm for presenting probability distributions of quantum walks ［J］. Journal of Informatics and Mathematical Sciences ， 2018 ， 10 ： 23 - 32 .

任春年，李文东，顾永建 . 普适投币算符作用的量子行走数值解以及安德森局域化仿真［J］. 中国海洋大学学报（自然科学版）， 2017 ， 47 （ 4 ）： 121 - 125 .

Ren Chun‑nian ， Li Wen‑dong ， Gu Yong‑jian . The numerical solution of quantum walk with general coin operator and simulation Anderson localization ［J］. Periodical of Ocean University of China ， 2017 ， 47 （ 4 ）： 121 - 125 . （in Chinese）

胡杨熠 . 离散时间量子漫步的动态演化［D］. 长沙：国防科技大学， 2019 .

王元 . 数学大辞典［M］. 北京：科学出版社， 2016 . 525 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Simplified Approach for Calculation Zero-Order Diffraction of the 1-D Grating with the Incident Plane Parallel to the Grating Line

Analysis of Airborne Radar Clutter at L-Band HH Polarization

Limit Distribution Theorem for a Sum of Independent Random Variables in a Finite Field and Its Applications in Stream Ciphers

Related Author

CHEN Shu-qiang

KANG Shi-feng

ZHANG Zhong-zhi

GE De-biao

Zhang Muxiang

Related Institution

University of Electronic Science and Technology of China

University of Electronic Science and Technology of ChinaChengduSichuan 610054China

Qingdao Branch,China Research Institute of Radiowave Propagation

School of Sciences,Xidian University

Qingdao BranchChina Research Institute of Radiowave PropagationQingdaoShandong 266071China

⁰