1982Quantumsimulator■Allclassicalcomputerswork

infundamentallythesame

way.■Quantum

systems

are

fundamentally

different.The

size

ofthe

problemgoesupexponentiallyin

the

size

ofthe

system,making

them

hard

to

simulate.Richard

Feynman■In

1982this

led

Feynmanto

propose

quantumcomputers.A

quantum

system

should

be

able

toefficientlysimulateanotherquantum

system.■Efficiently

meansthat

the

resources

used

(timeandsize

ofthe

system)shouldscaleat

most

polynomially

inthesizeofthesystem

to

be

simulated.■

Polynomiallymeansas

x,x2,x3,etc.1985Universalquantumcomputer■Aclassical

computeruses

bits,e.g.001100010010011110100001101101110011■Quantum

computers

replace

this

with

a

quantum

state|001100010010011110100001101101110011〉■Eachdigitisa

two-level

quantum

system-a

qubit.David

Deutsch■Quantum

computers

can

be

in

superpositions

of

these

states■Represent

the

state

as

a

vector:■The

allowed

operations

on

this

state

are

unitary

matrices.These

satisfyU+U=Ⅱ■The

t

indicates

the

Hermitian

conjugate-the

transpose

and

complex

conjugate

of

the

matrix.■

Any

allowed

operation

is

reversible.Using

U+on

U|ψ〉will

restore

the

state

|ψ〉.■Aspecial

caseispermutationmatrices-apermutationmatrix

only

changes

one

computational

basis

state

to

another.Universalquantumcomputer■Operations

on

the

state

can

be

represented

as

matrices:Ittakes

|0〉

to

|1〉,andviceversa.2.The

controlled

NOT

acts

on

two

qubits.It

performs

an

X

on

the

targetqubit

ifthe

control

qubit

is

in

the

state

|1〉.Otherwise

it

does

nothing.Examplesofpermutations1.The

NOT

operation,also

called

an

X,acts

on

a

single

qubit3.The

Toffoli

gate

is

a

NOT

controlled

by

twoonly

if

both

controls

are

in

the

state

|1〉.qubits.It

performs

an

XTurningclassical

intoquantum■

The

NANDgate

is

universalforclassicalcircuitsandacts

as

below.■We

can

convert

any

classical

algorithm

into

a

quantum

algorithm,replacing

the

NAND

gates

with

Toffolis,and

keeping

the

extra

qubits.ABQ001011101110■Wecan

performthesameoperation

usinga

Toffoli

gate.Turningclassical

intoquantum■Anyfunctionwecouldcalculateonaclassical

computerwe

could

alsocompute

on

a

quantum

computer,withthe

addition

ofsome

extra“garbage”registers.|x>|0〉|f(x)>|extra

data(x)〉■Thiscan

beturned

into

a

computationthat

does

this:Uf|x>|0>=|x>|f(x)〉■

Method:1.Add

an

ancilla,and

perform

the

program

as

above

to

give

If(x)>|0>|extradata(x)〉.2.Copythe

output

ofthefunction

intothe

extra

ancilla,to

giveIf(x)>|f(x)>|extradata(x)〉.3.Invert

the

program

above,giving

|x>|f(x)>|0>.■Forancillasthat

are

not

initiallyzeroed,we

canjust

perform

the

XOR.Uf|x>|b〉=|x>|b田

f(x)〉"Quantum

computationis.αdistinctivelynewway

of

harnessingnature….It

will

be

thefirsttechnology

thatallows

useful

tasks

to

beperformed

incollaboration

betweenparallel

universes.

"David

DeutschSHIFT

HAPPENS.FIREIVE

INVENTEDA

QUANTUM

COMPUTER,CAPABLE

OFINTERACTING

WITH

MATTERFROM

OTHER

UNIVERSES

ToSOLVE

COMPLEXEQUATION5.ACCORDINGTOCHAO5THEORY,YOURTINYCHANGETOANOTHERUNIVERSE

WILL

SHIFT

ITS

DESTINY,PO5STBLY

KILLING

EVERYINHABITANT.■

For

n

qubits,we

have

evaluated

anexponential

number

of

different

