基于量子随机游走的量子程序设计

Quantum walks as a quantum analogue of classical random walks play an important role in the development of quantum computing. It is an universal quantum computing model. One of the prominent application of quantum walks in quantum computing is used to design algorithms, such as search algorithms, element distinctness, etc. Another promising application of quantum walks is the perfect state transfer between two vertices of a graph or a lattice. It is often used to check and verify the correctness of a quantum program. However, existing quantum programming language is not power enough to display all the distinguished properties of quantum walks and quantum search algorithms. By using of formalization, graphic theory, algebraic spectrum theory, and quantum information theory, this project is intended to study the design of quantum programming language based on quantum random walks. First, we give a in-depth study of all kinds of quantum random walk models and its applications in search algorithms and quantum communication protocols, and show the clear gap between solvable problem by quantum walks and random walks, speed limit and complexity classification of solvable problems. Then we try to design a new more applicable quantum programming language to implement quantum walk models and its algorithms. This project can not only promote the study of quantum random walks and quantum algorithms, but also promote the establishment and improvement of the theory of quantum programming.

量子随机游走作为经典随机游走的量子推广在量子计算中扮演着重要的角色，它既是通用的量子计算模型也是设计量子算法，实现量子通讯协议，展示和验证量子程序的一种重要工具。由于现存的量子程序语言并不能完全的体现基于量子随机游走的量子算法的特性，本项目拟用形式化、图论、代数谱论和量子信息论等基本工具研究基于量子随机游走的量子程序语言的设计。通过深入的研究各种量子随机游走模型及它们在量子算法、量子通讯方面的应用，给出它们与经典随机游走模型在解决问题的类型分类、复杂度分类及加速极限方面的最大区别。在此基础上探索能真正展示基于量子随机游走算法特点的量子程序设计语言，进而给出一般的量子程序设计语言。本项目的研究不仅能推进量子随机游走、量子算法的发展，也能促进量子程序设计理论的建立和完善。

量子力学区别经典力学的特性是不可克隆、退相干、叠加、纠缠和隐形传输等特异性质，这使得量子信息的远程传输、纠缠态的制备、量子算法的设计都面临很大的挑战性。在信息爆炸时代，如何管理海量数据是人们面临的主要挑战之一，这也导致量子机器学习这个新兴领域的出现。如何设计超越经典机器学习的量子算法一直是一个特别困难的问题。. 针对量子计算中遇到的实际问题，本项目创新性地应用多硬币量子游走模型和张量网络，在量子隐形传输、量子态的完美传递、量子纠缠态的生成、量子算法的设计及经典机器学习中的聚类方面做出了原创性的理论和实验验证工作。具体地，首次提出了基于两硬币量子游走的隐形传输框架，成功实现了各种图及远距离的量子隐形传输。对比Bennett的框架，不需要提前准备纠缠态，所需的纠缠源可以在游走的过程中自动产生, 这也避免了退相干现象；不需要联合Bell基测量，只需在单粒子上进行局部测量，避开了实验的难点。利用两硬币量子游走模型，提出了基于直线，圈，完全图，正则图上的完美状态转移协议，以硬币为信息载体，通过交替的使用两个硬币算子，可以将信息完美的传到图上任意指定的位置，克服了单硬币模型遇到的问题。借助IBM量子计算机，首次在超导芯片机上成功进行了传递高维态的量子实验。创新性地提出了一种借助于多硬币量子游走模型制备多体高维纠缠态的方案，即在纠缠交换的框架下，利用量子游走代替贝尔基测量，从而自然地避免了Bell基测量难实现这个瓶颈问题。并给出实验实现和应用。基于马尔可夫链量子游走，将量子 fast-forwarding 思想用于量子插值游走模型构建了一个新的量子平稳分布采样算法，该算法不仅可以对非正则图加速，而且可以保持现有量子算法对正则图的加速。进一步提出广义量子插值游走模型，大大提高了搜索和采样的概率。提出了基于张量网络的K-means 聚类算法，即避免了局部极小值问题，又达到了当前最好的准确率。