PAR Class 21, Mon 2019-04-01

1   GTC19 videos, part 3

1. Robotics in Action at GTC 2019 (1:21)
2. Evolution of NVIDIA GeForce 1999-2017 (14:00)
3. Project Sol Part 3: A Real-Time Ray-Tracing Cinematic Scene Powered by NVIDIA RTX (3:44)
4. Introducing NVIDIA Safety Force Field (2:15)
5. Top 5 Higher Education Sessions at GTC 2019 (1:28)
6. GPU-Accelerated Data Science | NVIDIA GTC Keynote Demo (13:04)

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:
         1. 56153 = 233 × 241.
         2. https://medium.com/@aditya.yadav/rsa-2048-cracked-using-shors-algorithm-on-a-quantum-computer-660cb2297a95
2. https://quantumexperience.ng.bluemix.net/qx/tutorial ctd.