Continuous-time Quantum Algorithms [electronic Resource] : Searching and Adiabatic Computation


Book Description

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e.g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. Soon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. I begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework.




Quantum Walks and Search Algorithms


Book Description

The revised edition of this book offers an extended overview of quantum walks and explains their role in building quantum algorithms, in particular search algorithms. Updated throughout, the book focuses on core topics including Grover's algorithm and the most important quantum walk models, such as the coined, continuous-time, and Szedgedy's quantum walk models. There is a new chapter describing the staggered quantum walk model. The chapter on spatial search algorithms has been rewritten to offer a more comprehensive approach and a new chapter describing the element distinctness algorithm has been added. There is a new appendix on graph theory highlighting the importance of graph theory to quantum walks. As before, the reader will benefit from the pedagogical elements of the book, which include exercises and references to deepen the reader's understanding, and guidelines for the use of computer programs to simulate the evolution of quantum walks. Review of the first edition: “The book is nicely written, the concepts are introduced naturally, and many meaningful connections between them are highlighted. The author proposes a series of exercises that help the reader get some working experience with the presented concepts, facilitating a better understanding. Each chapter ends with a discussion of further references, pointing the reader to major results on the topics presented in the respective chapter.” - Florin Manea, zbMATH.







A Primer on Quantum Computing


Book Description

This book is about quantum computing and quantum algorithms. The book starts with a chapter introducing the basic rules of quantum mechanics and how they can be used to build quantum circuits and perform computations. Further, Grover's algorithm is presented for unstructured search discussing its consequences and applications. Next, important techniques are discussed such as Quantum Fourier Transform and quantum phase estimation. Finally, Shor's algorithm for integer factorization is explained. At last, quantum walks are explained in detail covering both the discrete and continuous time models,and applications of this techniques are described for the design and analyses of quantum algorithms.




Quantum Information with Continuous Variables


Book Description

Quantum information may sound like science fiction but is, in fact, an active and extremely promising area of research, with a big dream: to build a quantum computer capable of solving problems that a classical computer could not even begin to handle. Research in quantum information science is now at an advanced enough stage for this dream to be credible and well-worth pursuing. It is, at the same time, too early to predict how quantum computers will be built, and what potential technologies will eventually strike gold in their ability to manipulate and process quantum information. One direction that has reaped many successes in quantum information processing relies on continuous variables. This area is bustling with theoretical and experimental achievements, from continuous-variable teleportation, to in-principle demonstrations of universal computation and efficient error correction. Now the time has come to compile some of the major results into one volume. In this book the leading researchers of the field present up-to-date developments of continuous-variable quantum information. This book is organized to suit many reader levels with introductions to every topic and in-depth discussions of theoretical and experimental results.




Experimental Aspects of Quantum Computing


Book Description

Practical quantum computing still seems more than a decade away, and researchers have not even identified what the best physical implementation of a quantum bit will be. There is a real need in the scientific literature for a dialogue on the topic of lessons learned and looming roadblocks. This reprint from Quantum Information Processing is dedicated to the experimental aspects of quantum computing and includes articles that 1) highlight the lessons learned over the last 10 years, and 2) outline the challenges over the next 10 years. The special issue includes a series of invited articles that discuss the most promising physical implementations of quantum computing. The invited articles were to draw grand conclusions about the past and speculate about the future, not just report results from the present.




Quantum Information with Continuous Variables of Atoms and Light


Book Description

Quantum information describes the new field which bridges quantum physics and information science. The quantum world allows for completely new architectures and protocols. While originally formulated in continuous quantum variables, the field worked almost exclusively with discrete variables, such as single photons and photon pairs. The renaissance of continuous variables came with European research consortia such as ACQUIRE (Advanced Coherent Quantum Information Research) in the late 1990s, and QUICOV (Quantum Information with Continuous Variables) from 2000OCo2003. The encouraging research results of QUICOV and the new conference series CVQIP (Continuous Variable Quantum Information Processing) triggered the idea for this book. This book presents the state of the art of quantum information with continuous quantum variables. The individual chapters discuss results achieved in QUICOV and presented at the first five CVQIP conferences from 2002OCo2006. Many world-leading scientists working on continuous variables outside Europe also contribute to the book.




Quantum Walks for Computer Scientists


Book Description

Quantum computation, one of the latest joint ventures between physics and the theory of computation, is a scientific field whose main goals include the development of hardware and algorithms based on the quantum mechanical properties of those physical systems used to implement such algorithms. Solving difficult tasks (for example, the Satisfiability Problem and other NP-complete problems) requires the development of sophisticated algorithms, many ofwhich employ stochastic processes as their mathematical basis. Discrete random walks are a popular choice among those stochastic processes. Inspired on the success of discrete random walks in algorithm development, quantum walks, an emerging field of quantum computation, is a generalization of random walks into the quantum mechanical world. The purpose of this lecture is to provide a concise yet comprehensive introduction to quantum walks. Table of Contents: Introduction / Quantum Mechanics / Theory of Computation / Classical Random Walks / Quantum Walks / Computer Science and Quantum Walks / Conclusions




Handbook of Natural Computing


Book Description

Natural Computing is the field of research that investigates both human-designed computing inspired by nature and computing taking place in nature, i.e., it investigates models and computational techniques inspired by nature and also it investigates phenomena taking place in nature in terms of information processing. Examples of the first strand of research covered by the handbook include neural computation inspired by the functioning of the brain; evolutionary computation inspired by Darwinian evolution of species; cellular automata inspired by intercellular communication; swarm intelligence inspired by the behavior of groups of organisms; artificial immune systems inspired by the natural immune system; artificial life systems inspired by the properties of natural life in general; membrane computing inspired by the compartmentalized ways in which cells process information; and amorphous computing inspired by morphogenesis. Other examples of natural-computing paradigms are molecular computing and quantum computing, where the goal is to replace traditional electronic hardware, e.g., by bioware in molecular computing. In molecular computing, data are encoded as biomolecules and then molecular biology tools are used to transform the data, thus performing computations. In quantum computing, one exploits quantum-mechanical phenomena to perform computations and secure communications more efficiently than classical physics and, hence, traditional hardware allows. The second strand of research covered by the handbook, computation taking place in nature, is represented by investigations into, among others, the computational nature of self-assembly, which lies at the core of nanoscience, the computational nature of developmental processes, the computational nature of biochemical reactions, the computational nature of bacterial communication, the computational nature of brain processes, and the systems biology approach to bionetworks where cellular processes are treated in terms of communication and interaction, and, hence, in terms of computation. We are now witnessing exciting interaction between computer science and the natural sciences. While the natural sciences are rapidly absorbing notions, techniques and methodologies intrinsic to information processing, computer science is adapting and extending its traditional notion of computation, and computational techniques, to account for computation taking place in nature around us. Natural Computing is an important catalyst for this two-way interaction, and this handbook is a major record of this important development.




Quantum Computation and Quantum Information


Book Description

One of the most cited books in physics of all time, Quantum Computation and Quantum Information remains the best textbook in this exciting field of science. This 10th anniversary edition includes an introduction from the authors setting the work in context. This comprehensive textbook describes such remarkable effects as fast quantum algorithms, quantum teleportation, quantum cryptography and quantum error-correction. Quantum mechanics and computer science are introduced before moving on to describe what a quantum computer is, how it can be used to solve problems faster than 'classical' computers and its real-world implementation. It concludes with an in-depth treatment of quantum information. Containing a wealth of figures and exercises, this well-known textbook is ideal for courses on the subject, and will interest beginning graduate students and researchers in physics, computer science, mathematics, and electrical engineering.