values

ofthe

function.Partofthestory:Superposition■

Nowwhat

ifwestartthestate

in

a

superposition?■But

ifwemeasure

it,weonlyeverfindone

value

ofthe

function!■We

can't

just

calculate

many

valuesof

a

function,we

need

some

way

tointerfere

them

to

obtain

some

globalproperty

of

the

function.■

We

need

non-permutation

gates:The

Hadamard

gate

has

a

matrix

representation■JustmeasuringSchr?dinger'scat

would

never

show

it

in

asuperposition.■

Ifwe

could

do

a

Hadamard

onSchr?dinger's

cat,we

would

turn1.

(llive)+|dead〉)/√2to

|live),andTheotherpart:Interference2.(llive)-|dead>)/√2

to

|dead〉showing

we

have

superposition.HE

ESCAPED

BEFORETHE

EXPERIMENT

WASFINISHEDAND

NOWJHE'S

BOTH

ALIVE

ANDDEAD

AT

THE

SAMETIME.0>→

(10>+|1〉)/

√2

1〉→

(10〉-|1〉)/

√2THIS

IS

WULF.HE

USEDTOWORK

FORA

FAMOUS

PHYSICIST

NAMEDSCHRODINGER.WOW.I

HAVEHALFAMINDTO

BEOFFENDEDBYTHAT.LIKE

A

ZOMBIE?|

|Theotherpart:Interference■We

can't

just

calculate

many

values

of

a

function,we

need

some

way

tointerfere

them

to

obtain

some

global

property

of

the

function.togetherwiththeToffoligate

is

universalforreal

unitaries.2.

The

π/8

orT

gate■Universal

sets

of

gates:1.TheHadamard

gatetogetherwiththe

HadamardandCNOT

is

universal.The

Deutschalgorithm■Problem:Givenafunctionf(x)mappingbitstobits,determine

if

it

is

one-to-one

[i.e.f(0)≠f(1)].■Classically

we

need

to

evaluate

both

f(0)and

f(1).■

Quantum

algorithm:1.

Start

with|0>|1〉2.Perform

a

Hadamard

on

both

qubits

to

give3.Apply

the

gate

mappingx>|b〉x>|b

田

f(x)〉

to

give4.Apply

Hadamard

on

qubit

2

to

giveDavid

Deutsch1985The

Deutschalgorithm1.

Startwith|0>|1〉2.Perform

a

Hadamard

on

both

qubits

to

give1985David

Deutsch4.

Apply

Hadamard

on

qubit

2

to

give3.Apply

the

gate

mappingx>|b田

f(x)〉to

give|x>|b〉|The

Deutschalgorithm■

Problem:

Given

a

function

f(x)mapping1bit

to1bit

f(x):{0,1}→{0,1},determine

if

it

is

either

constant

orbalanced.■Classically

we

need

to

evaluate

both

f(0)and

f(1).■Deutsch

quantum

algorithm

gives

result

with

one

functionevaluation.■Quantum

algorithm

has

two

crucial

steps:1.Calculate

the

function

on

both

input

values

simultaneously.2.

Interfere

the

result.David

Deutsch1985The

Deutschalgorithm■Problem:

Given

a

function

f(x)mapping1

bit

to1

bitf(x):{0,1}→{0,1},determineifitiseitherconstantorbalanced.■

Classically

weneed

to

evaluateboth

f(0)and

f(1).■Deutschquantumalgorithmgives

result

with

onefunction

evaluation.Interferetheresult.H

measurementH1985David

DeutschCalculatethefunction

onboth

inputvalues

simultaneously.|0〉

H■

Problem:

Given

a

function

f(x)mapping

n

bits

to1bit

f(x):{0,1}n→{0,1},determine

if

it

is

either

constant

orbalanced.

There

is

a

promise

that

it

is

either.■

Classically

weneedtoevaluate2n-1+1valuesoff(x).■Deutsch-Jozsa

quantum

algorithm

gives

result

with

onefunction

evaluation.measurementRichard

Jozsa|1〉

HUf|x>|b〉=|x>|b

田

f(x)〉1992The

Deutsch-JozsaalgorithmDavid

