Why quantum computing?

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

You will learn to

Name two problem families where quantum algorithms scale better than the best known classical ones.
Explain why 'faster' is the wrong word and 'scales differently' is the right one.
Recognise 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.

Two 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.

Scaling, 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.

The 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

Try it

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

Quiz 1 · 10 XP

Which statement about quantum computers is accurate?

Quiz 2 · 10 XP

Why does Shor's algorithm matter for security?

Key takeaway

A quantum computer is not a faster laptop. It is a different machine whose cost grows differently on problems with the right structure: factoring, search with structure, and simulating quantum nature itself.

Docs: how the field got here

Up next: Bits, qubits and notation

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