1.1   Presentations

1. Mon April 20
   1. Sava C & Davi P & Emil V
2. Thurs April 23
   1. Kevi M
   2. Liz C
   3. Chri H
   4. Zhep L
3. Mon April 27
   1. Joe C & Alex Z
   2. Mike M
   3. Matt R & Skyl S
   4. Eliz C
   5. John F & Hayl R & Mish S
   6. Ross D
   7. Clar S & Garr D

1.2   Reports

Due last class day, Wed April 29.

See syllabus.

To the 2 students in the grad version: do more work.

2.1   Grover's algorithm etc

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 .

2.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)

7. Introduction to Quantum Computing (18) - Grover's Algorithm: Quantum Problem Statement (4:24)

8. Introduction to Quantum Computing (19) - Grover's Algorithm: Outline (16:09)

9. Introduction to Quantum Computing (20) - Grover's Algorithm: Subspace (7:42)

10. Introduction to Quantum Computing (21) - Grover's Algorithm: Geometric Interpretation

11. Introduction to Quantum Computing (23) - Grover's Algorithm: Implementation (9:33)

12. Introduction to Quantum Computing (24) - Grover's Algorithm: IBM Quantum Experience (11:39)