**What are quantum computers? ** - Store and process information according to the principles of quantum mechanics - Information is encoded in quantum bits (qubits), which store a superposition of classical data with positive and negative amplitudes - Such a device would let us solve certain problems much faster than is possible with ordinary, classical computers **Building a QC that can run interesting algorithms is really hard! ** 2 contradicting demands: - Need exquisite control over quantum mechanical systems, manipulate these qubits very precisely - Need to isolate from the environment so that they are not subject to noise ------ **The origin of quantum speedup** QC allow for interference between computational paths, like waves that interfere in a pond To perform a computation, we need to carefully choreograph the interference in a quantum mechanical system such that: - paths to a solution interfere constructively --> Add together - paths to non-solutions interfere destructively --> Not appear in the final answer Inteference is not a uniquely quantum mechanical phenomenon, though quantum mechanics gives an efficient representation of high-dimensional interference --> This allows to potentially have interference in an exponentially large state space that can sometimes enable us to solve problems really fast ------ How general do we expect these kind of speed ups to be? QC is not equal to exponential parallelism The linearity of quantum mechanics prohibits us from exploring all potential solutions in parallel and picking out the correct one. To get significant speedup, QC need to exploit the structure in problems. They only gives us advantage for particular types of problems. For exponential speedup, we need to have a promise on the input, the problem cannot have too much symmetry. What kinds of problems have the right structure for quantum computers to exploit? ---- Quantum attacks on public-key cryptography - Basic Problem - Write an integer as a product of prime factors - This is hard for a classical computer to do So much so that this problem is the basis of the RSA crypto system In 1994, Peter Shor showed that there is an efficient quantum algorithm for factoring integers Main idea of the algorithm is that the structure that is being exploited has to do with finding the periodicity of the function --> QC are good at detecting periodicity Also polynomial time quantum attacks are potential for Diffie-Helman, elliptic curve discrete log, Buchman Williams, and other cryptosystems ![[Pasted image 20210217201808.png]] ---- Qauntum Search and Walk In 1996, Grover showed that we could search over N possibilities using O ( square root of N ) queries / operations ![[Pasted image 20210217202110.png]] --- Optimization ![[Pasted image 20210217202234.png]] --- Quantum Simulation Problem --> Given a description of a quantum system, an evolution time t, and an initial quantum state, produce the state after time t. ---- QC to address High Dimensional Linear Algebra ![[Pasted image 20210217203217.png]] Solving a system of linear equations, all over science and engineering ![[Pasted image 20210217203549.png]] https://quantumalgorithmzoo.org/