Week 19 - my notes

• Classical algortihms can be slow and inneficient. Some even struggle to solve certain complex problems
• Linear Search goes through each element until it finds the right item - we go through this even with which a huge dataset (super inneficient, right?)
• Linear Search is not scalable

• It is a quantum algortihm that leverages amplitude amplification to speed up search
• As weel as demonstrating quadradic speedup
• We apply Grover’s Algorithm to unstructured search, but you know what you are looking for, you just don’t know where it is!
• Summarizing: It is a quantum algortihm that leverages superposition and interference to speed up the process

\[number of operations used in Grover's algorithm \approx \sqrt{number of operations used in linear search}\]

• Meaning:

\[O(\sqrt{n})\]

• Superposition: Combination of the 0 and 1 states
• Interference: Interaction between waves – they can add on to each other or cancel out
• We can create a superposition with all the possible different choices – all choices are equally likely
• As the algorithm goes on, the probability of incorrect choices reduces (interference) – amplitude amplification
• At the final state, you make a measurement, and with a very high probability, we find where it is

• Last week we learned that designing a quantum algorithm means translating words into linear algebra
• In the starting point, we just apply an H gate to each qubit

\[\frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix\]

• At the end, we wanna know the right answer.

\[\begin{bmatrix}0\\0\\0\\1\end{bmatrix}\]

• Which gate do we use from going from the starting point to the end point?

• It is a long-term algorithm: we will need a lot of fault-tolerant qubits; about 10,000 qubits to see an advantage over linear search