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

图上量子行走的控制理论及其在量子算法中的应用

• 批准号: 0824085
• 负责人: Domenico D'Alessandro
• 金额: $ 24.61万
• 依托单位: Iowa State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0824085&HistoricalAwards=false
• 关键词: Control; Theory; Quantum; Walks; Graphs

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.

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