Principal Quantum Computer Science: An Introduction
Due to the technical work on the site downloading books (as well as file conversion and sending books to email/kindle) may be unstable from May, 27 to May, 28 Also, for users who have an active donation now, we will extend the donation period.

Quantum Computer Science: An Introduction

In the 1990's it was realized that quantum physics has some spectacular applications in computer science. This book is a concise introduction to quantum computation, developing the basic elements of this new branch of computational theory without assuming any background in physics. It begins with an introduction to the quantum theory from a computer-science perspective. It illustrates the quantum-computational approach with several elementary examples of quantum speed-up, before moving to the major applications: Shor's factoring algorithm, Grover's search algorithm, and quantum error correction. The book is intended primarily for computer scientists who know nothing about quantum theory, but will also be of interest to physicists who want to learn the theory of quantum computation, and philosophers of science interested in quantum foundational issues. It evolved during six years of teaching the subject to undergraduates and graduate students in computer science, mathematics, engineering, and physics, at Cornell University.
Cambridge University Press
ISBN 10:
ISBN 13:
PDF, 1.10 MB
Descarga (pdf, 1.10 MB)

You may be interested in Powered by Rec2Me


Most frequently terms

You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
Quantum Computer Science
An Introduction
In the 1990s it was realized that quantum physics has some
spectacular applications in computer science. This book is a concise
introduction to quantum computation, developing the basic elements
of this new branch of computational theory without assuming any
background in physics. It begins with a novel introduction to the
quantum theory from a computer-science perspective. It illustrates
the quantum-computational approach with several elementary
examples of quantum speed-up, before moving to the major
applications: Shor’s factoring algorithm, Grover’s search algorithm,
and quantum error correction.
The book is intended primarily for computer scientists who know
nothing about quantum theory but would like to learn the elements of
quantum computation either out of curiosity about this new
paradigm, or as a basis for further work in the subject. It will also be
of interest to physicists who want to learn the theory of quantum
computation, and to physicists and philosophers of science interested
in quantum foundational issues. It evolved during six years of teaching
the subject to undergraduates and graduate students in computer
science, mathematics, engineering, and physics, at Cornell University.
N. DAVID MERMIN is Horace White Professor of Physics Emeritus at
Cornell University. He has received the Lilienfeld Prize of the
American Physical Society and the Klopsteg award of the American
Association of Physics Teachers. He is a member of the U.S. National
Academy of Sciences and the American Academy of Arts and
Sciences. Professor Mermin has written on quantum foundational
issues for several decades, and is known for the clarity and wit of his
scientific writings. Among his other books are Solid State Physics
(with N. W. Ashcroft, Thomson Learning 1976), Boojums all the Way
Through (Cambridge University Press 1990), and It’s about Time:
Understanding Einstein’s Relativity (Princeton University Press 2005).

“This is one of the finest books in the rapidly growing field o; f quantum information. Almost every page contains a unique insight or a
novel interpretation. David Mermin has once again demonstrated his
legendary pedagogical skills to produce a classic.”
Lov Grover, Bell Labs
“Mermin’s book will be a standard for instruction and reference for
years to come. He has carefully selected, from the mountain of knowledge accumulated in the last 20 years of research in quantum information theory, a manageable, coherent subset that constitutes a complete undergraduate course. While selective, it is in no sense “watered
down”; Mermin moves unflinchingly through difficult arguments in
the Shor algorithm, and in quantum error correction theory, providing
invaluable diagrams, clear arguments, and, when necessary, extensive
appendices to get the students successfully through to the end. The
book is suffused with Mermin’s unique knowledge of the history of
modern physics, and has some of the most captivating writing to be
found in a college textbook.”
David DiVincenzo, IBM T. J. Watson Research Center
“Mermin’s book is a gentle introduction to quantum computation especially aimed at an audience of computer scientists and mathematicians.
It covers the basics of the field, explaining the material clearly and containing lots of examples. Mermin has always been an entertaining and
comprehensible writer, and continues to be in this book. I expect it to
become the definitive introduction to this material for non-physicists.”
Peter Shor, Massachusetts Institute of Technology
“Textbook writers usually strive for a streamlined exposition, smoothing out the infelicities of thought and notation that plague any field’s
early development. Fortunately, David Mermin is too passionate and
acute an observer of the cultural side of science to fall into this blandness. Instead of omitting infelicities, he explains and condemns them,
at the same time using his experience of having taught the course many
times to nip nascent misunderstandings in the bud. He celebrates the
field’s mongrel origin in a shotgun wedding between classical computer scientists, who thought they knew the laws of information, and
quantum physicists, who thought information was not their job. Differences remain: we hear, for example, why physicists love the Dirac
notation and mathematicians hate it. Worked-out examples and exercises familiarize students with the necessary algebraic manipulations,
while Mermin’s lucid prose and gentle humor cajole them toward a
sound intuition for what it all means, not an easy task for a subject
superficially so counterintuitive.”
Charles Bennett, IBM T. J. Watson Research Center

Quantum Computer Science
An Introduction
N. David Mermin
Cornell University

In memory of my brother, Joel Mermin
You would have enjoyed it.


Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
Information on this title:
© N. D. Mermin 2007
This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.
First published in print format 2007
eBook (NetLibrary)
ISBN-13 978-0-511-34258-5
ISBN-10 0-511-34258-6
eBook (NetLibrary)


Cambridge University Press has no responsibility for the persistence or accuracy of urls
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.


A note on references

page xi

1 Cbits and Qbits
1.1 What is a quantum computer?
1.2 Cbits and their states
1.3 Reversible operations on Cbits
1.4 Manipulating operations on Cbits
1.5 Qbits and their states
1.6 Reversible operations on Qbits
1.7 Circuit diagrams
1.8 Measurement gates and the Born rule
1.9 The generalized Born rule
1.10 Measurement gates and state preparation
1.11 Constructing arbitrary 1- and 2-Qbit states
1.12 Summary: Qbits versus Cbits


2 General features and some simple examples
2.1 The general computational process
2.2 Deutsch’s problem
2.3 Why additional Qbits needn’t mess things up
2.4 The Bernstein–Vazirani problem
2.5 Simon’s problem
2.6 Constructing Toffoli gates


3 Breaking RSA encryption
3.1 Period finding, factoring, and cryptography
3.2 Number-theoretic preliminaries
3.3 RSA encryption
3.4 Quantum period finding: preliminary remarks
3.5 The quantum Fourier transform
3.6 Eliminating the 2-Qbit gates
3.7 Finding the period




3.8 Calculating the periodic function
3.9 The unimportance of small phase errors
3.10 Period finding and factoring


4 Searching with a quantum computer
4.1 The nature of the search
4.2 The Grover iteration
4.3 How to construct W
4.4 Generalization to several special numbers
4.5 Searching for one out of four items


5 Quantum error correction
5.1 The miracle of quantum error correction
5.2 A simplified example
5.3 The physics of error generation
5.4 Diagnosing error syndromes
5.5 The 5-Qbit error-correcting code
5.6 The 7-Qbit error-correcting code
5.7 Operations on 7-Qbit codewords
5.8 A 7-Qbit encoding circuit
5.9 A 5-Qbit encoding circuit


6 Protocols that use just a few Qbits
6.1 Bell states
6.2 Quantum cryptography
6.3 Bit commitment
6.4 Quantum dense coding
6.5 Teleportation
6.6 The GHZ puzzle


A. Vector spaces: basic properties and Dirac notation
B. Structure of the general 1-Qbit unitary transformation
C. Structure of the general 1-Qbit state
D. Spooky action at a distance
E. Consistency of the generalized Born rule
Other aspects of Deutsch’s problem
G. The probability of success in Simon’s problem
H. One way to make a cNOT gate
A little elementary group theory
Some simple number theory
K. Period finding and continued fractions
L. Better estimates of success in period finding




Factoring and period finding
Shor’s 9-Qbit error-correcting code
A circuit-diagrammatic treatment of the 7-Qbit code
On bit commitment




It was almost three quarters of a century after the discovery of quantum mechanics, and half a century after the birth of information theory
and the arrival of large-scale digital computation, that people finally
realized that quantum physics profoundly alters the character of information processing and digital computation. For physicists this development offers an exquisitely different way of using and thinking about
the quantum theory. For computer scientists it presents a surprising
demonstration that the abstract structure of computation cannot be
divorced from the physics governing the instrument that performs
the computation. Quantum mechanics provides new computational
paradigms that had not been imagined prior to the 1980s and whose
power was not fully appreciated until the mid 1990s.
In writing this introduction to quantum computer science I have
kept in mind readers from several disciplines. Primarily I am addressing computer scientists, electrical engineers, or mathematicians who
may know little or nothing about quantum physics (or any other kind
of physics) but who wish to acquire enough facility in the subject to be
able to follow the new developments in quantum computation, judge for
themselves how revolutionary they may be, and perhaps choose to participate in the further development of quantum computer science. Not
the least of the surprising things about quantum computation is that
remarkably little background in quantum mechanics has to be acquired
to understand and work with its applications to information processing. Familiarity with a few fundamental facts about finite-dimensional
vector spaces over the complex numbers (summarized and reviewed in
Appendix A) is the only real prerequisite.
One of the secondary readerships I have in mind consists of physicists who, like myself – I am a theorist who has worked in statistical
physics, solid-state physics, low-temperature physics, and mathematical physics – know very little about computer science, but would like
to learn about this extraordinary new application of their discipline.
I stress, however, that my subject is quantum computer science, not
quantum computer design. This is a book about quantum computational software – not hardware. The difficult question of how one might
actually build a quantum computer is beyond its scope.



Another secondary readership is made up of those philosophers and
physicists who – again like myself – are puzzled by so-called foundational issues: what the strange quantum formalism implies about the
nature of the world that it so accurately describes. By applying quantum mechanics in an entirely new way – and especially by applying it
to the processing of knowledge – quantum computation gives a new
perspective on interpretational questions. While I rarely address such
matters explicitly, for purely pedagogical reasons my presentation is
suffused with a perspective on the quantum theory that is very close to
the venerable but recently much reviled Copenhagen interpretation.
Those with a taste for such things may be startled to see how well
quantum computation resonates with the Copenhagen point of view.
Indeed, it had been my plan to call this book Copenhagen Computation until the excellent people at Cambridge University Press and my
computer-scientist friends persuaded me that virtually no members of
my primary readership would then have had any idea what it was about.
Several years ago I mentioned to a very distinguished theoretical physicist that I spent the first four lectures of a course in quantum computation giving an introduction to quantum mechanics for mathematically
literate people who knew nothing about quantum mechanics, and quite
possibly little if anything about physics. His immediate response was
that any application of quantum mechanics that can be taught after only
a four-hour introduction to the subject cannot have serious intellectual
content. After all, he remarked, it takes any physicist many years to
develop a feeling for quantum mechanics.
It’s a good point. Nevertheless computer scientists and mathematicians with no background in physics have been able quickly to learn
enough quantum mechanics to understand and make major contributions to the theory of quantum computation. There are two main
reasons for this.
First of all, a quantum computer – or, more accurately, the abstract
quantum computer that one hopes someday to be able to embody in actual hardware – is an extremely simple example of a physical system. It
is discrete, not continuous. It is made up out of a finite number of units,
each of which is the simplest possible kind of quantum-mechanical system, a so-called two-state system, whose behavior, as we shall see, is
highly constrained and easily specified. Much of the analytical complexity of learning quantum mechanics is connected with mastering
the description of continuous (infinite-state) systems. By restricting
attention to collections of two-state systems (or even d -state systems
for finite d ) one can avoid much suffering. Of course one also loses
much wisdom, but hardly any of it – at least at this stage of the art – is
relevant to the basic theory of quantum computation.
Second, and just as important, the most difficult part of learning
quantum mechanics is to get a good feeling for how the formalism


