Drafted from the themes and structure of Chapter 1 of Quantum Computing: A Gentle Introduction.

1. Why Quantum Computing?

Computer science usually begins by ignoring physics.

A bit is a 0 or a 1. An algorithm is a sequence of steps. A computer is any device that carries out those steps.

This abstraction is one of the great successes of twentieth-century science and engineering. It allows us to reason about algorithms, programming languages, communication protocols, and complexity without needing to know whether the machine is built from vacuum tubes, transistors, optical components, or something else.

Quantum computing begins with a different question:

What happens if the basic model of information is built directly on quantum mechanics?

This question does not merely ask whether we can build smaller or faster hardware. Classical computers already rely on quantum physics at the hardware level: transistors, lasers, and modern chips all depend on quantum effects.

A quantum computer is different because the information itself is represented and manipulated according to quantum rules.

The fundamental unit is no longer the bit, but the quantum bit, or qubit.

A qubit can behave like a bit when measured, but before measurement it can participate in phenomena with no classical counterpart:

• superposition,
• interference,
• measurement disturbance,
• entanglement.

These phenomena do not make quantum computers magically faster for every task. They do, however, make some forms of computation possible in dramatically different ways.

1.1 Learning goals

By the end of this chapter, you should be able to:

1. Explain why quantum computing is a new model of computation, not just a new kind of hardware.
2. Distinguish a classical bit from a qubit.
3. Describe why measurement matters in quantum computation.
4. Explain why entanglement is a central quantum resource.
5. Identify the roles of Shor’s algorithm, Grover’s algorithm, and quantum simulation.
6. Explain why quantum computers are powerful but not universal accelerators.
7. Understand the structure of the rest of the course.

1.2 Computation is physical

Every computation is carried out by a physical system.

A classical bit might be represented by:

• two voltage levels,
• a magnetic orientation,
• a switch position,
• a charge stored in a circuit,
• light being present or absent.

The mathematical model abstracts away those details. We say only that the bit is 0 or 1.

That abstraction is powerful. It lets us design algorithms without caring about the microscopic physics of the machine.

But it also hides an assumption.

Traditional models of computation are based on classical physics. The Turing machine, Boolean circuits, and ordinary programming languages all assume that information behaves classically: data has definite values, can be copied, can be read without disturbance, and can be manipulated by classical logical operations.

Quantum mechanics tells us that microscopic physical systems do not always behave this way.

So we ask:

If information is physical, and the physical world is quantum mechanical, what is the right model of computation?

Quantum computing is one answer to that question.

1.3 Bits and qubits

A classical bit has two possible values:

10 or 1

A qubit also has two distinguished classical-looking states, written

1|0> and |1>

These are pronounced “ket zero” and “ket one.” The notation comes from Dirac notation, which is standard in quantum mechanics and quantum information.

But a qubit is not limited to these two states. A qubit may also be in a state of the form

1a|0> + b|1>

where a and b are complex numbers called amplitudes.

These amplitudes satisfy

1|a|^2 + |b|^2 = 1

The values |a|^2 and |b|^2 determine the probabilities of seeing 0 or 1 if the qubit is measured in the standard basis.

This is the first major difference between bits and qubits.

A qubit is sometimes described as being “both 0 and 1 at the same time.” This phrase can be useful as a first intuition, but it is also misleading.

A qubit is not merely a hidden classical bit whose value we do not know. A quantum superposition is a definite quantum state, and different superpositions can behave differently even if they give the same measurement probabilities in one basis.

For example, the states

11/sqrt(2) (|0> + |1>)

and

11/sqrt(2) (|0> - |1>)

both give 0 and 1 with equal probability when measured in the standard basis. But they are different quantum states. Later transformations can distinguish them.

That difference is one of the places where quantum computation gets its power.

1.4 Measurement is not passive

In classical computing, reading a bit ideally does not change it.

If a classical bit is 0, we can read it many times and keep getting 0.

Quantum measurement is different.

Suppose a qubit is in the state

1a|0> + b|1>

If we measure it in the standard basis, we obtain:

10 with probability |a|^2
21 with probability |b|^2

After the measurement, the qubit is no longer in the original superposition. It has become the state corresponding to the observed result.

If the outcome was 0, the new state is

1|0>

If the outcome was 1, the new state is

