L19 - Quantum Computing Flashcards
Define superposition
The ability for quantum bits to exist in multiple states simultaneously.
What is the purpose of Quantum Computing?
Use superposition to execute massively parallel computations.
Explain how the Schrodingers Cat thought experiment details the absurdity of superposition…
A cat is place in a box with a delayed radioactive poison. Until the box is opened to know for sure, the cat is considered both dead and alive.
If superposition is not absurd, what is the likely hood that the cat is dead or alive?
Dead = 0.5
Alive = 0.5
How can a QBit in a superposition state be represented?
∣ψ⟩=α|0⟩+β|1⟩
What does each element of the superposition state equation represent?
α,β - probability of being in that state
|0⟩ and|1⟩ - basis states of the QBit
What does the Superposition equation of QBits show?
The probability that each bases is found upon measurement
Given a register of size 3, create a superposition formula to represent both 3 and 7…
3 = 011
7 = 111
0.5(|0⟩+|1⟩) XOR |1⟩ XOR |1⟩
= 0.5(011 + 111)
= 0.5(|3⟩ + |7⟩)
What are the 2 most important quantum computing algorithms?
- Grovers search
- Shors factorisation
What input does Grovers Search take?
Unstructured, unsorted data.
What is the worst case complexity of Grovers Search?
O(sqrt(N))
What is the Church-Turing thesis?
All reasonable definitions of algorithms can be represented as equal, and any new algorithm is also equivalent.
Does Quantum Computing algorithms conform to the Turing-Church thesis?
Yes. Quantum algorithms can be replicated on sequential machines, but have exponential slowdown.
