An introduction to quantum computing / Phillip Kaye, Raymond Laflamme, Michele Mosca.

Format:

Book

Author/Creator:

Kaye, Phillip.

Contributor:

Laflamme, Raymond.

Mosca, Michele.

Language:

English

Subjects (All):

Quantum computers.

Computers.

Physical Description:

xi, 274 p. : ill.

Edition:

1st ed.

Place of Publication:

Oxford : Oxford University Press, 2007.

Summary:

This concise, accessible introduction to quantum computing is aimed at advanced undergraduate and beginning graduate students from a variety of scientific backgrounds. The text is technically detailed and clearly illustrated throughout with diagrams and exercises.

Contents:

Intro

Contents

Preface

Acknowledgements

1 INTRODUCTION AND BACKGROUND

1.1 Overview

1.2 Computers and the Strong Church-Turing Thesis

1.3 The Circuit Model of Computation

1.4 A Linear Algebra Formulation of the Circuit Model

1.5 Reversible Computation

1.6 A Preview of Quantum Physics

1.7 Quantum Physics and Computation

2 LINEAR ALGEBRA AND THE DIRAC NOTATION

2.1 The Dirac Notation and Hilbert Spaces

2.2 Dual Vectors

2.3 Operators

2.4 The Spectral Theorem

2.5 Functions of Operators

2.6 Tensor Products

2.7 The Schmidt Decomposition Theorem

2.8 Some Comments on the Dirac Notation

3 QUBITS AND THE FRAMEWORK OF QUANTUM MECHANICS

3.1 The State of a Quantum System

3.2 Time-Evolution of a Closed System

3.3 Composite Systems

3.4 Measurement

3.5 Mixed States and General Quantum Operations

3.5.1 Mixed States

3.5.2 Partial Trace

3.5.3 General Quantum Operations

4 A QUANTUM MODEL OF COMPUTATION

4.1 The Quantum Circuit Model

4.2 Quantum Gates

4.2.1 1-Qubit Gates

4.2.2 Controlled-U Gates

4.3 Universal Sets of Quantum Gates

4.4 Efficiency of Approximating Unitary Transformations

4.5 Implementing Measurements with Quantum Circuits

5 SUPERDENSE CODING AND QUANTUM TELEPORTATION

5.1 Superdense Coding

5.2 Quantum Teleportation

5.3 An Application of Quantum Teleportation

6 INTRODUCTORY QUANTUM ALGORITHMS

6.1 Probabilistic Versus Quantum Algorithms

6.2 Phase Kick-Back

6.3 The Deutsch Algorithm

6.4 The Deutsch-Jozsa Algorithm

6.5 Simon's Algorithm

7 ALGORITHMS WITH SUPERPOLYNOMIAL SPEED-UP

7.1 Quantum Phase Estimation and the Quantum Fourier Transform

7.1.1 Error Analysis for Estimating Arbitrary Phases

7.1.2 Periodic States

7.1.3 GCD, LCM, the Extended Euclidean Algorithm

7.2 Eigenvalue Estimation.

7.3 Finding-Orders

7.3.1 The Order-Finding Problem

7.3.2 Some Mathematical Preliminaries

7.3.3 The Eigenvalue Estimation Approach to Order Finding

7.3.4 Shor's Approach to Order Finding

7.4 Finding Discrete Logarithms

7.5 Hidden Subgroups

7.5.1 More on Quantum Fourier Transforms

7.5.2 Algorithm for the Finite Abelian Hidden Subgroup Problem

7.6 Related Algorithms and Techniques

8 ALGORITHMS BASED ON AMPLITUDE AMPLIFICATION

8.1 Grover's Quantum Search Algorithm

8.2 Amplitude Amplification

8.3 Quantum Amplitude Estimation and Quantum Counting

8.4 Searching Without Knowing the Success Probability

8.5 Related Algorithms and Techniques

9 QUANTUM COMPUTATIONAL COMPLEXITY THEORY AND LOWER BOUNDS

9.1 Computational Complexity

9.1.1 Language Recognition Problems and Complexity Classes

9.2 The Black-Box Model

9.2.1 State Distinguishability

9.3 Lower Bounds for Searching in the Black-Box Model: Hybrid Method

9.4 General Black-Box Lower Bounds

9.5 Polynomial Method

9.5.1 Applications to Lower Bounds

9.5.2 Examples of Polynomial Method Lower Bounds

9.6 Block Sensitivity

9.6.1 Examples of Block Sensitivity Lower Bounds

9.7 Adversary Methods

9.7.1 Examples of Adversary Lower Bounds

9.7.2 Generalizations

10 QUANTUM ERROR CORRECTION

10.1 Classical Error Correction

10.1.1 The Error Model

10.1.2 Encoding

10.1.3 Error Recovery

10.2 The Classical Three-Bit Code

10.3 Fault Tolerance

10.4 Quantum Error Correction

10.4.1 Error Models for Quantum Computing

10.4.2 Encoding

10.4.3 Error Recovery

10.5 Three- and Nine-Qubit Quantum Codes

10.5.1 The Three-Qubit Code for Bit-Flip Errors

10.5.2 The Three-Qubit Code for Phase-Flip Errors

10.5.3 Quantum Error Correction Without Decoding

10.5.4 The Nine-Qubit Shor Code.

10.6 Fault-Tolerant Quantum Computation

10.6.1 Concatenation of Codes and the Threshold Theorem

APPENDIX A

A.1 Tools for Analysing Probabilistic Algorithms

A.2 Solving the Discrete Logarithm Problem When the Order of a Is Composite

A.3 How Many Random Samples Are Needed to Generate a Group?

A.4 Finding r Given k/r for Random k

A.5 Adversary Method Lemma

A.6 Black-Boxes for Group Computations

A.7 Computing Schmidt Decompositions

A.8 General Measurements

A.9 Optimal Distinguishing of Two States

A.9.1 A Simple Procedure

A.9.2 Optimality of This Simple Procedure

Bibliography

Index

A

B

C

D

E

F

G

H

I

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z.

Notes:

Includes bibliographical references and index.

Description based on publisher supplied metadata and other sources.

ISBN:

1-280-75761-2

0-19-191672-2

1-4294-5991-3

0-19-152461-1

OCLC:

437092641