# PAR Class 21, Mon 2019-04-01

## 2   Quantum computing on youtube

1. Quantum Algorithms (2:52)

Which problems can quantum computers solve exponentially faster than classical computers? David Gosset, IBM quantum computing research scientist, explains why algorithms are key to finding out.

2. David Deutsch - Why is the Quantum so Strange? (8:43)

3. Grover's Algorithm (9:57)

An overview of Grover's Algorithm. An unstructured search algorithm that can find an item in a list much faster than a classical computer can. Several sources are listed.

4. Bob Sutor demonstrates the IBM Q quantum computer (6:53)

5. Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19)

6. "Spooky" physics | Leo Kouwenhoven | TEDxDelft (18:00)

## 3   Quantum computing

ctd

1. Algorithms:
1. Some, but not all, are faster.
2. Bounded-error quantum polynomial time (BQP)
1. "is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances" - https://en.wikipedia.org/wiki/BQP
2. Includes integer factorization and discrete log.
3. Relation to NP is unknown (big unsolved problem).
3. Grover's algorithm:
1. https://en.wikipedia.org/wiki/Grover%27s_algorithm
2. Given a black box with N inputs and 1 output.
3. Exactly one input makes the output 1.
4. Problem: which one?
5. Classical solution: Try each input, T=N.
6. Quantum: $T=\sqrt(N)$.
7. Probabilistic.
8. Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.
9. Can extend to quantum partial search.
10. Grover's algorithm is optimal.
11. This suggests that NP is not in BQP .
4. Shor's algorithm:
1. Factorize an int.
2. in BQP.
3. almost exponentially faster than best classical algorithm.
4. Largest examples I can find:
2. https://quantumexperience.ng.bluemix.net/qx/tutorial ctd.