Bernhardt - Quantum computing for everyone

2019 Massachusetts Institute of Technology

All rights reserved. No part of this book may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher.

This book was set in ITC Stone Sans Std and ITC Stone Serif Std by Toppan Best-set Premedia Limited. Printed and bound in the United States of America.

Library of Congress Cataloging-in-Publication Data

Names: Bernhardt, Chris, author.

Title: Quantum computing for everyone / Chris Bernhardt.

Description: Cambridge, MA : The MIT Press, [2019] | Includes bibliographical references and index.

Identifiers: LCCN 2018018398 | ISBN 9780262039253 (hardcover : alk. paper)

eISBN 9780262350884

Subjects: LCSH: Quantum computing--Popular works.

Classification: LCC QA76.889 .B47 2019 | DDC 006.3/843--dc23 LC record available at https://lccn.loc.gov/2018018398

ePub Version 1.0

To Henryka

1. Chapter 1
2. Chapter 2
3. Chapter 3
4. Chapter 6
5. Chapter 9

I am very grateful to a number of people for their help with this book. Matt Coleman, Steve LeMay, Dan Ryan, Chris Staecker, and three anonymous reviewers read through various drafts with great care. Their suggestions and corrections have improved this book beyond measure. I also thank Marie Lee and her team at MIT Press for all of their support and work in turning a rough proposal into this book.

The aim of this book is to give an introduction to quantum computing that anyone who is comfortable with high school mathematics and is willing to put in a little work can understand. We will study qubits, entanglement, quantum teleportation, and quantum algorithms, among other quantum-related topics. The goal is not to give some vague idea of these concepts but to make them crystal clear.

Quantum computing is often in the news: China teleported a qubit from earth to a satellite; Shors algorithm has put our current encryption methods at risk; quantum key distribution will make encryption safe again; Grovers algorithm will speed up data searches. But what does all this really mean? How does it all work? All of this will be explained.

Can this be done without using mathematics? No, not if we want to really understand what is going on. The underlying ideas come from quantum mechanics and are often counterintuitive. Attempts to describe these in words dont work because we have no experience of them in our everyday lives. Even worse, verbal descriptions often give the impression that we have understood something when we really havent. The good news is that we really do not need to introduce much mathematics. My role as a mathematician is to simplify the mathematics as much as possiblejust sticking to the absolute essentialsand to give elementary examples to illustrate both how it is used and what it means. That said, the book probably contains mathematical ideas that you have not seen before, and, as with all mathematics, new concepts can seem strange at first. It is important not to gloss over the examples but to read them carefully, following each step of the calculations.

Quantum computing is a beautiful fusion of quantum physics with computer science. It incorporates some of the most stunning ideas of physics from the twentieth century into an entirely new way of thinking about computation. The basic unit of quantum computing is the qubit. We will see what qubits are and what happens when we measure them. A classical bit is either 0 or 1. If its 0 and we measure it, we get 0. If its 1 and we measure 1, we get 1. In both cases the bit remains unchanged. The situation is totally different for qubits. A qubit can be in one of an infinite number of statesa superposition of both 0 and 1but when we measure it, as in the classical case, we just get one of two values, either 0 or 1. The act of measurement changes the qubit. A simple mathematical model describes all of this precisely.

Qubits can also be entangled. When we make a measurement of one of them, it affects the state of the other. Again, this is something that we dont experience in our daily lives, but it is described perfectly by our mathematical model.

These three thingssuperposition, measurement, and entanglementare the key quantum mechanical ideas. Once we know what they mean, we can see how they may be used in computations. It is here that human ingenuity enters the picture.

Mathematicians often describe proofs as being beautiful, often containing unexpected insights. I feel exactly the same way about many of the topics we will look at. Bells theorem, quantum teleportation, superdense coding, all are gems. The error correcting circuit and Grovers algorithm are absolutely amazing.

By the end of the book, you should understand the basic ideas that underlie quantum computing, and you will have seen some ingenious and beautiful constructions. You will also come to realize that quantum computing and classical computing are not two distinct disciplines, but that quantum computing is the more fundamental form of computinganything that can be computed classically can be computed on a quantum computer. The qubit is the basic unit of computation, not the bit. Computation, in its essence, really means quantum computation.

Finally, it should be emphasized that this book is about the theory of quantum computation. It is about software, not hardware. We briefly mention hardware in places and occasionally talk about how to physically entangle qubits, but these topics are just asides. The book is not about how to build a quantum computer, but how to use one.

Heres a brief description of the books contents.

Chapter 1. The basic unit of classical computing is the bit. Bits can be represented by anything that can be in one of two possible states. The standard example is an electrical switch that can be either on or off. The basic unit of quantum computing is the qubit. This can be represented by the spin of an electron or the polarization of a photon, but the properties of spin and polarization are not nearly as familiar to us as a switch being in the on or off position.

We look at the basic properties of spin, starting with Otto Stern and Walther Gerlachs classic experiment in which they studied the magnetic properties of silver atoms. We see what happens when we measure spin in a number of different directions. The act of making a measurement can affect the state of a qubit. There is also an underlying randomness associated with some of the measurements that we will need to explain.

The chapter concludes by showing that experiments analogous to those for spin can be performed using polarized filters and ordinary light.

Chapter 2. Quantum computing is based on an area of mathematics called linear algebra. Fortunately, we only need a few concepts. This chapter introduces and describes the linear algebra we need and illustrates how it is going to be used in the later chapters.

We introduce vectors and matrices and show how to calculate the length of vectors and how to tell whether or not two vectors are perpendicular. The chapter starts by just considering elementary operations on vectors and then shows how matrices give a simple way of doing a number of these calculations simultaneously.

It is not initially apparent that this material is going to be useful, but it is. Linear algebra forms the foundation of quantum computing. Since the rest of the book uses the mathematics introduced here, this chapter needs to be read carefully.