can be applied to actual phenomena. This almost invariably involves
formulating oversimplified abstract models of real physical systems, to
which the quantum formalism can then be applied. The best physicists
have an extraordinary intuition for what features of the phenomena
are essential and must be represented in a model, and what features
are inessential and can be ignored. It takes years to develop such intuition. Some never do. The theory of quantum computation, however,
is entirely concerned with an abstract model – the easy part of the
To understand how to build a quantum computer, or even to study
what physical systems are promising candidates for realizing such a
device, you must indeed have many years of experience in quantum
mechanics and its applications under your belt. But if you only want to
know what such a device is capable in principle of doing once you have it,
then there is no reason to get involved in the really difficult physics of the
subject. Exactly the same thing holds for ordinary classical computers.
One can be a masterful practitioner of computer science without having
the foggiest notion of what a transistor is, not to mention how it works.
So while you should be warned that the subset of quantum mechanics
you will acquire from this book is extremely focused and quite limited
in its scope, you can also rest assured that it is neither oversimplified nor
incomplete, when applied to the special task for which it is intended.
I might note that a third impediment to developing a good intuition
for quantum physics is that in some ways the behavior implied by
quantum mechanics is highly counterintuitive, if not downright weird.
Glimpses of such strange behavior sometimes show up at the level
of quantum computation. Indeed, for me one of the major appeals of
quantum computation is that it affords a new conceptual arena for
trying to come to a better understanding of quantum weirdness. When
opportunities arise I will call attention to some of this strange behavior,
rather than (as I easily could) letting it pass by unremarked upon and
The book evolved as notes for a course of 28 one-hour lectures on quantum computation that I gave six times between 2000 and 2006 to a diverse group of Cornell University undergraduates, graduate students,
and faculty, in computer science, electrical engineering, mathematics,
physics, and applied physics. With so broad an audience, little common knowledge could be assumed. My lecture notes, as well as my own
understanding of the subject, repeatedly benefited from comments
and questions in and after class, coming from a number of different
perspectives. What made sense to one of my constituencies was often
puzzling, absurd, or irritatingly simple-minded to others. This final
form of my notes bears little resemblance to my earliest versions, having been improved by insightful remarks, suggestions, and complaints
about everything from notation to number theory.




In addition to the 200 or so students who passed through P481-P681CS483, I owe thanks to many others. Albert J. Sievers, then Director
of Cornell’s Laboratory of Atomic and Solid State Physics, started
me thinking hard about quantum computation by asking me to put
together a two-week set of introductory lectures for members of our
laboratory, in the Fall of 1999. So many people showed up from all over
the university that I decided it might be worth expanding this survey into a full course. I’m grateful to two Physics Department chairs,
Peter Lepage and Saul Teukolsky, for letting me continue teaching
that course for six straight years, and to the Computer Science Department chair, Charlie van Loan, for support, encouragement, and
a steady stream of wonderful students. John Preskill, though he may
not know it, taught me much of the subject from his superb online
Caltech lecture notes. Charles Bennett first told me about quantum
information processing, back when the term might not even have been
coined, and he has always been available as a source of wisdom and clarification. Gilles Brassard has on many occasions supplied me with help
from the computer-science side. Chris Fuchs has been an indispensable quantum-foundational critic and consultant. Bob Constable made
me, initially against my will, a certified Cornell Information Scientist
and introduced me to many members of that excellent community.
But most of all, I owe thanks to David DiVincenzo, who collaborated
with me on the 1999 two-week LASSP Autumn School and has acted
repeatedly over the following years as a sanity check on my ideas, an
indispensable source of references and historical information, a patient
teacher, and an encouraging friend.

A note on references

Quantum Computer Science is a pedagogical introduction to the basic
structure and procedures of the subject – a quantum-computational
primer. It is not a historical survey of the development of the field.
Many of these procedures are named after the people who first put
them forth, but although I use their names, I do not cite the original
papers unless they add something to my own exposition. This is because, not surprisingly, work done since the earliest papers has led to
clearer expositions of those ideas. I learned the subject myself almost
exclusively from secondary, tertiary, or even higher-order sources, and
then reformulated it repeatedly in the course of teaching it for six years.
On the few occasions when I do cite a paper it is either because
it completes an exposition that I have only sketched, or because the
work has not yet become identified in the field with the name(s) of the
author(s) and I wanted to make clear that it was not original with me.
Readers interested in hunting down earlier work in the field can
begin (and in most cases conclude) their search at the quantum-physics
subdivision of the Cornell (formerly Los Alamos) E-print Archive,, where most of the
important papers in the field have been and are still being posted.

Chapter 1

Cbits and Qbits

1.1 What is a quantum computer?
It is tempting to say that a quantum computer is one whose operation
is governed by the laws of quantum mechanics. But since the laws of
quantum mechanics govern the behavior of all physical phenomena,
this temptation must be resisted. Your laptop operates under the laws
of quantum mechanics, but it is not a quantum computer. A quantum
computer is one whose operation exploits certain very special transformations of its internal state, whose description is the primary subject of
this book. The laws of quantum mechanics allow these peculiar transformations to take place under very carefully controlled conditions.
In a quantum computer the physical systems that encode the individual logical bits must have no physical interactions whatever that are
not under the complete control of the program. All other interactions,
however irrelevant they might be in an ordinary computer – which
we shall call classical – introduce potentially catastrophic disruptions
into the operation of a quantum computer. Such damaging encounters can include interactions with the external environment, such as
air molecules bouncing off the physical systems that represent bits, or
the absorption of minute amounts of ambient radiant thermal energy.
There can even be disruptive interactions between the computationally relevant features of the physical systems that represent bits and
other features of those same systems that are associated with computationally irrelevant aspects of their internal structure. Such destructive
interactions, between what matters for the computation and what does
not, result in decoherence, which is fatal to a quantum computation.
To avoid decoherence individual bits cannot in general be encoded
in physical systems of macroscopic size, because such systems (except
under very special circumstances) cannot be isolated from their own
irrelevant internal properties. Such isolation can be achieved if the bits
are encoded in a small number of states of a system of atomic size, where
extra internal features do not matter, either because they do not exist, or
because they require unavailably high energies to come into play. Such
atomic-scale systems must also be decoupled from their surroundings
except for the completely controlled interactions that are associated
with the computational process itself.




Two things keep the situation from being hopeless. First, because
the separation between the discrete energy levels of a system on the
atomic scale can be enormously larger than the separation between the
levels of a large system, the dynamical isolation of an atomic system
is easier to achieve. It can take a substantial kick to knock an atom
out of its state of lowest energy. The second reason for hope is the
discovery that errors induced by extraneous interactions can actually
be corrected if they occur at a sufficiently low rate. While error correction is routine for bits represented by classical systems, quantum
error correction is constrained by the formidable requirement that it
be done without knowing either the original or the corrupted state of
the physical systems that represent the bits. Remarkably, this turns out
to be possible.
Although the situation is therefore not hopeless, the practical difficulties in the way of achieving useful quantum computation are enormous. Only a rash person would declare that there will be no useful
quantum computers by the year 2050, but only a rash person would
predict that there will be. Never mind. Whether or not it will ever
become a practical technology, there is a beauty to the theory of quantum computation that gives it a powerful appeal as a lovely branch of
mathematics, and as a strange generalization of the paradigm of classical computer science, which had completely escaped the attention of
computer scientists until the 1980s. The new paradigm demonstrates
that the theory of computation can depend profoundly on the physics
of the devices that carry it out. Quantum computation is also a valuable
source of examples that illustrate and illuminate, in novel ways, the
mysterious phenomena that quantum behavior can give rise to.
For computer scientists the most striking thing about quantum computation is that a quantum computer can be vastly more efficient than
anything ever imagined in the classical theory of computational complexity, for certain computational tasks of considerable practical interest. The time it takes the quantum computer to accomplish such tasks
scales up much more slowly with the size of the input than it does in
any classical computer. Much of this book is devoted to examining the
most celebrated examples of this speed-up.
This exposition of quantum computation begins with an introduction to quantum mechanics, specially tailored for this particular application. The quantum-mechanics lessons are designed to give you,
as efficiently as possible, the conceptual tools needed to delve into
quantum computation. This is done by restating the rules of quantum
mechanics, not as the remarkable revision of classical Newtonian mechanics required to account for the behavior of matter at the atomic
and subatomic levels, but as a curious generalization of rules describing an ordinary classical digital computer. By focusing exclusively on
how quantum mechanics enlarges the possibilities for the physical manipulation of digital information, it is possible to characterize how


the quantum theory works in an elementary and quite concise way,
which is nevertheless rigorous and complete for this special area of
While I assume no prior familiarity with quantum physics (or any
other kind of physics), I do assume familiarity with elementary linear
algebra and, in particular, with the theory of finite-dimensional vector
spaces over the complex numbers. Appendix A summarizes the relevant
linear algebra. It is worth examining even if you are well acquainted
with the mathematics of such vector spaces, since it also provides a
compact summary of the mathematically unconventional language –
Dirac notation – in which linear algebra is couched in all treatments of
quantum computation. Dirac notation is also developed, more informally, throughout the rest of this chapter.

1.2 Cbits and their states
We begin with an offbeat formulation of what an ordinary classical
computer does. I frame the elementary remarks that follow in a language which may look artificial and cumbersome, but is designed to
accommodate the richer variety of things that a computer can do if it
takes full advantage of the possibilities made available by the quantummechanical behavior of its constituent parts. By introducing and applying the unfamiliar nomenclature and notation of quantum mechanics
in a familiar classical context, I hope to make a little less strange its
subsequent extension to the broader quantum setting.
A classical computer operates on strings of zeros and ones, such
as 110010111011000, converting them into other such strings. Each
position in such a string is called a bit, and it contains either a 0 or a
1. To represent such collections of bits the computer must contain a
corresponding collection of physical systems, each of which can exist
in two unambiguously distinguishable physical states, associated with
the value (0 or 1) of the abstract bit that the physical system represents.
Such a physical system could be, for example, a switch that could be
open (0) or shut (1), or a magnet whose magnetization could be oriented
in two different directions, “up” (0) or “down” (1).
It is a common practice in quantum computer science to use the
same term “bit” to describe the two-state classical system that represents the value of the abstract bit. But this use of a single term to
characterize both the abstract bit (0 or 1) and the physical system whose
two states represent the two values is a potential source of confusion.
To avoid such confusion, I shall use the term Cbit (“C” for “classical”) to describe the two-state classical physical system and Qbit to
describe its quantum generalization. This terminology is inspired by
Paul Dirac’s early use of c-number and q-number to describe classical
quantities and their quantum-mechanical generalizations. “Cbit” and




