NOTICE -- THIS WEB SITE IS UNDER CONSTRUCTION!

To contribute to the qunet wiki book, please email mbyrd at physics dot siu dot edu and ask for an account. ACCESS IS RESTRICTED. This is not wikipedia where anyone can edit pages. However, registering is easy and many people will be eligible.

Right now, there are only a few very active users. Mark Byrd and Kevin Reuter are working diligently to get qunet's basic functions up and running properly as well as uploading notes. These notes are based on a class taught by Mark Byrd in the Spring of 2009.

===Table of Contents===

:   <big>[[Preface]]</big>

#<big>[[Chapter 1]] - Introduction</big>
##[[Chapter_1#Introduction|Introduction]]
##[[Chapter_1#An Introduction to Quantum Computation|An Introduction to Quantum Computation]]
##[[Chapter_1#Bits and qubits: An Introduction|Bits and qubits: An Introduction]]
##[[Chapter_1#Obstacles to Building a Reliable Quantum Computer|Obstacles to Building a Reliable Quantum Computer]]
#<big>[[Chapter 2 - Qubits and Collections of Qubits]]</big>
##[[Chapter 2 - Qubits and Collections of Qubits#Introduction|Introduction]]
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit States|Qubit States]]
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit Gates|Qubit Gates]]
##[[Chapter 2 - Qubits and Collections of Qubits#The Pauli Matrices|The Pauli Matrices]]
##[[Chapter 2 - Qubits and Collections of Qubits#States of Many Qubits|States of Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Quantum Gates for Many Qubits|Quantum Gates for Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Measurement|Measurement]]
#<big>[[Chapter 3 - Physics of Quantum Information]]</big>
##[[Chapter 3 - Physics of Quantum Information#Introduction|Introduction]]
##[[Chapter 3 - Physics of Quantum Information#Schrodinger.27s_Equation|Schrodinger’s Equation]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for Pure States|Density Matrix for Pure States]]
##[[Chapter 3 - Physics of Quantum Information#Measurements Revisited|Measurements Revisited]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for a Mixed State|Density Matrix for a Mixed State]]
##[[Chapter 3 - Physics of Quantum Information#Expectation Values|Expectation Values]]

#<big>[[Chapter 4 - Entanglement]]</big>
##[[Chapter 4 - Entanglement#Introduction|Introduction]]
##[[Chapter 4 - Entanglement#Entangled Pure States|Entangled Pure States]]
##[[Chapter 4 - Entanglement#Entangled Mixed States|Entangled Mixed States]]
##[[Chapter 4 - Entanglement#Extensions and Open Problems|Extensions and Open Problems]]
#<big>[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples]]</big>
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Introduction|Introduction]]
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#No Cloning!|No Cloning!]]
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Uncertainty Principle|Uncertainty Principle]]
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Quantum Dense Coding|Quantum Dense Coding]]
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Teleporting a Quantum State|Teleporting a Quantum State]]
##[[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#QKD: BB84|QKD: BB84]]
#<big>Chapter 6 - Quantum Computation</big>
##Quantum Computation Basics
##Deutsch-Josza Algorithm
##Simon’s Algorithm
##Shor’s Algorithm
##Grover’s Algorithm
#<big>Chapter 7 - Experiments</big>
#<big>[[Chapter 8 - Noise in Quantum Systems]]</big>
##[[Chapter 8 - Noise in Quantum Systems#Introduction|Introduction]]
##[[Chapter 8 - Noise in Quantum Systems#SMR Representation or Operator-Sum Representation|SMR Representation or Operator-Sum Representation]]
##[[Chapter 8 - Noise in Quantum Systems#Physics Behind the Noise and Completely Positive Maps|Physics Behind the Noise and Completely Positive Maps]]
##[[Chapter 8 - Noise in Quantum Systems#Notes|Notes]]
#<big>Chapter 9 - Conclusions</big>
##What have we learned?

===Appendices===

#<big>[[Appendix A - Basic Probability Concepts]]</big>
#<big>[[Appendix B - Complex Numbers]]</big>
#<big>[[Appendix C - Vectors and Linear Algebra]]</big>
##[[Appendix C - Vectors and Linear Algebra#Vectors|Vectors]]
##[[Appendix C - Vectors and Linear Algebra#Linear Algebra: Matrices|Linear Algebra: Matrices]]
##[[Appendix C - Vectors and Linear Algebra#More Dirac Notation|More Dirac Notation]]
##[[Appendix C - Vectors and Linear Algebra#Transformations|Transformations]]
##[[Appendix C - Vectors and Linear Algebra#Eigenvalues and Eigenvectors|Eigenvalues and Eigenvectors]]
##[[Appendix C - Vectors and Linear Algebra#Tensor Products|Tensor Products]]
#<big>[[Appendix D - Group Theory]]</big>
##[[Appendix D - Group Theory#Introduction|Introduction]]
##[[Appendix D - Group Theory#Definitions and Examples|Definitions and Examples]]
##[[Appendix D - Group Theory#Comparing Groups: Homomorphisms and Isomorphisms|Comparing Groups: Homomorphisms and Isomorphisms]]
##[[Appendix D - Group Theory#Infinite Order Groups: Lie Groups|Infinite Order Groups: Lie Groups]]
##[[Appendix D - Group Theory#More Representation Theory|More Representation Theory]]
#<big>[[Appendix E - Density Operator: Extensions]]</big>
##[[Appendix E - Density Operator: Extensions#Introduction|Introduction]]
##[[Appendix E - Density Operator: Extensions#An N-dimensional Generalization of the Polarization Vector|An N-dimensional Generalization of the Polarization Vector]]
##[[Appendix E - Density Operator: Extensions#The Density Matrix for Two Qubits|The Density Matrix for Two Qubits]]
#<big>[[Appendix F - NOTES and CREDITS]]</big>

===Index===

<big>[[Index]]</big>

===Bibliography===

<big>[[Bibliography]]</big>

----

''Much of this material is based upon work supported by the National Science Foundation under Grant No. 0545798. However, any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.''

Index

2010-03-31T22:42:37Z

Kreuter: Changed protection level for "Index" ([edit=autoconfirmed] (indefinite) [move=autoconfirmed] (indefinite))

<div style="float: left; width: 33%">

;<div id="A"><big>A</big></div>
:average - [[Appendix A - Basic Probability Concepts|Appendix A]]

