Quantum Class 12, Thu 20221013
1 Followup on freeranging discussion from last time

What use is quantum computation?
"What good is a newborn baby?"  attributed to Mike Faraday and Ben Franklin.

Value of PhD
I like the idea, but maybe it's obsolescent.
It teaches stubbornness and how to accomplish a 4 year project, which is unusual in industry.
It's required for academia, but universities are obsolescent.
It can be a status symbol in government, military, business.

It's required to manage technical people with PhDs. Otherwise they won't respect you and you'll have trouble making technical decisions. Similarly, effective hospital managers are MDs.
The mushy degrees that combine management with a technical concentration, either in math or health, have been tried for decades and always fail. OK, them's fighting words, so bring it on.
However, you won't live longer because of the time you spent as a grad student. Maybe there were better uses of those 4 years.

Strategic career advice
Work to stay current in your field. Your employer may oppose this. If so, do it on your own time.

E.g., I'm 70 years old and I'm teaching quantum computing.
I proposed this course to ECSE 3 years ago, created it, and spend a lot of time learning the material.
The difference between you and me is that RPI pays me to learn this.
If you don't stay current, you'll be laid off after 20 years as obsolescent.
In this credentialed society, collect the pretty pieces of paper. It's easier now with all the online courses.
Be prepared for big unexpected changes. Imaging describing today's world to someone from even 5 years ago....
Finally, make contacts and be friendly. All of my jobs have been from people I knew. As my grandmother said, "Be nice to the people you meet on the way up. You may meet them again on the way down."
2 Shor's algorithm to factor an integer
2.1 The problem
Factorize an integer.
in BQP.
almost exponentially faster than best classical algorithm.
Largest examples I can find: 56153 = 233 × 241.
2.2 Notes
This is the most famous quantum algorithm.
It's the one that has the potential to break much public key crypto.
This is the deepest topic of this course so far.
Takeaways from this algorithm are that some serious math is involved, and the quantum version is unlike the classical version.
If you don't absorb all the details, then absorb its flavor.
I sometimes show videos because they present the idea better than me.
OK to ask questions and make comments during the videos. I'll pause the video and try to answer.
2.3 Application: break RSA
Publicprivate key crypto.

Oversimpifying, RSA private key is a pair of large primes.
Public key is their product.
Odd fact: if 2 public keys have a common factor, then you can easily factor both of them with gcd.
Publish the public key.

Use intended recipient's public key to encrypt message then send it.
Recipient uses his private key to decrypt it.

Or, use private key to sign message then publish or send it.
Anyone can use the public key to verify it.
Invented in 1970s, secretly before publicly.
Aside: visit the NSA's National Cryptologic Museum. Note how nothing there is under 50 years old.

All this assumes that you can reliably get someone's genuine public key.
Some scams involve faking phone numbers, email addresses, etc.
Based on a function that's hard to invert, e.g., factoring.
RSA has competitors.
There are various ways to embed RSA or a competitor into an encryption program, with choices of algorithm, key length, etc.
On linux, you can encrypt a file with pgp, gnupg, LUKS, zip encryption, zfs encryption, truecrypt (suddenly discontinued w/o any stated reason in 2014), etc, etc.
At one time, there was no version of pgp that was legal both in the US and outside the US.
At one time, the US proposed that crypto must have a back door. However this was dropped.
A paranoid person might suspect that the chaos was deliberate to make it harder to use crypto. But that's just crazy talk.
RSA is slow, so it's used only to encrypt a sessionspecific symmetric key that is used for the rest of the message, ssh session, etc.

Gnupg et al do a 3rd level of encryption.
The private key is encrypted with a passphrase.
You use the passphrase to decrypt the file.
The encrypted passphrase is stored ~/.gnupg .
If you lose ~/.gnupg, you lose all your encrypted data.
You can change the passphrase by reencrypting the private key w/o reencrypting the whole file.
You can have multiple passphrases to give to different people.
You can cancel a passphrase by deleting the version of the encrypted private key that was encrypted with it.
So, you need 3 things to access the encrypted file: the encrypted file, the encrypted secret key, and the passphrase.
2.4 Classical factoring
Efficient algorithms are complicated and use number theory.
Rational sieve is good first algorithm to study. It's simple and reasonably fast.
2.5 Videos

Shor on, what is Shor's factoring algorithm? (2:09)
It's good to listen to the inventor of a big idea.

Umesh Vazirani's lecture, 2018.
This jumps into the middle of things a little. However the alternatives are worse: not to show Vazirani at all, or to also show all the earlier videos.
Lecture 10 1 Period Finding (19:27)
Hacking at Quantum Speed with Shor's Algorithm (16:35). Optional to watch on your own.
The Story of Shor's Algorithm, Straight From the Source  Peter Shor (31:27) 20210702 Gives the history. Optional to watch on your own.
Five lectures by Abraham Asfaw in Qiskit's Introduction to Quantum Computing and Quantum Hardware.
2.6 Vanished videos
2.7 IBM Quantum
https://quantumcomputing.ibm.com/composer/docs/iqx/guide/shorsalgorithm
3 Grover's search
3.1 Problem
Blackbox $F: \{0,1\}^n \to \{0,1\}$
For only one x, F(x) = 1. Otherwise F(x)=0.
Determine x.
Classically: T(n)=O(n).
Quantumly: $T(n) = O(\sqrt{n})$.
3.2 Videos
Introduction to Quantum Computing (18)  Grover's Algorithm: Quantum Problem Statement (4:24)
Introduction to Quantum Computing (19)  Grover's Algorithm: Outline (16:09)
Introduction to Quantum Computing (20)  Grover's Algorithm: Subspace (7:42)
Introduction to Quantum Computing (21)  Grover's Algorithm: Geometric Interpretation
Introduction to Quantum Computing (23)  Grover's Algorithm: Implementation (9:33)
Introduction to Quantum Computing (24)  Grover's Algorithm: IBM Quantum Experience (11:39)
4 HHL algorithm to solve a linear system of equations

Quantum Machine Learning  37  Overview of the HHL Algorithm 5:48.
quick, deep, intro.

Quantum algorithm for solving linear equations 36:31.
quite understandable.
Quantum Algorithms for Systems of Linear Equations (Quantum Summer Symposium 2020) 19:22.

IBM Quantum Algorithms for Applications from qiskit
E.g., Fourier transform and HHL.

This is in Huawei HiQ, an opensource software framework for quantum computing.
https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_systems_of_equations
5 Term project
Time to start thinking of a term project, on a topic at least vaguely related to the course. Teams of any size ok. For the grad version, also write a paper.