1|1>

A second measurement in the same basis gives the same result with certainty.

This has two important consequences.

First, measurement is the only way to extract classical information from a quantum state.

Second, measurement usually destroys some of the information present in the quantum state.

This is why a qubit cannot be treated as a classical object storing an infinite amount of information. Even though the amplitudes a and b range over infinitely many possible values, a single measurement of a single qubit produces only one classical bit of information.

1.5 Superposition is useful only when combined with interference

A quantum computer can place a register of qubits into a superposition of many classical states.

For example, n qubits can be put into a state involving all 2^n bit strings:

11/sqrt(2^n) sum_x |x>

where the sum ranges over all n-bit strings x.

This fact is sometimes called quantum parallelism.

It is tempting to say that the quantum computer has computed on all possible inputs at once. There is some truth in this picture, but it is incomplete and often misleading.

The problem is measurement.

If we simply measure the final superposition, we do not get all 2^n answers. We get one outcome.

Quantum algorithms must do something more subtle. They must arrange the computation so that amplitudes leading to wrong or unwanted answers cancel, while amplitudes leading to useful answers reinforce.

This process is called interference.

A useful mental model is:

Superposition creates many possible computational paths. Interference determines which paths survive measurement.

Quantum algorithms are designed around this principle.

1.6 Entanglement

When we combine classical systems, the state of the whole system is determined by the states of its parts.

For example, if one classical bit is 0 and another is 1, the two-bit system is in state

101

Quantum systems are different.

Two qubits may be in a state such as

11/sqrt(2) (|00> + |11>)

This state is called an entangled state.

It cannot be described by assigning a separate state to the first qubit and a separate state to the second qubit. The two qubits have a joint state that is not reducible to individual states of the parts.

Entanglement is one of the central features of quantum information.

It plays a role in:

• quantum algorithms,
• quantum teleportation,
• dense coding,
• quantum key distribution,
• quantum error correction,
• quantum communication complexity.

Entanglement also explains why simulating quantum systems on classical computers can be difficult. A system of n qubits is described by a state space whose dimension grows like 2^n. For even moderately large n, this becomes enormous.

This observation was one of the original motivations for quantum computing: perhaps quantum systems are hard to simulate classically because they are naturally doing something that classical systems do not easily reproduce.

1.7 What quantum computing is not

Quantum computing is often described carelessly. It is important to separate the real claims from the hype.

Quantum computing is not just faster hardware.

Classical computers already use quantum mechanics in their physical components. A classical computer built from smaller transistors is still a classical computer if it stores and processes information as classical bits.

Quantum computing is also not the same as optical computing, DNA computing, or other alternative physical implementations of classical computation. Those approaches may change the physical substrate, but they do not necessarily change the model of information.

Quantum computing changes the model.

It uses qubits rather than bits and quantum transformations rather than purely classical logical operations.

Quantum computing is also not a universal way to make every algorithm faster.

It does not make hard problems automatically easy. It does not solve all NP-complete problems efficiently, as far as anyone knows. It is not simply classical parallel computation with exponentially many processors.

The power of quantum computation is real, but specialized.

1.8 Why people became excited

Quantum information processing developed from several independent insights.

Quantum cryptography

Charles Bennett and Gilles Brassard, building on ideas of Stephen Wiesner, showed that quantum measurement could be used to establish secret cryptographic keys.

The resulting protocol, now called BB84, uses the fact that measuring an unknown quantum state can disturb it. This disturbance can reveal the presence of an eavesdropper.

This was one of the first practical-looking applications of quantum information.

Quantum simulation

Richard Feynman, Yuri Manin, and others observed that quantum systems can be extremely hard to simulate efficiently on classical computers.

Their idea was simple and profound:

If nature is quantum mechanical, perhaps the most natural computer for simulating quantum systems is itself quantum mechanical.

Quantum simulation remains one of the most important potential applications of quantum computing.

Quantum models of computation

David Deutsch introduced a formal model of a quantum computer. Later work by Bernstein, Vazirani, Yao, and others refined the model and related it to classical computation.

One crucial result is that quantum computers can simulate classical computation efficiently. In that sense, quantum computation is at least as powerful as classical computation.

The deeper question is whether it is more powerful.

1.9 Shor’s algorithm

