1 of 33

Introduction to �Quantum Computing

COMS 4281 (Fall 2022)

Week 1

Course homepage: http://www.henryyuen.net/classes/fall2022

2 of 33

Welcome!

Bird’s eye view

Administrivia

The physics of computation

3 of 33

Welcome!

Bird’s eye view

Administrivia

The physics of computation

4 of 33

What is quantum computing?

It is computation (and more generally, information processing) based on the principles of quantum mechanics, rather than classical physics.

Quantum mechanics is a description of nature at its most fundamental level.

Formulated in the early 20^th century to explain the behavior of subatomic particles.�
QM, and its specializations (quantum field theory, quantum chromodynamics, etc), have been spectacularly successful in explaining microscopic physical phenomena.

Hydrogen atom

Superconductivity

Superfluidity

5 of 33

The exponentiality of QM

6 of 33

The exponentiality of QM

So how do physicists actually do (quantum) physics?

Answer #1: 100+ years of extremely clever approximations and shortcuts for calculations.

Bethe ansatz, Feynman diagrams, perturbation theory, �mean field approximations,…

Answer #2: computer simulations

Density functional theory, Quantum Markov Chain Monte Carlo,..

Answer #3: studying systems that allow for Answers #1 and #2 above

Systems that are mostly classical
Systems with non-strongly interacting particles
Lucky that most things we’ve studied so far fall in this category!

But simulating general quantum physics still seems like a hard task…

7 of 33

The exponentiality of QM

In 1981 Richard Feynman asked the following question: �“Can probabilistic computers simulate quantum mechanics?”
His conclusion: NO!�
“…Nature isn’t classical, damnit, and if you want to �make a simulation of nature, you’d better make it�quantum mechanical. ��By golly, it’s a wonderful problem, because it doesn’t�look so easy.”
Feynman (along with David Deutsch, Paul Benioff, Yuri Manin) �came up with the idea of computing based �on quantum mechanical principles.

8 of 33

The early days

Feynman’s motivation for quantum computers is the most obvious one: simulating quantum systems. (almost tautological!)
To physicists in the '80s, this idea might have seemed obvious. To a computer scientist in the ‘80s, QCs would have seemed like a wild crackpot idea.
1980s: David Deutsch found example of a (non-physics) problem that could be solved faster on QC than any classical computer (by a constant factor)
1992: Bernstein and Vazirani, and then Dan Simons found examples of (non-physics) problems that could be solved by QC super-polynomially faster than with classical computer.

9 of 33

Shor’s breakthrough

1993: Peter Shor realized that Simons’s idea could be extended to efficiently solve the following problem:
(Integer Factorization) Given integer N > 0, output its prime factorization.
The security of the RSA cryptosystem (the most widely deployed public-key encryption on the internet) crucially relies on the assumption that factoring integers is hard!

10 of 33

Crossroads

Since Shor’s algorithm, physicists and computer scientists have been faced with three options:

Quantum mechanics is wrong.
There is a fast classical algorithm for factoring.
Quantum computers are more powerful than classical computers.

At least one of these must be true!

Which do you think is most likely to be true?

11 of 33

Crossroads

Option #1: QM is wrong

Perhaps the most successful theory of nature to date.
In all its domains of applicability, we have never found experimental disagreement.

Option #2: Polynomial-time classical factoring algorithm.

RSA has been out for nearly 50 years. There is enormous economic pressure to discover weaknesses, if it exists.

12 of 33

Crossroads

Option #3: Quantum computers are more powerful than classical computers.

This would refute the Extended Church-Turing Thesis.

Church-Turing Thesis: A Turing machine can simulate any �computation process.

Extended Church-Turing Thesis: A probabilistic Turing machine can efficiently simulate any computation process.

Option #3 would violate the ECT (assuming factoring is hard for �classical computers)!

13 of 33

Crossroads

Since Shor’s algorithm, physicists and computer scientists have been faced with three options:

Quantum mechanics is wrong.
There is a fast classical algorithm for factoring.
Quantum computers are more powerful than classical computers.

At least one of these must be true!

14 of 33

Present day

Exciting times for quantum computing:

Engineering: primitive quantum computers are being built.

Theoretical developments: new algorithms, new cryptographic protocols, �new insights into how quantum computing compares to classical computing

Deep connections to other sciences: condensed matter physics, quantum gravity, materials science, chemistry, computer science, pure mathematics.

15 of 33

Emerging quantum computers

Many players racing to build (scalable) quantum computers:

Different labs/companies are betting on different horses

Superconducting qubits, ion traps, photonic systems, topological qubits, …

16 of 33

Emerging quantum computers

Until 2017 or so, most quantum computing devices had ~10 qubits.
Suddenly, there was a flood of resources devoted to engineering efforts, and now we are seeing programmable quantum computers with 50+ qubits.
Major problem: devices are insanely noisy!
We are in the “NISQ” era:

