A Gentle Introduction Eleanor Rieffel and Wolfgang Polak

1 QUANTUM COMPUTINGA Gentle IntroductionEleanor Rieffel and Wolfgang PolakThe MIT PressCambridge, MassachusettsLondon, England 2011 Massachusetts Institute of TechnologyAll rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (includingphotocopying, recording, or information storage and retrieval) without permission in writing from the information about special quantity discounts, please email book was set in Syntax and Times Roman by Westchester Book Group. Printed and bound in the United States of Congress Cataloging-in-Publication DataRieffel, Eleanor , 1965 Quantum computing : a Gentle Introduction / Eleanor Rieffel and Wolfgang cm.

2 (Scientific and engineering computation)Includes bibliographical references and 978-0-262-01506-6 (hardcover : alk. paper) 1. Quantum computers. 2. Quantum theory. I. Polak , Wolfgang ,1950 II. dc22201002268210987654321 ContentsPreface xi1 Introduction 1 IQUANTUM BUILDING BLOCKS 72 Single-Qubit Quantum Systems The Quantum Mechanics of Photon Polarization Simple Experiment Quantum Explanation Single Quantum Bits Single-Qubit Measurement A Quantum Key Distribution Protocol The State Space of a Single-Qubit System Phases versus Global Phases Views of the State Space of a Single Qubit on General Quantum State Spaces References Exercises 263 Multiple-Qubit Systems Quantum State Spaces Sums of Vector Spaces Products of Vector Spaces State Space of ann-Qubit System Entangled

3 States Basics of Multi-Qubit Measurement Quantum Key Distribution Using Entangled States References Exercises 444 Measurement of Multiple-Qubit States Dirac s Bra/Ket Notation for Linear Transformations Projection Operators for Measurement Hermitian Operator Formalism for Measurement Measurement Postulate EPR Paradox and Bell s Theorem for Bell s Theorem Quantum Mechanics Predicts Case of Bell s Theorem: What Any Local Hidden Variable Theory Predicts s Inequality References Exercises 665 Quantum State Transformations Unitary Transformations Transformations: The No-Cloning Principle Some Simple Quantum Gates Pauli Transformations Hadamard Transformation Transformations from Single-Qubit Transformations Controlled-NOTand Other Singly Controlled Gates Applications of Simple Gates Coding Teleportation Realizing Unitary Transformations as Quantum Circuits of Single-Qubit Transformations Single-Qubit Transformations Single-Qubit Transformations Unitary Transformations A Universally Approximating Set of Gates The Standard Circuit Model References Exercises 946 Quantum Versions of Classical Computations From Reversible Classical Computations to Quantum

4 Computations and Quantum Versions of Simple Classical Gates Reversible Implementations of Classical Circuits Naive Reversible Implementation General Construction A Language for Quantum Implementations Basics Some Example Programs for arithmetic Operations Implementation Implementation of Multiply-Controlled Single-Qubit Transformations Addition Addition Multiplication Exponentiation References Exercises 121II QUANTUM ALGORITHMS 1237 Introduction to Quantum Algorithms Computing with Superpositions Walsh-Hadamard Transformation Parallelism Notions of Complexity Complexity Complexity A Simple Quantum Algorithm s Problem Quantum Subroutines Importance of Unentangling Temporary Qubits in Quantum Subroutines Change for a Subset of Basis Vectors Phase Shifts Single-Qubit Amplitude Shifts A Few Simple Quantum Algorithms Problem Problem s Problem Computation Comments on Quantum Parallelism Machine Models and Complexity Classes Classes.

5 Known Results Quantum Fourier Transformations Classical Fourier Transform Quantum Fourier Transform Quantum Circuit for Fast Fourier Transform References Exercises 1598 Shor s Algorithm Classical Reduction to Period-Finding Shor s Factoring Algorithm Quantum Core Extraction of the Period from the Measured Value Example Illustrating Shor s Algorithm The Efficiency of Shor s Algorithm Omitting the Internal Measurement Generalizations Discrete Logarithm Problem Subgroup Problems References Exercises 1769 Grover s Algorithm and Generalizations Grover s Algorithm Iteration Step Many Iterations?