“Qbit” are preferable to “c-bit” and “q-bit” because the terms themselves often appear in hyphenated constructions.
Unfortunately the preposterous spelling qubit currently holds sway
for the quantum system. The term qubit was invented and first used
in print by the otherwise admirable Benjamin Schumacher.1 A brief
history of the term can be found in the acknowledgments at the end of
his paper. Although “qubit” honors the English (German, Italian, . . .)
rule that q should be followed by u, it ignores the equally powerful
requirement that qu should be followed by a vowel. My guess is that
“qubit” has gained acceptance because it visually resembles an obsolete
English unit of distance, the homonymic cubit. To see its ungainliness
with fresh eyes, it suffices to imagine that Dirac had written qunumber
instead of q-number, or that one erased transparencies and cleaned one’s
ears with Qutips.
Because clear distinctions among bits, Cbits, and Qbits are crucial
in the introduction to quantum computation that follows, I shall use
this currently unfashionable terminology. If you are already addicted
to the term qubit, please regard Qbit as a convenient abbreviation.
To prepare for the extension from Cbits to Qbits, I introduce what
may well strike you as a degree of notational overkill in the discussion
of Cbits that follows. We shall represent the state of each Cbit as a kind
of box, depicted by the symbol | , into which we place the value, 0
or 1, represented by that state. Thus the two distinguishable states of
a Cbit are represented by the symbols |0 and |1. It is the common
practice to call the symbol |0 or |1 itself the state of the Cbit, thereby
using the same term to refer to both the physical condition of the
Cbit and the abstract symbol that represents that physical condition.
There is nothing unusual in this. For example one commonly uses the
term “position” to refer to the symbol x that represents the physical
position of an object. I call this common, if little noted, practice to your
attention only because in the quantum case “state” refers only to the
symbol, there being no internal property of the Qbit that the symbol
represents. The subtle relation between Qbits and their state symbol
will emerge later in this chapter.
Along the same lines, we shall characterize the states of the five Cbits
representing 11001, for example, by the symbol


and refer to this object as the state of all five Cbits. Thus a pair of Cbits
can have (or “be in”) any of the four possible states
|0|0, |0|1, |1|0, |1|1,

1 Benjamin Schumacher, “Quantum coding,” Physical Review A 51,
2738–2747 (1995).



three Cbits can be in any of the eight possible states
|0|0|0, |0|0|1, |0|1|0, |0|1|1, |1|0|0,
|1|0|1, |1|1|0, |1|1|1,


and so on.
As (1.4) already makes evident, when there are many Cbits such
products are often much easier to read if one encloses the whole string
of zeros and ones in a single bigger box of the form |  rather than
having a separate box for each Cbit:
|000, |001, |010, |011, |100, |101, |110, |111.


We shall freely move between these two equivalent ways of expressing
the state of several Cbits that represent a string of bits, boxing the whole
string or boxing each individual bit. Whether the form (1.3) or (1.4) is
to be preferred depends on the context.
There is also a third form, which is useful when we regard the zeros
and ones as constituting the binary expansion of an integer. We can
then replace the representations of the 3-Cbit states in (1.4) by the
even shorter forms
|0, |1, |2, |3, |4, |5, |6, |7.


Note that, unlike the forms (1.3) and (1.4), the form (1.5) is ambiguous,
unless we are told that these symbols express states of three Cbits. If
we are not told, then there is no way of telling, for example, whether
|3 represents the 2-Cbit state|11, the 3-Cbit state|011, or the 4-Cbit
state |0011, etc. This ambiguity can be removed, when necessary, by
adding a subscript making the number of Cbits explicit:
|03 , |13 , |23 , |33 , |43 , |53 , |63 , |73 .


Be warned, however, that, when there is no need to emphasize how
many Cbits |x represents, it can be useful to use such subscripts for
other purposes. If, for example, Alice and Bob each possess a single
Cbit it can be convenient to describe the state of Alice’s Cbit (if it has
the value 1) by |1a , Bob’s (if it has the value 0) by |0b , and the joint
state of the two by |1a |0b or |10ab .
Dirac introduced the |  notation (known as Dirac notation) in the
early days of the quantum theory, as a useful way to write and manipulate vectors. For silly reasons he called such vectors kets, a terminology
that has survived to this day. In Dirac notation you can put into the box
|  anything that serves to specify what the vector is. If, for example, we
were talking about displacement vectors in ordinary three-dimensional
space, we could have a vector
|5 horizontal centimeters northeast.





In using Dirac notation to express the state of a Cbit, or a collection
of Cbits, I’m suggesting that there might be some utility in thinking
of the states as vectors. Is there? Well, in the case of Cbits, not very
much, but maybe a little. We now explore this way of thinking about
Cbit states, because when we come to the generalization to Qbits, it
becomes absolutely essential to consider them to be vectors – so much
so that the term state is often taken to be synonymous with vector (or,
more precisely, “vector that represents the state”).
We shall briefly explore what one can do with Cbits when one takes
the two states |0 and |1 of a single Cbit to be represented by two
orthogonal unit vectors in a two-dimensional space. While this is little
more than a curious and unnecessarily elaborate way of describing
Cbits, it is fundamental and unavoidable in dealing with Qbits. Playing
unfamiliar and somewhat silly games with Cbits will enable you to
become acquainted with much of the quantum-mechanical formalism
in a familiar setting.
If you prefer your vectors to be expressed in terms of components,
note that we can represent the two orthogonal states of a single Cbit,
|0 and |1, as column vectors
|0 =
|1 =
In the case of two Cbits the vector space is four-dimensional, with
an orthonormal basis
|00, |01, |10, |11.


The alternative notation for this basis,
|0|0, |0|1, |1|0, |1|1,


is deliberately designed to suggest multiplication, since it is, in fact,
a short-hand notation for the tensor product of the two single-Cbit
2-vectors, written in more formal mathematical notation as
|0 ⊗ |0, |0 ⊗ |1, |1 ⊗ |0, |1 ⊗ |1.


In terms of components, the tensor product a ⊗ b of an M-component
vector a with components a µ and an N-component vector b with components b ν is the (MN)-component vector with components indexed
by all the MN possible pairs of indices (µ, ν), whose (µ, ν)th component is just the product a µ b ν . A broader view can be found in the
extended review of vector-space concepts in Appendix A. I shall freely
move back and forth between the various ways (1.9)–(1.11) of writing
the tensor product and their generalizations to multi-Cbit states, using
in each case a form that makes the content clearest.
Once one agrees to regard the two 1-Cbit states as orthogonal unit
vectors, the tensor product is indeed the natural way to represent


multi-Cbit states, since it leads to the obvious multi-Cbit generalization of the representation (1.8) of 1-Cbit states as column vectors. If we
express the states |0 and |1 of each single Cbit as column vectors, then
we can get the column vector describing a multi-Cbit state by repeatedly applying the rule for the components of the tensor product of two
vectors. The result is illustrated here for a three-fold tensor product:
⎛x y z ⎞
0 0 0

⎜ x0 y0 z1 ⎟
x0 y1 z0 ⎟
⎜x y z ⎟
= ⎜ 0 1 1 ⎟.
⎜ x1 y0 z0 ⎟
⎜ x1 y0 z1 ⎟
x1 y1 z0
x1 y1 z1
On applying this, for example, to the case |53 , we have



⎜ ⎟
⎜ ⎟
|53 = |101 = |1|0|1 =
= ⎜ ⎟. (1.13)
⎜ ⎟
⎝ ⎠
If we label the vertical components of the 8-vector on the right
0, 1, . . ., 7, from the top down, then the single nonzero component is
the 1 in position 5 – precisely the position specified by the state vector
in its form on the left of (1.13). This is indeed the obvious multi-Cbit
generalization of the column-vector form (1.8) for 1-Cbit states.
This is quite general: the tensor-product structure of multi-Cbit
states is just what one needs in order for the 2n -dimensional column
vector representing the state |m n to have all its entries zero except for
a single 1 in the m th position down from the top.
One can turn this development upside down, taking as one’s starting
point the simple rule that an integer x in the range 0 ≤ x < N is
represented by one of N orthonormal vectors in an N-dimensional
space. One can then pick a basis so that 0 is represented by an Ncomponent column vector |0 that has 0 in every position except for a
1 in the top position, and x is to be represented by an N-component
column vector |x that has 0 in every position except for a 1 in the
position x down from the top. It then follows from the nature of the
tensor product that if N = 2n and x has the binary expansion x =
j =0 x j 2 , then the column vector |xn is the tensor product of the n
2-component column vectors |x j :
|xn = |xn−1  ⊗ |xn−2  ⊗ · · · ⊗ |x1  ⊗ |x0 .





In dealing with n-Cbit states of the form (1.14) we shall identify each
of the n 1-Cbit states, out of which they are composed, by giving the
power of 2 associated with the individual bit that the Cbit represents.
Thus the 1-Cbit state on the extreme right of (1.14) represents Cbit 0,
the state immediately to its left represents Cbit 1, and so on.
This relation between tensor products of vectors and positional
notation for integers is not confined to the binary system. Suppose,
for example, one represents a decimal digit x = 0, 1, . . ., 9 as a 10component column vector v(x) with all components 0 except for a
1, x positions down from the top. If the n-digit decimal number
(xn−1 )
X = n−1
j =0 x j 10 is represented by the tensor product V = v
(xn−2 )
⊗ · · · ⊗ v ⊗ v , then V will be a 10 -component column vector with all components 0 except for a 1, x positions down from the
Although the representation of Cbit states by column vectors clearly
shows why tensor products give a natural description of multi-Cbit
states, for almost all other purposes it is better and much simpler to
forget about column vectors and components, and deal directly with
the state vectors in their abstract forms (1.3)–(1.6).

