Quantum computation lies at the intersection of computer science and physics and is a promising emerging technology. Quantum algorithms take advantage of quantum effects not available to conventional computers. There are striking examples where a quantum algorithm, running on a quantum computer, would outperform any classical computer attempting the same task. These include finding the prime factors of a number, searching an unordered list and determining who wins a game. The discovery of new algorithms is key to the growth of this field. The investigators hope to develop new algorithms as well as study the performance of certain known algorithms whose run time is not yet established. The hope is to continue to develop a fruitful synergy between techniques used in physics and conventional algorithm design. The research here would bridge the fields of computer science and physics looking for new algorithms as well as deepening our understanding of the physics which underlies the quantum speedups. The development of a large scale functioning quantum computer would change the world of computation and this research attempts to aid the effort to develop such a machine.
The topics to be investigated include quantum walk algorithms, algorithms for evaluating the Jones polynomial and other related quantities, as well as cryptographic protocols for unforgeable identification. The adiabatic algorithm will be studied using a Matrix Product State ansatz as well as by large scale numerical simulation and the fault tolerance of this algorithm will also be investigated.
We all know that the world we live in has been dramatically changed by computers. In some sense, all computers in use work on the same set of principles: binary operations; that is, the manipulation of 0's and 1's (bits). However, at base, the world is quantum mechanical. Quantum mechanics does not have a simple description in terms of bits. The simplest quantum mechanical object is a two-state quantum system, such as a spinning electron. Like a bit, the spin of an electron can be in one of two states, up or down. However, for the electron, there are more possibilies. The electron can also be in a "superposition" of up and down. and there is no analog of this superposition in a classical computer. This, along with other quantum mechanical features, introduces the possibility that quantum computers have power that ordinary computers do not have. In fact, this power has been demonstrated. There are certain computational problems that a quantum computer can solve with many fewer steps than any algorithm for these problems running on a classical computer. The goal of this investigation was to use ideas from physics in the design of algorithms for quantum computers. Since aside from tiny toy experimental systems, there is no functioning quantum computer yet in existence, the study of the performance of quantum algorithms on an as-yet-unrealized machine necessitates a mathematical approach. This project has focussed on the development of mathematical tools which allow us to study the performance of these computers of the future. One of the approaches to quantum computation is the quantum adiabatic algorithm. This algorithm was designed to solve difficult optimization problems, such as finding good airline route schedules or finding the best match for a feature in a picture. This physics-based algorithm can be shown to solve these problems if it runs for long enough, but it is not clear how long "long enough" needs to be. One of the goals of this project was to see whether the quantum algorithm would achieve run times which are shorter than those required by a classical computer. The investigors developed several techniques for analyzing the run time of the adiabatic algorithm for problems of practical interest, and ran a large-scale study on a computer cluster to help determine the required run-times on a quantum computer. Quantum mechanical effects have made possible provably secure communication over a fiber optic cable. This guarantees that any attempt at eavesdropping will either fail or be detected. The investigators on this project have invented another quantum cryptographic protocol, quantum money. Good currency should be very difficult to copy, but it should be easy to check whether a bill is counterfeit. Quantum mechanics can dramatically improve the difficulty of counterfeiting bills while still allowing the merchant to easily check that a bill is valid. The investigators have proposed a specific theoretical scheme for minting quantum bills which makes them counterfeit-proof and still verifiable. However, for this scheme to be practical, quantum computers would have to be as ubiquitous as ATMs are today.
