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 a最近的工作，PI在每个步骤中引入某种程度的自由度之后，PI显示了如何将量子步行视为控制系统。通过这种修改，量子步行可能会实现在实际应用中感兴趣的新州。这种更丰富，有用的动态行为是以仅在现有实验建议中进行的微小修改为代价的。这激发了量子步行的控制理论的发展，该理论研究了他们的动态，并设计了合适的控制定律以获得所需的行为。该项目的主要目的是发展这样的理论。PI将应用和增强一般工具来控制和分析他在过去几年中开发的量子系统。该方法主要使用谎言代数的几何思想和谎言群体理论，但将引入其他数学领域的几个概念。初步研究和结果表明，这是研究这些模型的正确方法。在此过程中，PI将解决一些相关问题，这些问题已成为量子信息中基本的开放问题。 实际上，预计此处进行的一些分析也会影响这些长期存在的问题。从更一般的角度来看，该项目将在量子算法设计中引入新的观点。在许多情况下，这种算法是以所需方式控制量子系统状态的方法。因此，可以将算法本身视为受控过程，并且可以从控制理论的角度研究有关其效率和性能的问题。量子算法的控制理论将它们与其物理实施联系起来，并提供新的见解和分析。通过使用量子步道查看重要的算法类别，PI将在这个新方向上采取第一步。BoaderImpactalgorithmic在计算机科学中的应用程序将从这项研究中受益，因此，这将对更多的科学和技术领域有间接的有益影响。例如，一种称为随机算法的大量计算算法需要随机采样，并具有规定的概率分布。通过量子系统实现这种概率分布可以看作是控制理论的问题，并将在本研究中对待。该项目的重大影响是它将在物理，控制和计算机科学社区中产生的协同作用。拟议的研究的强大跨学科性质将需要来自不同地区的人们之间的交流。此外，这项研究具有强大的教育价值。它结合了来自不同领域的想法在对一类系统的分析中，这些系统相对简单，因此可以使用分析工具，但同时在许多不同的应用中都非常重要。研究生和本科生将直接参与计划的研究，并将受益于与文化多样的科学环境的互动。