CS 294-2 Introduction, Axioms, Bell Inequalities 1/17/07

Spring 2007 Lecture 1

1 Why Quantum Computation?

• Quantum computers are the only model of computation that escape the limitations on computation
imposed by the extended Church-Turing thesis. These theoretical limitations will soon have practical
consequences as Moore’s Law (the doubling every eighteen months in transistor density on chips and
the resulting increase in computer speed) is expected in a decade or so to run into inherent (classical)
physical limits such as transistors scaling down to the size of elementary particles.

• Quantum computers would have a profound effect on complexity based cryptography, via the poly-
nomial time quantum algorithms for factoring and discrete logs. Understanding how to meet these
threats by designing quantum resistant cryptosystems or by resorting to quantum cryptography is a
major challenge.

• Quantum computation has brought about a renaissance in the examination of the foundations of quan-
tum mechanics: highlighting phenomena such as entanglement and the resulting exponential power
inherent in quantum physics, and showing that quantum error-correcting codes may be used to bring
stability into the seemingly inherently unstable quantum world.

• Lastly, the study of quantum computation has helped broaden and deepen our insights into complexity
theory (and tools such as Fourier analysis and information theory), and in a few cases helped resolve
open questions in classical complexity theory.

2 Basic Quantum Mechanics

The basic formalism of quantum mechanics is very simple, though understanding and interpreting the re-
sults is much more challenging. There are three basic principles, enshrined in the three basic postulates of
quantum mechanics:

• The superpostion principle: this axiom tells us what the state of a quantum system looks like.
* An addendum to this axiom tells us given two subsystems, what the allowable states of the composte
system are.

• The measurement principle: this axiom governs how much information about the state we can access.

• Unitary evolution: this axiom governs how the state of the quantum system evolves in time.

2.1 The superposition principle

Consider a system with k distinguishable states. For example, the electron in an atom might be either in its
ground state or one of k − 1 excited states, each of progressively higher energy. As a classical system, we
might use the state of this system to store a number between 0 and k − 1. The superposition principle says
that if a quantum system is allowed to be any one of number of different states then it can also be placed in a

CS 294-2, Spring 2007, Lecture 1 1

linear superposition of these states with complex coefficients. Thus the quantum state of the k-state system
above is described by a sequence of k complex numbers α0 , . . . , αk−1 ∈ C . α j is said to be the (complex)
amplitude with which the system is in state j. We will require that the amplitudes are normalized so that
∑ j |α j |2 = 1. It is natural to write the state of the system as a k dimensional vector:

α0
 
 α1 
 
 . 
 
 . 
αk−1

The normalization on the complex amplitudes means that the state of the system is a unit vector in a k
dimensional complex vector space — called a Hilbert space.
In quantum mechanics it is customary to use the Dirac’s ket notation to write vectors. As we shall see later,
this is a particularly useful notation in the context of quantum computation. In the ket notation, the above
state is written as:
  k−1  
ψ = ∑ α j  j
j=0
   
1 0
0 0
       
Here 0 =   .  and k − 1 =  . . The Dirac notation has the advantage that the it labels the basis
   
. .
0 1
vectors explicitly. This is very convenient because the notation expresses both that the state of the quantum
system is a vector, while at the same time it represents a number (in superposition) describing the physical
quantity of interest (energy level, spin, polarization, etc). In
 the context
  of quantum
 computation and quan-
tum information it is data (0 or 1) to be processed. The {0 , 1 , . . . , k − 1 } basis is called the standard
basis.

2.2 Measurement Principle

This linear superposition ψ = ∑k−1j=0 α j j is part of the private
   
 world of the electron. For us to know the
electron’s state, we must make a measurement. Measuring ψ in the standard basis yields j with probability


|α j | 2 .
One important aspect of the measurement process is that it alters the state of the quantum system: the effect
of the measurement is that the new state is exactly the outcome of the measurement.  I.e., if the outcome
of the measurement is j, then following the measurement, the qubit is in state  j . This implies that you
cannot collect any additional information about the amplitudes α j by repeating the measurement. This
property forms the basis of quantum cryptography where the presence of an eavesdropper necessarily alters
the quantum state being transmitted.
Intuitively, a measurement provides the only way of reaching into the Hilbert
 space
 to probe the quantum
  this is done by selecting an orthonormal basis e0 , . . . , ek−1 . The outcome of the
