Synthesis Lectures on Quantum Computing – serie

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

In this text we present a technical overview of the emerging field of quantum computation along with new research results by the authors. What distinguishes our presentation from that of others is our focus on the relationship between quantum computation and computer science. Specifically, our emphasis is on the computational model of quantum computingrather than on the engineering issues associated with its physical implementation. We adopt this approach for the same reason that a book on computer programming doesn't cover the theory and physical realization of semiconductors. Another distinguishing feature of this text is our detailed discussion of the circuit complexity of quantum algorithms. To the extent possible we have presented the material in a form that is accessible to the computer scientist, but in many cases we retain the conventional physics notation so that the reader will also be able to consult the relevant quantum computing literature. Although we expect the reader tohave a solid understanding of linear algebra, we do not assume a background in physics. This text is based on lectures given as short courses and invited presentations around the world, and it has been used as the primary text for a graduatecourse at George Mason University. In all these cases our challenge has been the same: how to present to a generalaudience a concise introduction to the algorithmic structure and applications of quantum computing on an extremely short period of time. The feedback from these courses and presentations has greatly aided in making our exposition of challenging concepts more accessible to a general audience.Table of Contents: Introduction / The Algorithmic Structure of Quantum Computing / Advantages and Limitations of Quantum Computing / Amplitude Amplification / Case Study: Computational Geometry / The Quantum Fourier Transform / Case Study: The Hidden Subgroup / Circuit Complexity Analysis of Quantum Algorithms / Conclusions / Bibliography

Quantum cryptography is a rapidly developing field that draws from a number of disciplines, from quantum optics to information theory to electrical engineering. By combining some fundamental quantum mechanical principles of single photons with various aspects of information theory, quantum cryptography represents a fundamental shift in the basis for security from numerical complexity to the fundamental physical nature of the communications channel. As such, it promises the holy grail of data security: theoretically unbreakable encryption. Of course, implementing quantum cryptography in real broadband communications systems poses some unique challenges, including generating single photons, distilling random keys from the quantum key distribution process, and maintaining security at both the theoretical and practical level. Overall, quantum cryptography has a place in the history of secret keeping as a novel and potentially useful paradigm shift in the approach to broadband data encryption.Table of Contents: Introduction / Elements of Classical Cryptography / The Quantum Mechanics of Photons / Fundamentals of Quantum Key Distribution / Information Theory and Key Reconciliation / Components for Broadband QKD / A Survey of QKD Implementations / Conclusion - QKD in the Marketplace

In quantum computing, where algorithms exist that can solve computational problems more efficiently than any known classical algorithms, the elimination of errors that result from external disturbances or from imperfect gates has become the "holy grail", and a worldwide quest for a large scale fault-tolerant, and computationally superior, quantum computer is currently taking place. Optimists rely on the premise that, under a certain threshold of errors, an arbitrary long fault-tolerant quantum computation can be achieved with only moderate (i.e., at most polynomial) overhead in computational cost. Pessimists, on the other hand, object that there are in principle (as opposed to merely technological) reasons why such machines are still inexistent, and that no matter what gadgets are used, large scale quantum computers will never be computationally superior to classical ones. Lacking a complete empirical characterization of quantum noise, the debate on the physical possibility of such machines invites philosophical scrutiny. Making this debate more precise by suggesting a novel statistical mechanical perspective thereof is the goal of this project.Table of Contents: Introduction / The Curse of the Open System / To Balance a Pencil on Its Tip / Universality at All Cost / Coda

This book offers a concise review of quantum radar theory. Our approach is pedagogical, making emphasis on the physics behind the operation of a hypothetical quantum radar. We concentrate our discussion on the two major models proposed to date: interferometric quantum radar and quantum illumination. In addition, this book offers some new results, including an analytical study of quantum interferometry in the X-band radar region with a variety of atmospheric conditions, a derivation of a quantum radar equation, and a discussion of quantum radar jamming.This book assumes the reader is familiar with the basic principles of non-relativistic quantum mechanics, special relativity, and classical electrodynamics. Our discussion of quantum electrodynamics and its application to quantum radar is brief, but all the relevant equations are presented in the text. In addition, the reader is not required to have any specialized knowledge on classical radar theory.Table of Contents: Introduction / The Photon / Photon Scattering / Classical Radar Theory / Quantum Radar Theory / Quantum Radar Cross Section / Conclusions

This book is concerned with the models of quantum computation. Information processing based on the rules of quantum mechanics provides us with new opportunities for developing more efficient algorithms and protocols. However, to harness the power offered by quantum information processing it is essential to control the behavior of quantum mechanical objects in a precise manner. As this seems to be conceptually difficult at the level of quantum states and unitary gates, high-level quantum programming languages have been proposed for this purpose.The aim of this book is to provide an introduction to abstract models of computation used in quantum information theory. Starting from the abstract models of Turing machine and finite automata, we introduce the models of Boolean circuits and Random Access Machine and use them to present quantum programming techniques and quantum programming languages.Table of Contents: Introduction / Turing machines / Quantum Finite State Automata / Computational Circuits / Random Access Machines / Quantum Programming Environment / Quantum Programming Languages / Imperative quantum programming / Functional Quantum Programming / Outlook