In 1994, Peter Shor gave a quantum algorithm for factoring integers in polynomial time.

This was a turning point.

Factoring is the problem of decomposing an integer into prime factors. For example:

121 = 3 x 7

For very large numbers, factoring appears to be hard for classical computers. Many cryptographic systems, including RSA, rely on this difficulty.

Shor’s algorithm showed that a sufficiently large and reliable quantum computer could factor large integers efficiently.

This does not prove that no efficient classical factoring algorithm exists. But it showed that quantum computation could solve a famous and practically important problem in a radically different way.

Shor’s algorithm is one of the main reasons quantum computing became a major research field.

In this course, Shor’s algorithm will appear after we have developed:

• qubits,
• quantum gates,
• reversible computation,
• quantum Fourier transforms,
• period finding.

1.10 Grover’s algorithm

Soon after Shor’s algorithm, Lov Grover discovered a quantum algorithm for unstructured search.

Suppose we have a large unsorted list of N items, and exactly one item satisfies some condition. Classically, finding the item requires checking about N possibilities in the worst case.

Grover’s algorithm finds the item using about

1sqrt(N)

queries.

This is a quadratic speedup.

That is significant, but it is not exponential. Grover’s algorithm is important partly because it shows both the power and the limits of quantum computation.

For unstructured search, the quadratic speedup is the best possible quantum improvement.

This means quantum computers do not simply make brute force search exponentially faster.

1.11 Quantum error correction

Quantum systems are fragile.

They interact with their environment. These unwanted interactions can destroy superpositions and entanglement. This process is called decoherence.

At first, this seemed like a fatal obstacle.

Classical error correction works partly by copying information. But unknown quantum states cannot be copied perfectly. This is the no-cloning principle.

So how can quantum information be protected?

The surprising answer is quantum error correction.

Quantum error-correcting codes protect quantum information without copying unknown quantum states. They spread information across entangled states of multiple qubits in such a way that errors can be detected and corrected without directly measuring the encoded quantum information.

This discovery changed the outlook for quantum computing.

It showed that, at least in principle, reliable quantum computation may be possible even with imperfect physical devices.

Later in the course, we will study:

• bit-flip and phase-flip errors,
• simple quantum codes,
• stabilizer codes,
• fault-tolerant computation,
• threshold theorems.

1.12 What quantum computers may be useful for

The best-known applications of quantum computing fall into several categories.

Factoring and number theory

Shor’s algorithm factors integers efficiently and also solves related problems such as discrete logarithms.

These problems are important in cryptography.

Search and optimization subroutines

Grover’s algorithm gives a quadratic speedup for unstructured search. More general amplitude amplification techniques extend this idea.

This can improve some algorithms, but usually not exponentially.

Quantum simulation

Quantum computers may efficiently simulate quantum systems that are difficult for classical computers to simulate.

This is important for:

• chemistry,
• materials science,
• condensed matter physics,
• high-energy physics,
• quantum device design.

Quantum communication

Entanglement enables communication tasks with no classical counterpart, including:

• dense coding,
• teleportation,
• entanglement-based key distribution.

Insight into computation and physics

Even when no immediate application is available, quantum information gives new ways to understand:

• computation,
• probability,
• measurement,
• entanglement,
• complexity,
• physical law.

Quantum computing is not only about building faster machines. It is also about understanding what computation means in a quantum universe.

1.13 What this course will do

This course is organized into three main parts.

Part I: Quantum building blocks

We begin with the basic objects of quantum information.

You will learn about:

• single qubits,
• measurement,
• multiple-qubit systems,
• tensor products,
• entanglement,
• quantum gates,
• quantum circuits,
• reversible classical computation,
• quantum versions of classical computations.

The goal of Part I is to build the mathematical and computational language needed for quantum algorithms.

Part II: Quantum algorithms

Next we study algorithms that use genuinely quantum effects.

Topics include:

• quantum parallelism,
• interference,
• Deutsch’s algorithm,
• Deutsch-Jozsa,
• Bernstein-Vazirani,
• Simon’s algorithm,
• quantum Fourier transforms,
• Shor’s algorithm,
• Grover’s algorithm,
• amplitude amplification.

The goal of Part II is to understand how quantum algorithms gain speedups and what kinds of problems they help with.

Part III: Entanglement, noise, and robustness