6 Amplitude Amplification Geometry of Amplitude Amplification Optimality of Grover s Algorithm to Three Inequalities of the Three Inequalities Derandomization of Grover s Algorithm and Amplitude Amplification 1: Modifying Each Step 2: Modifying Only the Last Step Unknown Number of Solutions the Number of Iterations Counting Practical Implications of Grover s Algorithm and Amplitude Amplification References Exercises 201 III ENTANGLED SUBSYSTEMS AND ROBUST QUANTUM COMPUTATION 20310 Quantum Subsystems and Properties of Entangled States Quantum Subsystems and Mixed States Operators of Density Operators Geometry of Single-Qubit Mixed States Neumann Entropy Classifying Entangled States Quantum Systems Bipartite Pure States up to LOCC Equivalence Entanglement in Bipartite Mixed States Entanglement Density Operator Formalism for

7 Measurement of Density Operators Transformations of Quantum Subsystems and Decoherence Sum Decomposition Relation Between Quantum State Transformations and Measurements References Exercises 240 Contentsix11 Quantum Error Correction Three Simple Examples of Quantum Error Correcting Codes Quantum Code That Corrects Single Bit-Flip Errors Code for Single-Qubit Phase-Flip Errors Code for All Single-Qubit Errors Framework for Quantum Error Correcting Codes Error Correcting Codes Error Correcting Codes Sets of Errors for Classical Codes Sets of Errors for Quantum Codes Errors Using Classical Codes and Correcting Errors Using Quantum Codes Error Correction across Multiple Blocks on Encoded Quantum States and Mixtures of Correctable Errors Are Correctable The Classical Independent Error Model Quantum Independent Error Models CSS Codes Classical Codes of CSS Codes from Classical Codes Satisfying a Duality Condition Steane Code Stabilizer Codes Observables for Quantum Error Correction Observables for Quantum Error Correction and Correcting Errors on Encoded Stabilizer States CSS Codes as Stabilizer Codes References Exercises 29112 Fault Tolerance and Robust Quantum Computing Setting the Stage for

8 Robust Quantum Computation Fault-Tolerant Computation Using Steane s Code Problem with Syndrome Computation Syndrome Extraction and Error Correction Gates for Steane s Code Measurement State Preparation of| /4 Robust Quantum Computation Coding Threshold Theorem References Exercises 31013 Further Topics in Quantum Information Processing Further Quantum Algorithms Limitations of Quantum Computing Further Techniques for Robust Quantum Computation Alternatives to the Circuit Model of Quantum Computation Cluster State Quantum Computation Quantum Computation Quantum Computation Quantum Computation Quantum Protocols Insight into Classical Computation Building Quantum Computers Simulating Quantum Systems Where Does the Power of Quantum Computation Come From?

9 What if Quantum Mechanics Is Not Quite Correct? 327 APPENDIXES 329A Some Relations Between Quantum Mechanics and Probability Theory Tensor Products in Probability Theory Quantum Mechanics as a Generalization of Probability Theory References Exercises 339B Solving the Abelian Hidden Subgroup Problem Representations of Finite Abelian Groups s Lemma Quantum Fourier Transforms for Finite Abelian Groups Fourier Basis of an Abelian Group Quantum Fourier Transform Over a Finite Abelian Group General Solution to the Finite Abelian Hidden Subgroup Problem Instances of the Abelian Hidden Subgroup Problem s Problem s Algorithm.

10 Finding the Period of a Function Comments on the Non-Abelian Hidden Subgroup Problem References Exercises 352 Bibliography 353 Notation Index 365 Index 369 PrefaceQuantum computing is a beautiful combination of quantum physics, computer science, and infor-mation theory. The purpose of this book is to make this exciting research area accessible to abroad audience. In particular, we endeavor to help the reader bridge the conceptual and notationalbarriers that separate quantum computing from conventional book is concerned with theory: what changes when the classical model underpinningconventional computing is replaced with a quantum one. It contains only a brief discussion ofthe ongoing efforts to build quantum computers, an active area which is still so young that it isimpossible even for experts to predict which approaches will be most successful.