DeutschPhaseoracles■We

have

previously

assumed

that

the

unitary

for

the

function

acts

asUf|x>|b〉=|x>|b田

f(x)〉■In

both

caseswe

have

needed

to

turn

this

into

a

phase

in

ordertomake

the

algorithm

work,i.e.■Instead

we

canjust

take

the

oracle

to

have

this

form:Uf|x

〉=(-1)f(x)|x〉The

Deutsch-Jozsaalgorithm■Deutsch

algorithm:start

with■Deutsch-Jozsa

algorithm:start■

The

probabilityofmeasuringy

is■

The

probabilityofmeasuringy

is■

Thefunction

evaluation

yields■

Thefunction

evaluation

yields■

A

Hadamard

givesly>=|00…0〉■Hadamards

give1992with■

Problem:

Givena

function

f(x)mapping1bitto1bitf(x):{0,1}→{0,1}such

that

f(x)=s·x,determine

s.■

The

function

evaluation

yieldssampling■

The

probabilityofmeasuringy

isFourier1993Bernstein,Vazirani■

Hadamardsgive1996Grover'ssearchalgorithm■

Problem:

Given

a

function

f(x)mapping

n

bits

to1

bitf(x):{0,1}n→{0,1},determine

the

value

of

x

such

thatf(x)=1.We

have

a

promise

that

the

value

is

unique.■Classically

we

need

to

evaluate

O(N)values,N=2n.Lov

Grover■Grover's

algorithm

enables

a

search

with

o(√

N)queries.■Quantum

algorithm

has

two

crucial

steps:1.Calculate

the

function

on

all

values

simultaneously.2.

Reflect

about

the

equal

superposition

state.■These

steps

are

repeated

o(√

N)times.1996Grover'ssearchalgorithm■

We

start

in

the

state■

We

repeat

the

following~√

N

times:1.Apply

the

function

calculation

Uf.

Lov

Grover2.Apply

the

reflection

operation

Us=2|s〉〈s|-Ⅱ

.■The

system

will

be

in

the

state|w

〉such

that

f(w)=1.■

But

how

dowe

perform

Us?Grover'ssearchalgorithm■

But

how

dowe

perform

Us?■First,invert

the

operation

thatprepares|s

〉-justHadamards

on

all

qubits.■Then,reflect

about|0〉;i.e.apply

2|0><0|-Ⅱ

.■Lastly,repeattheoperationthatprepares|s)|1〉Lov

Grover19961996Grover'ssearchalgorithm■

Eachcoefficient

is

reflectedaboutthe

mean■What

does

Us

do?Lov

GroverGrover'ssearchalgorithm■Example:Take

N=4,withsolution

x=3.■

We

start

in

the

state■

Apply

the

function

calculationUf,giving■

The

mean

isLov

Grover1996Grover'ssearchalgorithm■Example:Take

N=4,withsolution

x=3.■

We

start

in

the

state■

Apply

the

function

calculationUf,giving■

The

mean

is■Therefore,when

we

apply

the

reflection

operation

Us,we

get1996Lov

GroverGrover'ssearchalgorithm■

Example:Take

N=9,withsolution

x=6.■

Reflectingtarget..■

The

mean

is

7/27.Lov

Grover1996Grover'ssearchalgorithm■

Example:Take

N=9,withsolution

x=6.■Reflectingtarget..■

The

mean

is

7/27.■Reflecting

aboutmean...■Reflectingtarget..■

The

mean

is

17/243.Lov

Grover1996Grover'ssearchalgorithm■

Example:Take

N=9,withsolution

x=6.■Reflectingtarget..■

The

mean

is

7/27.■Reflecting

aboutmean...■Reflectingtarget..■

The

mean

is

17/243.■

Reflecting

about

mean...Solutionwithhigh

probability.Lov

Grover1996■Then|s〉=cosφ|s'>+sinφ|w〉with

sinφ=1/√

N.■

The

operation

Uf

reflects

|w>and

leaves

all

orthogonalstates

unchanged.Uf=Ⅱ-2|w

〉w|■

The

action

of

Uf