1.3 Reversible operations on Cbits
Quantum computers do an important part of their magic through reversible operations, which transform the initial state of the Qbits into
its final form using only processes whose action can be inverted. There
is only a single irreversible component to the operation of a quantum
computer, called measurement, which is the only way to extract useful
information from the Qbits after their state has acquired its final form.
Although measurement is a nontrivial and crucial part of any quantum
computation, in a classical computer the extraction of information from
the state of the Cbits is so conceptually straightforward that it is not
viewed as an inherent part of the computational process, though it is,
of course, a nontrivial concern for those who design digital displays
or printers. Because the only computationally relevant operations on
a classical computer that can be extended to operations on a quantum
computer are reversible, only operations on Cbits that are reversible
will be of interest to us here.
In a reversible operation every final state arises from a unique initial
state. An example of an irreversible operation is ERASE, which forces
a Cbit into the state |0 regardless of whether its initial state is |0 or
|1. ERASE is irreversible in the sense that, given only the final state
and the fact that it was the output of the operation ERASE, there is no
way to recover the initial state.
The only nontrivial reversible operation we can apply to a single Cbit
is the NOT operation, denoted by the symbol X, which interchanges


the two states |0 and |1:
X : |x → |x̃; 1̃ = 0, 0̃ = 1.


This is sometimes referred to as flipping the Cbit. NOT is reversible
because it has an inverse: applying X a second time brings the state of
the Cbit back to its original form:
X 2 = 1,


where 1 is the unit (identity) operator. If we represent the two orthogonal states of the Cbit by the column vectors (1.8), then we can
express NOT by a linear operator X on the two-dimensional vector
space, whose action on the column vectors is given by the matrix

0 1
1 0
So the two reversible things you can do to a single Cbit – leaving it
alone and flipping it – correspond to the two linear operators X and 1,

1 0
0 1
on its two-dimensional vector space.
A pedantic digression: since multiplication by the scalar 1 and action by the unit operator 1 achieve the same result, I shall sometimes
follow the possibly irritating practice of physicists and not distinguish
notationally between them. I shall take similar liberties with the scalar
0, the zero vector 0, and the zero operator 0.
Possibilities for reversible operations get richer when we go from a
single Cbit to a pair of Cbits. The most general reversible operation on
two Cbits is any permutation of their four possible states. There are 4!
= 24 such operations. Perhaps the simplest nontrivial example is the
swap (or exchange) operator Si j , which simply interchanges the states
of Cbits i and j :
S10 |xy = |yx.


Since the swap operator S10 interchanges |01 = |12 and |10 = |22 ,
while leaving |00 = |02 and |11 = |32 fixed, its matrix in the basis
|02 , |12 , |22 , |32 is
1 0 0 0
⎜0 0 1 0⎟
S10 = S01 = ⎜
⎝ 0 1 0 0 ⎠.
0 0 0 1
The 2-Cbit operator whose extension to Qbits plays by far the
most important role in quantum computation is the controlled-NOT
or cNOT operator Ci j . If the state of the i th Cbit (the control Cbit) is
|0, Ci j leaves the state of the j th Cbit (the target Cbit) unchanged, but,




if the state of the control Cbit is |1, Ci j applies the NOT operator X
to the state of the target Cbit. In either case the state of the control Cbit
is left unchanged.
We can summarize this compactly by writing
C10 |x|y = |x|y ⊕ x,

C01 |x|y = |x ⊕ y|y,


where ⊕ denotes addition modulo 2:
y ⊕ 0 = y,

y ⊕ 1 = ỹ = 1 − y.


The modulo-2 sum x ⊕ y is also called the “exclusive OR” (or XOR)
of x and y.
You can construct SWAP out of three cNOT operations:
Si j = Ci j C j i Ci j .


This can easily be verified by repeated applications of (1.21), noting
that x ⊕ x = 0. We note some other ways of showing it below.
To construct the matrix for the cNOT operation in the fourdimensional 2-Cbit space, note that if the control Cbit is on the left
then cNOT leaves |00 = |02 and |01 = |12 fixed and exchanges
|10 = |22 and |11 = |32 . Therefore the 4 ⊗ 4 matrix representing
C10 is just
1 0 0 0
⎜0 1 0 0⎟
C10 = ⎜
⎝ 0 0 0 1 ⎠.
0 0 1 0
If the control Cbit is on the right, then the states |01 = |12 and
|11 = |32 are interchanged, and |00 = |02 and |10 = |22 are fixed,
so the matrix representing C01 is
1 0 0 0
⎜0 0 0 1⎟
C01 = ⎜
⎝ 0 0 1 0 ⎠.
0 1 0 0
The construction (1.23) of S out of cNOT operators also follows
from (1.20), (1.24), and (1.25), using matrix multiplication. As a practical matter, it is almost always more efficient to establish operator
identities by dealing with them directly as operators, avoiding matrix
A very common kind of 2-Cbit operator consists of the tensor product ⊗ of two 1-Cbit operators:
(a ⊗ b)|xy = (a ⊗ b)|x ⊗ |y = a|x ⊗ b|y,


from which it follows that
(a ⊗ b)(c ⊗ d) = (ac) ⊗ (bd).



This tensor-product notation for operators can become quite ungainly when one is dealing with a large number of Cbits and wants to
write a 2-Cbit operator that affects only a particular pair of Cbits. If,
for example, the 2-Cbit operator in (1.26) acts only on the second and
fourth Cbits from the right in a 6-Cbit state, then the operator on the
6-Cbit state has to be written as
1 ⊗ 1 ⊗ a ⊗ 1 ⊗ b ⊗ 1.


To avoid such typographical monstrosities, we simplify (1.28) to
1 ⊗ 1 ⊗ a ⊗ 1 ⊗ b ⊗ 1 = a3 b1 = b1 a3 ,


where the subscript indicates which Cbit the 1-Cbit operator acts on,
and it is understood that those Cbit states whose subscripts do not
appear remain unmodified – i.e. they are acted on by the unit operator.
As noted above, we label each 1-Cbit state by the power of 2 it would
represent if the n Cbits were representing an integer: the state on the
extreme right is labeled 0, the one to its left, 1, etc. Since the order
in which a and b are written is clearly immaterial if their subscripts
specify different 1-Cbit states, the order in which one writes them in
(1.29) doesn’t matter: 1-Cbit operators that act on different 1-Cbit
states commute.
Sometimes we deal with 1-Cbit operators that already have subscripts in their names; under such conditions it is more convenient to indicate which Cbit state the operator acts on by a superscript, enclosed in parentheses to avoid confusion with an exponent:
thus X(2) represents the 1-Cbit operator that flips the third Cbit
state from the right, but X2 represents the square of the flip operator (i.e. the unit operator) without reference to which Cbit state it
acts on.
To prepare for some of the manipulations we will be doing with
operations on Qbits, we now examine a few examples of working with
operators on Cbits.

1.4 Manipulating operations on Cbits
It is useful to introduce a 1-Cbit operator n that is simply the projection
operator onto the state |1:
n|x = x|x, x = 0 or 1.


Because |0 and |1 are eigenvectors of n with eigenvalues 0 and 1, n is
called the 1-Cbit number operator. We also define the complementary
ñ = 1 − n,





which projects onto the state |0, so |0 and |1 are eigenvectors of ñ with
eigenvalues 1 and 0. These operators have the matrix representations

0 0
1 0
ñ =
0 1
0 0
It follows directly from their definitions that
n 2 = n,

ñ2 = ñ,

nñ = ñn = 0,

n + ñ = 1.


We also have
nX = Xñ,

ñX = Xn,


since flipping the state of a Cbit and then acting on it with n (ñ) is the
same as acting on the state with ñ (n) and then flipping it. All the simple
relations in (1.33) and (1.34) also follow, as they must, from the matrix
representations (1.17) and (1.32) for X, n, and ñ.
Although n has no interpretation as a physical operation on Cbits –
replacing the state of a Cbit by the zero vector corresponds to no physical operation – it can be useful in deriving relations between operations
that do have physical meaning. Since, for example, the SWAP operator
Si j acts as the identity if the states of the Cbits i and j are the same, and
flips the numbers represented by both Cbits if their states are different,
it can be written as
Si j = ni n j + ñi ñ j + (Xi X j )(ni ñ j + ñi n j ).


At the risk of belaboring the obvious, I note that (1.35) acts as the
swap operator because if both Cbits are in the state |1 (so swapping
their states does nothing) then only the first term in the sum acts (i.e.
each of the other three terms gives 0) and multiplies the state by 1;
if both Cbits are in the state |0, only the second term acts and again
multiplies the state by 1; if Cbit i is in the state |1 and Cbit j is in the
state |0, only the third term acts and the effect of flipping both Cbits
is to swap their states; and if Cbit i is in the state |0 and Cbit j is in
the state |1, only the fourth term acts and the effect of the two Xs is
again to swap their states.
To help you become more at home with this notation, you are urged
to prove from (1.35) that Si2j = 1, using only the relations in (1.33) and
(1.34), the fact that X2 = 1, and the fact that 1-Cbit operators acting
on different Cbits commute.
The construction (1.23) of SWAP out of cNOT operators can also
be demonstrated using a more algebraic approach. Note first that Ci j
can be expressed in terms of ns and Xs by
Ci j = ñi + X j ni ,


since if the state of Cbit i is |0 only the first term acts, which leaves the
states of both Cbits unchanged, but if the state of Cbit i is |1 only the
second term acts, which leaves the state of Cbit i unchanged, while X j


flips Cbit j . If you substitute expressions of the form (1.36) for each
of the three terms in (1.23), then you can show by purely algebraic
manipulations that four of the eight terms into which the products
expand vanish and the remaining four can be rearranged to give the
swap operator (1.35).
An operator that has no direct role to play in classical computation, but which is as important as the NOT operator X in quantum
computation, is the operator Z defined by

Z = ñ − n =
0 −1
It follows from (1.34) (or from the matrix representations (1.17) and
(1.37)) that X anticommutes with Z:
ZX = −XZ.


Since ñ + n = 1, we can use (1.37) to express the 1-Cbit projection
operators ñ and n in terms of 1 and Z:
n = 12 (1 − Z),

ñ = 12 (1 + Z).


Using this we can rewrite the cNOT operator (1.36) in terms of X
and Z operators:
Ci j =



1 + Zi + 12 X j 1 − Zi
1 + X j + 12 Zi 1 − X j .


The second form follows from the first because X j and Zi commute
when i = j . Note that, if we were to interchange X and Z in the second
line of (1.40), we would get back the expression directly above it except
for the interchange of i and j . So interchanging the X and Z operators
has the effect of switching which Cbit is the control and which is
the target, changing Ci j into C j i . An operator that can produce just
this effect is the Hadamard transformation (also sometimes called the
Walsh–Hadamard transformation),

1 1
H = √ (X + Z ) = √
2 1 −1
This is another operator of fundamental importance in quantum
2 Physicists should note here an unfortunate clash between the notations of
quantum computer science and physics. Quantum physicists invariably use
H to denote the Hamiltonian function (in classical mechanics) or
Hamiltonian operator (in quantum mechanics). Fortunately Hamiltonian
operators, although of crucial importance in the design of quantum
computers, play a very limited role in the general theory of quantum
computation, being completely overshadowed by the unitary
transformations that they generate. So physicists can go along with the
computer-science notation without getting into serious trouble.




Since X2 = Z2 = 1 and XZ = −ZX, one easily shows from the
definition (1.41) of H in terms of X and Z that
H2 = 1