state vector. In general  
measurement ise j (or j) with probability equal to the square of the length of the projection of
 the
 state
vector ψ on e j . A consequence of performing the measurement is that the new state vector is e j . Thus
measurement may be regarded as a probabilistic rule for projecting the state vector onto one of the vectors
of the orthonormal measurement basis.

CS 294-2, Spring 2007, Lecture 1 2

2.3 Qubits

The basic entity of quantum information is a qubit (pronounced “cue-bit”), or a quantum bit.
This corre-
α
sponds to a 2-state quantum system, and its state can be written as a unit (column) vector β ∈ C 2 . In
Dirac notation, this may be written as:

ψ = α 0 + β 1 α,β ∈ C |α |2 + |β |2 = 1
     
and

This linear superposition ψ = α 0 + β 1 is part of the private

     
 world of the electron. For us to know
the electron’s state, we must make a measurement. Measuring ψ in the { 0 , 1 } basis yields 0 with
 
  
probability |α | 2 , and 1 with probability |β | 2 .
As we noted above, the measurement process alters the state of the qubit: the outcome of the measurement
is a single classical bit of information, and the effect of the measurement is that the
 new state
  is exactly the
outcome of the measurement. I.e., if the outcome ofthe measurement ofψ = α 0 + β 1 yields 0, then
following the measurement, the qubit is in state 0 . This implies that you cannot collect any additional
information about α , β by repeating the measurement.
   
