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.