and that
HXH = Z,

HZH = X.


This shows how H can be used to interchange the X and Z operators
in C j i : it follows from (1.43), together with (1.40) and (1.42), that
C j i = Hi H j Ci j Hi H j .


We shall see that this simple relation can be put to some quite
remarkable uses in a quantum computer. While one can achieve
this interchange on a classical computer using the SWAP operation,
C j i = Si j Ci j Si j , the crucial difference between Si j and Hi H j is that
the latter is a product of two 1-Cbit operators, while the former is not.
Of course, the action of H on the state of a Cbit that follows from
H|0 =

√1 (|0

+ |1),

H|1 =

√1 (|0

− |1),


describes no meaningful transformation of Cbits. Nevertheless, when
combined with other operations, as on the right side of (1.44), the
Hadamard operations result in the perfectly sensible operation given
on the left side. In a quantum computer the action of H on 1-Qbit
states turns out to be not only meaningful but also easily implemented,
and the possibility of interchanging control and target Qbits using only
1-Qbit operators in the manner shown in (1.44) turns out to have some
striking consequences.
The use of Hadamards to interchange the control and target Qbits of
a cNOT operation is sufficiently important in quantum computation
to merit a second derivation of (1.44), which further illustrates the
way in which one uses the operator formalism. In strict analogy to the
definition of cNOT (see (1.21) and the preceding paragraph) we can
define a controlled-Z operation, CiZj , which leaves the state of the target
Cbit j unchanged if the state of the control Cbit i is |0, and operates
on the target Cbit with Z if the state of the control Cbit is |1. As a
|xy acts as the identity on |xy unless both x and y are 1, in
result C10
which case it simply takes |11 into −|11. This behavior is completely
symmetric in the two Cbits, so
CiZj = C Zji .


It is a straightforward consequence of (1.42) and (1.43) that sandwiching the target Cbit of a cNOT between Hadamards converts


it to a C Z :
H j Ci j H j = CiZj ,

Hi C j i Hi = C Zji .


In view of (1.46), we then have
H j Ci j H j = Hi C j i Hi ,


which is equivalent to (1.44), since H2 = 1.
As a final exercise in treating operations on Cbits as linear operations
on vectors, we construct an alternative form for the swap operator. If
we use (1.39) to reexpress each n and ñ appearing in the swap operator
(1.35) in terms of Z, we find that
Si j = 12 (1 + Zi Z j ) + 12 (Xi X j )(1 − Zi Z j ).

If we define

Y = i XZ =



(i =





we get the more compact form
Si j = 12 (1 + Xi X j + Yi Y j + Zi Z j ).


For three quarters of a century physicists have enjoyed grouping the
matrix representations of the three operators X, Y, and Z into a “3→
vector” −
σ whose “components” are 2 ⊗ 2 matrices:

0 −i
σx =
σy =
σz =
0 −1
The swap operator then becomes3
Si j =



(i )

σ ( j) ,


where “·” represents the ordinary three-dimensional scalar product:
σ (i ) · −
σ ( j ) = σ (ix ) σ (xj ) + σ (iy ) σ (yj ) + σ (iz ) σ (zj ) .
The three components of −
σ have many properties that are unchanged under cyclic permutations of x, y, and z. All three are
Hermitian.4 All square to unity,
σ 2x = σ 2y = σ 2z = 1.


3 Physicists might enjoy the simplicity of this “computational” derivation of
the form of the exchange operator, compared with the conventional
quantum-mechanical derivation, which invokes the full apparatus of
angular-momentum theory.
4 The elements of a Hermitian matrix A satisfy A j i = Ai∗j , where ∗ denotes
complex conjugation. A fuller statement in a broader context can be found in
Appendix A.




They all anticommute in pairs and the product of any two of them is
simply related to the third:
σ x σ y = −σ y σ x = i σ z,
σ y σ z = −σ zσ y = i σ x ,
σ zσ x = −σ x σ z = i σ y .


The three relations (1.56) differ only by cyclic permutations of x, y,
and z.
All the relations in (1.55) and (1.56) can be summarized in a single
compact and useful identity. Let −
a and b be two 3-vectors with
components a x , a y , a z and b x , b y , b z that are ordinary real numbers.
(They can also be complex numbers, but in most useful applications
they are real.) Then one easily confirms that all the relations in (1.55)
and (1.56) imply and are implied by the single identity
→ →
→ →
a × b )·−
a ·−
σ )( b · −
σ ) = (−
a · b )1 + i (−
where −
a × b denotes the vector product (or “cross product”) of −
and b ,
a × b )x = a y b z − a zb y ,
a × b ) y = a zb x − a x b z,
( a × b )z = a x b y − a y b x .
Together with the unit matrix 1, the matrices σ x , σ y , and σ z form
a basis for the four-dimensional algebra of two-dimensional matrices
of complex numbers: any such matrix is a unique linear combination of
these four with complex coefficients. Because the four are all Hermitian,
any two-dimensional Hermitian matrix A of complex numbers must
be a real linear combination of the four, and therefore of the form
A = a0 1 + −
a ·−


where a 0 and the components of the 3-vector −
a are all real numbers.
The matrices σ x , σ y , and σ z were introduced in the early days of
quantum mechanics by Wolfgang Pauli, to describe the angular momentum associated with the spin of an electron. They have many other
useful purposes, being simply related to the quaternions invented by
Hamilton to deal efficiently with the composition of three-dimensional
rotations.5 It is pleasing to find them here, buried in the interior of the
operator that simply swaps two classical bits. We shall have extensive
occasion to use Pauli’s 1-Qbit operators when we come to the subject of
5 Hamilton’s quaternions i, j, k are represented by i σ x , i σ y , i σ z . The
beautiful and useful connection between Pauli matrices and
three-dimensional rotations discovered by Hamilton is developed in
Appendix B.


quantum error correction. Some of their properties, developed further
in Appendix B, prove to be quite useful in treating Qbits, to which we
now turn.

1.5 Qbits and their states
The state of a Cbit is a pretty miserable specimen of a two-dimensional
vector. The only vectors with any classical meaning in the whole twodimensional vector space are the two orthonormal vectors |0 and |1,
since those are the only two states a Cbit can have. Happily, nature has
provided us with physical systems, Qbits, described by states that do
not suffer from this limitation. The state |ψ associated with a Qbit
can be any unit vector in the two-dimensional vector space spanned by
|0 and |1 over the complex numbers. The general state of a Qbit is
|ψ = α0 |0 + α1 |1 =
where α0 and α1 are two complex numbers constrained only by the
requirement that |ψ, like |0 and |1, should be a unit vector in the
complex vector space – i.e. only by the normalization condition
|α0 |2 + |α1 |2 = 1.


The state |ψ is said to be a superposition of the states |0 and |1 with
amplitudes α0 and α1 . If one of α0 and α1 is 0 and the other is 1 – i.e.
the special case in which the state of the Qbit is one of the two classical
states |0 or |1 – it can be convenient to retain the language appropriate
to Cbits, speaking of the Qbit “having the value” 0 or 1. More correctly,
however, one is entitled to say only that the state of the Qbit is |0 or
|1. Qbits, in contrast to Cbits, cannot be said to “have values.” They
have – or, more correctly, are described by, or, better still, are associated
with – states. We shall often sacrifice correctness for ease of expression.
Some reasons for this apparently pedantic terminological hair splitting
will emerge below.
Just as the general state of a single Qbit is any normalized superposition (1.60) of the two possible classical states, the general state |
that nature allows us to associate with two Qbits is any normalized
superposition of the four orthogonal classical states,
⎛α ⎞

⎜α ⎟
| = α00 |00 + α01 |01 + α10 |10 + α11 |11 = ⎝ 01 ⎠,




with the complex amplitudes being constrained only by the normalization condition
|α00 |2 + |α01 |2 + |α10 |2 + |α11 |2 = 1.





This generalizes in the obvious way to n Qbits, whose general state can
be any superposition of the 2n different classical states, with amplitudes
whose squared magnitudes sum to unity:
αx |xn ,

| =



|αx |2 = 1.



In the context of quantum computation, the set of 2n classical states –
all the possible tensor products of n individual Qbit states |0 and |1 –
is called the computational basis. For most purposes classical basis is a
more appropriate term. I shall use the two interchangeably. The states
that characterize n Cbits – the classical-basis states – are an extremely
limited subset of the states of n Qbits, which can be any (normalized)
superposition with complex coefficients of these classical-basis states.
If we have two Qbits, one in the state |ψ = α0 |0 + α1 |1 and the
other in the state |φ = β0 |0 + β1 |1, then the state | of the pair,
in a straightforward generalization of the rule for multi-Cbit states, is
taken to be the tensor product of the individual states,
| = |ψ ⊗ |φ = α0 |0 + α1 |1 ⊗ β0 |0 + β1 |1
= α0 β0 |00 + α0 β1 |01 + α1 β0 |10 + α1 β1 |11
⎛α β ⎞
0 0
⎜ α0 β1 ⎟
α1 β0 ⎠
α1 β1
Note that a general 2-Qbit state (1.62) is of the special form (1.66) if
and only if α00 α11 = α01 α10 . Since the four amplitudes in (1.62) are
constrained only by the normalization condition (1.63), this relation
need not hold, and the general 2-Qbit state, unlike the general state
of two Cbits, is not a product (1.66) of two 1-Qbit states. The same is
true for states of n Qbits. Unlike Cbits, whose general state can only
be one of the 2n products of |0s and |1s, a general state of n Qbits
is a superposition of these 2n product states and cannot, in general,
be expressed as a product of any set of 1-Qbit states. Individual Qbits
making up a multi-Qbit system, in contrast to individual Cbits, cannot
always be characterized as having individual states of their own.6
Such nonproduct states of two or more Qbits are called entangled
states. The term is a translation of Schrödinger’s verschränkt, which I
6 More precisely, they do not always have what are called pure states of their
own. It is often convenient to give a statistical description of an individual
Qbit (or a group of Qbits) in terms of what is called a density matrix or mixed
state. If one wishes to emphasize that one is not talking about a mixed state,
one uses the term “pure state.” In this book the term “state” always means
“pure state.”


am told is rendered more accurately as “entwined” or “enfolded.” But
Schrödinger himself used the English word “entangled,” and may even
have used it before coining the German term. When the state of several
Qbits is entangled, they can sometimes behave in some very strange
ways. An example of such peculiar behavior is discussed in Appendix
D. Aside from its intrinsic interest, the appendix provides some further
exercise in the analytical manipulation of Qbits.

1.6 Reversible operations on Qbits
The only nontrivial reversible operation a classical computer can perform on a single Cbit is the NOT operation X. Nature has been far
more versatile in what it allows us to do to a Qbit. The reversible
operations that a quantum computer can perform upon a single Qbit
are represented by the action on the state of the Qbit of any linear
transformation that takes unit vectors into unit vectors. Such transformations u are called unitary and satisfy the condition7
uu† = u† u = 1.