on|s'>isUfls'〉=(Ⅱ-2|w>(w|)|s'>=|s'〉Grover'ssearchalgorithm■Another

wayof

looking

at

it:Rotations■Define

the

ket

perpendicular

to

|w>.Lov

Grover1996Grover'ssearchalgorithm■Another

way

of

looking

at

it:Rotations■

The

action

of

Uf

on

|s'>isUfls'〉=|s'〉■

The

action

of

Us

on

|w>isUs|w〉=(2|s>〈s|-Ⅱ)|w〉=2(s|w

〉|s〉-|w〉=2

sinφ|s〉-|w〉■

Now

use|s〉=cosφ|s'>+sinφ|w〉■

This

givesUs|w

〉=2sinφ(cosφ|s'>+sinφ|w

〉)-|w〉=2

sinφcosφ|s'>-(1-2

sin2φ)|w

〉=sin

2φ|s'〉-cos

2φ|w〉Lov

Grover1996Grover'ssearchalgorithm■Anotherwayoflookingat

it:Rotations■

The

action

of

U

on|s'>isUfls'〉=|s'〉■

The

action

of

Us

on

|w>isUs|w〉=sin

2φ|s'>-cos

2φ|w〉■

The

action

of

Us

on

|s'>isUs|s'>=(2|s>〈s|-Ⅱ)|s'〉=2s|s'>|s〉-|s'〉=2cosφls〉-|s'〉■

Now

use|s〉=cosφ|s'>+sinφ|w〉■

This

givesUs|s'〉=2cosφ(cosφ|s'〉+sinφ|w〉)-|s'〉=(2cos2φ-1)|s'>+2

sinφcosφ|w

〉

=cos2φ|s'>+sin

2φ|w〉Lov

Grover1996Grover'ssearchalgorithm■Anotherwayoflookingat

it:RotationsUfls'〉=|s'〉Us|w

〉=sin

2φ|s'〉-cos

2φ|w〉Us|s'>=cos2φ|s'>+sin2φ|w〉■Consider

a

state

writtenasψ〉=cosθ|s'〉+sinθ|w〉■The

action

of

U

on

|4>isUflψ〉=cosθ|s'〉-sinθ|w〉■

Then

applying

Us

gives

UsUflψ〉=cosθ[cos2φ|s'>+sin2φ|w]-sinθ[sin2φ|s'〉-cos

2φ|w]

=[cosθcos2φ-sinθsin

2φ]|s'>+[cosθ

sin

2φ+sinθ

cos

2φ]|w〉

=cos(θ+2φ)|s'>+sin(θ+2φ)|w〉Lov

Grover1996Grover'ssearchalgorithm■Anotherwayoflookingat

it:RotationsUfls'〉=|s'〉Us|w

〉=sin

2φ|s'〉-cos

2φ|w〉Us|s'>=cos

2φ|s'>+sin

2φ|w〉■The

Grover

iteration

givesψ〉=cosθ|s'>+sinθ|w〉lw)

UsUflψ〉=cos(θ+2φ)|s'>+sin(θ+2φ)|w〉→

|s〉→

|s'〉Uf|s〉Lov

Grover1996Grover'ssearchalgorithm■Anotherwayoflookingat

it:RotationsUfls'〉=|s'〉Us|w

〉=sin2φ|s'〉-cos2φ|w〉Us|s'>=cos2φ|s'>+sin

2φ|w〉■The

Grover

iteration

givesψ〉=cosθ|s'>+sinθ|w

〉

UsUflψ〉=cos(θ+2φ)|s'>+sin(θ+2φ)|w〉1996Lov

GroverUsUf|s〉3φGrover'ssearchalgorithm■Another

wayof

looking

at

it:RotationsUfls'〉=|s'〉Us|w

〉=sin2φ|s'〉-cos2φ|w〉Us|s'>=cos

2φ|s'>+sin

2φ|w〉■TheGrover

iteration

givesψ〉=cosθ|s'>+sinθ|w〉UsUflψ〉=cos(θ+2φ)|s'>+sin(θ+2φ)|w〉1996Lov

Grover(U?U)2|s)5φGrover'ssearchalgorithm■A