Intro Quantum Computing

Question 1

Church-Turing Thesis

Answer 1

anything that is computable can be computed by a Turing Machine
Strong: anything that can be efficiently computed can be efficiently computed by a Turing Machine

Question 2

Quantum Computing Motivation

Answer 2

Turing Machine does not simulate quantum mechanics efficiently
-> Quantum Machine: can solve provably faster than Turing machine ? Church turing thesis broken

Question 3

Qbit

Answer 3

A bit is {0,1}, a Qbit is [0,1]
Qbit can be in a supperposition of both ! -> collapse -> goes in 1 state.
|s> = a|0>+b|1> such that a^2+b^2=1
a and b are amplitudes
Described this way to possibly have negative interference of computational path that lead to incorrect solution. Negative amplitudes also allow more operations !
-> Unitary operators: linear transformations that preserve the length of the vector

Question 4

Double slit

Answer 4

Light source: photon/beam of electron
2 thin slit, a background
Result: not 2 light bars on background but many !
Electrons are waves : different orientations
Destructive interference: opposite phase cancel -> dark
Constructive interference: same wave/orientation reinforce -> light

Question 5

Stern Gerlach Experiment

Answer 5

Silver atom shot between 2 magnets. Which way magnetic field pointing ? Up/Down
Classical physics: expect a vertical line of possible position, continuous values
Reality: 2 points up/down, no inbetween
Rotate by 90° apparatus: measure up spins -> 50% 1 direction 50% another -> random ! Randomness does not exist on a computer, Turing Machine are deterministic :o
Before experiment: unknown orientation -> superposition of 2 states, both state at the same time

Question 6

Qbit vs Cbit

Answer 6

Superposition, interference, entanglement

1 Qbit can encode 2 Cbit of information