Since any unitary transformation has a unitary inverse, such actions of a
quantum computer on a Qbit are reversible. The reason why reversibility is crucial for the effective functioning of a quantum computer will
emerge in Chapter 2.
The most general reversible n-Cbit operation in a classical computer is a permutation of the (2n )! different classical-basis states. The
most general reversible operation that a quantum computer can perform upon n Qbits is represented by the action on their state of any
linear transformation that takes unit vectors into unit vectors – i.e. any
2n -dimensional unitary transformation U, satisfying
UU† = U† U = 1.


Any reversible operation on n Cbits – i.e. any permutation P of the
2n Cbit states – can be associated with a unitary operation U on n Qbits.
One defines the action of U on the classical-basis states of the Qbit to
be identical to the operation of P on the corresponding classical states
of the Cbit. Since the classical basis is a basis, U can be extended to
arbitrary n-Qbit states by requiring it to be linear. Since the action
of U on the classical-basis states is to permute them, its effect on any
superposition of such states
αx |xn is to permute the amplitudes
|αx |2 , so U takes
αx . Such a permutation preserves the value of
unit vectors into unit vectors. Being norm-preserving and linear, U is
indeed unitary.
7 These and other facts about linear operators on vector spaces over the
complex numbers are also reviewed and summarized in Appendix A.




Many important unitary operations on Qbits that we shall be examining below are defined in this way, as permutations of the classical-basis
states, which are implicitly understood to be extended by linearity to
all Qbit states. In particular, the transformations NOT, SWAP, and
cNOT on Cbits are immediately defined in this way for Qbits as well.
But the available unitary transformations on Qbits are, of course, much
more general than straightforward extensions of classical operations.
We have already encountered two such examples, the operator Z and
the Hadamard transformation H. Both of these take the classical-basis
states of a Qbit into another orthonormal basis, so their linear extensions to all Qbit states are necessarily unitary.
In designing quantum algorithms, the class of allowed unitary transformations is almost always restricted to ones that can be built entirely
out of products of unitary transformations that act on only one Qbit
at a time, called 1-Qbit gates, or that act on just a pair of Qbits, called
2-Qbit gates. This restriction is imposed because the technical problems
of making higher-order quantum gates are even more formidable than
the (already difficult) problems of constructing reliable 1- and 2-Qbit
It turns out that this is not a fundamental limitation, since arbitrary
unitary transformations can be approximated to an arbitrary degree
of precision by sufficiently many 1- and 2-Qbit gates. We shall not
prove this general result,8 because all of the quantum algorithms to
be developed here will be explicitly built up entirely out of 1- and
2-Qbit gates. One very important illustration of the sufficiency of 1and 2-Qbit gates will emerge in Chapter 2. For a reversible classical
computer, it can be shown that at least one 3-Cbit gate is needed to
build up general logical operations. But, in a quantum computer, we
shall find, remarkably – and importantly for the feasibility of practical
quantum computation – that the quantum extension of this 3-Cbit gate
can be constructed out of a small number of 1- and 2-Qbit gates.
While unitarity is generally taken to be the hallmark of the transformations nature allows us to perform on quantum states, what is really
remarkable about the transformations of Qbit states is their linearity
(which is, of course, one aspect of their unitarity). It is easy to dream
up simple classical models for a Qbit, particularly if one restricts its
states to real linear combinations of the two computational basis states.
It is not hard to invent classical models for NOT and Hadamard 1Qbit gates that act linearly on all the 1-Qbit states of the model Qbit.
But I know of no classical model that can extend a cNOT on the
four computational basis states of two Cbits to an operation that acts
8 The argument is given by David P. DiVincenzo, “Two-bit gates are universal
for quantum computation,” Physical Review A 51, 1015–1022 (1995),




u y

Fig 1.1 A circuit diagram representing the action on a single Qbit of

the 1-Qbit gate u. Initially the Qbit is described by the input state |ψ
on the left. The thin line (wire) represents the subsequent history of
the Qbit. After emerging from the box representing u, the Qbit is
described on the right by the final state u|ψ.




Fig 1.2 A circuit diagram representing the action on n Qbits of the

n-Qbit gate U. Initially the Qbits ares described by the input state |
on the left. The thick line (bar) represents the subsequent history of
the Qbits. After emerging from the box representing U, the Qbits are
described on the right by the final state U|.

linearly on all the states of two model Qbits. It is a remarkable and
highly nontrivial fact about the physical world that nature does allow
us, with much ingenuity and hard work, to fabricate unitary cNOT
gates for a pair of genuine quantum Qbits.

1.7 Circuit diagrams
It is the practice in quantum computer science to represent the action
of a sequence of gates acting on n Qbits by a circuit diagram. The initial
state of the Qbits appears on the left, the final state on the right, and the
gates themselves in the central part of the figure. Figure 1.1 shows the
simplest possible such diagram: a Qbit initially in the state |ψ is acted
on by a 1-Qbit gate u, with the result that the Qbit is assigned the new
state u|ψ. Figure 1.2 shows the analogous diagram for an n-Qbit gate
U and an n-Qbit initial state |. The line that goes into and out of the
box representing the unitary transformation – which becomes useful
when one starts chaining together a sequence of gates – is sometimes
called a wire in the case of a single Qbit, and the thicker line (which
represents n wires) associated with an n-Qbit gate is sometimes called
a bar.
Figure 1.3 reveals a peculiar feature of these circuit diagrams that it is
important to be aware of. The diagrams are read from left to right (as one
reads ordinary prose in European languages). Part (a) portrays a circuit
that acts first with V and then with U on the initial state |. The result
is the state UV|, because it is the convention, in writing equations
for linear operators on vector spaces, that the operation appears to the



Fig 1.3 (a) A circuit

diagram representing the
action on n Qbits of two
n-Qbit gates. Initially the
Qbits are described by the
input state | on the left.
They are acted upon first
by the gate V and then by
the gate U, emerging on
the right in the final state
UV|. Note that the
order in which the Qbits
encounter unitary gates in
the figure is opposite to the
order in which the
corresponding symbols are
written in the symbol for
the final state on the right.
(b) This emphasizes the
unfortunate convention
that, because gates on the
left act before gates on the
right in a circuit diagram, a
circuit showing V on the
left and U on the right
represents the operation
conventionally denoted by











left of the state on which it acts. Thus the sequence of symbols |,
V, and U on the left of the circuit diagram in (a) is reversed from the
sequence in which they appear in the mathematical representation of
the state that is produced on the right. Part (b) shows the consequences
of this for the part of the circuit diagram containing just the gates: a
diagram in which a gate V (on the left) is followed by a gate U on the
right describes the unitary transformation UV.
One should be wary of the possibility for confusion arising from
the fact that operators (and states) in circuit diagrams always appear
in the diagrams in the opposite sequence from the order in which
they appear on the page in the corresponding equations. While several of the most important diagrams we shall encounter are left–right
symmetric, many are not, so one should be on guard against getting
things backwards when translating equations into circuit diagrams and
vice versa.
In lecturing on quantum computation I tried for several years to
reverse the computer-science convention, putting the initial state on
the right of the circuit diagram and letting the gates on the right act
first. This has the great advantage of making the diagram look like
the equation it represents. It has, however, a major disadvantage, even
setting aside the fact that it flies in the face of well established convention. It requires one to write on the blackboard in the wrong direction,
from right to left, whenever one wishes to produce a circuit diagram.
Guessing how far to the right one should start is hard to do if the diagram is a lengthy one, and for this reason I gave up after a few years
and reverted to the conventional form. A better alternative would be
for physicists to start writing their equations with the states on the left
(represented by bra vectors rather than ket vectors9 ) and with linear
operators appearing to the right of the states on which they act. But
this would require abandoning a tradition that goes back three quarters
of a century. So we are stuck with a clash of cultures, and must simply
keep in mind that confusion can arise if one forgets the elementary fact
represented in Figure 1.3(b).
There is little utility to circuit diagrams of the simple form in
Figures 1.1–1.3, but they are important as building blocks out of which
9 See Appendix A for the distinction between bras and kets.


larger circuit diagrams are constructed. As the number of operations
increases, the diagrams enable one to see at a glance the action of a
sequence of 1- and 2-Qbit unitary gates on a collection of many Qbits
in a way that is far more transparent and much more easily remembered than the corresponding formulae. Indeed, many calculations that
involve rather lengthy equations can be simply accomplished by manipulating circuit diagrams, as we shall see.
When the state vectors entering or leaving a wire or bar in a circuit
diagram are computational-basis states like |x, one sometimes omits
the symbol |  and simply writes x.

1.8 Measurement gates and the Born rule
To give the state of a single Cbit you need only one bit of information:
whether the state of the Cbit is |0 or |1. But to specify the state
(1.60) of a single Qbit to an arbitrarily high degree of precision, you
need arbitrarily many bits of information, since you must specify two
complex numbers α and β subject only to the normalization constraint
(1.61). Because Qbits not only have a much richer set of states than
Cbits, but also can be acted on by a correspondingly richer set of
transformations, it might appear obvious that a quantum computer
would be vastly more powerful than a classical computer. But there is a
major catch!
The catch is this: if you have n Cbits, each representing either 0 or
1, you can find out the state of each just by looking. There is nothing
problematic about learning the state of a Cbit, and hence learning the
result of any calculation you may have built up out of operations on those
Cbits. Furthermore – and this is taken for granted in any discussion of
a classical computer – the state of Cbits is not altered by the process
of reading them. The act of acquiring the information from Cbits is
not disruptive. You can read the Cbits at any stage of a computation
without messing up subsequent stages.
In stark contrast, if you have n Qbits in a superposition (1.64) of
computational basis states, there is nothing whatever you can do to them
to extract from those Qbits the vast amount of information contained in
the amplitudes αx . You cannot read out the values of those amplitudes,
and therefore you cannot find out what the state is. The state of n Qbits
is not associated with any ascertainable property of those Qbits, as it is
for Cbits.
There is only one way to extract information from n Qbits in a
given state. It is called making a measurement.10 Making a measurement
10 Physicists will note – others need pay no attention to this remark – that
what follows is more accurately characterized as “making a (von Neumann)
measurement in the computational (classical) basis.” There are other ways




consists of performing a certain test on each Qbit, the outcome of which
is either 0 or 1. The particular collection of zeros and ones produced by
the test is not in general determined by the state | of the Qbits; the
state determines only the probability of the possible outcomes, according
to the following rule: the probability of getting a particular result – say
01100, if you have five Qbits – is given by the squared magnitude of the
amplitude of the state |01100 in the expansion of the state | of the
Qbits in the 25 computational basis states. More generally, if the state
of n Qbits is
|n =

αx |xn ,



then the probability that the zeros and ones resulting from measurements of all the Qbits will give the binary expansion of the integer x is
p(x) = |αx |2 .


