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

Iowa State University, Ames IA

Investigators

Abstract

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 MERIT In 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 IMPACT Algorithmic 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.