An Introduction to Quantum Computing Phillip Kaye Raymond Laflamme Michele Mosca 1 TEAM LinG 3 Great Clarendon Street, Oxford ox2 6dp Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide in Oxford New York Auckland Cape Town Dar es Salaam Hong Kong Karachi Kuala Lumpur Madrid Melbourne Mexico City Nairobi New Delhi Shanghai Taipei Toronto With offices in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York c Phillip R. Kaye, Raymond Laflamme and Michele Mosca, 2007 The moral rights of the authors have been asserted Database right Oxford University Press (maker) First published 2007 All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization.
Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose the same condition on any acquirer British Library Cataloguing in Publication Data Data available Library of Congress Cataloging in Publication Data Data available Typeset by SPI Publisher Services, Pondicherry, India Printed in Great Britain on acid-free paper by Biddles Ltd., King’s Lynn, Norfolk ISBN 0-19-857000-7 978-0-19-857000-4 ISBN 0-19-857049-x 978-0-19-857049-3 (pbk) 1 3 5 7 9 10 8 6 4 2 TEAM LinG Contents Preface x Acknowledgements xi 1 INTRODUCTION AND BACKGROUND 1 1.2 Computers and the Strong Church–Turing Thesis 2 1.3 The Circuit Model of Computation 6 1.4 A Linear Algebra Formulation of the Circuit Model 8 1.6 A Preview of Quantum Physics 15 1.7 Quantum Physics and Computation 19 2 LINEAR ALGEBRA AND THE DIRAC NOTATION 21 2.1 The Dirac Notation and Hilbert Spaces 21 2.4 The Spectral Theorem 30 2.5 Functions of Operators 32 2.7 The Schmidt Decomposition Theorem 35 2.8 Some Comments on the Dirac Notation 37 3 QUBITS AND THE FRAMEWORK OF QUANTUM MECHANICS 38 3.1 The State of a Quantum System 38 3.2 Time-Evolution of a Closed System 43 3.4 Measurement 48 v TEAM LinG vi CONTENTS 3.5 Mixed States and General Quantum Operations 53 3.3 General Quantum Operations 59 4 A QUANTUM MODEL OF COMPUTATION 61 4.1 The Quantum Circuit Model 61 4.3 Universal Sets of Quantum Gates 68 4.4 Efficiency of Approximating Unitary Transformations 71 4.5 Implementing Measurements with Quantum Circuits 73 5 SUPERDENSE CODING AND QUANTUM TELEPORTATION 78 5.3 An Application of Quantum Teleportation 82 6 INTRODUCTORY QUANTUM ALGORITHMS 86 6.1 Probabilistic Versus Quantum Algorithms 86 6.2 Phase Kick-Back 91 6.3 The Deutsch Algorithm 94 6.4 The Deutsch–Jozsa Algorithm 99 6.5 Simon’s Algorithm 103 7 ALGORITHMS WITH SUPERPOLYNOMIAL SPEED-UP 110 7.1 Quantum Phase Estimation and the Quantum Fourier Trans- form 110 7.1 Error Analysis for Estimating Arbitrary Phases 117 7.3 GCD, LCM, the Extended Euclidean Algorithm 124 7.2 Eigenvalue Estimation 125 TEAM LinG CONTENTS vii 7.1 The Order-Finding Problem 130 7.2 Some Mathematical Preliminaries 131 7.3 The Eigenvalue Estimation Approach to Order Find- ing 134 7.4 Shor’s Approach to Order Finding 139 7.4 Finding Discrete Logarithms 142 7.1 More on Quantum Fourier Transforms 147 7.2 Algorithm for the Finite Abelian Hidden Subgroup Problem 149 7.6 Related Algorithms and Techniques 151 8 ALGORITHMS BASED ON AMPLITUDE AMPLIFICATION 152 8.1 Grover’s Quantum Search Algorithm 152 8.2 Amplitude Amplification 163 8.3 Quantum Amplitude Estimation and Quantum Counting 170 8.4 Searching Without Knowing the Success Probability 175 8.5 Related Algorithms and Techniques 178 9 QUANTUM COMPUTATIONAL COMPLEXITY THEORY AND LOWER BOUNDS 179 9.1 Language Recognition Problems and Complexity Classes 181 9.2 The Black-Box Model 185 9.3 Lower Bounds for Searching in the Black-Box Model: Hybrid Method 188 9.4 General Black-Box Lower Bounds 191 9.1 Applications to Lower Bounds 194 9.2 Examples of Polynomial Method Lower Bounds 196 TEAM LinG viii CONTENTS 9.1 Examples of Block Sensitivity Lower Bounds 197 9.1 Examples of Adversary Lower Bounds 200 9.2 Generalizations 203 10 QUANTUM ERROR CORRECTION 204 10.1 Classical Error Correction 204 10.1 The Error Model 205 10.2 The Classical Three-Bit Code 207 10.4 Quantum Error Correction 212 10.1 Error Models for Quantum Computing 213 10.5 Three- and Nine-Qubit Quantum Codes 223 10.1 The Three-Qubit Code for Bit-Flip Errors 223 10.2 The Three-Qubit Code for Phase-Flip Errors 225 10.3 Quantum Error Correction Without Decoding 226 10.4 The Nine-Qubit Shor Code 230 10.6 Fault-Tolerant Quantum Computation 234 10.1 Concatenation of Codes and the Threshold Theorem 237 APPENDIX A 241 A.1 Tools for Analysing Probabilistic Algorithms 241 A.2 Solving the Discrete Logarithm Problem When the Order of a Is Composite 243 A.3 How Many Random Samples Are Needed to Generate a Group? 245 A.4 Finding r Given kr for Random k 247 A.5 Adversary Method Lemma 248 TEAM LinG CONTENTS ix A.6 Black-Boxes for Group Computations 250 A.7 Computing Schmidt Decompositions 253 A.9 Optimal Distinguishing of Two States 258 A.2 Optimality of This Simple Procedure 258 Bibliography 260 Index 270 TEAM LinG Preface We have offered a course at the University of Waterloo in quantum comput- ing since 1999. We have had students from a variety of backgrounds take the course, including students in mathematics, computer science, physics, and engi- neering. While there is an abundance of very good introductory papers, surveys and books, many of these are geared towards students already having a strong background in a particular area of physics or mathematics. With this in mind, we have designed this book for the following reader.
The reader has an undergraduate education in some scientific field, and should par- ticularly have a solid background in linear algebra, including vector spaces and inner products. Prior familiarity with topics such as tensor products and spectral decomposition is not required, but may be helpful. We review all the necessary material, in any case. In some places we have not been able to avoid using notions from group theory.
We clearly indicate this at the beginning of the relevant sec- tions, and have kept these sections self-contained so that they may be skipped by the reader unacquainted with group theory. We have attempted to give a gentle and digestible introduction of a difficult subject, while at the same time keeping it reasonably complete and technically detailed. We integrated exercises into the body of the text. Each exercise is designed to illustrate a particular concept, fill in the details of a calculation or proof, or to show how concepts in the text can be generalized or extended.
To get the most out of the text, we encourage the student to attempt most of the exercises. We have avoided the temptation to include many of the interesting and im- portant advanced or peripheral topics, such as the mathematical formalism of quantum information theory and quantum cryptography. Our intent is not to provide a comprehensive reference book for the field, but rather to provide stu- dents and instructors of the subject with a reasonably brief, and very accessible introductory graduate or senior undergraduate textbook. x TEAM LinG Acknowledgements The authors would like to extend thanks to the many colleagues and scientists around the world that have helped with the writing of this textbook, including Andris Ambainis, Paul Busch, Lawrence Ioannou, David Kribs, Ashwin Nayak, Mark Saaltink, and many other members of the Institute for Quantum Comput- ing and students at the University of Waterloo, who have taken our introductory quantum computing course over the past few years.
Phillip Kaye would like to thank his wife Janine for her patience and support, and his father Ron for his keen interest in the project and for his helpful comments. Raymond Laflamme would like to thank Janice Gregson, Patrick and Jocelyne Laflamme for their patience, love, and insights on the intuitive approach to error correction. Michele Mosca would like to thank his wife Nelia for her love and encouragement and his parents for their support. xi TEAM LinG This page intentionally left blank TEAM LinG 1 INTRODUCTION AND BACKGROUND 1.1 Overview A computer is a physical device that helps us process information by executing algorithms.
An algorithm is a well-defined procedure, with finite description, for realizing an information-processing task. An information-processing task can always be translated into a physical task. When designing complex algorithms and protocols for various information- processing tasks, it is very helpful, perhaps essential, to work with some idealized computing model. However, when studying the true limitations of a computing device, especially for some practical reason, it is important not to forget the rela- tionship between computing and physics.
Real computing devices are embodied in a larger and often richer physical reality than is represented by the idealized computing model. Quantum information processing is the result of using the physical reality that quantum theory tells us about for the purposes of performing tasks that were previously thought impossible or infeasible. Devices that perform quantum in- formation processing are known as quantum computers. In this book we examine how quantum computers can be used to solve certain problems more efficiently than can be done with classical computers, and also how this can be done reliably even when there is a possibility for errors to occur.
In this first chapter we present some fundamental notions of computation theory and quantum physics that will form the basis for much of what follows. After this brief introduction, we will review the necessary tools from linear algebra in Chapter 2, and detail the framework of quantum mechanics, as relevant to our model of quantum computation, in Chapter 3. In the remainder of the book we examine quantum teleportation, quantum algorithms and quantum error correc- tion in detail. 1 TEAM LinG 2 INTRODUCTION AND BACKGROUND 1.2 Computers and the Strong Church–Turing Thesis We are often interested in the amount of resources used by a computer to solve a problem, and we refer to this as the complexity of the computation.
An important resource for a computer is time. Another resource is space, which refers to the amount of memory used by the computer in performing the computation. We measure the amount of a resource used in a computation for solving a given problem as a function of the length of the input of an instance of that problem. For example, if the problem is to multiply two n bit numbers, a computer might solve this problem using up to 2n2 +3 units of time (where the unit of time may be seconds, or the length of time required for the computer to perform a basic step).
Of course, the exact amount of resources used by a computer executing an algo- rithm depends on the physical architecture of the computer. A different computer multiplying the same numbers mentioned above might use up to time 4n3 + n + 5 to execute the same basic algorithm. This fact seems to present a problem if we are interested in studying the complexity of algorithms themselves, abstracted from the details of the machines that might be used to execute them. To avoid this problem we use a more coarse measure of complexity.
One coarser measure is to consider only the highest-order terms in the expressions quantifying re- source requirements, and to ignore constant multiplicative factors. For example, consider the two computers mentioned above that run a searching algorithm in times 2n2 + 3 and 4n3 + n + 7, respectively. The highest-order terms are n2 and n3 , respectively (suppressing the constant multiplicative factors 2 and 4, respec- tively). We say that the running time of that algorithm for those computers is in O(n2 ) and O(n3 ), respectively.