**The Quantum Computer**

**Matthias Christandl**

Professor

Department of Mathematical Sciences

University of Copenhagen, Denmark

Professor

Department of Mathematical Sciences

University of Copenhagen, Denmark

**1600s**

**1920s**

**1930s**

**1980s**

**. . .**

**1996**

**today**

**?**

**0101**

1100

1100

**First Quantum**

Computer

Computer

Information

Classical Mechanics

abstract concept

independent of

physical implementation

Claude Shannon

Alan Turing

unit of information, the bit: 0 or 1

0101

1100

all physical information

can be abstracted this way

0 or 1

information theory

?

Quantum Mechanics

claim based on world being classical

position

measurement:

left or right?

position

measurement:

left or right?

particles have definite properties

location, velocity, color, ....

these can be measured (to arbitrary accuracy)

The Quantum Computer

single atoms (and other small objects)

they behave according to quantum mechanics

do not behave according to classical mechanics

spin of an electron

measurement:

up or down?

measurement:

left or right?

50%

50%

Particles have properties that only come into being through measurement

Quantum bits - Qubits

=

a

+ b

one qubit

. . .

Are several qubits described by several a´s and b´s?

No!

. . .

+

. . .

+ . . . +

. . .

Writing down the a´s of 100 qubits, we would need more bits than atoms in the universe! Qubits are very powerful!

number of a´s exponential

in number of particles

Computation

Entanglement

Einstein-Podolsky-Rosen pair

Schrödinger´s cat

. . .

. . .

achieved for 10 - 1000 particles

a real cat has 1000000000000000000000 atoms

Can this help us to compute faster?

Birth of the quantum computer

How many gates do we need? Depends on the function!

. . .

. . .

. . .

. . .

. . .

multiplication

factorisation

number of gates

x

y

x

x+y+1

number of digits (2n)

fast!

number of gates

exponential in number of digits

slow!

0

0

0

1

p*q=?

k=?*?

. . .

. . .

. . .

. . .

. . .

Idea: Compute function for all inputs simultaneously!

input

output

Problem: get all answers at the same time...

+

+ . . . +

. . .

. . .

. . .

+

+ . . . +

. . .

. . .

. . .

Peter Shor solved this problem for factoring in 1996

On a quantum computer factoring is as fast as multiplying!

Building a Quantum Computer

State of the art: ca. 10 -100 qubits, can factor 15

0

1

0

0

1

0

1

0

1

1

1

1

. . .

input

output

. . .

function

gate

gate

gate

gate

gate

gate

gate

gate

=

Any function can be computed with gates!

Challenges:

Need: Mega

qu

bits, even Giga

qu

bits

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

gate

gate

gate

keep atoms isolated

Blatt, Wineland

excellent control over many atoms

Experimentally difficult, no fundamental obstruction!

Conceptual Fabric

Classical Computer Quantum Computer

is not just an upgrade, it is a paradigm shift

underlying physical theory is quantum mechanics

all previous computation was based on Newtonian mechanics

quantum parallelism

exponential speedup possible!

no conventional hardware upgrade can achieve this

. . .

. . .

no such superposition seen in universe yet!

Planck, Heisenberg,

Bohr, Schrödinger,

Einstein, ...

Includes classical mechanics.

more than classical mechanics!

Deutsch, Feynman

particle

interaction

particle

interaction

particle

interaction

Input

Output

efficient simulation of quantum physics

universe quantum computer

Large and growing field of research

universities, ibm, microsoft, google...

Nobel prize 2012

area of my own research

try all pairs until you find the correct one