More generally, we may choose any orthogonal basis {v , w and measure the qubit in it. To do this, we
rewrite our state in that basis: ψ = α 0 v + β 0 w . The outcome is v with probability |α 0 | 2 , and w with
       

  |β | . If the outcome of the measurement on ψ yields v , then as before, the the qubit is then
0 2
   
probability  
in state v .

2.3.1 Measurement example I.

ψ = α 0 + β 1 in the v , v⊥ basis, where v = a0 + b1 . What is the probability

               
Q: We measure 
of measuring v ?

     
+ = √1 (0 + 1 )
2

     
ψ = cos θ0 + sin θ1
i
|ψ
h+

45◦
θ  
0
h−
|ψ
i

     
− = √1 (0 − 1 )
2

Figure 1:

A: First let’s do the simpler case a = b = √12 , so v = √12 (0 + 1 ) ≡  + , v⊥ = √12 (0 − 1 ) ≡  − .

               

CS 294-2, Spring 2007, Lecture 1 3

See Figure 1. We express ψ in the  + ,  − basis:
     

ψ = α 0 + β 1
     

= α √12 ( + +  − ) + β √12 ( + −  − )
       

α√
+β   α√
−β  
   
= 2
+ + 2
− .

Therefore the probability of measuring  + is | √12 (α + β )|2 = |α + β |2 /2. The probability of measuring
 

 − is |α + β |2 /2. We will do the general case in §2.3.2.

 

2.3.2 Measurement example II.

The notation hv| (“bra v”) denotes a row vector, the conjugate-transpose of |vi, or |vi† . For example, h0| =
( 1 0 ) and h1| = ( 0 1 ). More generally,

α
†
hψ | = β = ( ᾱ β̄ ) = ᾱ h0| + β̄ h1| .

The Dirac notation can be handy. For example, let

           
v1 = a1 0 + b1 1 , v2 = a2 0 + b2 1 .

 
 

  v1 v2 (shorthand for v1 v2 ) is a matrix product of the 1 × 2 matrix v1 and the 2 × 1 matrix
Then   
v2 , or just a scalar:

  a2

v1  v2 = ( ā1 b̄1 ) b2 = ā1 a2 + b̄1 b2 .

 
 
 
 
 
 
v1  v2 = v2  v1 is an inner product. Note that 0 0 = 1 1 = 1 and 0 1 = 1 0 = 0. Thus the
above equation could have been expanded,

 

    
v1  v2 = (ā1 0 + b̄1 1 )(a2 0 + b2 1 )

 
 
 
 
= ā1 a2 0 0 + ā1 b2 0 1 + b̄1 a2 1 0 + b̄1 b2 1 1
= ā1 a2 · 1 + ā1 b2 · 0 + b̄1 a2 · 0 + b̄1 b2 · 1
= ā1 a2 + b̄1 b2 .

In this notation, α = 0 ψ , β = 1 ψ . The normalization condition |α |2 + |β |2 = 1 is

 
 

1 = |α |2 + |β |2 = ᾱα + β̄ β
= ψ  0 0 ψ + ψ  1 1 ψ

 
 
 
 

= ψ  (0 0 + 1 1)ψ

  
  
  

= ψψ .

 

 

 

 
  

The last equality above follows since 0 0 = 10 00 , 1 1 = 00 01 , so 0 0 + 1 1 is the 2 × 2 identity
matrix. (This trick is important enough to have its own name, the “resolution of the identity.”)
In the next lecture, we will introduce tensor product spaces, where the advantages of this notation increase.

CS 294-2, Spring 2007, Lecture 1 4

With the new notation, it is simple to solve the general case of the question asked in §2.3.1. Recall |vi =
a|0i + b|1i and choose |v⊥ i = b̄|0i − ā|1i. Indeed, hv|v⊥ i = ab − ba = 0.
 
|ψ i = |vihv| + |v⊥ ihv⊥ | |ψ i
= α (|vihv|0i + |v⊥ ihv⊥ |0i) + β (|vihv|1i + |v⊥ ihv⊥ |1i)
= (α hv|0i + β hv|1i)|vi + (α hv⊥ |0i + β hv⊥ |1i)|v⊥ i
= (α ā + β b̄)|vi + (α b + β a)|v⊥ i .

The probability of measuring |vi in a measurement in the v, v⊥ basis is therefore

|hv|ψ i|2 = |α ā + β b̄|2 .

3 Two qubits:
Now let us examine the case of two qubits. Consider the two electrons in two hydrogen atoms:
1 1
0 0
+ +

Since each electron can be in either of the ground or excited state, classically the two electrons are in one of
four states – 00, 01, 10, or 11 – and represent 2 bits of classical information. Quantum mechanically, they
are in a superposition of those four states:

ψ = α00 00 + α01 01 + α10 10 + α11 11 ,

         

where ∑i j |αi j |2 = 1. Again, this is just Dirac notation for the unit vector in C 4 :

α00
 
α01 
α10 
 

α11

where αi j ∈ C , ∑ |αi j |2 = 1.
Measurement:
If the two electrons (qubits) are in state ψ and we measure them, then the probability that the first qubit
 

is in state i, and
 the second qubit is in state j is P(i, j) = |αi j | 2 . Following the measurement, the state of the
two qubits is ψ 0 = i j . What happens if we measure just the first qubit? What is the probability that the
  

first qubit is 0? In that case, the outcome is the same as if we had measured both qubits: Pr {1st bit = 0} =
|α00 | 2 + |α01 | 2 . The new state of the two qubit system now consists of those terms in the superposition that
are consistent with the outcome of the measurement – but normalized to be a unit vector:
  α00 00 + α01 01
   
φ = q
|α00 | 2 + |α01 | 2
.

CS 294-2, Spring 2007, Lecture 1 5

Tensor products (informal):
φ1 = α1 0 + β1 1 and the second qubit is in the state φ2 =
       
Suppose the first qubit is in the state
α2 0 + β2 1 . How do we describe the joint state of the two qubits?
   

φ = φ1 ⊗ φ2
     

= α1 α2 00 + α1 β2 01 + β1 α2 10 + β1 β2 11 .
       

We have simply multiplied together the amplitudes of |0i1 and |0i2 to determine the amplitude of |00i12 ,
and so on. The two qubits are not entangled with each other and measurements of the two qubits will be
distrbuted independently.
Given a general state of two qubits can we say what the state of each of the individual qubits is? The answer
is usually no. For a random state of two qubits is entangled — it cannot be decomposed into state of each
of two qubits. In next section we will study the Bell states, which are maximally entangled states of two
qubits.
Example:
               
State 11 (00 − 01 + 10 − 11 ) can be decomposed into √12 (0 + 1 ) √12 (0 − 1 ), but for state
   
√1 (00 + 11 ) there is no such decomposition - the states of the two qubits are not independent but
2
entangled/correlated.

4 EPR Paradox:
In 1935, Einstein, Podolsky and Rosen (EPR) wrote a paper “Can quantum mechanics be complete?” [Phys.
Rev. 47, 777, Available online via PROLA: http://prola.aps.org/abstract/PR/v47/i10/p777 1]
For example, consider coin-flipping. We can model coin-flipping as a random process giving heads 50% of
the time, and tails 50% of the time. This model is perfectly predictive, but incomplete. With a more accurate
experimental setup, we could determine precisely the range of initial parameters for which the coin ends up
heads, and the range for which it ends up tails.
   
For Bell state √1 (00 + 11 ), when you measure first qubit, the second qubit is determined. However, if
2
two qubits are far apart, then the second qubit must have had a determined state in some time interval before
measurement, since the speed of light is finite. Moreover this holds in any basis. This appears analogous to
the coin flipping example. EPR therefore suggested that there is a more complete theory where “God does
not throw dice.”
What would such a theory look like? Here is the most extravagant framework. . . When the entangled state
is created, the two particles each make up a (very long!) list of all possible experiments that they might be
subjected to, and decide how they will behave under each such experiment. When the two particles separate
and can no longer communicate, they consult their respective lists to coordinate their actions.
But in 1964, almost three decades later, Bell showed that properties of EPR states were not merely fodder
for a philosophical discussion, but had verifiable consequences: local hidden variables are not the answer.

5 Bell’s Inequality
Bell’s inequality states: There does not exist any local hidden variable theory consistent with these outcomes
of quantum physics.

CS 294-2, Spring 2007, Lecture 1 6

Consider the following communication protocol in the classical world: Alice (A) and Bob (B) are two
parties who share a common string S. They receive independent, random bits XA , XB , and try to output bits
a, b respectively, such that XA ∧ XB = a ⊕ b. (The notation x ∧ y takes the AND of two binary variables x and
y, i.e., is one if x = y = 1 and zero otherwise. x ⊕ y ≡ x + y mod 2, the XOR.)
   
In the quantum mechanical analogue of this protocol, A and B share the EPR pair √1 (00 + 11 ). As
2
before, they receive bits XA , XB , and try to output bits a, b respectively, such that XA ∧ XB = a ⊕ b.
If the odd behavior of the Bell state can be explained using some hidden variable theory, then for any
protocol in the quantum world there should be a corresponding classical protocol that achieves the same
results.
However, Alice and Bob’s best protocol for the classical (hidden variable) game, as you will prove in the
homework, is to output a = 0 and b = 0, respectively. Then a ⊕ b = 0, so as long as the inputs (XA , XB ) 6=
(1, 1), they are successful: a ⊕ b = 0 = XA ∧ XB . If XA = XB = 1, then they fail. Therefore they are successful
with probability exactly 3/4.
We will show that the quantum mechanical system can do better. Specifically, if Alice and Bob share an
EPR pair, we will describe a protocol for which the probability Pr{XA ∧ XB = a ⊕ b} is greater than 3/4, and
is about cos2 π /8 = 0.85.
Here is the protocol:

• if XA = 0, then Alice measures in the −π /16 basis.

• if XA = 1, then Alice measures in the 3π /16 basis.

• if XB = 0, then Bob measures in the π /16 basis.

• if XB = 1, then Bob measures in the −3π /16 basis.

Now an easy calculation shows that in each of the four cases XA = XB = 0, etc, the success probability is
cos2 π /8. This is because in the three cases where xA · xB = 0, Alice and Bob measure in bases that differ by
/pi/8. In the last case they measure in bases that differ by 3π /8, but in this case they must output different
bits.

CS 294-2, Spring 2007, Lecture 1 7