This basic rule for how information can be extracted from a quantum state was first enunciated by Max Born, and is known as the Born
rule. It provides the link between amplitudes and the numbers you can
actually read out when you test – i.e. measure – the Qbits. The squared
magnitudes of the amplitudes give the probabilities of outcomes of
measurements. Normalization conditions like (1.65) are just the requirements that the probabilities for all of the 2n mutually exclusive
outcomes add up to 1.
The process of measurement is carried out by a piece of hardware
with a digital display, known as an n-Qbit measurement gate. Such an
n-Qbit measurement gate is depicted schematically in Figure 1.4. In
contrast to unitary gates, which have a unique output state for each
input state, the state of the Qbits emerging from a measurement gate is
only statistically determined by the state of the input Qbits. In further
contrast to unitary gates, the action of a measurement gate cannot be
undone: given the final state |x, there is no way of reconstructing the
initial state |. Measurement is irreversible. Nor is the action of a
measurement gate in any sense linear.
To the extent that it suggests that some preexisting property is being
revealed, “measurement” is a dangerously misleading term, but it is
to make such a measurement, but they can all be reduced to measurements
in the computational basis if an appropriate unitary transformation is
applied to the n-Qbit state of the computer just before carrying out the
measurement. In this book the term “measurement” always means
measurement in the computational basis. Measurements in other bases will
always be treated as measurements in the computational basis preceded by
suitable unitary transformations. There are also more general forms of
measurement than von Neumann measurements, going under the
unpleasant acronym POVM (for “positive operator-valued measure”). We
shall make no explicit use of POVMs.





Σ ax x n




p = ax


Fig 1.4 A circuit diagram representing an n-Qbit measurement gate.

The Qbits are initially described by the n-Qbit state
|n =

αx |xn ,

on the left. After the measurement gate Mn has acted, with probability
p = |αx |2 it indicates an integer x, 0 ≤ x < 2n , and the Qbits are
subsequently described by the state |xn  on the right.

hallowed by three quarters of a century of use by quantum physicists,
and impossible to avoid in treatments of quantum computation. One
should avoid being misled by such spurious connotations of “measurement,” though it confused many physicists in the early days of quantum
mechanics and may well continue to confuse some to this day. In quantum computation “measurement” means nothing more or less than
applying and reading the display of an appropriate measurement gate,
whose action is fully specified by the Born rule, as described above,
and expanded upon below. While measurement in quantum mechanics is not at all like measuring somebody’s weight, it does have some
resemblance to measuring Alice’s IQ , which, one can argue, reveals no
preexisting numerical property of Alice, but only what happens when
she is subjected to an IQ test.
The simplest statement of the Born rule is for a single Qbit. If the
state of the Qbit is the superposition (1.60) of the states |0 and |1
with amplitudes α0 and α1 then the result of the measurement is 0 with
probability |α0 |2 and 1 with probability |α1 |2 . This measurement is
carried out by a 1-Qbit measurement gate, as illustrated in Figure 1.5.
We shall see below that n-Qbit measurement gates can be realized by
applying 1-Qbit measurement gates to each of the n Qbits. The process
of measurement can thus be reduced to applying multiple copies of a
single elementary piece of hardware: the 1-Qbit measurement gate.
In addition to displaying an n-bit integer with probabilities determined by the amplitudes, there is a second very important aspect of the
action of measurement gates: if n Qbits, initially described by a state
|, are sent through an n-Qbit measurement gate, and the display of
the measurement gate indicates the integer x, then one must associate
with the Qbits emerging from that measurement gate the classical-basis
state |xn , as shown in Figures 1.4 and 1.5. This means that all traces
of the amplitudes αx characterizing the input state have vanished from
the output state. The only role they have played in the measurement is
to determine the probability of a particular output.




Fig 1.5 A special case of

Figure 1.4: a 1-Qbit
measurement gate. The
reading x of the gate is
either 0 or 1.

y = a0 0 + a1 1




p = ax 2

If the state of the input Qbits is one of the classical-basis states |xn ,
then according to the Born rule the probability that the measurement
gate will read x and the output state will remain |xn is 1. But for
superpositions (1.69) with more than a single nonzero amplitude αx , the
output state is not determined. Being a single one of the classical basis
states |xn , the output state no longer carries any information about
the amplitudes characterizing the initial state, other than certifying that
the particular amplitude αx was not zero, and, in all likelihood, was not
exceedingly small.
So once you send n Qbits through an n-Qbit measurement gate,
you remove the possibility of extracting any further information about
their original state |. After such a measurement of five Qbits, if the
result is 01100, then the post-measurement state associated with the
Qbits is no longer |, but |01100. The original state |, with all
the rich information potentially available in its amplitudes, is irretrievably lost. Qbits emerging from a measurement gate that indicates the
outcome x are characterized by the state |x, regardless of what their
pre-measurement state may have been.
This change of state attendant upon a measurement is often referred to as a reduction or collapse of the state. One says that the premeasurement state reduces or collapses to the post-measurement state, as
a consequence of the measurement. This should not be taken to imply
(though, alas, it often is) that the Qbits themselves suffer a catastrophic
“reduction” or “collapse.” It is important to keep in mind, in this context, that the state of n Qbits is nothing more than an abstract symbol,
used, via the Born rule, to calculate probabilities of measurement outcomes. As has already been noted, there is no internal property of the
Qbits that corresponds to their state.
You might well wonder how one can learn anything at all of computational interest under these wretched conditions. The artistry of
quantum computation consists of producing, through a cunningly constructed unitary transformation, a superposition in which most of the
amplitudes αx are zero or extremely close to zero, with useful information being carried by any of the values of x that have an appreciable
probability of being indicated by the measurement. It is thus important
to be seeking information that, once possessed, can easily be confirmed,
perhaps with an ordinary (classical) computer (e.g. the factors of a large
number), so that one is not misled by rare and irrelevant low-probability
outcomes. How this is actually accomplished in various cases of interest
will be one of our major preoccupations.
It is important to note and immediately reject a possible misunderstanding of the Born rule. One might be tempted to infer from


the rule that for a Qbit to be in a superposition, such as the state
|ψ = α0 |0 + α1 |1, means nothing more than that the “actual state”
of the Qbit is either |0 with probability |α0 |2 or |1 with probability
|α1 |2 . Such an assertion goes beyond the rule, of course, which merely
asserts that if one subjects a Qbit in the state |ψ to an appropriate
test – a measurement – then the outcome of the test will be 0 or 1
with those probabilities and the post-measurement state of the Qbit
can correspondingly be taken to be |0 or |1. This does not imply that
prior to the test the Qbit already carried the value revealed by the test
and was already described by the corresponding classical-basis state,
since, among other possibilities, the action of the test itself might well
play a role in bringing forth the outcome.
In fact, it is easy to produce examples that demonstrate that the Qbit,
prior to the test, could not have been in either of the states |0 and |1.
We can see this with the help of the Hadamard transformation (1.41).
We have defined the action of the 1-Qbit operators H, X, and Z only
on the computational-basis states |0 and |1, but, as noted above, we
can extend their action to arbitrary linear combinations of these states
by requiring the extensions to be linear operators. Since the states |0
and |1 form a basis, this determines the action of H, X, and Z on any
1-Qbit state.
Because it is linear and norm-preserving, H is unitary, and is therefore the kind of operation a quantum computer can apply to the state
of a Qbit: a 1-Qbit gate. The result of the operation of a Hadamard
gate is to change the state |φ of a Qbit to H|φ. Suppose, now, that we
apply H to a Qbit that is initially in the state
|φ =

√1 (|0

+ |1).


It follows from (1.45) that the result is just
H|φ = |0.


So according to the Born rule, if we measure a Qbit described by the
state H|φ, the result will be 0 with probability 1.
But suppose that a Qbit in the state |φ were indeed either in the state
|0 with probability 12 or in the state |1 with probability 12 . In either
case, according to (1.45),
the subsequent√action of H would produce
a state – either (1/ 2)(|0 + |1) or (1/ 2)(|0 − |1) – that under
measurement yielded 0 or 1 with equal probability. This contradicts
the fact just extracted directly from (1.72) that the result of making a
measurement on a Qbit in the state H|φ is invariably 0.
So a Qbit in a quantum superposition of |0 and |1 cannot be viewed
as being either in the state |0 or in the state |1 with certain probabilities.
Such a state represents something quite different. Although the Qbit
reveals only a 0 or a 1 when you query it with a measurement gate,




prior to the query its state is not in general either |0 or |1, but a
superposition of the form (1.60). Such a superposition is as natural
and irreducible a description of a Qbit as |0 and |1 are. This point is
expanded on in Appendix C.
If the states of n Qbits are restricted to computational-basis states
then the process of measurement is just like the classical process of
“learning the value” of x without altering the state. Thus a quantum
computer can be made to simulate a reversible classical computer by
allowing only computational-basis states as input, and using only unitary gates that take computational-basis states into computational-basis
The Born rule, relating the amplitudes αx in the expansion (1.64)
of a general n-Qbit state | to the probabilities of measuring x,
is often stated in terms of inner products or projection operators.11
The probability of a measurement giving the result x (0 ≤ x < 2n )
p  (x) = | αx |2 = | x||2 .


It can also be usefully expressed in terms of projection operators:
p  (x) = x| |x = x|P |x


p  (x) = |x x| = |Px |,



where P = | | is the projection operator on the state |, and
Px = |x x| is the projection operator on the state |x.

1.9 The generalized Born rule
There is a stronger version of the Born rule, which plays an important
role in quantum computation, even though, surprisingly, it is rarely
explicitly mentioned in most standard quantum-mechanics texts. We
shall call it the generalized Born rule. This stronger form applies when
one measures only a single one of n + 1 Qbits, by sending it through a
standard 1-Qbit measurement gate.
To formulate the generalized Born rule, note that any state of all
n + 1 Qbits can be represented in the form
|n+1 = α0 |0|0 n + α1 |1|1 n ,

|α0 |2 + |α1 |2 = 1, (1.76)

11 The Dirac notation for inner products and projection operators is
described in Appendix A.



Ψ =

a 0 0 Φ0



+ a 1 1 Φ1

p = ax



where |0 n and |1 n are normalized (but not necessarily orthogonal).
This follows directly from the general form,
|n+1 =

2n+1 −1

2n+1 −1

γ (x)|xn+1 ,


|γ (x)|2 = 1.



The states |0 n and |1 n are given by
|0 n = (1/α0 )

2n −1

γ (x)|xn ,

|1 n = (1/α1 )


2n −1

γ (2n + x)|xn ,




2n −1

| γ (x)| ,




2n −1

|γ (2n + x)|2 .



