.. title: PAR Class 23, Thurs 2020-04-16
.. slug: class23
.. date: 2020-04-16
.. tags: class
.. category: 
.. link: 
.. description: 
.. type: text
.. has_math: true

.. raw:: html

   <style> .red {color:red} </style>
   <style> .blue {color:blue} </style>

.. role:: red
.. role:: blue

.. sectnum::
.. contents:: Table of contents
..


Final projects
---------------------------

Presentations
=============

#. Mon April 20

   #. Sava C & Davi P & Emil V

#. Thurs April 23

   #. Kevi M
   #. Liz C
   #. Chri H
   #. Zhep L

#. Mon April 27
   
   #. Joe C & Alex Z
   #. Mike M
   #. Matt R & Skyl S
   #. Eliz C
   #. John F & Hayl R & Mish S
   #. Ross D
   #. Clar S & Garr D

Reports
=======

Due last class day, Wed April 29.

See syllabus.

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

Quantum computing ctd
---------------------

Grover's algorithm etc
======================
   
#. Algorithms:

   a. Some, but not all, are faster.

   #. Bounded-error quantum polynomial time (BQP)

      i. "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

      #. Includes integer factorization and discrete log.

      #. Relation to NP is unknown (big unsolved problem).

   #. Grover's algorithm:

      i. https://en.wikipedia.org/wiki/Grover%27s_algorithm

      #. Given a black box with N inputs and 1 output.

      #. Exactly one input makes the output 1.
	    
      #. Problem: which one?

      #. Classical solution: Try each input, T=N.

      #. Quantum:  $T=\\sqrt(N)$.

      #. Probabilistic.

      #. Apps: mean, median, reverse a crypto hash, find collisions, generate false blocks.

      #. Can extend to quantum partial search.

      #. Grover's algorithm is optimal.

      #. This suggests that NP is not in BQP .



Quantum computing on youtube
============================

#. `Quantum Algorithms (2:52) <https://www.youtube.com/watch?v=-ysVGWtAjio>`_

   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.

#. `David Deutsch - Why is the Quantum so Strange? (8:43) <https://www.youtube.com/watch?v=MckuBQC6gKU>`_

#. `Grover's Algorithm (9:57) <https://www.youtube.com/watch?v=hK6BBluTGhU>`_

   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.

#. `Bob Sutor demonstrates the IBM Q quantum computer (6:53) <https://www.youtube.com/watch?v=b-0ZNlqaSBE>`_

#. `Can we make quantum technology work? | Leo Kouwenhoven | TEDxAmsterdam (18:19) <https://www.youtube.com/watch?v=aUuaWVHhx-U>`_

#. `"Spooky" physics | Leo Kouwenhoven | TEDxDelft (18:00) <https://www.youtube.com/watch?v=wZzHnZzm_58>`_

#. `Introduction to Quantum Computing (18) - Grover's Algorithm: Quantum Problem Statement (4:24) <https://www.youtube.com/watch?v=tu6E9XhXMDs&list=PLIxlJjN2V90w3KBWpELOE7jNQMICxoRwc&index=20>`_
   
#. `Introduction to Quantum Computing (19) - Grover's Algorithm: Outline (16:09) <https://www.youtube.com/watch?v=7tc3DCAJC7E&list=PLIxlJjN2V90w3KBWpELOE7jNQMICxoRwc&index=21>`_
   
#. `Introduction to Quantum Computing (20) - Grover's Algorithm: Subspace (7:42) <https://www.youtube.com/watch?v=XyBa3PL_yNg&list=PLIxlJjN2V90w3KBWpELOE7jNQMICxoRwc&index=22>`_
   
#. `Introduction to Quantum Computing (21) - Grover's Algorithm: Geometric Interpretation <https://www.youtube.com/watch?v=AS8T0wp72Lk&list=PLIxlJjN2V90w3KBWpELOE7jNQMICxoRwc&index=23>`_
   
#. `Introduction to Quantum Computing (23) - Grover's Algorithm: Implementation (9:33) <https://www.youtube.com/watch?v=7cPEZmdSCUI&list=PLIxlJjN2V90w3KBWpELOE7jNQMICxoRwc&index=29&t=0s>`_
   
#. `Introduction to Quantum Computing (24) - Grover's Algorithm: IBM Quantum Experience (11:39) <https://www.youtube.com/watch?v=Uw6zEMSxKvg>`_