Quantum Computing: Bits and Qubits

1
Quantum Computing
Lecture 1
Anuj Dawar
Bits and Qubits

2
What is Quantum Computing?
Aim to use quantum mechanical phenomena that have no classical

counterpart for computational purposes.
Central research tasks include:

• Building devices — with a specified behaviour.
• Designing algorithms — to use the behaviour.
Mediating these two are models of computation.

3
Bird’s eye view
A computer scientist looks at Quantum Computing:

Algorithmic Languages
Theory/complexity
System Architecture
Specified Behaviour
Physics
Dragons
4
Why look at Quantum Computing?
• The world is quantum

– classical models of computation provide a level of
abstraction
– discrete state systems
• Devices are getting smaller
– Moore’s law
– the only descriptions that work on the very small scale are
quantum
• Exploit quantum phenomena
– using quantum phenomena may allow us to perform
computational tasks that are not otherwise possible/efficient
– understand capabilities/resources
5
Course Outline
A total of eight lecturers.

1. Bits and Qubits (this lecture).
2. Linear Algebra
3. Quantum Mechanics
4. Models of Computation
5. Some Applications
6. Search Algorithms
7. Factorisation
8. Complexity
6
Useful Information
Some useful books:

• Nielsen, M.A. and Chuang, I.L. (2010). Quantum Computation
and Quantum Information. 2nd ed. Cambridge University
Press.
• Mermin, N.D. (2007). Quantum Computer Science. CUP.
• Kitaev, A.Y., Shen, A.H. and Vyalyi, M.N. (2002). Classical
and Quantum Computation. AMS.
Course website:
http://www.cl.cam.ac.uk/teaching/1213/QuantComp/
7
Bits
A building block of classical computational devices is a two-state

system.
0 ←→ 1
Indeed, any system with a finite set of discrete, stable states, with
controlled transitions between them will do.
8
Qubits
Quantum mechanics tells us that any such system can exist in a

superposition of states.
In general, the state of a quantum bit (or qubit for short) is

described by:
α|0i + β|1i
where, α and β are complex numbers, satisfying
|α|2 + |β|2 = 1
9
Qubits
A qubit may be visu-

|1i alised as a unit vector
β α|0i + β|1i on the plane.
In general, however,
α |0i α and β are complex
numbers.
10
Measurement
Any attempt to measure the state
α|0i + β|1i
results in |0i with probability |α|2 , and |1i with probability |β|2 .
After the measurement, the system is in the measured state!
That is, further measurements will always yield the same value.
We can only extract one bit of information from the state of a

qubit.
11
Measurement
|1i
α|0i + β|1i and α|0i − β|1i have β α|0i + β|1i
the same probabilities for their
measurement α |0i
However, they are distinct states

α|0i − β|1i
which behave differently in terms
of how they evolve.
12
Vectors
Formally, the state of a qubit is a unit vector in C2 —the

2-dimensional complex vector space.
 
α
The vector   can be written as
β
α|0i + β|1i
   
1 0
where, |0i =   and |1i =  .
0 1
|φi— a ket, Dirac notation for vectors.

13
Basis
Any pair of vectors |φi, |ψi ∈ C2 that are linearly independent

could serve as a basis.
α|0i + β|1i = α′ |φi + β ′ |ψi
The basis is determined by the measurement process or device.
Most of the time, we assume a standard (orthonormal) basis |0i

and |1i is given.
This will be called the computational basis
14
Example
" #
√1
The vector 2
measured in the computational basis gives
√1
2
either outcome with probability 1/2.
Measured in the basis

   
√1 √1
 2 , 2 
√1 −1
√
2 2
it gives the first outcome with probability 1.

15
Entanglement
An n-qubit system can exist in any superposition of the 2n basis

states.
α0 |000000i + α1 |000001i + · · · + α2n −1 |111111i

P2n −1
with i=0 |αi |2 = 1
Sometimes such a state can be decomposed into the states of

individual bits
1 1 1
(|00i + |01i + |10i + |11i) = √ (|0i + |1i) ⊗ √ (|0i + |1i)
2 2 2
16
Entanglement
Compare the two (2-qubit) states:

1 1
√ (|00i + |01i) and √ (|00i + |11i)
2 2
If we measure the first qubit in the first case, we see |0i with
probability 1 and the state remains unchanged.
In the second case (an EPR pair), measuring the first bit gives |0i
or |1i with equal probability. After this, the second qubit is also
determined.

Quantum Computing: Bits and Qubits

Uploaded by

Copyright:

Available Formats

Quantum Computing: Bits and Qubits

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Quantum Computing: Bits and Qubits

Uploaded by

Copyright:

Available Formats

1

Bits and Qubits

What is Quantum Computing?

Aim to use quantum mechanical phenomena that have no classical

Central research tasks include:

Mediating these two are models of computation.

Bird’s eye view

A computer scientist looks at Quantum Computing:

Why look at Quantum Computing?

• The world is quantum

A total of eight lecturers.

Some useful books:

A building block of classical computational devices is a two-state

Quantum mechanics tells us that any such system can exist in a

In general, the state of a quantum bit (or qubit for short) is

A qubit may be visu-

Any attempt to measure the state

After the measurement, the system is in the measured state!

We can only extract one bit of information from the state of a

However, they are distinct states

Formally, the state of a qubit is a unit vector in C2 —the

|φi— a ket, Dirac notation for vectors.

Any pair of vectors |φi, |ψi ∈ C2 that are linearly independent

α|0i + β|1i = α′ |φi + β ′ |ψi

The basis is determined by the measurement process or device.

Most of the time, we assume a standard (orthonormal) basis |0i

Measured in the basis

it gives the first outcome with probability 1.

An n-qubit system can exist in any superposition of the 2n basis

α0 |000000i + α1 |000001i + · · · + α2n −1 |111111i

Sometimes such a state can be decomposed into the states of

Compare the two (2-qubit) states:

You might also like