Finally, we study quantum systems as parts of larger systems.

Topics include:

• mixed states,
• density operators,
• decoherence,
• quantum error correction,
• stabilizer codes,
• fault tolerance,
• alternative models of quantum computation,
• open questions about the source of quantum speedup.

The goal of Part III is to understand why quantum computation is difficult to build and how it can be made robust.

1.14 Running example: a first measurement simulation

Before we develop the full mathematical model, we can simulate one small piece of quantum behavior: measurement statistics.

The following code does not simulate a full qubit. It only simulates repeated measurements with fixed probabilities.

 1import random
 2from collections import Counter
 3
 4def measure_qubit(prob_zero, shots=1000):
 5    """
 6    Simulate repeated measurements of a qubit-like system.
 7
 8    prob_zero:
 9        Probability of measuring 0.
10
11    shots:
12        Number of repeated measurements.
13    """
14    results = []
15
16    for _ in range(shots):
17        if random.random() < prob_zero:
18            results.append(0)
19        else:
20            results.append(1)
21
22    return Counter(results)
23
24measure_qubit(0.5, shots=1000)

Try changing the value of prob_zero.

For example:

1measure_qubit(0.8, shots=1000)

This gives a useful first picture of measurement probabilities.

But it is not yet a quantum simulation.

A full qubit simulation must also include:

• amplitudes,
• complex numbers,
• phase,
• change of basis,
• unitary transformations,
• interference.

Those are the topics of the next chapters.

1.15 Concept check

Answer these before moving on.

Question 1

Why is quantum computing not simply the same thing as building classical computers out of quantum devices?

Question 2

What is the main difference between a bit and a qubit?

Question 3

Why does measurement prevent us from extracting unlimited classical information from a qubit?

Question 4

Why was Shor’s algorithm such an important discovery?

Question 5

What does Grover’s algorithm tell us about both the power and the limits of quantum computing?

Question 6

Why is quantum error correction surprising?

1.16 Short answers

Answer 1

Classical computers may use quantum physics in their hardware, but they still represent and manipulate information as classical bits. Quantum computers represent and manipulate information as quantum states.

Answer 2

A classical bit has value 0 or 1. A qubit may be in a state a|0> + b|1>, and its behavior depends on amplitudes, phase, transformations, and measurement.

Answer 3

A measurement gives only one classical outcome and usually changes the quantum state. A single qubit measurement yields at most one classical bit of information.

Answer 4

Shor’s algorithm showed that a quantum computer could factor integers in polynomial time, threatening cryptographic systems based on the assumed classical hardness of factoring.

Answer 5

Grover’s algorithm gives a quadratic speedup for unstructured search, but no more than that. It shows that quantum speedups can be real but limited.

Answer 6

Quantum error correction is surprising because unknown quantum states cannot be copied, and measurement can disturb quantum information. Nevertheless, quantum information can be protected by encoding it across multiple qubits.

1.17 Reflection

Write a short paragraph answering the following question:

Why should quantum computing be understood as a new model of computation rather than merely a new hardware technology?

A good answer should mention:

• bits versus qubits,
• quantum measurement,
• superposition or entanglement,
• the fact that classical computers can already use quantum hardware without being quantum computers.

1.18 Key terms

1.19 Summary

Quantum computing begins from the idea that information is physical.

Classical computing abstracts away physics and treats information as bits. Quantum computing replaces this classical model with one based on quantum mechanics.

The central unit is the qubit. Qubits can be placed in superpositions, transformed by quantum operations, entangled with other qubits, and measured to produce classical outcomes.

Quantum computers are not universal accelerators. They appear to offer major advantages for some special tasks, including factoring, quantum simulation, and certain search and hidden-structure problems. They also impose severe limitations: measurement reveals only limited information, unknown quantum states cannot be copied, and quantum systems are fragile.

The rest of this course develops the mathematical, computational, and physical ideas needed to understand how quantum algorithms work and how quantum information can be protected.

1.20 What comes next

In the next chapter, we study the simplest quantum system: a single qubit.

We will use photon polarization as a motivating example and introduce:

• state vectors,
• Dirac notation,
• measurement probabilities,
• basis dependence,
• global and relative phase,
• the Bloch sphere.

The goal is to move from the broad ideas of this chapter to the precise mathematical model used throughout quantum computing.