Control Theory for Quantum Walks on Graphs and its Applications to Quantum Algorithms

在过去的十年里，全球范围内开展了一场激烈的研究活动，旨在将量子力学系统用作计算工具。这既关系到实验，也关系到理论。量子信息理论得到了发展，其目标之一是设计出可以在量子系统中执行的高效计算算法。这些被称为量子算法。可以用来执行算法的重要的量子系统类别是量子行走。这些系统可以以各种方式物理实现，例如通过耦合原子和电磁场。他们的行为类似于随机行走，这种系统由步行者组成，根据投掷硬币的结果在不同的位置之间移动。已经证明，当用作计算工具时，量子行走提供了比在经典计算机上实现的算法更快、更有效的算法。INTELLECTUAL MERIT在最近的一项工作中，PI展示了如何在每一步的进化中引入一定的自由度后，量子行走可以被视为控制系统。通过这种修改，量子行走可能会获得在实际应用中感兴趣的新状态。这种更丰富的、潜在有用的动态行为是以仅对现有实验方案进行微小修改为代价的。这推动了量子行走控制理论的发展，该理论研究量子行走的动力学，并设计合适的控制律来获得期望的行为。这个项目的主要目标是发展这样的理论。PI将应用和增强他在过去几年开发的用于控制和分析量子系统的通用工具。这种方法主要使用李代数和李群理论的几何思想，但也将引入其他数学领域的一些概念。初步研究和结果表明，这是研究这些模型的正确方法。在这个过程中，PI将解决一些相关的问题，这些问题多年来一直是量子信息中的基本公开问题。事实上，可以预料到，这里的一些分析也将影响这些长期存在的问题。从更广泛的角度来看，这个项目将为量子算法的设计引入一个新的观点。在许多情况下，这样的算法是以理想的方式控制量子系统状态的方法。因此，算法本身可以被视为受控过程，并且可以从控制理论的角度来研究有关其效率和性能的问题。量子算法的控制理论将把它们与它们的物理实现联系起来，并提供新的见解和分析。通过研究使用量子行走的重要算法类别，PI将朝着这个新方向迈出第一步。BROADER IMPACT量子行走算法在计算机科学中的应用将受益于这项研究，因此将对更多的科学和技术领域产生间接有益的影响。例如，一大类被称为随机化算法的计算算法需要以规定的概率分布随机抽样。用量子系统实现这样的概率分布可以被视为控制理论的问题，将在本研究中处理。该项目的一个重要影响是它将在物理、控制和计算机科学界之间产生协同效应。拟议的研究具有很强的跨学科性质，需要来自不同领域的人之间进行交流。此外，本研究还具有较强的教育价值。它结合了不同领域的想法来分析一类系统，这类系统相对简单，因此可以用分析工具接近，但同时在许多不同的应用中具有重要意义。研究生和本科生将直接参与计划中的研究，并将从与多元文化科学环境的互动中受益。

The last decade has seen an intense research activity worldwide aiming at the use of quantum mechanical systems as computational tools. This has concerned both experiments and the theory. Quantum information theory was developed and one of its goals was to devise efficient computational algorithms which can be performed with quantum systems. These are called quantum algorithms.The important classes of quantum systems that can be used to perform algorithms are quantum walks. These systems may be physically implemented in various ways, for example by coupling an atom and an electromagnetic field. Their behavior resembles that of a random walk, the system consisting of a walker that moves among different positions according to the result of a coin tossing. It has been shown that, when used as computational tools, quantum walks give fast and efficient algorithms that perform better than algorithms implemented on a classical computer.INTELLECTUAL MERITIn a recent work, the PI has shown how quantum walks can be considered as control systems after introducing some degree of freedom in the evolution at each step. With this modification, quantum walks may achieve new states that are of interest in practical applications. This richer, potentially useful, dynamical behavior comes at the expense of only minor modifications in existing experimental proposals. This motivates the development of a control theory for quantum walks which studies their dynamics and designs suitable control laws to obtain the desired behavior. The main objective of this project is to develop such a theory.The PI will apply and enhance the general tools for control and analysis of quantum systems he has developed in the last few years. This methodology mainly uses geometric ideas of Lie algebra and Lie group theory but several concepts from other areas of mathematics will be introduced. Preliminary studies and results have shown that this is the correct approach to investigate these models. In the process, the PI will tackle some related issues which have stood as fundamental open problems in quantum information for several years. It is in fact expected that some of the analysis developed here will impact these long standing problems as well.From a more general perspective, this project will introduce a new point of view in the design of quantum algorithms. Such algorithms are, in many cases, methods to control the state of a quantum system in a desired fashion. Therefore algorithms themselves can be seen as controlled processes and issues concerning their efficiency and performance can be studied from a control theoretic perspective. A control theory for quantum algorithms will link them to their physical implementation and provide new insight and analysis. By looking at the important class of algorithms using quantum walks, the PI will take the first steps in this new direction.BROADER IMPACTAlgorithmic applications of quantum walks in computer science will benefit from this research, which will have therefore indirect beneficial impact on many more areas of science and technology. For example, a large class of computational algorithms called, randomized algorithms, requires sampling at random with a prescribed probability distribution. Achieving such a probability distribution with a quantum system can be seen as a problem of control theory and will be treated in this research.A significant impact of this project is the synergy it will create among the physics, the control and the computer science communities. The strong interdisciplinary nature of the proposed research will require communication among people from different areas. Moreover this study has strong educational value. It combines ideas from different fields in the analysis of a class of systems which is relatively simple, and therefore approachable with analytic tools, but at the same time of great importance in many different applications. Graduate and undergraduate students will be directly involved in the planned research and will benefit from the interaction with a culturally diverse scientific environment.