Noisy Intermediate-Scale Quantum
Noisy devices with ~100 qubits.
Not capable of running Shor’s algorithm, but should still be capable of solving interesting, hard problems.

17 of 33

Quantum supremacy

In Fall 2019, Google announced that they had achieved “Quantum Supremacy” using their 53-qubit Sycamore quantum processor.

Quantum supremacy: a convincing real-world �demonstration of that a quantum computer�is accomplishing a task that cannot feasibly �be performed by a classical computer.

Sweet spot: 53 qubits just beyond the reach of �Google’s compute clusters to simulate �in a reasonable time. (~2⁵³ ops)

18 of 33

Quantum vs classical

Other research groups have also announced �quantum supremacy results.

Biggest competitor to quantum computers are clever classical algorithms:

In Nov 2021, a group from Chinese Academy of Sciences used tensor network algorithms to�reproduce the statistics of the Google supremacy experiment using 512 GPUs in �15 hours.

19 of 33

Outlook for quantum advantage

The race between quantum computers and classical computers has just started, so jostling is bound to happen.

The race is complicated, with incomparable�metrics of success. ��
However, when the dust settles, we expect �QC will be lightyears ahead of classical �computers -- on certain tasks.

20 of 33

Summary of hardware efforts

We’re in the NISQ era.
There’s a ”qubit race” going on, but qubit count is �not everything!
Scaling up (i.e. more qubits, better qubits) is a tough engineering challenge, but no fundamental obstacles to building QC with 10⁶ noiseless qubits.
Still, large-scale fault-tolerant QCs look like they’re many years away.

What interesting problems can we solve on near-term quantum computers?

21 of 33

Quantum algorithms

Exponential speedups for structured, algebraic problems

Factoring (Shor’s algorithm)
Hidden subgroup problem

Polynomial speedups for unstructured search problems

Grover search

Exponential speedups for quantum simulation

Simulating quantum physics and chemistry (Feynman’s dream)
Probably the most important application of quantum computers so far!

N = pq

22 of 33

Quantum algorithms

Algorithms to be run on near-term QCs:

Variational eigensolvers
Classical-quantum hybrid algorithms

Quantum Machine Learning

Linear system solvers/SDPs/Convex Optimization
Quantum neural nets
Recommendation systems
…more

What types of problems admit a quantum advantage?

23 of 33

Connections with fundamental physics

The key to a theory of Quantum Gravity could be quantum entanglement, and quantum error correcting codes.

The ”Blackhole Firewall Paradox” is an issue about quantum information, and possible resolutions involve quantum cryptography.

What can Quantum Computing tell us about Nature?

24 of 33

Uncharted territory

25 of 33

What you’ll get out of this class:

Learn the basic principles of quantum information and computation

Learn fundamental quantum algorithms and quantum protocols

Get an idea of the current state of the field, and

Get an idea of what the big questions are.

26 of 33

Target audience

Who this class is for:

Computer scientists, physicists, mathematicians, chemists, …
People with a solid linear algebra and probability background
People who want to learn about the theory of quantum computing and quantum information.

Who this class is NOT for:

People who want to learn how to build a quantum computer
People who want to learn quantum physics

27 of 33

Prerequisites

(Important) Basic linear algebra. You should be comfortable with:

Vector space (subspaces, orthogonal complements, dimension, linear independence, basis, span,...). Inner products. Row vs column vectors. Linear operators (invertibility, matrix representation, composition of linear operators, transpose, adjoint). Eigenvalues and eigenvectors. Trace.

(Important) Basic probability theory. You should be comfortable with:

Bayes’ rule, conditional distributions. Joint probability spaces. Independent random variables. Mean, variance, etc.

(Helpful, but not required) Computer Science Theory exposure: Analysis and design of algorithms; Complexity theory; Discrete math.
(Helpful) Experience with Python

28 of 33

Welcome!

Bird’s eye view

Administrivia

The physics of computation

29 of 33

Grading

70% Problem Sets 1 thru 4

30% Problem Set 5

30 of 33

Class resources

Tas: John Bostanci, Yulong Li�
Course homepage: www.henryyuen.net/classes/fall2022

Syllabus, office hours, problem sets, schedule

Discussions on EdStem

Office hours starts this week

31 of 33

Textbook

Recommended Textbook:

Affectionately called “Mike ‘n Ike” in the �field.

Can get it on Amazon…or wherever else you�get textbooks.

Links to other courses and notes at: www.henryyuen.net/resources

32 of 33

Your first task

Sign up for IBM Quantum Lab (https://quantum-computing.ibm.com/)

Make sure you can log in by next week!�
Open up some of the �Jupyter notebooks�

33 of 33

Welcome!

Bird’s eye view

Administrivia

The physics of computation