Why quantum computing?

What kind of problems a quantum computer is for, and what it is not.

Beginner10 min read7 sections · 2 questions+45

By the end you will be able to

01Name two problem families where quantum algorithms scale better than the best known classical ones.
02Explain why 'faster' is the wrong word and 'scales differently' is the right one.
03Recognise the three ingredients every quantum algorithm uses: superposition, interference, entanglement.

Your laptop is not slow. For almost everything you do with a computer, a classical processor is the right tool and will stay the right tool. A quantum computer is a different machine built for a narrow set of problems whose difficulty grows explosively with their size: the number of possibilities doubles every time you add one more variable, and a classical machine has to look at those possibilities one group at a time.

01Two problems that motivate the field

Factoring and discrete logarithms. Much of today's public-key cryptography rests on the belief that factoring a 600-digit number is hopeless. Shor's algorithm factors in polynomial time on a large, error-corrected quantum computer, which is why post-quantum cryptography exists.
Simulating nature. Molecules, magnets and new materials are quantum systems. Writing down the state of 50 interacting electrons exactly needs more numbers than there are atoms on Earth; a quantum computer stores that state in 50 qubits.

Notice what both have in common: the size of the problem is small (a number, a molecule) but the space of possibilities is enormous. That is the shape of a problem that fits a quantum computer. Sorting a list, serving a web page or training a spreadsheet do not have that shape.

02Scaling, not speed

classical search: O (2^{n}) Grover: O (2^{n}) = O (2^{n /2})

Searching 2^n unsorted candidates. For n = 10 the difference is 1024 against 32 steps; for n = 60 it is 10^18 against 10^9. Each quantum step is slower than a classical one, so the advantage only appears at scale.

03The three ingredients

Ingredient	What it gives you	Where you will meet it
Superposition	A register of n qubits carries amplitudes for all 2^n bit strings at once.	Lesson 3 and the Hadamard gate
Interference	Amplitudes add like waves: wrong answers can cancel, right answers can reinforce.	Deutsch–Jozsa and Grover
Entanglement	Correlations between qubits that no classical description of each qubit alone can reproduce.	The Bell state in Gates and Circuits

Hands-on

A first look

Open this two-qubit circuit and press Simulate. Only 00 and 11 come out. Nothing classical built from two independent coins behaves like this; the rest of the course explains why.

OpenQASM 3

OPENQASM 3.0;
include "stdgates.inc";
qubit[2] q;
bit[2] c;
h q[0];
cx q[0], q[1];
c = measure q;

Open in the IDE Open in the Playground

Knowledge check

2 questions · one try each counts

Question 1

Which statement about quantum computers is accurate?

Question 2

Why does Shor's algorithm matter for security?

01Two problems that motivate the field

Factoring and discrete logarithms. Much of today's public-key cryptography rests on the belief that factoring a 600-digit number is hopeless. Shor's algorithm factors in polynomial time on a large, error-corrected quantum computer, which is why post-quantum cryptography exists.
Simulating nature. Molecules, magnets and new materials are quantum systems. Writing down the state of 50 interacting electrons exactly needs more numbers than there are atoms on Earth; a quantum computer stores that state in 50 qubits.

03The three ingredients

Ingredient	What it gives you	Where you will meet it
Superposition	A register of n qubits carries amplitudes for all 2^n bit strings at once.	Lesson 3 and the Hadamard gate
Interference	Amplitudes add like waves: wrong answers can cancel, right answers can reinforce.	Deutsch–Jozsa and Grover
Entanglement	Correlations between qubits that no classical description of each qubit alone can reproduce.	The Bell state in Gates and Circuits