Week 11 Flashcards
What is a quantum bit?
A qbit can be represented as a superposition a|0> + b|1> such that probabilities a^2 + b^2 = 1
A quantum register of size 3 can store either the individual number 3 or 7 (if probabilities are 1 for all qbits)
How can the quantum register of size 3 can store both individual numbers 3 or 7 by superposition?
1/sqrt(2) (|0> + |1>) x |1> x |1> = 1/sqrt(2)(|011> + |111>
= 1/sqrt(2)(|3> + |7>
What happens if we put all 3 bits in superposition?
We can have any numbers 1 to 7.
What is Schrodigners Cat?
Thought experiment to highlight the absurdity of superposition.
A cat is placed in a box with a flask of poison and a radioactive decay that controls this poison release. the cat is considered dead and alive at the same time until one checks the box to see.
What are the two most important Quantum algorithms?
Grover’s search algorithm
Shor’s factorisation algorithm.
What is Grover’s search algorithm?
Quantum search algorithm for unsorted, unstructured data. Compare searching a telephone directory by name or by NUMBER.
How does Grover’s search work?
Encodes all of the data as superpositions of bits.
The function inputs are a superposition of all possible database entries, and searches the database in one operation. When it finds the matching entry, it marks it by flipping the sign of the wave function of this entry.
Whats the complexity of unordered list length search?
O(n) for normal pc
O(sqrt(n)) for quantum pc
What is Shor’s factorisation algorithm?
Finds the prime factors of an integer. (NP)
How is Shor’s factorisation algorithm implemented?
a reduction of factoring to order-finding running on a classical computer
an order-finding problem running on a quantum computer.
Moves factorisation into P.
Time for factorisation
Exponential in d
Polynomial in d for a normal pc
Significance of Shor’s algorithm
RSA asymmetric encryption will be broken.
2 200 digit primes p and q make the private key, the public key is N = p*q
Private keys will be able to be factored out.
What is the Church Turing thesis
all existing reasonable definitions of ‘algorithm’ are equivalent
any new reasonable definition of ‘algorithm’ will turn out to be equivalent to an existing one
Does quantum break the Church Turing thesis
Quantum conforms to the Church Turing thesis because a quantum computer can be simulated on a conventional computer, albeit with an exponential slowdown.
To build a quantum computer, what DiVincenzo criteria must be satisfied?
scalability with will-defined qubits
initialization of qubits to a pure state
a universal set of quantum gates
long coherence times
a qubit-specific measurement capability.
What is scalability with will-defined qubits?
A qubit must be in one of two states with a clear energy gap between them.
Why is scaling hard?
more qubits require exponentially more hardware. today, quantum computers have about 50 qubits.
What is initialization of qubits to a pure state?
the initial state must be known for certain.
How do we reset qubits to a given state?
Wait for them to decay to their ground state. Takes time, as qubit lifetimes steadily improve.
Spontaneous excitation means there is always a chance that a qubit is not actually in the ground state.
What is a universal set of quantum gates?
Small set of 1 and 2 qubit logic gates can implement any algorithm. (so that we can write programs)
THEY ARE REVERSIBLE UNLIKE CLASSICAL LOGIC GATES
What is long coherence times?
A system must maintain its state for as long as possible. if they lose coherence use a majority vote for qubits.
What is a qubit-specific measurement capability
measurement of the final state of qubits must be reliable. (measurement is IRREVERSIBLE, qubit is collapsed to a measured value)
What technologies used to implement quantum?
Photons
Trapped atoms
Nuclear magnetic resonance
Dots
Superconductors