;<div id="B"><big>B</big></div>
:basis vectors real - [[Appendix C - Vectors and Linear Algebra#Real Vectors|Appendix C]]
:bit - [[Chapter 1#Bits and qubits: An Introduction|Chapter 1]]
:bit-flip operation - [[Chapter 2 - Qubits and Collections of Qubits#Examples of Important Qubit Gates|'''2.3.2''']]
:Bloch Sphere [[Chapter 3 - Physics of Quantum Information#Two-State Example: Bloch Sphere|3.5.4]]
:bra
:bracket

;<div id="C"><big>C</big></div>
:closed-system evolution [[Chapter 1#Obstacles to Building a Reliable Quantum Computer|1.4]]
:CNOT gate(see controlled NOT)
:commutator [[Chapter 2 - Qubits and Collections of Qubits#Examples of Important Qubit Gates|'''2.3.2''']],
:complex conjugate [[Appendix B]]
::of a matrix [[Appendix C - Vectors and Linear Algebra#Complex Conjugate|C.3.1]]
:complex number [[Appendix B]]
:computational basis
:controlled NOT [[Chapter 2 - Qubits and Collections of Qubits#Controlled Operations|'''2.6.1''']], [[Chapter 2 - Qubits and Collections of Qubits#Many-qubit Circuits|2.6.2]], [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Quantum Dense Coding|5.4]], [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Teleporting a Quantum State|5.5]]
:controlled phase gate
:controlled unitary operation[[Chapter 2 - Qubits and Collections of Qubits#Controlled Operations|'''2.6.1''']]

;<div id="D"><big>D</big></div>
:decoherence
:degenerate
:delta
::Kronecker
:dense coding [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Quantum Dense Coding|5.4]]
:density matrix [[Chapter 3 - Physics of Quantum Information#Density Matrix for Pure States|3.3]],[[Chapter 3 - Physics of Quantum Information#Density Matrix for Mixed States|3.5]]
::for two qubits [[Chapter 3 - Physics of Quantum Information#Density Matrix for a Mixed State: Two States|3.5.2]], [[Chapter 3 - Physics of Quantum Information#Density Matrix for the Description of Open Quantum Systems: An Example|3.5.3]], [[Chapter 3 - Physics of Quantum Information#Two-State Example: Bloch Sphere|3.5.4]]
::mixed state [[Chapter 3 - Physics of Quantum Information#Density Matrix for Mixed States|3.5]]
::pure state [[Chapter 3 - Physics of Quantum Information#Density Matrix for Pure States|3.3]]
:density operator
:determinant [[Appendix C - Vectors and Linear Algebra#The Determinant|'''C.3.6''']]
:DiVencenzo's requirements [[Chapter 2 - Qubits and Collections of Qubits#Introduction|2.1]]
:dot product

;<div id="E"><big>E</big></div>
:eigenvalue decomposition
:eigenvalues [[Appendix C - Vectors and Linear Algebra#Eigenvalues and Eigenvectors|'''C.6''']]
:eigenvectors [[Appendix C - Vectors and Linear Algebra#Eigenvalues and Eigenvectors|'''C.6''']]
:entangled states (see entanglement)
:entanglement [[Chapter 4 - Entanglement|4]], [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Quantum Dense Coding|5.4]], [[Chapter 1#How do quantum computers provide an advantage?|1.2.5]]
::pure state [[Chapter 4 - Entanglement#Entangled Pure States|4.2]]
::mixed state [[Chapter 4 - Entanglement#Entangled Mixed States|4.3]]
:expectation value

;<big>F</big>

;<div id="G"><big>G</big></div>
:group [[Appendix D - Group Theory#Definitions and Examples|'''D.2''']]

;<div id="H"><big>H</big></div>
:Hadamard gate [[Chapter 2 - Qubits and Collections of Qubits#eq2.16|(2.16)]]
:Hamiltonian [[Chapter 3 - Physics of Quantum Information#Schrodinger's Equation|3.2]]
:Hermitian matrix
:Hilbert-Schmidt inner product

</div><div style="float: left; width: 33%">

;<div id="I"><big>I</big></div>
:inner product
::for real vectors [[Appendix C - Vectors and Linear Algebra#Real Vectors|C.2.1]]
::for complex vectors [[Appendix C - Vectors and Linear Algebra#More Dirac Notation|C.4]]
:inverse of a matrix [[Appendix C - Vectors and Linear Algebra#The Inverse of a Matrix|'''C.3.7''']]

;<div id="K"><big>K</big></div>
:ket [[Appendix C - Vectors and Linear Algebra#Complex Vectors|C.2.2]]
:Kraus operators
:Kronecker delta [[Appendix C - Vectors and Linear Algebra#More Dirac Notation|'''C.4''']]
:Kronecker product

;<div id="L"><big>L</big></div>
:local operations
:local unitarty transformations

;<div id="M"><big>M</big></div>
:matrix exponentiation [[Chapter 3 - Physics of Quantum Information#expmatrix|3.2]]
:maximally entangled states
:maximally mixed state
::two qubits
:mean
:median
:mixed state density matrix
:modulus squared

;<div id="O"><big>O</big></div>
:open quantum systems
:open-system evolution [[Chapter 1#Obstacles to Building a Reliable Quantum Computer|1.4]]
:operator-sum decomposition
:orthogonal
::vectors

;<div id="P"><big>P</big></div>
:partial trace
::of a Bell state
:Pauli matrices [[Chapter 2 - Qubits and Collections of Qubits#The Pauli Matrices|2.4]], [[Chapter 3 - Physics of Quantum Information#Measurements Revisited|3.4]], [[Chapter 3 - Physics of Quantum Information#Two-State Example: Bloch Sphere|3.5.4]]
:phase gate
:phase-flip
:Planck's constant
:projection operator
:pure state

;<div id="Q"><big>Q</big></div>
:Qbit (see qubit)
:quantum bit [[Chapter 1#Bits and qubits: An Introduction|1.3]]
:quantum dense coding (see [[#D|dense coding]])
:quantum gates
:qubit

</div><div style="float: left; width: 33%">
;<div id="R"><big>R</big></div>
:reduced density operator
::of a Bell state
:reduced density matrix
::see reduced density operator
:reduced density operator
:requirements for scalable quantum computing [[Chapter 2 - Qubits and Collections of Qubits#Introduction|2.1]]

;<div id="S"><big>S</big></div>
:scalability
:Schrodinger Equation
::for density matrix
:separable state
::simply separable
:similar matrices
:similarity transformation
:singular values
:special unitary matrix
:spectrum
:standard deviation
:SU

;<div id="T"><big>T</big></div>
:teleportation [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Teleporting a Quantum State|5.5]]
:tensor product [[Appendix C - Vectors and Linear Algebra#Tensor Products|'''C.7''']]
:trace [[Appendix C - Vectors and Linear Algebra#The Trace|'''C.3.5''']]
::partial(see partial trace)
:transpose [[Appendix C - Vectors and Linear Algebra#Transpose|'''C.3.2''']]

;<div id="U"><big>U</big></div>
:uncertainty principle [[Chapter 5 - Quantum Information: Basic Principles and Simple Examples#Uncertainty Principle|'''5.3''']]
:unitary matrix
:universal set of gates [[Chapter 2 - Qubits and Collections of Qubits#Quantum Gates for Many Qubits|2.6]]
:universality [[Chapter 2 - Qubits and Collections of Qubits#Quantum Gates for Many Qubits|2.6]]

;<div id="V"><big>V</big></div>
:variance

;<div id="X"><big>X</big></div>
:x-gate

;<div id="Y"><big>Y</big></div>
:y-gate

;<div id="Z"><big>Z</big></div>
:z-gate

</div>

2010-02-26T03:25:49Z

Kreuter: Protected "Index" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

Index

2010-02-26T03:22:49Z

Kreuter:

2010-02-25T04:28:27Z

Kreuter:

[[Quantum_Computation_and_Quantum_Error_Prevention|Main Page]]
===Introduction===

''In science one tries to tell people, in such a way as to be understood by everyone, something that no one ever knew before. But in poetry, it's the exact opposite.''

-Paul Dirac

===An Introduction to Quantum Computation===

This introductory chapter is a survey of, and introduction to, topics in quantum information
processing. All of these topics (and more) will be revisited in later sections. Therefore,
it is not necessary, nor expected, that these topics will be completely explained in this
introductory material.

====Quantum Computing====

A quantum computer would be a computer that take advantage of quantum mechanical
principles according to which physical systems behave. We often think of quantum mechanics
as being the set of mechanical laws or principles that very small particles obey. While this
is not entirely true, it is a somewhat reasonable way of explaining things to the layman. For our
purposes, we should note that everything obeys the laws of quantum mechanics and that
Newtonian mechanics are rules that we use to approximate quantum mechanics. However,
quantum mechanical control and natural quantum mechanical evolution are what we are
talking about when we talk about quantum systems. We must have quantum mechanical
evolution, which cannot be reasonably approximated with classical mechanics, and use it in a
particular way to really perform a quantum computation or to really do quantum information
processing.

So what is quantum mechanics? We should think of it as a set of rules, in some ways
similar to Newton’s laws, which describe the way the world works. These are the rules
to which we must carefully attend in order to build what we will describe as a quantum
computing device. We will return to this topic briefly again later. However, as is done in
many places, this question is never quite answered directly. Most often we simply learn the
rules and how use them. The question itself is perhaps a little vague because there are many
physical systems that don’t quite fit into an either/or categorization of quantum vs. classical.
Also, it should noted that throughout these notes the terms will be somewhat misused in
the sense that certain systems will be called quantum mechanical or classical, and from now
on, with few exceptions, no care will be taken to discuss subtleties.

We have not yet built a quantum computing device. However, there are many reasons
to study quantum information processing other than building a fully functional quantum
computer. One main reason we haven’t built one is that we have to figure out how. The
experiments to perform quantum computation in physical devices take an enormous amount
of effort due to noises which corrupt the information. We are going to need to fix the
corrupted information, avoid the noises, or do away with them by some other means. A
second reason to study quantum computing, and quantum information processing more
generally, is that there are really many quantum information processing tasks, or tasks
which can be thought of in this way, which concern quantum control. Precise control of
a quantum system is important for a variety of reasons, not the least of which is that our
world is quantum mechanical! When we get right down to the very basic elements of the
universe, they behave quantum mechanically. If there is one thing that the study of quantum
information processing has already taught us, its that we need to pay attention to quantum
mechanics because it can be very useful to be able to manipulate quantum systems and take
advantage of uniquely quantum properties. Quantum technologies are going to be extremely
important in the future, even if we never built a quantum computer. (Oh, but we will!) As
Feynman said, “There is plenty of room at the bottom.” We have a lot to discover about
the world of the small.

Since noise has been, and is still, such a problem for quantum information, we need to
deal with it. I started learning about these things in 2000, and I would attribute most of
what I know about the subject to Daniel Lidar, whether it be direct or indirect. He was one
of the first people to realize the importance of attacking the problem whole-heartedly. People
recognized the problem, and Shor, et al. really made remarkable statements with their work
on quantum error correcting codes. This work showed that errors could, in principle, be
corrected, leading the way for future research since it was now plausible that a quantum
computer could be built – there are no fundamental obstacles. However, quantum error
correcting codes are, in some sense, a software solution to a hardware problem. More physical
treatments include decoherence-free subspaces, (and noiseless subsystems) and dynamical
decoupling. However, an all-out attack will include other methods of error prevention. Error
prevention methods, as I call all of these along with combinations, are the subject of the last
part of this course/book for that reason.

====Motivation====
Why do we want to build a quantum computing device?

#To make computers faster and more compact, we have been making them smaller.(This has obeyed Moore’s law. (ref.)) However, there is a limit to how much smaller we can make them, and still have them function as they do now. This is due to quantum mechanics. The limit to small is quantum mechanics – quantum mechanics starts to become the dominate mechanism by which constituents interact. So, to make things smaller, we need to use quantum mechanics! More than this though, the fact that Moore’s law cannot continue indefinitely means that we will need to look elsewhere for advances in computing power. One way to increase computing power is to parallelize computations. However, there are processes which cannot be parallelized. So where do we turn? A quantum computer would help with this.
#We now know of several different quantum algorithms which are faster than any known classical algorithm for performing the same task. Some are actually provably faster. These are listed and discussed futher in the next section.
#Quantum information can be used in a variety of ways beyond computing. Such as quantum cryptography, quantum games, and quantum communication of all sorts. (Use Carl’s notes here and cite them (ref.))

An important point to take away from this section is that information is stored and
manipulated by physical devices. They way in which they behave is important for the tasks
that are to be performed.

====Specific Uses====
There are three advantages of quantum computing devices which are often quoted.

#Factor large integers efficiently (known as Shor’s algorithm)
#Find an object in an unsorted database more efficiently than a classical machine (known as Govers algorithm, e.g. phone number lookup)
#Simulate quantum mechanical systems more efficiently than any classical system (due to Feynman and others)

====COMMENTS====
Shor’s algorithm would render RSA encryption useless. It is more efficient than any
known classical algorithm. (There is a quantum answer to this problem however-quantum
cryptography through QKD.)

Gover’s algorithm is better than any classical algorithm – phone book example: classical
algorithm grows as N/2 and Grover’s grows as sqrt N

Simulating quantum mechanical systems is quite difficult classically. For physical scientists
this could be the most important application of quantum computers. This could enable
the simulation of nuclear systems, solid-state devices, biological molecules and molecular
interactions, etc.

====How do quantum computers provide an advantage?====
Now, the claim is that quantum computers could solve some problems more efficiently than
classical ones. So viewing our information systems as quantum systems, we may note that
quantum mechanics is more than a description of the physical world (which is how physicists
treated it for years) but a set of rules governing the behaviour of information when stored
and manipulated quantum mechanically.

So the natural question is, “How does it do this?” We may also ask, “Where is the
advantage?” In other words, “What exactly about quantum mechanics enables us to achieve
speed-ups and other information processing tasks more efficiently than classical systems?”
Most people, as of the time of this writing, would likely say they don’t know. For example,
it is not known if there is a classical algorithm which could factor efficiently. (By efficiently
here, let us just say that we mean “as well as a quantum one.” We'll be more specific later.
) So what I will discuss is
what I would call intuitive arguments for why be believe a quantum computer can accomplish
things a classical one cannot. We should not claim this is proof of anything at this point.

The first argument is that when a machine has different rules for operating, we expect
it to do different things. The rules by which classical computing machines function are, in
some sense, different from the ones governing the behaviour of quantum machines. This is
quite vague, especially given the earlier comments about how everything really is quantum
mechanical. The way I think about it (you’re welcome to argue) is that a “classical object”
transforms according to a “classical equation of motion” ∗ and the result is determined by
its initial state, which is “classical.” A quantum mechanical state transforms according to a
“quantum equation of motion” and the result of the evolution is determined by some initial
conditions, which describe a “quantum system.” Perhaps this sounds like a circular argument,
primarily involving semantics. However, my motivation for this is
a definition I was given in a vector and tensor analysis class: an object is a tensor if it
transforms like a tensor. So I say, an object is classical if it obeys classical equations. In practice, this is often the way things are done. If the physical system can be approximated using classical mechanics, it is classical.

The next argument is that there are states which are uniquely quantum mechanical.
These are states which would have been mysterious to Newton, and indeed they were mysterious
to Einstein, and furthermore they are still mysterious today! The important point is
that they are not states of classical systems, i.e. they are not states which behave classically.
They are unique to quantum mechanics and are called entangled states. Let us first discuss
bits and qubits. We will then discuss quantum states of many particles which correspond
to entangled states. Finally, we will revisit this notion of intuition behind the quantum
mechanical speed-ups.

===Bits and qubits: An Introduction===
A ''classical bit'' is represented by two different states of a classical system. In classical computers
it is represented by two different values of an electrical potential difference. The two
different states of the system are represented by 0 and 1.

A ''quantum bit'' or ''qubit'' (better, but less used is Qbit, see [11]) is represented by two
states of a quantum mechanical system. The two different states are represented by <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math>. This notation is common and is explained in some detail in Appendix D.
<center>
[[File:Doublewell.jpeg]]

Figure 1.1: This is a double well with a ball in one of the two wells.</center>
<br />
Let us discuss a way in which to think about the differences between classical and quantum
systems. We will consider two wells, or valleys, with a hill in between as in Fig. 1.1.
First we will consider a classical system and we will suppose there are no frictional forces.
If we start the ball rolling where it is in the figure, then it will roll back and forth in Well
0. (Well 0, or “Well zero” is our name for the well on the left-hand side.) It will never leave
Well 0 if we leave it alone. If we wanted it to go into Well 1 (the well on the right-hand side)
we would need to nudge it or push it a little to get it over the hill. Or we could just pick it
up and move it from one well to the other.

Now suppose the system is quantum mechanical.<ref>For those with a little background in physics, these are potential wells. An example is a ball in between two hills for the classical case. For the quantum case, we can think of a quantum particle in a potential well
with this shape and solve Schr¨odinger’s equation.</ref> In this case, if we set up the system
so that the particle initially has some kinetic energy (imagine a moving “quantum ball”),
and let it go, there is some probability, after some amount of time, that the particle will be
found in Well 1. This is true when the energy of the ball was not great enough to travel over
the hill in the classical analogy. The probability if it being found in the other well depends
on several things; the initial energy of the particle, the width of the hill, and the height of
the hill (equivalently the depth(s) of the wells, which could be different). However, it won’t
happen with a classical bit! So this is a difference between the classical and quantum mechanics.<ref> Now, if it is admitted that every particle is described by quantum mechanics, the the classically forbidden zone is forbidden because the probability of finding the ball there is extremely small (essentially zero).</ref> In
quantum mechanics, the particle is in some sense in both wells at the same time. This has
to do with the “wave” nature of quantum mechanics. We then say that the particle is in a
superposition of Well 0 and Well 1 and the same time. Mathematically, we describe these
different physical “states” or conditions of the system in the following way.

{{Equation|<math>\begin{align}\mbox{Particle is in Well } 0&=\left\vert{0}\right\rangle, \\ \mbox{Particle is in Well } 1&=\left\vert{1}\right\rangle\end{align}</math>|1.1}}

In other words, the state of the system is “the particle is in Well 0” is written mathematically as <math>\left\vert{0}\right\rangle</math>, and simiarly for <math>\left\vert{1}\right\rangle\,\!</math>. If the particle is in a superposition of the two, which will mean some probability for finding in each well, we would write this as

{{Equation|<math>\left\vert{\psi}\right\rangle=\alpha\left\vert{0}\right\rangle+\beta\left\vert{1}\right\rangle\,\!</math>|1.2}}

where <math>\alpha\,\!</math> and <math>\beta\,\!</math> are complex numbers (see Appendix D) and the probability of the particle
being found in Well 0 is <math>|\alpha|^2\,\!</math> and the probability of it being found in Well 1 is <math>|\beta|^2\,\!</math>.

Now, some (physicists no less) have asked how to make a deterministic transformation
in a quantum system. After all, this seems to be probablistic. The way to do that is the
following. We make the hill very wide and tall and we put the particle right down in the
bottom of one well and give it as little initial energy as possible. Then if we want it moved
to the other well, we pick it up and move it<ref>Again a note for physicists. If we cool it to its ground state and make sure we don’t have stray kicks that will knock it out, we achieve this. Then we put the right amount of energy to get it to transition to the first excited state.</ref>.

If we measure the system, i.e. look to see if it is Well 0 or Well 1, we will “project it into
one state or the other.” In other words, suppose the system is in the state |ψi above. If we
look to see where the particle is and find it in Well 1, then the probability is clearly zero
that it is in the other one. This is called the projection postulate in quantum mechanics and
we will see how to represent this mathematically later.

Throughout the notes, when trying to think about a physical qubit, this simple picture
is often good enough. Therefore, we will refer back to it from time to time.

NOTE: Don’t forget to add the “intuition” part.

===Obstacles to Building a Reliable Quantum Computer===

Noise is the greatest obstacle to building a quantum computer. This was also the case with
early electronic classical computing devices. In this case there is an intuitive explanation ...

For our purposes, we will need to discuss ''open-system evolution'' and ''closed-system evolution''. A closed system is one which does not have any interaction with external objects. We may also refer to such a system as isolated. For example, one knows that if a jar has a very good lid on it, no liquid can leak out, or into, the jar. So if we put a certain amount of liquid in it now, we can expect it will all be there later. This is a closed system and the liquid is isolated from masses external to the jar. In other words, no other mass can get in or out.

A better example is what we call thermally isolated, meaning no heat energy is exchanged
with any other system, so this is a thermally closed system. An open system is one which
can interact with its environment in some way. In these examples, a lid that is not sealed
can allow liquid vapors to escape and one that is not thermally isolated, or thermally closed
can heat up or cool down.

For the quantum information processing tasks we have in mind, we will consider quantum
information which is isolated form its environment and what we usually mean is that the
quantum system is isolated and cannot be affected by an outside source.
It is important to note that isolated, or closed systems, are ideal. They may often be
good approximations to a system, but are basically never really completely isolated or closed.

One may consider larger and larger systems to try to obtain a closed system, but this is most
often impractical, although it can be useful for modeling.

==Footnotes==
<references />

MediaWiki:Sidebar

2010-02-25T04:27:12Z

Kreuter:

MediaWiki:Sidebar

2010-02-25T04:26:52Z

Kreuter:

Quantum Computation and Quantum Error Prevention

2010-02-24T05:54:17Z

Kreuter: /* Table of Contents */

Just to remind everyone -- THIS IS UNDER CONSTRUCTION!

=Table of Contents=

#<big>[[Chapter 1]] - Introduction</big>
##[[Chapter_1#An Introduction to Quantum Computation|An Introduction to Quantum Computation]]
##[[Chapter_1#Bits and qubits: An Introduction|Bits and qubits: An Introduction]]
##[[Chapter_1#Obstacles to Building a Reliable Quantum Computer|Obstacles to Building a Reliable Quantum Computer]]
#<big>[[Chapter 2 - Qubits and Collections of Qubits]]</big>
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit States|Qubit States]]
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit Gates|Qubit Gates]]
##[[Chapter 2 - Qubits and Collections of Qubits#The Pauli Matrices|The Pauli Matrices]]
##[[Chapter 2 - Qubits and Collections of Qubits#States of Many Qubits|States of Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Quantum Gates for Many Qubits|Quantum Gates for Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Measurement|Measurement]]
#<big>[[Chapter 3 - Physics of Quantum Information]]</big>
##[[Chapter 3 - Physics of Quantum Information#Schrodinger’s Equation|Schrodinger’s Equation]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for Pure States|Density Matrix for Pure States]]
##[[Chapter 3 - Physics of Quantum Information#Measurements Revisited|Measurements Revisited]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for a Mixed State|Density Matrix for a Mixed State]]
##[[Chapter 3 - Physics of Quantum Information#Expectation Values|Expectation Values]]
##[[Chapter 3 - Physics of Quantum Information#Types of Two-state Systems|Types of Two-state Systems]]
##[[Chapter 3 - Physics of Quantum Information#Entangled States|Entangled States]]
##[[Chapter 3 - Physics of Quantum Information#Entanglement: Extentions and Open Problems|Entanglement: Extentions and Open Problems]]
#<big>[[Chapter 4 - Quantum Information: Basic Principles and Simple Examples]]</big>
##Uncertainty Principle
##Quantum Dense Coding
##Teleporting a Quantum State
##No Cloning!
##QKD: BB84
#<big>Chapter 5 - Quantum Computation</big>
##Quantum Computation Basics
##Deutsch-Josza Algorithm
##Simon’s Algorithm
##Shor’s Algorithm
##Grover’s Algorithm
#<big>Chapter 6 - Experiments</big>
#<big>Chapter 7 - Noise in Quantum Systems</big>
##Operator-Sum Decomposition
##Sudarshan Representation
##Superoperators: (more or less) Standard representation
##Notes
#<big>Chapter 8 - Conclusions</big>
##What have we learned?

#<big>[[Appendix A - Basic Probability Concepts]]</big>
#<big>[[Appendix B - Complex Numbers]]</big>
#<big>[[Appendix C - Vectors and Linear Algebra]]</big>
##[[Appendix C - Vectors and Linear Algebra#Vectors|Vectors]]
##[[Appendix C - Vectors and Linear Algebra#Linear Algebra: Matrices|Linear Algebra: Matrices]]
##[[Appendix C - Vectors and Linear Algebra#More Dirac Notation|More Dirac Notation]]
##[[Appendix C - Vectors and Linear Algebra#Transformations|Transformations]]
##[[Appendix C - Vectors and Linear Algebra#Eigenvalues and Eigenvectors|Eigenvalues and Eigenvectors]]
##[[Appendix C - Vectors and Linear Algebra#Tensor Products|Tensor Products]]
#<big>[[Appendix D - Group Theory]]</big>
##Definitions and Examples
##Properties of Groups with Finite Order
##Infinite Order Groups: Lie Groups
#<big>[[Appendix E - Density Operator: Extensions]]</big>
##The Coherence Vector/Polarization Vector
##The Polarization Vector: Other Conventions
##The Density Matrix for Two Qubits
#<big>[[Appendix F - NOTES and CREDITS]]</big>

==Preface==
These are notes to accompany the course on quantum computing taught at Southern Illinois
University. Until otherwise noted these notes are a work in progress. Therefore, if there are
any suggestions, questions, comments, errors, etc. please let me know so that appropriate
modifications can be made.

There are several good books on quantum computing. This is not an attempt to displace
them or replace them. The concentration on error prevention and noise is likely different
than what has been done before and the desire is to have them rather self-contained so that
few, if any, other resources are absolutely required. However, it is strongly recommended
that other resources are consulted along with these notes since they are unlikely to be a
complete resource any time soon. Furthermore, the are not likely to be a better resource for
many topics which are better and more thoroughly treated elsewhere.

The objective to provide course material which will be introductory enough to enable an
undergraduate science major with some background in linear algebra to follow the course.
This includes physics, mathematics, computer science, and engineering majors. A good place
to start is N. David Mermin’s book [11].

N. David Mermin’s book [11], David J. Giffiths’s book [8], and (of course) Michael Nielsen
and Isaac Chuang’s book [13] have all greatly influenced these notes. They have influenced
many parts even if they are not explicitly cited. In the case of Griffiths’s book, I taught an
undergraduate quantum mechanics course the semester before I taught this course. Therefore
many of the examples, pedagogy, and exposition were influenced by his book, which I very
much appreciate.

Quantum Computation and Quantum Error Prevention

2010-02-24T05:53:28Z

Kreuter: /* Table of Contents */

Just to remind everyone -- THIS IS UNDER CONSTRUCTION!

=Table of Contents=

#<big>[[Chapter 1]] - Introduction</big>
##[[Chapter_1#An Introduction to Quantum Computation|An Introduction to Quantum Computation]]
##[[Chapter_1#Bits and qubits: An Introduction|Bits and qubits: An Introduction]]
##[[Chapter_1#Obstacles to Building a Reliable Quantum Computer|Obstacles to Building a Reliable Quantum Computer]]
#<big>[[Chapter 2 - Qubits and Collections of Qubits]]</big>
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit States|Qubit States]]
##[[Chapter 2 - Qubits and Collections of Qubits#Qubit Gates|Qubit Gates]]
##[[Chapter 2 - Qubits and Collections of Qubits#The Pauli Matrices|The Pauli Matrices]]
##[[Chapter 2 - Qubits and Collections of Qubits#States of Many Qubits|States of Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Quantum Gates for Many Qubits|Quantum Gates for Many Qubits]]
##[[Chapter 2 - Qubits and Collections of Qubits#Measurement|Measurement]]
#<big>[[Chapter 3 - Physics of Quantum Information]]</big>
##[[Chapter 3 - Physics of Quantum Information#Schrodinger’s Equation|Schrodinger’s Equation]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for Pure States|Density Matrix for Pure States]]
##[[Chapter 3 - Physics of Quantum Information#Measurements Revisited|Measurements Revisited]]
##[[Chapter 3 - Physics of Quantum Information#Density Matrix for a Mixed State|Density Matrix for a Mixed State]]
##[[Chapter 3 - Physics of Quantum Information#Expectation Values|Expectation Values]]
##[[Chapter 3 - Physics of Quantum Information#Types of Two-state Systems|Types of Two-state Systems]]
##[[Chapter 3 - Physics of Quantum Information#Entangled States|Entangled States]]
##Entanglement: Extentions and Open Problems
#<big>[[Chapter 4 - Quantum Information: Basic Principles and Simple Examples]]</big>
##Uncertainty Principle
##Quantum Dense Coding
##Teleporting a Quantum State
##No Cloning!
##QKD: BB84
#<big>Chapter 5 - Quantum Computation</big>
##Quantum Computation Basics
##Deutsch-Josza Algorithm
##Simon’s Algorithm
##Shor’s Algorithm
##Grover’s Algorithm
#<big>Chapter 6 - Experiments</big>
#<big>Chapter 7 - Noise in Quantum Systems</big>
##Operator-Sum Decomposition
##Sudarshan Representation
##Superoperators: (more or less) Standard representation
##Notes
#<big>Chapter 8 - Conclusions</big>
##What have we learned?

#<big>[[Appendix A - Basic Probability Concepts]]</big>
#<big>[[Appendix B - Complex Numbers]]</big>
#<big>[[Appendix C - Vectors and Linear Algebra]]</big>
##[[Appendix C - Vectors and Linear Algebra#Vectors|Vectors]]
##[[Appendix C - Vectors and Linear Algebra#Linear Algebra: Matrices|Linear Algebra: Matrices]]
##[[Appendix C - Vectors and Linear Algebra#More Dirac Notation|More Dirac Notation]]
##[[Appendix C - Vectors and Linear Algebra#Transformations|Transformations]]
##[[Appendix C - Vectors and Linear Algebra#Eigenvalues and Eigenvectors|Eigenvalues and Eigenvectors]]
##[[Appendix C - Vectors and Linear Algebra#Tensor Products|Tensor Products]]
#<big>[[Appendix D - Group Theory]]</big>
##Definitions and Examples
##Properties of Groups with Finite Order
##Infinite Order Groups: Lie Groups
#<big>[[Appendix E - Density Operator: Extensions]]</big>
##The Coherence Vector/Polarization Vector
##The Polarization Vector: Other Conventions
##The Density Matrix for Two Qubits
#<big>[[Appendix F - NOTES and CREDITS]]</big>

==Preface==
These are notes to accompany the course on quantum computing taught at Southern Illinois
University. Until otherwise noted these notes are a work in progress. Therefore, if there are
any suggestions, questions, comments, errors, etc. please let me know so that appropriate
modifications can be made.

There are several good books on quantum computing. This is not an attempt to displace
them or replace them. The concentration on error prevention and noise is likely different
than what has been done before and the desire is to have them rather self-contained so that
few, if any, other resources are absolutely required. However, it is strongly recommended
that other resources are consulted along with these notes since they are unlikely to be a
complete resource any time soon. Furthermore, the are not likely to be a better resource for
many topics which are better and more thoroughly treated elsewhere.

The objective to provide course material which will be introductory enough to enable an
undergraduate science major with some background in linear algebra to follow the course.
This includes physics, mathematics, computer science, and engineering majors. A good place
to start is N. David Mermin’s book [11].

N. David Mermin’s book [11], David J. Giffiths’s book [8], and (of course) Michael Nielsen
and Isaac Chuang’s book [13] have all greatly influenced these notes. They have influenced
many parts even if they are not explicitly cited. In the case of Griffiths’s book, I taught an
undergraduate quantum mechanics course the semester before I taught this course. Therefore
many of the examples, pedagogy, and exposition were influenced by his book, which I very
much appreciate.

Chapter 2 - Qubits and Collections of Qubits

2010-02-24T05:49:50Z

Kreuter: /* Phase in/Phase out */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> |2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> |2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> |2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> |2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Figure 2.7. 

<center>
[[File:measurementcd.jpg‎]]<br />
Figure 2.7: The circuit diagram for a measurement.
</center>

As an example, the measurement result can be used for input for another state. The unitary
in Figure 2.8 is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.

<center>
[[File:measurement.jpg‎]]<br />
Figure 2.8: A circuit which includes a measurement.
</center>



====Projection Operators====

Projection operators are used quite often and the description of
measurement in the previous section is a good example of how they are
used. One may ask, what is a projecter? In ordinary
three-dimensional space, a vector is written as
<math>\vec v=v_x\hat{x}+v_y\hat{y}+v_z\hat{z}\,\!</math> and the <math>x\,\!</math> part of the
vector can be obtained by

{{Equation|<math>\hat{x}(\hat{x}\cdot\vec v) = v_x\hat{x}.\,\!</math>|2.40}}

This is the part of the vector lying along the x axis. Notice that if
the projection is performed again, the same result is obtained

{{Equation|<math>\hat{x}(\hat{x} \cdot v_x\hat{x}) = v_x\hat{x}.\,\!</math>|2.41}}

This is (the) characteristic of projection operations. When one is
performed twice, the second result is the same as the first.

This can be extended to the complex vectors in quantum mechanics. The
outter product <math>\left\vert{x}\right\rangle\!\!\left\langle{x}\right\vert\,\!</math> is a projecter. For example,
<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert\,\!</math> is a projecter and can be written in matrix form as

{{Equation|<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert = \left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right).
\,\!</math>|2.42}}

Acting with this on <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle\,\!</math>
gives

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
\alpha_1
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.43}}

Acting again produces

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.44}}

This is due to the fact that

{{Equation|<math>(\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert)^2 = \left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert.
\,\!</math>|2.45}}

In fact this property essentially defines a project. A projection is
a linear transformation <math>P\,\!</math> such that <math>P^2 = P\,\!</math>. Much of our intuition about geometric projections in
three-dimensions carries to the more abstact cases. One important
example is that the sum over all projections is the identity. The
generalization to arbitrary dimensions, where <math>\left\vert{i}\right\rangle\,\!</math> is any basis
vector in that space, is immediate. In this case the identity,
expressed as a sum over all projectors, is

{{Equation|<math>\sum_{i} \left\vert{i}\right\rangle\!\!\left\langle{i}\right\vert = 1.
\,\!</math>|2.46}}

====Phase in/Phase out====

The probability of finding the system in the state <math>\left\vert{x}\right\rangle\,\!</math>,
where <math>x=0\,\!</math> or <math>1\,\!</math>, is
{{Equation|<math>\begin{align}
\mbox{Prob}_{\left\vert{\psi}\right\rangle}(\left\vert{x}\right\rangle) &=& \left\langle{\psi}\mid{x}\right\rangle\left\langle{x}\mid{\psi}\right\rangle \\
&=& |\left\langle{\psi}\mid{x}\right\rangle|^2.
\end{align}</math>|2.47}}
Note that since <math>\left\vert{\psi}\right\rangle\,\!</math> and <math>\left\langle{\psi}\right\vert\,\!</math> both appear in this
expressioin, if <math>\left\vert{\psi^\prime}\right\rangle = e^{-i\theta}\left\vert{\psi}\right\rangle\,\!</math> were
substituted into the expression for <math>\mbox{Prob}(\left\vert{x}\right\rangle)\,\!</math>, the
expression is unchanged,
{{Equation|<math>\begin{align}
\mbox{Prob}_{\left\vert{\psi^\prime}\right\rangle}(\left\vert{x}\right\rangle)
&=& \left\langle{\psi^\prime}\mid{x}\right\rangle\left\langle{x}\mid{\psi^\prime}\right\rangle \\
&=& e^{-i\theta}\left\langle{\psi}\mid{x}\right\rangle\left\langle{x}\mid{\psi}\right\rangle e^{i\theta} \\
&=& |\left\langle{\psi}\mid{x}\right\rangle|^2.
\end{align}</math>|2.48}}
Therefore when <math>\left\vert{\psi}\right\rangle\,\!</math> changes by a phase, it has no effect on
this probability. This is why it is often said that
{{Equation|<math>\left(\begin{array}{cc}
e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right)
= e^{i\theta}\left(\begin{array}{cc}
1 & 0 \\
0 & e^{-i2\theta} \end{array}\right)
\,\!</math>|2.49}}
is equivalent to
{{Equation|<math>
\left(\begin{array}{cc}
1 & 0 \\
0 & e^{-2i\theta} \end{array}\right).
\,\!</math>|2.50}}

However, as we will see later, there are times when a phase can make a difference. In
those cases it is really a ''relative'' phase between two states that makes the difference.

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-24T05:48:48Z

Kreuter: /* Phase in/Phase out */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> |2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> |2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> |2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> |2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Figure 2.7. 

<center>
[[File:measurementcd.jpg‎]]<br />
Figure 2.7: The circuit diagram for a measurement.
</center>

As an example, the measurement result can be used for input for another state. The unitary
in Figure 2.8 is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.

<center>
[[File:measurement.jpg‎]]<br />
Figure 2.8: A circuit which includes a measurement.
</center>



====Projection Operators====

Projection operators are used quite often and the description of
measurement in the previous section is a good example of how they are
used. One may ask, what is a projecter? In ordinary
three-dimensional space, a vector is written as
<math>\vec v=v_x\hat{x}+v_y\hat{y}+v_z\hat{z}\,\!</math> and the <math>x\,\!</math> part of the
vector can be obtained by

{{Equation|<math>\hat{x}(\hat{x}\cdot\vec v) = v_x\hat{x}.\,\!</math>|2.40}}

This is the part of the vector lying along the x axis. Notice that if
the projection is performed again, the same result is obtained

{{Equation|<math>\hat{x}(\hat{x} \cdot v_x\hat{x}) = v_x\hat{x}.\,\!</math>|2.41}}

This is (the) characteristic of projection operations. When one is
performed twice, the second result is the same as the first.

This can be extended to the complex vectors in quantum mechanics. The
outter product <math>\left\vert{x}\right\rangle\!\!\left\langle{x}\right\vert\,\!</math> is a projecter. For example,
<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert\,\!</math> is a projecter and can be written in matrix form as

{{Equation|<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert = \left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right).
\,\!</math>|2.42}}

Acting with this on <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle\,\!</math>
gives

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
\alpha_1
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.43}}

Acting again produces

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.44}}

This is due to the fact that

{{Equation|<math>(\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert)^2 = \left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert.
\,\!</math>|2.45}}

In fact this property essentially defines a project. A projection is
a linear transformation <math>P\,\!</math> such that <math>P^2 = P\,\!</math>. Much of our intuition about geometric projections in
three-dimensions carries to the more abstact cases. One important
example is that the sum over all projections is the identity. The
generalization to arbitrary dimensions, where <math>\left\vert{i}\right\rangle\,\!</math> is any basis
vector in that space, is immediate. In this case the identity,
expressed as a sum over all projectors, is

{{Equation|<math>\sum_{i} \left\vert{i}\right\rangle\!\!\left\langle{i}\right\vert = 1.
\,\!</math>|2.46}}

====Phase in/Phase out====

The probability of finding the system in the state <math>\left\vert{x}\right\rangle\,\!</math>,
where <math>x=0\,\!</math> or <math>1\,\!</math>, is
{{Equation|<math>\begin{align}
\mbox{Prob}_{\left\vert{\psi}\right\rangle}(\left\vert{x}\right\rangle) &=& \left\langle{\psi}\mid{x}\right\rangle\left\langle{x}\mid{\psi}\right\rangle \\
&=& |\left\langle{\psi}\mid{x}\right\rangle|^2.
\end{align}</math>|2.47}}
Note that since <math>\left\vert{\psi}\right\rangle\,\!</math> and <math>\left\langle{\psi}\right\vert\,\!</math> both appear in this
expressioin, if <math>\left\vert{\psi^\prime}\right\rangle = e^{-i\theta}\left\vert{\psi}\right\rangle\,\!</math> were
substituted into the expression for <math>\mbox{Prob}(\left\vert{x}\right\rangle)\,\!</math>, the
expression is unchanged,
{{Equation|<math>\begin{align}
\mbox{Prob}_{\left\vert{\psi^\prime}\right\rangle}(\left\vert{x}\right\rangle)
&=& \left\langle{\psi^\prime}\mid{x}\right\rangle\left\langle{x}\mid{\psi^\prime}\right\rangle \\
&=& e^{-i\theta}\left\langle{\psi}\mid{x}\right\rangle\left\langle{x}\mid{\psi}\right\rangle e^{i\theta} \\
&=& |\left\langle{\psi}\mid{x}\right\rangle|^2.
\end{align}</math>|2.48}}
Therefore when <math>\left\vert{\psi}\right\rangle\,\!</math> changes by a phase, it has no effect on
this probability. This is why it is often said that
{{Equation|<math>\left(\begin{array}{cc}
e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right)
= e^{i\theta}\left(\begin{array}{cc}
1 & 0 \\
0 & e^{-i2\theta} \end{array}\right)
\,\!</math>|2.49}}
is equivalent to
{{Equation|<math>
\left(\begin{array}{cc}
1 & 0 \\
0 & e^{-2i\theta} \end{array}\right).
\,\!</math>|2.50}}

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T10:14:14Z

Kreuter: /* Projection Operators */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



====Projection Operators====

Projection operators are used quite often and the description of
measurement in the previous section is a good example of how they are
used. One may ask, what is a projecter? In ordinary
three-dimensional space, a vector is written as
<math>\vec v=v_x\hat{x}+v_y\hat{y}+v_z\hat{z}\,\!</math> and the <math>x\,\!</math> part of the
vector can be obtained by

{{Equation|<math>\hat{x}(\hat{x}\cdot\vec v) = v_x\hat{x}.\,\!</math>|2.40}}

This is the part of the vector lying along the x axis. Notice that if
the projection is performed again, the same result is obtained

{{Equation|<math>\hat{x}(\hat{x} \cdot v_x\hat{x}) = v_x\hat{x}.\,\!</math>|2.41}}

This is (the) characteristic of projection operations. When one is
performed twice, the second result is the same as the first.

This can be extended to the complex vectors in quantum mechanics. The
outter product <math>\left\vert{x}\right\rangle\!\!\left\langle{x}\right\vert\,\!</math> is a projecter. For example,
<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert\,\!</math> is a projecter and can be written in matrix form as

{{Equation|<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert = \left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right).
\,\!</math>|2.42}}

Acting with this on <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle\,\!</math>
gives

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
\alpha_1
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.43}}

Acting again produces

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.44}}

This is due to the fact that

{{Equation|<math>(\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert)^2 = \left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert.
\,\!</math>|2.45}}

In fact this property essentially defines a project. A projection is
a linear transformation <math>P\,\!</math> such that <math>P^2 = P\,\!</math>. Much of our intuition about geometric projections in
three-dimensions carries to the more abstact cases. One important
example is that the sum over all projections is the identity. The
generalization to arbitrary dimensions, where <math>\left\vert{i}\right\rangle\,\!</math> is any basis
vector in that space, is immediate. In this case the identity,
expressed as a sum over all projecters, is

{{Equation|<math>\sum_{\mbox{\scriptsize all}\; i} \left\vert{i}\right\rangle\!\!\left\langle{i}\right\vert = 1.
\,\!</math>|2.46}}

====Phase in/Phase out====

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T10:13:19Z

Kreuter: /* Projection Operators */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



====Projection Operators====

Projection operators are used quite often and the description of
measurement in the previous section is a good example of how they are
used. One may ask, what is a projecter? In ordinary
three-dimensional space, a vector is written as
<math>\vec v=v_x\hat{x}+v_y\hat{y}+v_z\hat{z}\,\!</math> and the <math>x\,\!</math> part of the
vector can be obtained by

{{Equation|<math>\hat{x}(\hat{x}\cdot\vec v) = v_x\hat{x}.\,\!</math>|2.40}}

This is the part of the vector lying along the x axis. Notice that if
the projection is performed again, the same result is obtained

{{Equation|<math>\hat{x}(\hat{x} \cdot v_x\hat{x}) = v_x\hat{x}.\,\!</math>|2.41}}

This is (the) characteristic of projection operations. When one is
performed twice, the second result is the same as the first.

This can be extended to the complex vectors in quantum mechanics. The
outter product <math>\left\vert{x}\right\rangle\!\!\left\langle{x}\right\vert\,\!</math> is a projecter. For example,
<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert\,\!</math> is a projecter and can be written in matrix form as

{{Equation|<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert = \left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right).
\,\!</math>|2.42}}

Acting with this on <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle\,\!</math>
gives

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
\alpha_1
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.43}}

Acting again produces

{{Equation|<math>\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>|2.44}}

This is due to the fact that

{{Equation|<math>(\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert)^2 = \left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert.
\,\!</math>|2.45}}

In fact this property essentially defines a project. A projection is
a linear transformation <math>P\,\!</math> such that <math>P^2 = P\,\!</math>. Much of our intuition about geometric projections in
three-dimensions carries to the more abstact cases. One important
example is that the sum over all projections is the identity. The
generalization to arbitrary dimensions, where <math>\left\vert{i}\right\rangle\,\!</math> is any basis
vector in that space, is immediate. In this case the identity,
expressed as a sum over all projecters, is

{{Equation|<math>\sum_{\mbox{\scriptsize all}\; i} \left\vert{i}\right\rangle\!\!\left\langle{i}\right\vert = 1.
\,\!</math>|2.46}}

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T10:07:01Z

Kreuter: /* Projection Operators */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



====Projection Operators====

Projection operators are used quite often and the description of
measurement in the previous section is a good example of how they are
used. One may ask, what is a projecter? In ordinary
three-dimensional space, a vector is written as
<math>\vec v=v_x\hat{x}+v_y\hat{y}+v_z\hat{z}\,\!</math> and the <math>x\,\!</math> part of the
vector can be obtained by

{{Equation|<math>\hat{x}(\hat{x}\cdot\vec v) = v_x\hat{x}.\,\!</math>|2.40}}

This is the part of the vector lying along the x axis. Notice that if
the projection is performed again, the same result is obtained

{{Equation|<math>\hat{x}(\hat{x} \cdot v_x\hat{x}) = v_x\hat{x}.\,\!</math>|2.41}}

This is (the) characteristic of projection operations. When one is
performed twice, the second result is the same as the first.

This can be extended to the complex vectors in quantum mechanics. The
outter product <math>\left\vert{x}\right\rangle\!\!\left\langle{x}\right\vert\,\!</math> is a projecter. For example,
<math>\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert\,\!</math> is a projecter and can be written in matrix form as

<math>
\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert = \left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right).
\,\!</math>

Acting with this on <math>\ket{\psi} = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle\,\!</math>
gives

<math>
\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
\alpha_1
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>

Acting again produces

<math>
\left(\begin{array}{cc}
1 & 0 \\
0 & 0 \end{array}\right)
\left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right)
= \left(\begin{array}{c}
\alpha_0 \\
0
\end{array}\right).
\,\!</math>

This is due to the fact that

<math>
(\left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert)^2 = \left\vert{0}\right\rangle\!\!\left\langle{0}\right\vert.
\,\!</math>

In fact this property essentially defines a project. A projection is
a linear transformation <math>P\,\!<math> such that <math>P^2 = P\,\!<math>. \index{projection
operator} Much of our intuition about geometric projections in
three-dimensions carries to the more abstact cases. One important
example is that the sum over all projections is the identity.
(See also Appendix \ref{app:alg}, Sec.~\ref{sec:MDirac}.) The
generalization to arbitrary dimensions, where <math>\ket{i}\,\!<math> is any basis
vector in that space, is immediate. In this case the identity,
expressed as a sum over all projecters, is

<math>
\sum_{\mbox{\scriptsize all}\; i} \left\vert{i}\right\rangle\!\!\left\langle{i}\right\vert = 1.
\,\!</math>

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T09:52:54Z

Kreuter: /* Standard Prescription */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



====Projection Operators====

==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T09:42:42Z

Kreuter: /* Many-qubit Circuits */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]<br />
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



==Footnotes==
<references />

Chapter 2 - Qubits and Collections of Qubits

2010-02-20T09:42:16Z

Kreuter: /* Many-qubit Circuits */

===Introduction===

There are several parts to any quantum information processing task. Some of these were
written down and discussed by David DiVincenzo in the early days of quantum computing
research and are therefore called DiVincenzo’s requirements for quantum computing. These
include, but are not limited to, the following, which will be discussed in this chapter. Other
requirements will be discussed later.

Five requirements [3]:
#Be a scalable physical system with well-defined qubits
#Be initializable to a simple fiducial state such as <math>\left\vert{000...}\right\rangle</math>
#Have much longer decoherence times than gating times
#Have a universal set of quantum gates
#Permit qubit-specific measurements

The first requirement is a set of two-state quantum systems which can serve as qubits. The
second is to be able to initialize the set of qubits to some reference state. In this chapter,
these will be taken for granted. The third concerns noise and noise has become known by
the term decoherence. The term decoherence has had a more precise definition in the past,
but here it will usually be synonymous with noise. Noise and decoherence will be the topics of
later sections. The fourth and fifth will be discussed in this chapter.

Backwards is it? Not from a computer science perspective or from a motivational perspective.
Besides, to a large extent, the first two rely very heavily on experimental physics
and engineering. These topics are primarily beyond the scope of this introductory material,
but will be treated superficially in Chapter 6.

===Qubit States===

As mentioned in the introduction, a qubit, or quantum bit, is represented by a two-state
quantum system. It is referred to as a two-state quantum system, although there are many
physical examples of qubits which are represented by two different states of a quantum
system which has many available states. These two states are represented by the vectors <math>\left\vert{0}\right\rangle</math>
and <math>\left\vert{1}\right\rangle</math> and qubit could be in the state <math>\left\vert{0}\right\rangle</math>, or the state <math>\left\vert{1}\right\rangle</math>, or a complex superposition of
these two. A qubit state which is an arbitrary superposition is written as

{{Equation | <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle,</math> | 2.1}}

where <math>\alpha_0\,\!</math> and <math>\alpha_1\,\!</math> are complex numbers. Our objective is to use these two states to store and
manipulate information. If the state of the system is confined to one state, the other, or a
superposition of the two, then

{{Equation | <math>|\alpha_0|^2 + |\alpha_1|^2 = 1.\,\!</math> | 2.2}}

Thus this vector is normalized, i.e. it has magnitude, or length one. The set of all such
vectors forms a two-dimensional complex (so four-dimensional real) vector space.<ref name="test">Appendix C.1 contains a basic introduction to complex numbers.</ref> The basis
vectors for such a space are the two vectors <math>\left\vert{0}\right\rangle</math> and <math>\left\vert{1}\right\rangle</math> which are called ''computational basis''
states. These two basis states are represented by

{{Equation | <math>\left\vert{0}\right\rangle = \left(\begin{array}{c} 1 \\ 0\end{array}\right), \;\;\left\vert{1}\right\rangle = \left(\begin{array}{c} 0 \\ 1\end{array}\right).</math> | 2.3}}

Therefore,

{{Equation |<math>\left\vert{\psi}\right\rangle = \left(\begin{array}{c} \alpha_0 \\ \alpha_1\end{array}\right).</math> | 2.4}}

===Qubit Gates===

During a computation, one qubit state will need to be taken to a different one. In fact,
any valid state should be able to be operated upon to obtain any other state. Since this
is a complex vector with magnitude one, the matrix transformation required for closedsystem
evolution is unitary. (See Appendix D, Sec. D.2.) These unitary matrices, or unitary
transformations, as well as their generalization to many qubits, transform a one complex
vector into another and are also called ''quantum gates'', or gating operations. Mathematically,
we may think of them as rotations of the complex vector and in some cases (but not all)
correspond to actual rotations of the physical system.

====Circuit Diagrams for Qubit Gates====

Unitary transformations are represented in a circuit diagram with a box around the untary
transformation. Consider a unitary transformation <math>V</math> on a single qubit state <math>\left\vert{\psi}\right\rangle</math>. If the
result of the transformation is <math>\left\vert{\psi^\prime}\right\rangle</math> then we write

{{Equation|<math>\left\vert{\psi^\prime}\right\rangle = V\left\vert{\psi}\right\rangle.</math>|2.5}}

The corresponding circuit diagram is shown in Fig. 2.1.

Notice that the diagram is read from left to right. This means that if two consecutive
gates are implemented, say <math>V</math> first and then <math>U</math>, the equation reads

{{Equation|<math>\left\vert{\psi^{\prime\prime}}\right\rangle = UV\left\vert{\psi}\right\rangle.</math>|2.6}}
<br />

<center>
{|
|<math>\left\vert{\psi}\right\rangle</math>
|[[File:Vbox1qu.jpg]]
|<math>\left\vert{\psi^\prime}\right\rangle</math>
|}

Figure 2.1: Circuit diagram for a one-qubit gate which implements the unitary transformation
<math>V\,\!</math>. The input state <math>\left\vert{\psi}\right\rangle</math> is on the right and the output, <math>\left\vert{\psi^\prime}\right\rangle</math>, is on the right.</center>

However, the circuit diagram will have the boxes in the reverse order from the equation, i.e.
<math>V</math> on the left and <math>U</math> on the right.

====Examples of Important Qubit Gates====

There are, of course, an infinite number of possible unitary transformations that we could
implement on a single qubit since the set of unitary transformations can be parameterized by
three parameters. However, a single gate will contain a single unitary transformation, which
means that all three parameters a fixed. There are several such transformations which are
used repeatedly. For this reason, they are listed here along with their actions on a generic
state <math>\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle + \alpha_1\left\vert{1}\right\rangle</math>. Note that one could also completely define the transformation by
its action on a complete set of basis states.

The following is called an “x” gate, or a bit-flip,

{{Equation|<math>X = \left(\begin{array}{cc} 0 & 1 \\
1 & 0 \end{array}\right).</math>|2.7}}

Its action on a state <math>\left\vert{\psi}\right\rangle</math> is to exchange the basis states,

{{Equation|<math>X\left\vert{\psi}\right\rangle = \alpha_0\left\vert{1}\right\rangle + \alpha_1\left\vert{0}\right\rangle,</math>|2.8}}

for this reason it is also sometimes called a NOT gate. However, this term will be avoided
because a general NOT gate does not exist for all quantum states. (It does work for all qubit
states, but this is a special case.)

The next gate is called a ''phase gate'' or a “z” gate. It is also sometimes called a ''phase-flip'',
and is given by

{{Equation|<math>Z = \left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right).</math>|2.9}}

The action of this gate is to introduce a sign change on the state <math>\left\vert{1}\right\rangle</math> which can be seen
through

{{Equation|<math>Z\left\vert{\psi}\right\rangle = \alpha_0\left\vert{0}\right\rangle - \alpha_1\left\vert{1}\right\rangle,</math>|2.10}}

The term phase gate is also used for the more general transformation

{{Equation|<math>P = \left(\begin{array}{cc} e^{i\theta} & 0 \\
0 & e^{-i\theta} \end{array}\right).</math>|2.11}}

For this reason, the z-gate will either be called a “z-gate” or a phase-flip gate.

Another gate closely related to these, is the “y” gate. This gate is

{{Equation|<math>Y = \left(\begin{array}{cc} 0 & -i \\
i & 0 \end{array}\right).</math>|2.12}}

The action of this gate on a state is

{{Equation|<math>Y\left\vert{\psi}\right\rangle = -i\alpha_1\left\vert{0}\right\rangle +i \alpha_0\left\vert{1}\right\rangle
= -i(\alpha_1\left\vert{0}\right\rangle - \alpha_0\left\vert{1}\right\rangle)</math>|2.13}}

From this last expression, it is clear that, up to an overall factor of <math>−i</math>, this gate is the same
as acting on a state with both <math>X</math> and <math>Z</math> gates. However, the order matters. Therefore, it
should be noted that

<center><math>XZ = -i Y,\,\!</math></center>

whereas

<center><math>ZX = i Y.\,\!</math></center>

The fact that the order matters should not be a surprise to anyone since matrices in general
do not commute. However, such a condition arises so often in quantum mechanics, that the
difference between these two is given an expression and a name. The difference between the
two is called the ''commutator'' and is denoted with a <math>[\cdot,\cdot]</math>. That is, for any two matrices, <math>A</math>
and <math>B</math>, the commutator is defined to be

{{Equation|<math>[A,B] = AB -BA.\,\!</math>|2.14}}

For the two gates <math>X</math> and <math>Z</math>,

{{Equation|<math>[X,Z] = -2iY.\,\!</math>|2.15}}

A very important gate which is used in many quantum information processing protocols,
including quantum algorithms, is called the Hadamard gate,

{{Equation|<math>H = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} 1 & 1 \\
1 & -1 \end{array}\right).</math>|2.16}}

In this case, its helpful to look at what this gate does to the two basis states:

{{Equation|<math>H \left\vert{0}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle + \left\vert{1}\right\rangle), </math><br /><math>H \left\vert{1}\right\rangle = \frac{1}{\sqrt{2}}(\left\vert{0}\right\rangle - \left\vert{1}\right\rangle).</math>|2.17}}

So the Hadamard gate will take either one of the basis states and produce an equal superposition
of the two basis states. This is the reason it is so-often used in quantum information
processing tasks. On a generic state

{{Equation|<math>H\left\vert{\psi}\right\rangle = [(\alpha_0+\alpha_1)\left\vert{0}\right\rangle + (\alpha_0-\alpha_1)\left\vert{1}\right\rangle].</math>|2.18}}

===The Pauli Matrices===
The three matrices <math>X, Y,</math> and <math> Z </math> are called the Pauli matrices. They are also sometimes
denoted <math>\sigma_x\,\!</math>, <math>\sigma_y\,\!</math> and <math>\sigma_z\,\!</math>, or <math>\sigma_1\,\!</math>, <math>\sigma_2\,\!</math> and <math>\sigma_3\,\!</math> respectively. They are ubiquitous in quantum
computing and quantum information processing. This is because they, along with the <math>2 \times 2\,\!</math>
identity matrix, form a basis for the set of <math>2 \times 2\,\!</math> Hermitian matrices and can be used to
describe all <math>2 \times 2</math> unitary transformations as well. We will return to this latter point in the
next chapter.

To show that they form a basis for <math>2 \times 2</math> Hermitian matrices, note that any such matrix can be written in the form

{{Equation|<math>A = \left(\begin{array}{cc}
a_0+a_3 & a_1+ia_2 \\
a_1-ia_2 & a_0-a_3 \end{array}\right).</math>|2.19}}

Since <math>a_0\,\!</math> and <math>a_3\,\!</math> are arbitrary, <math>a_0 + a_3\,\!</math> and <math>a_0 − a_3\,\!</math> are abitrary too. This matrix can be written as

{{Equation|<math>\begin{align}A &= a_0 \mathbb{I} + a_1X + a_2Y + a_3 Z \\
&= a_0 \mathbb{I} + a_1\sigma_1 + a_2\sigma_2 + a_3 \sigma_3 \\
&= a_0 \mathbb{I} + \vec{a}\cdot\vec{\sigma}, \\
\end{align}
</math>|2.20}}

where <math>\vec{a}\cdot\vec{\sigma} = \sum_{i=1}^3a_i\sigma_i\,\!</math> is the "dot
product" beteen <math>\vec{a}\,\!</math> and <math>\vec{\sigma} = (\sigma_1,\sigma_2,\sigma_3)\,\!</math>.

An important and useful relationship between these is the following (which shows why
the latter notation above is so useful)

{{Equation|<math>\sigma_i\sigma_j = \mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k,</math>|2.21}}

where <math>i, j, k\,\!</math> are numbers from the set <math>\{1, 2, 3\}\,\!</math> and the defintions for <math>\delta_{ij}\,\!</math> and <math>\epsilon_{ijk}\,\!</math> are given
in Eqs. [[Appendix_D#eqd.17|(D.17)]] and [[Appendix_D#eqd.8|(D.8)]] respectively. The three matrices <math>\sigma_1, \sigma_2, \sigma_3\,\!</math> are traceless Hermitian
matrices and they can be seen to be orthogonal using the so-called ''Hilbert-Schmidt inner
product'' which is defined, for matrices<math> A\,\!</math> and <math>B\,\!</math>, as

{{Equation|<math>(A,B) = \mbox{Tr}(A^\dagger B).</math>|2.22}}

The orthogonality for the set is then summarized as

{{Equation|<math>(\sigma_i,\sigma_j) = \mbox{Tr}(\sigma_i\sigma_j) = 2\delta_{ij}.\,\!</math>|2.23}}

This property is contained in Eq. [[#eq2.21|(2.21)]]. This one equation also contains all of the commutators.
By subtracting the equation with the product reversed

{{Equation|<math>[\sigma_i,\sigma_j] = (\mathbb{I}\delta_{ij} +i \epsilon_{ijk}\sigma_k)
-(\mathbb{I}\delta_{ji} +i \epsilon_{jik}\sigma_k),</math>|2.24}}

but <math>\delta_{ij}=\delta_{ji}\,\!</math> and <math>\epsilon_{ijk} = -\epsilon_{jik}\,\!</math>
so

{{Equation|<math>[\sigma_i,\sigma_j] = 2i \epsilon_{ijk}\sigma_k.\,\!</math>|2.25}}

===States of Many Qubits===
Let us now consider the states of several (or many) qubits. For one qubit, there are two
possible basis states, say <math>\left\vert{0}\right\rangle\,\!</math> and <math>\left\vert{1}\right\rangle\,\!</math>. If there are two qubits, each with these basis states,
basis states for the two together are found by using the tensor product. (See Section D.6.)
The set of basis states obtained in this way is

<center>
<math>\left\{\left\vert{0}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{0}\right\rangle\otimes\left\vert{1}\right\rangle, \;
\left\vert{1}\right\rangle\otimes\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle\otimes\left\vert{1}\right\rangle \right\}.\,\!</math>
</center>

This set is more often written as

{{Equation|<math>\left\{\left\vert{00}\right\rangle, \; \left\vert{01}\right\rangle, \;
\left\vert{10}\right\rangle, \; \left\vert{11}\right\rangle \right\},\,\!</math>|2.26}}

which can also be expressed as

{{Equation|<math>\left\{\left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 1 \\ 0 \end{array}\right), \;
\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \end{array}\right)
\right\}.\,\!</math>|2.27}}

The extension to three qubits is straight-forward

{{Equation|<math>\left\{\left\vert{000}\right\rangle, \; \left\vert{001}\right\rangle, \;
\left\vert{010}\right\rangle, \; \left\vert{011}\right\rangle, \; \left\vert{100}\right\rangle, \; \left\vert{101}\right\rangle, \;
\left\vert{110}\right\rangle, \; \left\vert{111}\right\rangle \right\}.\,\!</math>|2.28}}

Those familiar with binary will recognize these as the numbers zero through seven. Thus we
consider this an ''ordered basis'' with the following notation also perfectly acceptable

{{Equation|<math>\left\{\left\vert{0}\right\rangle, \; \left\vert{1}\right\rangle, \;
\left\vert{2}\right\rangle, \; \left\vert{3}\right\rangle, \; \left\vert{4}\right\rangle, \; \left\vert{5}\right\rangle, \;
\left\vert{6}\right\rangle, \; \left\vert{7}\right\rangle \right\}.\,\!</math>|2.29}}

The ordering of the products is important because each spot
corresponds to a physical particle or physical system. When some
confusion may arise, we may also label the ket with a subscript to
denote the particle or position. For example, two different people,
Alice and Bob, can be used to represent distant parties which may
share some information or may wish to communicate. In this case, the
state belonging to Alice may be denoted <math>\left\vert{\psi}\right\rangle_A\,\!</math>. Or if she is
referred to as party 1 or particle 1, <math>\left\vert{\psi}\right\rangle_1\,\!</math>.

The most general 2-qubit state is written as

{{Equation|<math>\left\vert{\psi}\right\rangle = \alpha_{00}\left\vert{00}\right\rangle + \alpha_{01}\left\vert{01}\right\rangle
+ \alpha_{10}\left\vert{10}\right\rangle + \alpha_{11}\left\vert{11}\right\rangle
=\left(\begin{array}{c} \alpha_{00} \\ \alpha_{01} \\
\alpha_{10} \\ \alpha_{11} \end{array}\right).</math>|2.30}}

The normalization condition is
<math>|\alpha_{00}|^2 + |\alpha_{01}|^2
+ |\alpha_{10}|^2 + |\alpha_{11}|^2=1.\,\!</math>
The generalization to an arbitrary number of qubits, say $n$, is also
rather straight-forward and can be written as
<center>
<math>\left\vert{\psi}\right\rangle = \sum_{i=0}^{2^n-1} \alpha_i\left\vert{i}\right\rangle.\,\!</math>
</center>

===Quantum Gates for Many Qubits===

Just as the case for one single qubit, the most general closed-system transformation of a
state of many qubits is a unitary transformation. Being able to make an abitrary unitary
transformation on many qubits is an important task. If an arbitrary unitary transformation
on a set of qubits can be made, then any quantum gate can be implemented. If this ability to
implement any arbitrary quantum gate can be accomplished using a particular set of quantum
gates, that set is said to be a ''universal set of gates'' or that the condition of ''universality'' has
been met by this set. It turns out that there is a theorem which provides one way for
identifying a universal set of gates.

'''Theorem:'''

''The ability to implement an entangling gate between any two qubits, plus the ability to
implement all single-qubit unitary transformations, will enable universal quantum computing.''

It turns out that one doesn’t need to be able to perform an entangling gate between
distant qubits. Nearest-neighbor interactions are sufficient. We can transfer the state of a
qubit to a qubit which is next to the one we would like it to interact with. Then perform
the entangling gate between the two and then transfer back.

This is an important and often used theorem which will be the main focus of the next
few sections. A particular class of two-qubit gates which can be used to entangle qubits will
be discussed along with circuit diagrams for many qubits.

====Controlled Operations====

A controlled operation is one which is conditioned on the state of another part of the system,
usually a qubit. The most cited example is the CNOT gate, which is a NOT operation on
one qubit that is implemented only if another qubit is in the state <math>\left\vert{1}\right\rangle\,\!</math>, in other words a
controlled NOT operation. This gate is used so often that it is discussed here in detail.

Consider the following matrix operation on two qubits

{{Equation|<math>C_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \end{array}\right).</math>|2.31}}

Under this transformation, the following changes occur:

{{Equation|<math>\begin{array}{c|c}
\; \left\vert{\psi}\right\rangle\; & C_{12}\left\vert{\psi}\right\rangle \\ \hline
\left\vert{00}\right\rangle & \left\vert{00}\right\rangle \\
\left\vert{01}\right\rangle & \left\vert{01}\right\rangle \\
\left\vert{10}\right\rangle & \left\vert{11}\right\rangle \\
\left\vert{11}\right\rangle & \left\vert{10}\right\rangle
\end{array}</math>|2.32}}

This transformation is called the CNOT, or controlled NOT, since the second bit is flipped
if the first is in the state <math>\left\vert{1}\right\rangle\,\!</math>, and otherwise left alone. The circuit diagram for this transformation corresponds to the following representation of the gate. Let <math>x\,\!</math> and <math>y\,\!</math> be zero or one.
Then the CNOT is given by

{{Equation|<math>\left\vert{x,y}\right\rangle \overset{CNOT}{\rightarrow} \left\vert{x,x\oplus y}\right\rangle.</math>|2.33}}

In binary, of course <math>0\oplus 0 =0</math>, <math>0\oplus 1 = 1 = 1\oplus 0</math>, and
<math>1\oplus 1 =0</math>. The circuit diagram is given in Fig. 2.2.
The first qubit, <math>\left\vert{x}\right\rangle</math>, at the top of the diagam, is called the
''control bit'' and the second, <math>\left\vert{y}\right\rangle</math>, at the top of the diagam,
is called the ''target bit''.

<center>
{|
|<math>\left\vert{X}\right\rangle\,\!</math>
|-
|[[File:CNOT.jpg]]
|-
|<math>\left\vert{Y}\right\rangle\,\!</math>
|}</center>

<center>Figure 2.2: Circuit diagram for a CNOT gate.</center>

One can immediately generalize the operation of the CNOT to a controlled-U gate. This
is a gate, shown in Fig. 2.3, which implements a unitary transformation <math>U\,\!</math> on the second
qubit, if the state of the first is <math>\left\vert{1}\right\rangle\,\!</math>. The matrix transformation is given by

{{Equation|<math>CU_{12} = \left(\begin{array}{cccc}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & u_{11} & u_{12} \\
0 & 0 & u_{21} & u_{22} \end{array}\right),</math>|2.34}}

where the matrix

<center>
<math>U = \left(\begin{array}{cc}
u_{11} & u_{12} \\
u_{21} & u_{22} \end{array}\right).</math>
</center>

For example the controlled-phase gate is given in Fig. 2.4.

<center>
[[File:CU.jpg]]<br />
Figure 2.3: Circuit diagram for a CU gate.
</center>

====Many-qubit Circuits====

Many qubit circuits are a straight-forward generalization of the single quibit circuit diagrams.
For example, Fig. 2.5 shows the implementation of CNOT<math>_{14}</math> and CNOT<math>_{23}</math> in the
same diagram. The crossing of lines is not confusing since there is a target and control
which are clearly distinguished in each case.

It is quite interesting however, that as the diagrams become more complicated, the possibility
arises that one may change between equivalent forms of a circuit which, in the end,

<center>
[[File:CP.jpg]]<br />
Figure 2.4: Circuit diagram for a Controlled-phase gate.

[[File:Multiqcs.jpg]]<br />
Figure 2.5: Multiple CNOT gates on a set of qubits.
</center>

implements the same multiple-qubit unitary. For example, noting that <math>HZH = X\,\!</math>, the two
circuits in Fig. 2.6 implement the same two-qubit unitary transformation. This enables the
simplication of some quite complicated circuits.

<center>
[[File:Hzhequiv.jpg‎]]
Figure 2.6: Two circuits which are equivalent since they implement the same two-qubit
unitary transformation.
</center>

===Measurement===

Measurement in quantum mechanics is quite different from that of
classical mechanics. In classical mechanics, and therefore for
classical bits in classical computers, one assumes that a measurement
can be made at will without disturbing or changing the state of the
physical system. In quantum mechanics this assumption cannot be
made. This is important for a variety of reasons which will become
clear later.

====Standard Prescription====

In the intoduction a simple example was provided as motivation for
distinguishing quantum states from classical states. This example of
two wells with one particle, can be used (cautiously) here as well.

Consider the quantum state in a superposition of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math>
of the form

{{Equation|<math>\left\vert\psi\right\rangle = \alpha_0\left\vert 0\right\rangle +
\alpha_1\left\vert 1\right\rangle,
\,\!</math>|2.35}}

with <math>|\alpha_0|^2 + |\alpha_1|^2 = 1\,\!</math>. If the state is measured in
the computational basis, the result will be <math>\left\vert 0\right\rangle\,\!</math> with probability
<math>|\alpha_0|^2\,\!</math> and <math>\left\vert 1\right\rangle\,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. Recall
that the particle is in this state and that this state really means
that the particle is not in the state <math>\left\vert 0\right\rangle\,\!</math> or the state
<math>\left\vert 1\right\rangle \,\!</math>, it really means that it is in both at the same time.

This is worth emphasizing since it really ''cannot'' be thought of as
being in state <math>\left\vert 0\right\rangle\,\!</math> with probability <math>|\alpha_0|^2\,\!</math> ''or'' in
<math>\left\vert 1\right\rangle \,\!</math> with probability <math>|\alpha_1|^2\,\!</math>. If it were then one could
act on the state with a Hadamard transformation and there would be some probability of it being in <math>\left\vert 0\right\rangle\,\!</math> and some probability of being in <math>\left\vert 1\right\rangle\,\!</math>. However, acting on the state <math>\left\vert \psi\right\rangle\,\!</math> with a Hadamard transformation,

{{Equation|<math>H\left\vert \psi\right\rangle = \left\vert 0\right\rangle.
\,\!</math>|2.36}}

This state has probability zero of being in the state <math>\left\vert 1\right\rangle\,\!</math> and
probability one of being in the state <math>\left\vert 0\right\rangle\,\!</math>. (This argument is so
simple and pointed, that I lifted it directly from Mermin's book
{Mermin:book}, page 27.)

A measurement in the computational basis is said to project this state
into either the state <math>\left\vert 0\right\rangle\,\!</math> or the state <math>\left\vert 1\right\rangle\,\!</math> with
probabilities <math>|\alpha_0|^2\,\!</math> and <math>|\alpha_1|^2\,\!</math> respectively. To
understand this as a projection, consider the following way in which
the <math>0\,\!</math>-component of the state <math>\left\vert \psi\right\rangle\,\!</math> is found. The state
<math>\left\vert \psi\right\rangle\,\!</math> is projected onto the the state <math>\left\vert 0\right\rangle\,\!</math> mathematically
by taking the inner product of <math>\left\vert 0\right\rangle\,\!</math> and <math>\left\vert \psi\right\rangle\,\!</math>

{{Equation|<math>\left\langle 0\mid \psi\right\rangle = \alpha_0.
\,\!</math>|2.37}}

Notice that this is a complex number and that its complex conjugate
can be expressed as

{{Equation|<math>\left\langle\psi \mid 0\right\rangle = \alpha_0^*.
\,\!</math>|2.38}}

Therefore the probability can be expressed as

{{Equation|<math>\left\langle\psi\mid 0 \right\rangle \left\langle 0\mid\psi\right\rangle = \left\vert\left\langle
0\mid \psi\right\rangle \right\vert^2.\,\!</math>|2.39}}

Now consider a multiple-qubit system with state

{{Equation|<math>\left\vert \Psi\right\rangle = \sum_i \alpha_i\left\vert i\right\rangle.\,\!</math>|2.40}}

The result of a measurement is a projection and the
state is projected onto the state <math>\left\vert i\right\rangle\,\!</math> with probability
<math>|\alpha_i|^2\,\!</math> and the same properties are true of this more general
system.

To summarize, if a measurement is made on the system <math>\left\vert\Psi\right\rangle\,\!</math>, the
result <math>\left\vert i\right\rangle\,\!</math> is obtained with probability <math>|\alpha_i|^2\,\!</math>.
Assuming that <math>\left\vert i\right\rangle \,\!</math> results from the measurement, the state of the
system has been projected into the state <math>\left\vert i\right\rangle\,\!</math>. Therefore, the
state of the system immediately after the measurement is <math>\left\vert i\right\rangle\,\!</math>.

A circuit diagram with a measurement represented by a box with an
arrow is given in Fig.~\ref{fig:measex}. In this case, the
measurement result is used for input for another state. The unitary
in this diagram is one that depends upon the outcome of the
measurement. Notice that the information input, since it is
classical, is represented by a double line.



==Footnotes==
<references />