QUANTUM COMPUTING - Masaryk University
iQUANTUM COMPUTINGJozef GruskaQUANTUM WORLDCLASSICAL WORLDQuantum computationClassical computationisdeterministichighly (exponentially) parallelworking with on).described by Schrodinger equationusing entanglement as a computationalresourceisprobabilistic, sequentialworking with real probabilitiesMEASUREMENTone of the outcomes of quantum superpositionis randomly picked up - all other resultsof computation are irreversibly lostE.T.Only at this point do indeterminacy and probabilitiescome inquantum measurement has the effect of ‘‘magnifying’’quantum events from quantum to classical level
ii
iii
ivOn the book web pageshttp://mcgraw-hill.co.uk/gruskaone findes.1. Basic information about the contents of the book.2. Ordering and price information.3. Second part of the Appendix. (A survey of basic concepts from complexity theory andmodels of computing. Additional exercises. Historical and bibliographical refrences.)4. eps-versions of figures from the book.5. Corrections.6. Additions.
vTo my parentsfor their love and care.To my wifefor her ever increasing care, support and patience.To my childrenwith best wishes for their future.To my grandsonwith best wishes for quantum computing age.
vi
ContentsContentsvPrefacexiii1 FUNDAMENTALS1.1 Why Quantum Computing . . . . . . . . . . . . . . . . .1.2 Prehistory of Quantum Computing . . . . . . . . . . . . .1.3 From Randomized to Quantum Computation . . . . . . .1.3.1 Probabilistic Turing machines . . . . . . . . . . . .1.3.2 Quantum Turing machines . . . . . . . . . . . . .1.4 Hilbert Space Basics . . . . . . . . . . . . . . . . . . . . .1.4.1 Orthogonality, bases and subspaces . . . . . . . . .1.4.2 Operators . . . . . . . . . . . . . . . . . . . . . . .1.4.3 Observables and measurements . . . . . . . . . . .1.4.4 Tensor products in Hilbert spaces . . . . . . . . . .1.4.5 Mixed states and density operators . . . . . . . . .1.5 Experiments . . . . . . . . . . . . . . . . . . . . . . . . . .1.5.1 Classical experiments . . . . . . . . . . . . . . . .1.5.2 Quantum experiments—single particle interference1.5.3 Quantum experiments—measurements . . . . . . .1.6 Quantum Principles . . . . . . . . . . . . . . . . . . . . .1.6.1 States and amplitudes . . . . . . . . . . . . . . . .1.6.2 Measurements—the projection approach . . . . . .1.6.3 Evolution of quantum systems . . . . . . . . . . .1.6.4 Compound quantum systems . . . . . . . . . . . .1.6.5 Quantum theory interpretations . . . . . . . . . .1.7 Classical Reversible Gates and Computing . . . . . . . . .1.7.1 Reversible gates . . . . . . . . . . . . . . . . . . .1.7.2 Reversible Turing machines . . . . . . . . . . . . .1.7.3 Billiard ball model of (reversible) computing . . 2 ELEMENTS2.1 Quantum Bits and Registers .2.1.1 Qubits . . . . . . . . .2.1.2 Two-qubit registers . .2.1.3 No-cloning theorem .2.1.4 Quantum registers . .575858666869.vii.
viiiCONTENTS2.2.747478798181889095973 ALGORITHMS3.1 Quantum Parallelism and Simple Algorithms . . . . . . . . . . . .3.1.1 Deutsch’s problem . . . . . . . . . . . . . . . . . . . . . . .3.1.2 The Deutsch–Jozsa promise problem . . . . . . . . . . . . .3.1.3 Simon’s problems . . . . . . . . . . . . . . . . . . . . . . . .3.2 Shor’s Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.1 Number theory basics . . . . . . . . . . . . . . . . . . . . .3.2.2 Quantum Fourier Transform . . . . . . . . . . . . . . . . .3.2.3 Shor’s factorization algorithm . . . . . . . . . . . . . . . . .3.2.4 Shor’s discrete logarithm algorithm . . . . . . . . . . . . . .3.2.5 The hidden subgroup problems . . . . . . . . . . . . . . . .3.3 Quantum Searching and Counting . . . . . . . . . . . . . . . . . .3.3.1 Grover’s search algorithm . . . . . . . . . . . . . . . . . . .3.3.2 G-BBHT search algorithm . . . . . . . . . . . . . . . . . . .3.3.3 Minimum-finding algorithm . . . . . . . . . . . . . . . . . .3.3.4 Generalizations and modifications of search problems . . . .3.4 Methodologies to Design Quantum Algorithms . . . . . . . . . . .3.4.1 Amplitude amplification–boosting search probabilities . . .3.4.2 Amplitude amplification—speeding of the states searching .3.4.3 Case studies . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5 Limitations of Quantum Algorithms . . . . . . . . . . . . . . . . .3.5.1 No quantum speed-up for the parity function . . . . . . . .3.5.2 Framework for proving lower bounds . . . . . . . . . . . . .3.5.3 Oracle calls limitation of quantum computing . . . . . . . 371371391391401401431474 AUTOMATA4.1 Quantum Finite Automata . . . . . . . . . . . . . . . . . . . .4.1.1 Models of classical finite automata . . . . . . . . . . . .4.1.2 One-way quantum finite automata . . . . . . . . . . . .4.1.3 1QFA versus 1FA . . . . . . . . . . . . . . . . . . . . . .4.1.4 Two-way quantum finite automata . . . . . . . . . . . .4.1.5 2QFA versus 1FA . . . . . . . . . . . . . . . . . . . . . .4.2 Quantum Turing Machines . . . . . . . . . . . . . . . . . . . .4.2.1 One-tape quantum Turing machines . . . . . . . . . . .4.2.2 Variations on the basic model . . . . . . . . . . . . . . .4.2.3 Are quantum Turing machines analogue or discrete? . .4.2.4 Programming techniques for quantum Turing machines4.3 Quantum Cellular Automata . . . . . . . . . . . . . . . . . . .1491511511521551571601641641691711741772.3Quantum Entanglement . . . . . . . . . . . . . . . .2.2.1 Entanglement of pure states . . . . . . . . . .2.2.2 Quantifying entanglement . . . . . . . . . . .2.2.3 Substituting entanglement for communicationQuantum Circuits . . . . . . . . . . . . . . . . . . .2.3.1 Quantum gates . . . . . . . . . . . . . . . . .2.3.2 Measurement gates . . . . . . . . . . . . . . .2.3.3 Universality of quantum gates . . . . . . . . .2.3.4 Arithmetical circuits . . . . . . . . . . . . . .2.3.5 Quantum superoperator circuits . . . . . . .
ixCONTENTS4.3.14.3.24.3.34.3.4Classical cellular automata . . . . . . . . . . . . . . . . . . .One-dimensional quantum cellular automata . . . . . . . . .Partitioned quantum one-dimensional cellular automata . . .Quantum cellular automata versus quantum Turing machines.1771801831855 COMPLEXITY5.1 Universal Quantum Turing Machines . . . . . . . . . . . . . . . . . . .5.1.1 Efficient implementation of unitary transformations . . . . . . .5.1.2 Design of a universal quantum Turing machine . . . . . . . . . .5.2 Quantum Computational Complexity . . . . . . . . . . . . . . . . . . . .5.2.1 Basic quantum versus classical complexity classes . . . . . . . . .5.2.2 Relativized quantum complexity . . . . . . . . . . . . . . . . . .5.3 Quantum Communication Complexity . . . . . . . . . . . . . . . . . . .5.3.1 Classical and quantum communication protocols and complexity5.3.2 Quantum communication versus computation complexity . . . .5.4 Computational Power of quantum non-linear mechanics . . . . . . . . .1911921921961991992042072082102126 CRYPTOGRAPHY6.1 Prologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2 Quantum Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . .6.2.1 Basic ideas of two parties quantum key generation . . . . . . . . .6.2.2 Security issues of QKG protocols . . . . . . . . . . . . . . . . . . .6.2.3 Quantum key generation protocols BB84 and B92 . . . . . . . . .6.2.4 Multiparty key generation . . . . . . . . . . . . . . . . . . . . . . .6.2.5 Entanglement-based QKG protocols . . . . . . . . . . . . . . . . .6.2.6 Unconditional security of QKG . . . . . . . . . . . . . . . . . . .6.2.7 Experimental quantum cryptography . . . . . . . . . . . . . . . . .6.3 Quantum Cryptographic Protocols . . . . . . . . . . . . . . . . . . . . . .6.3.1 Quantum coin-flipping and bit commitment protocols . . . . . . .6.3.2 Quantum oblivious transfer protocols . . . . . . . . . . . . . . . .6.3.3 Security of the quantum protocols . . . . . . . . . . . . . . . . . .6.3.4 Security limitations of the quantum cryptographic protocols . . . .6.3.5 Insecurity of quantum one-sided two-party computation protocols .6.4 Quantum Teleportation and Superdense Coding . . . . . . . . . . . . . . .6.4.1 Basic principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6.4.2 Teleportation circuit . . . . . . . . . . . . . . . . . . . . . . . . . .6.4.3 Quantum secret sharing . . . . . . . . . . . . . . . . . . . . . . . .6.4.4 Superdense coding . . . . . . . . . . . . . . . . . . . . . . . . . . 502502522542567 PROCESSORS7.1 Early Quantum Computers Ideas . . . . . . . . . .7.1.1 Benioff’s quantum computer . . . . . . . .7.1.2 Feynman’s quantum computer . . . . . . .7.1.3 Peres’ quantum computer . . . . . . . . . .7.1.4 Deutsch’s quantum computer . . . . . . . .7.2 Impacts of Imperfections . . . . . . . . . . . . . .7.2.1 Internal imperfections . . . . . . . . . . . .7.2.2 Decoherence . . . . . . . . . . . . . . . . . .7.3 Quantum Computation and Memory Stabilization.259261261261262263264264265268.
073083103113138 INFORMATION8.1 Quantum Entropy and Information . . . . . . . . . . . . . . . . .8.1.1 Basic concepts of classical information theory . . . . . . .8.1.2 Quantum entropy and information . . . . . . . . . . . . .8.2 Quantum Channels and Data Compression . . . . . . . . . . . .8.2.1 Quantum sources, channels and transmissions . . . . . . .8.2.2 Shannon’s coding theorems . . . . . . . . . . . . . . . . .8.2.3 Schumacher’s noiseless coding theorem . . . . . . . . . . .8.2.4 Dense quantum coding . . . . . . . . . . . . . . . . . . . .8.2.5 Quantum Noisy Channel Transmissions . . . . . . . . . .8.2.6 Capacities of erasure and depolarizing channels . . . . . .8.3 Quantum Entanglement . . . . . . . . . . . . . . . . . . . . . . .8.3.1 Transformation and the partial order of entangled states.8.3.2 Entanglement purification/distillation . . . . . . . . . . .8.3.3 Entanglement concentration and dilution . . . . . . . . .8.3.4 Quantifying entanglement . . . . . . . . . . . . . . . . . .8.3.5 Bound entanglement . . . . . . . . . . . . . . . . . . . . .8.4 Quantum information processing principles and primitives . . . .8.4.1 Search for quantum information principles . . . . . . . .8.4.2 Quantum information processing primitives . . . . . . . 3.1 The symmetric space . . . . . . . . . . . . . . . . . . . .7.3.2 Stabilization by projection into the symmetric subspaceQuantum Error-Correcting Codes . . . . . . . . . . . . . . . .7.4.1 Classical error-detecting and -correcting codes . . . . .7.4.2 Framework for quantum error-correcting codes . . . . .7.4.3 Case studies . . . . . . . . . . . . . . . . . . . . . . . . .7.4.4 Basic methods to design quantum error-correcting codes7.4.5 Stabilizer codes . . . . . . . . . . . . . . . . . . . . . . .Fault-tolerant Quantum Computation . . . . . . . . . . . . . .7.5.1 Fault-tolerant quantum error correction . . . . . . . . .7.5.2 Fault-tolerant quantum gates . . . . . . . . . . . . . . .7.5.3 Concatenated coding . . . . . . . . . . . . . . . . . . .Experimental Quantum Processors - . . . . . . . . . . . . . . .7.6.1 Main approaches . . . . . . . . . . . . . . . . . . . . . .7.6.2 Ion trap . . . . . . . . . . . . . . . . . . . . . . . . . . .7.6.3 Cavity QED . . . . . . . . . . . . . . . . . . . . . . . .7.6.4 Nuclear magnetic resonance (NMR) . . . . . . . . . . .7.6.5 Other potential technologies . . . . . . . . . . . . . . . .APPENDIX9.1 Quantum Theory . . . . . . . . . . . . . . . .9.1.1 Pre-history of quantum theory . . . . .9.1.2 Heisenberg’s uncertainty principle . . .9.1.3 Quantum theory versus physical reality9.1.4 Quantum measurements . . . . . . . . .9.1.5 Quantum paradoxes . . . . . . . . . . .9.1.6 The quantum paradox . . . . . . . . . .9.1.7 Interpretations of quantum theory . . .
xiCONTENTS9.29.39.49.59.1.8 Incompleteness of quantum mechanics . . . . .Hilbert Space Framework for Quantum Computing . .9.2.1 Hilbert spaces . . . . . . . . . . . . . . . . . . .9.2.2 Linear operators . . . . . . . . . . . . . . . . .9.2.3 Mixed states and density matrices . . . . . . .9.2.4 Probabilities and observables . . . . . . . . . .9.2.5 Evolution of quantum states . . . . . . . . . . .9.2.6 Measurements . . . . . . . . . . . . . . . . . .9.2.7 Tensor products and Hilbert spaces . . . . . . .9.2.8 Generalized measurements-POV measurementsDeterministic and Randomized Computing . . . . . .9.3.1 Computing models . . . . . . . . . . . . . . . .9.3.2 Randomized computations . . . . . . . . . . . .9.3.3 Complexity classes . . . . . . . . . . . . . . . .9.3.4 Computational theses . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . .Historical and Bibliographical References . . . . . . 386387391392396403
xiiCONTENTS
PrefacexiiiPREFACEACome forth into the light of things.Let Nature be your teacher.W. Wordsworth (1770–1850)simplified view of the history of computing shows that computing was thought of mainly as mental processes in the 19th century; it is thought ofmainly as machine processes in the 20th century, and it will be thought of mainly as Natureprocesses in the 21st century.We cannot tell, of course, how much of this vision will be true. Currently, we see vigorous,interesting and, we expect, very important attempts to go much deeper than before intoNature in order to discover its potential for information processing. In this way we alsohope to deepen our understanding of Nature. Perhaps the two areas of greatest potentialare quantum computing and molecular computing.The amount of theoretical research and experimental developments in quantum computing grows rapidly. At the same time, interest grows within the science and technologycommunity, especially in physics and theoretical computing, and this interest in turn givesrise to a need for a systematic presentation and summary of the main concepts, methodsand achievements through textbooks and courses. This book is addressed to this need.There has long been a tradition in computing to look into the natural world for inspiration. There have been many attempts to understand, mimic and harnest informationprocessing tools and power of the brain. Already finite automata have been developed as anabstraction of neurons activities. Neural networks represent another model inspired by thebrain. Information processing of genetic mechanisms is a further source of inspiration. Allthese attempts are of interest and importance. However, the current attempts in molecularand quantum computing seem to go even deeper into Nature in the quest of exploring itsinformation processing potential.
xivPrefaceOur world is quantum mechanical. It is therefore natural, necessary, interesting andimportant to explore the foundations and potentials of quantum information processing. Atthe same time, we must explore the technologies and methods that allow the experimentalrealization of quantum information processing systems.Quantum computing is a very new, fascinating, promising and puzzling scientific adventure in which we witness a merging and mutual influence of two of the most significantdevelopments in science and technology of 20th century—quantum mechanics and computing. An adventure that may lead not only to the computer revolution, but also to a newscientific and technological basis for information processing in the 21st century.It has been known, but not realized enough, from the birth of modern quantummechanics theory that the most basic processes of Nature are actually quantuminformation processing processes and that amount of information processing going on everywhere around us in a tiny portion of matter and time is incomparablelarger than all information processing classical technology has ever provided. Inaddition, it has not been realised, till the birth of modern quantum informationprocessing research, that information processing capabilities of Nature cannot bematched by classical information processing tools, and due to severe limitationson retrieval of information from quantum to classical world, it has not been clearat all whether and how we can harness enormous information processing powerof Nature for classical information processing.At the same time, as it is often the case with the very fundamental and powerful theoriesand ideas, the very basic concepts of quantum computing are surprisingly simple and eleganteven though they seem to deal with mysterious and puzzling phenomena. Moreover, thetechnical—mathematical—tools needed to present an introduction to quantum computingare mostly those that are included in basic science education. The book demonstrates andutilises this fact in a way that is readable and understandable by the broad science andtechnology community.It is hard to foresee exactly where the research and development in quantum computingwill take us. However, we can safely say that something important will come out and thatquantum computing is a challenge not only for informatics and physics—theoretical and alsoexperimental — but also for science, technology and society in general.For informatics as a science, quantum computing may bring the most radical change inits main research aims, scope and paradigms. Indeed, so far informatics has been developed, largely, with the global aims of serving current and foreseeable information processingtechnology. Quantum computing (with molecular computing) is perhaps the first significantchallenge, chance and necessity for informatics to free itself from this short-term role of theservant of technology and to start to concentrate more on its most basic long term aims:to study the laws and limitations of the information processing world, to contribute to thedevelopment of new global theories and to deepen our understanding of various worlds: forexample physical, biological, and chemical.For informatics as a technology, the development of quantum information processingtechnologies can make a revolutionary contribution to the potential and security of informatio
QUANTUM COMPUTING Jozef Gruska quantum measurement has the effect of ‘‘magnifying’’ one of the outcomes of quantum superposition probabilistic, sequential Only at this point do indeterminacy and probabilities E. T. QUANTUM WORLD CLASSICAL WORLD Quantum computation is deterministic highly
1. Quantum bits In quantum computing, a qubit or quantum bit is the basic unit of quantum information—the quantum version of the classical binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics.
Quantum computing is a subfield of quantum information science— including quantum networking, quantum sensing, and quantum simulation—which harnesses the ability to generate and use quantum bits, or qubits. Quantum computers have the potential to solve certain problems much more quickly t
Topics History of Computing What are classical computers made of? Moore's Law (Is it ending?) High Performance computing Quantum Computing Quantum Computers Quantum Advantage The Qubit (Information in superposition) Information storage Different kinds of quantum computers Superconducting vs Ion Traps Annealing vs Universal/Gate quantum computers
Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments . quantum computing are presented and the quantum circuit model as well as measurement-based models of quantum computing are introduced. Furthermore, it is shown how these concepts can
Keywords—machine learning, quantum computing, deep learning, quantum machine intelligence I. INTRODUCTION There is currently considerable interest in quantum computing. In the U.S. in January 2019, the National Quantum Initiative Act authorized 1.2 billion investment over the next 5-10 years (Rep Smith, 2019). A quantum computing race is ongoing
According to the quantum model, an electron can be given a name with the use of quantum numbers. Four types of quantum numbers are used in this; Principle quantum number, n Angular momentum quantum number, I Magnetic quantum number, m l Spin quantum number, m s The principle quantum
Quantum effects - superposition, interference, and entanglement NISQ - Noisy Intermediate-Scale Quantum technology, often refers in the context of modern very noisy quantum computers QASM - Quantum Assembly used for programming quantum computers Quantum supremacy - demonstration of that a programmable quantum
The Asset Management Strategy supports our strategic priority to: To provide quality, well maintained homes that are fit for the future . Page 5 of 10 Asset Management Strategy 2018 The strategy supports our growth aspirations and development strategy. A key principle is that any development decision will complement and enhance our current asset portfolio. Our aim is that: We invest in our .