This book is a brief introduction to negative quantum channels, i.e., linear, trace-preserving (and consistent) quantum maps that are not completely positive. The flat and sharp operators are introduced and explained. Complete positivity is presented as a mathematical property, but it is argued that complete positivity is not a physical requirement of all quantum operations. Negativity, a measure of the lack of complete positivity, is proposed as a tool for empirically testing complete positivity assumptions.Table of Contents: Preface / Acknowledgments / Introduction and Definition of Terms / Tomography / Non-Positive Reduced Dynamics / Complete Positivity / Physical Motivation of Complete Positivity / Measures of Complete Positivity / Negative Channels / Negative Climates with Diagonal Composite Dynamics / Rabi Channels / Physical Motivations for Sharp Operations / Negative Qubit Channel Examples with Multi-Qubit Baths / Proposed Experimental Demonstration of Negativity / Implications of Negative Channels / Uses for Negative Channels / Conclusions / Bibliography / Author's Biography

Adiabatic quantum computation (AQC) is an alternative to the better-known gate model of quantum computation. The two models are polynomially equivalent, but otherwise quite dissimilar: one property that distinguishes AQC from the gate model is its analog nature. Quantum annealing (QA) describes a type of heuristic search algorithm that can be implemented to run in the ``native instruction set'' of an AQC platform. D-Wave Systems Inc. manufactures {quantum annealing processor chips} that exploit quantum properties to realize QA computations in hardware. The chips form the centerpiece of a novel computing platform designed to solve NP-hard optimization problems. Starting with a 16-qubit prototype announced in 2007, the company has launched and sold increasingly larger models: the 128-qubit D-Wave One system was announced in 2010 and the 512-qubit D-Wave Two system arrived on the scene in 2013. A 1,000-qubit model is expected to be available in 2014. This monograph presents an introductory overview of this unusual and rapidly developing approach to computation. We start with a survey of basic principles of quantum computation and what is known about the AQC model and the QA algorithm paradigm. Next we review the D-Wave technology stack and discuss some challenges to building and using quantum computing systems at a commercial scale. The last chapter reviews some experimental efforts to understand the properties and capabilities of these unusual platforms. The discussion throughout is aimed at an audience of computer scientists with little background in quantum computation or in physics.Table of Contents: Acknowledgments / Introduction / Adiabatic Quantum Computation / Quantum Annealing / The D-Wave Platform / Computational Experience / Bibliography / Author's Biography

The adiabatic quantum computation (AQC) is based on the adiabatic theorem to approximate solutions of the Schrödinger equation. The design of an AQC algorithm involves the construction of a Hamiltonian that describes the behavior of the quantum system. This Hamiltonian is expressed as a linear interpolation of an initial Hamiltonian whose ground state is easy to compute, and a final Hamiltonian whose ground state corresponds to the solution of a given combinatorial optimization problem. The adiabatic theorem asserts that if the time evolution of a quantum system described by a Hamiltonian is large enough, then the system remains close to its ground state. An AQC algorithm uses the adiabatic theorem to approximate the ground state of the final Hamiltonian that corresponds to the solution of the given optimization problem. In this book, we investigate the computational simulation of AQC algorithms applied to the MAX-SAT problem. A symbolic analysis of the AQC solution is given in order to understand the involved computational complexity of AQC algorithms. This approach can be extended to other combinatorial optimization problems and can be used for the classical simulation of an AQC algorithm where a Hamiltonian problem is constructed. This construction requires the computation of a sparse matrix of dimension 2n × 2n, by means of tensor products, where n is the dimension of the quantum system. Also, a general scheme to design AQC algorithms is proposed, based on a natural correspondence between optimization Boolean variables and quantum bits. Combinatorial graph problems are in correspondence with pseudo-Boolean maps that are reduced in polynomial time to quadratic maps. Finally, the relation among NP-hard problems is investigated, as well as its logical representability, and is applied to the design of AQC algorithms. It is shown that every monadic second-order logic (MSOL) expression has associated pseudo-Boolean maps that can be obtained by expanding the given expression, and also can be reduced to quadratic forms.Table of Contents: Preface / Acknowledgments / Introduction / Approximability of NP-hard Problems / Adiabatic Quantum Computing / Efficient Hamiltonian Construction / AQC for Pseudo-Boolean Optimization / A General Strategy to Solve NP-Hard Problems / Conclusions / Bibliography / Authors' Biographies