(The α0 and α1 in (1.78) and (1.79) are real numbers, but can be multiplied by arbitrary phase factors if |0 n and |1 n are multiplied by
the inverse phase factors.)
The generalized Born rule asserts that if one measures only the single
Qbit whose state symbol is explicitly separated out from the others in
the (n + 1)-Qbit state (1.76), then the 1-Qbit measurement gate will
indicate x (0 or 1) with probability |αx |2 , after which the (n + 1)-Qbit
state can be taken to be the product state |x|x n . (The rule holds for
the measurement of any single Qbit – there is nothing special about the
Qbit whose state symbol appears on the left in the (n + 1)-Qbit state
symbol.) This action of a 1-Qbit measurement gate on an (n + 1)-Qbit
state is depicted schematically in Figure 1.6.
If the Qbit on which the 1-Qbit gate acts is initially unentangled with
the remaining n Qbits, then the action of the gate on the measured Qbit
is just that specified by the ordinary Born rule, and the unmeasured
Qbits play no role at all, remaining in their original state throughout the
process. This is evident from the above statement of the generalized
Born rule, specialized to the case in which the two states |0 n and
|1 n are identical. It is illustrated in Figure 1.7.
If one applies the generalized Born rule n times to successive
1-Qbit measurements of each of n Qbits, initially in the general
n-Qbit state (1.69), one can show by a straightforward argument, given
in Appendix E, that the final state of the n Qbits is x with probability
|αx |2 , where x is the n-bit integer whose bits are given by the readings


Fig 1.6 The action of a
1-Qbit measurement gate
on a single one of n + 1
Qbits, according to the
generalized Born rule. The
initial state (on the left) is a
general (n + 1)-Qbit state,
expressed in the form
|n+1 = a 0 |0|0 n +
a 1 |1|1 n . Only the single
Qbit on the left of this
expression is subjected to a
measurement gate.



Fig 1.7 A simplification of

Figure 1.6 when
|0  = |1  = |. In this
case the initial state on the
left is just the product state
|n = |ψ| =
a 0 |0 + a 1 |1 |, and
the final state of the
unmeasured Qbits
continues to be |
regardless of the value of x
indicated by the 1-Qbit
measurement gate. The
unmeasured Qbits are
unentangled with the
measured Qbit and
described by the state |
throughout the process.
The 1-Qbit measurement
gate acts on the measured
Qbit exactly as it does in
Figure 1.5 when no other
Qbits are present, and the
generalized Born rule of
Figure 1.6 reduces to the
ordinary Born rule.


y = a 0 +a 1




p = ax



on the n 1-Qbit measurement gates. This is nothing but the ordinary
Born rule, with the n 1-Qbit measurement gates playing the role of
the single n-Qbit measurement gate. There is thus, as remarked upon
above, only a single primitive piece of measurement hardware: the 1Qbit measurement gate. The construction of an n-Qbit measurement
gate out of n 1-Qbit measurement gates is depicted in Figure 1.8.
An even more general version of the Born rule follows from the
generalized Born rule itself. The general state of m + n Qbits can be
written as

|m +n =

αx |xm |x n ,



where x |αx |2 = 1 and the states |x n are normalized, but not necessarily orthogonal. By applying the generalized Born rule m times to
m Qbits in an (m + n)-Qbit state, one establishes the rule that if just
the m Qbits on the left of (1.80) are measured, then with probability
|αx |2 the result will be x, and after the measurement the state of all
m + n Qbits will be the product state
|xm |x n


in which the m measured Qbits are in the state |xm and the n unmeasured ones are in the state |x n .

1.10 Measurement gates and state preparation
In addition to providing an output at the end of a computation, measurement gates also play a crucial role (which is not often emphasized)
at the beginning. Since there is no way to determine the state of a given
collection of Qbits – indeed, in general such a collection might be entangled with other Qbits and therefore not even have a state of its own – how
can one produce a set of Qbits in a definite state for the gates of a quantum computer to transform into another computationally useful state?
The answer is by measurement. If one takes n Qbits off the shelf,
and subjects them to an n-Qbit measurement gate that registers x,
then the Qbits emerging from that gate are assigned the classical-basis
state |xn . If one then applies the 1-Qbit operation X to each Qbit that
registered a 1 in the measurement, doing nothing to the Qbits that







registered 0, the resulting set of Qbits will be described by the state
|0n . It is this state that most quantum-computational algorithms take
as their input. Such a use of a measurement gate to produce a Qbit
described by the state |0 is shown in Figure 1.9.
Measurement gates therefore play two roles in a quantum computation. They get the Qbits ready for the subsequent action of the
computer, and they extract from the Qbits a digital output after the
computer has acted. The initial action of the measurement gates is
called state preparation, since the Qbits emerging from the process can
be characterized by a definite state. The association of unitary operators with the gates that subsequently act on the Qbits permits one
to update that initial state assignment into the corresponding unitary
transformation of the initial state, thereby making it possible to calculate, using the Born rule, the probabilities of the outcomes of the final
measurement gates.
This role of measurement gates in state preparation follows from
the Born rule if the Qbits that are to be prepared already have a state of
their own, even though that state might not be known to the user of the
quantum computer. It also follows from the generalized Born rule if the
Qbits already share an entangled state – again, not necessarily known to
the user – with additional (unmeasured) Qbits. But one cannot deduce
from the Born rules that measurement gates serve to prepare states
for Qbits “off the shelf,” whose past history nobody knows anything
about. In such cases the use of measurement gates to assign a state to
the Qbits is a reasonable and plausible extension of the Born rules. It
is consistent with them, but goes beyond them.
For particular physical realizations of Qbits, there may be other ways
to produce the standard initial state |0n . Suppose, for example, that
each Qbit is an atom, the state |0 is the lowest-energy state (the ground
state) of the atom, and the state |1 is the atomic state of next-lowest


Fig 1.8 Constructing a
4-Qbit measurement gate
out of four 1-Qbit
measurement gates. The
integer x has the binary
expansion x3 x2 x1 x0 .



Fig 1.9 Using a 1-Qbit

measurement gate to
prepare an off-the-shelf
Qbit so that its associated
state is |0. The input on
the left is a Qbit in an
unknown condition – i.e.
nothing is known of its past
history. After the
measurement gate is
applied, the NOT gate X is
or is not applied,
depending on whether the
measurement gate
indicates 1 or 0. The Qbit
that emerges (on the right)
is described by the state |0.







energy (the first excited state). Then one can produce the state |0n by
cooling n such atoms to an appropriately low temperature (determined
by the energy difference between the two states – the smaller that
energy, the lower the temperature must be).
From the conceptual point of view, state preparation by the use of
measurement gates is the simplest way. An acceptable physical candidate for a Qbit must be a system for which measurement gates are
readily available. Otherwise there would be no way of extracting information from the computation, however well the unitary gates did their
job. So the hardware for state preparation by measurement is already
there. Whether one chooses to use it or other (e.g. cryogenic) methods
to initialize the Qbits to the state |0n is a practical matter that need
not concern us here. It is enough to know that it can always be done
with measurement gates.

1.11 Constructing arbitrary 1- and 2-Qbit states
The art of quantum computation is to construct circuits out of 1and 2-Qbit gates that produce final states capable of revealing useful
information, when measured. The expectation is that 1-Qbit gates
will be comparatively easy to construct. Two-Qbit gates that are not
mere tensor products of 1-Qbit gates are likely to be substantially more
difficult to make. Attention has focused strongly on the cNOT gate,
and gates that can be constructed from it in combination with 1-Qbit
unitaries. All of the circuits we shall be examining can, in fact, be
reduced to combinations of 1-Qbit gates and 2-Qbit cNOT gates. Given
the difficulty in making cNOT gates, it is generally considered desirable
to keep their number as small as possible. As an illustration of such
constructions, we now examine how to assign arbitrary states to one or
two Qbits, starting with the standard 1-Qbit state |0 or the standard
2-Qbit state |00. (Both of these standard states can be produced with
the help of measurement gates, as described in Section 1.10.)
The situation for 1-Qbit states is quite simple. Let |ψ be any 1-Qbit
state, and let |φ be the orthogonal state (unique to within an overall
phase), satisfying φ|ψ = 0. Since |0 and |1 are linearly independent, there is a unique linear transformation taking them into |ψ and
|φ. But, since |ψ and |φ are an orthonormal pair (as are |0 and
|1), this linear transformation is easily verified to preserve the norm


of arbitrary states, so it is a unitary transformation u. Thus, for any |ψ
there is a 1-Qbit unitary gate u that takes |0 into |ψ:
|ψ = u|0.


Things are more complicated for 2-Qbit states. An unentangled 2Qbit state, being the product of two 1-Qbit states, can be constructed
out of |00 by the application of 1-Qbit unitaries to each of the two Qbits.
But a general 2-Qbit state is entangled, and its production requires
a 2-Qbit gate that is not just a tensor product of 1-Qbit unitaries.
Interestingly, a single cNOT gate, combined with 1-Qbit unitaries, is
enough to do the trick.
To see this, note that the general 2-Qbit state,
| = α00 |00 + α01 |01 + α10 |10 + α11 |11,


is of the form
| = |0 ⊗ |ψ + |1 ⊗ |φ,


where |ψ = α00 |0 + α01 |1 and |φ = α10 |0 + α11 |1. Apply u ⊗ 1
to |, where u is a linear transformation, whose action on the computational basis is of the form
u|0 = a|0 + b |1,

u|1 = −b ∗ |0 + a ∗ |1;

|a|2 + |b |2 = 1.
The transformation u is unitary because it preserves the orthogonality
and normalization of the basis |0, |1.
We have
u ⊗ 1 | = a|0 + b |1 ⊗ |ψ + − b ∗ |0 + a ∗ |1 ⊗ |φ

= |0 ⊗ |ψ  + |1 ⊗ |φ ,


|ψ  = a|ψ − b ∗ |φ,

|φ  = b |ψ + a ∗ |φ.


We would like to choose the complex numbers a and b to make |φ 
and |ψ  orthogonal. The inner product φ |ψ  is
φ |ψ  = a 2 φ|ψ − b ∗2 ψ|φ + ab ∗ ψ|ψ − φ|φ .


If φ|ψ = 0, then setting φ |ψ  to 0 gives a quadratic equation for
a/b ∗ , which has two complex solutions. If a in (1.85) is any nonzero
complex number then either solution determines b , which, with a,
gives a 1-Qbit unitary u for which
u ⊗ 1 | = |0 ⊗ |ψ  + |1 ⊗ |φ 


where |ψ  and |φ  are orthogonal. If φ|ψ = 0 then (1.84) is already
of this form with u = 1.




We can pick positive real numbers λ and µ so that |ψ  = |ψ /λ and
|φ  = |φ /µ are unit vectors, making |ψ  and |φ  an orthonormal
pair. They are therefore related to |0 and |1 by a unitary transformation v:
|ψ  = v|0,

|φ  = v|1.


Equation (1.89) then gives12
| = u† ⊗ v λ|0 ⊗ |0 + µ|1 ⊗ |1 .


We can write this as
| = u† ⊗ v C10 λ|0 + µ|1 ⊗ |0.


Since | is a unit vector and unitary transformations preserve unit
vectors, it follows f