Quantum Algorithms and Complexity

Chapter 2
Quantum Information and Computation Models

Diploma in Quantum Computing
Quantum Algorithms and Complexity   •   Diploma

Quantum Information and Computation Models

Introduction

Quantum computing is a model of computation based on the laws of quantum mechanics. Unlike classical computers, which manipulate bits with definite values 0 or 1, quantum computers manipulate quantum states that may encode combinations of classical possibilities. This difference does not mean that a quantum computer simply tries every answer simultaneously and reads all answers at once. Rather, quantum algorithms exploit superposition, interference, entanglement, and measurement to transform probability amplitudes so that useful outcomes become more likely.

This chapter introduces the information-processing principles needed for the study of quantum algorithms and complexity. It develops the qubit model, explains measurement and entanglement, introduces unitary transformations and quantum gates, and describes how quantum circuits and oracle models are represented. It also compares the circuit model with alternative models such as adiabatic and measurement-based quantum computation.

Learning Objectives

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

  1. Represent a qubit using Dirac notation and probability amplitudes.
  2. Explain superposition, measurement, interference, and entanglement.
  3. Describe unitary transformations and common one- and two-qubit gates.
  4. Explain the no-cloning theorem and its implications.
  5. Identify universal gate sets and read basic quantum-circuit notation.
  6. Distinguish state preparation, computation, measurement, and classical post-processing.
  7. Explain oracle models and their role in algorithm design and complexity analysis.
  8. Compare circuit, adiabatic, measurement-based, and quantum-Turing-machine models.

1. Classical and Quantum Information

A classical bit is a physical system with two distinguishable logical states, conventionally written 0 and 1. A classical register of n bits can hold one string from a set of 2ⁿ possible strings at any instant. Classical logic gates transform these strings, usually through deterministic or probabilistic operations.

A quantum bit, or qubit, is a two-dimensional quantum system. Examples include the spin of an electron, two energy levels of an atom, or two polarization states of a photon. The computational basis states are written |0⟩ and |1⟩. A general pure qubit state is

|ψ⟩ = α|0⟩ + β|1⟩

where α and β are complex probability amplitudes satisfying

|α|² + |β|² = 1

The normalization condition ensures that the total probability of all measurement outcomes is one. The symbol |z| denotes the complex magnitude of z. A global phase multiplying the entire state, such as e^{iγ}|ψ⟩, has no observable effect, whereas a relative phase between α and β can affect later interference.

The state α|0⟩ + β|1⟩ is not a classical probabilistic mixture. In a classical mixture, the system is in either 0 or 1, but our knowledge is incomplete. In a quantum superposition, amplitudes can interfere before measurement. This distinction is central to quantum algorithms.

Vector and matrix representation

Using column vectors, the computational basis is represented as

|0⟩ = [1, 0]ᵀ, |1⟩ = [0, 1]ᵀ

Thus, a qubit may be written as

|ψ⟩ = [α, β]ᵀ

A bra is the conjugate transpose of a ket. For example, ⟨ψ| is the conjugate transpose of |ψ⟩. The inner product ⟨ψ|ψ⟩ gives the squared norm of the state and equals 1 for a normalized state.

2. Superposition and Measurement

The defining computational feature of a qubit is superposition. For example, the state

|+⟩ = (|0⟩ + |1⟩)/√2

assigns equal amplitudes to |0⟩ and |1⟩. Measurement in the computational basis produces 0 with probability 1/2 and 1 with probability 1/2. More generally, measuring α|0⟩ + β|1⟩ in this basis produces:

OutcomeProbability
0
1

After the measurement, the state is projected onto the observed basis state. This is often called state collapse. Measurement is therefore not merely passive observation; it changes the state and generally destroys information about the original amplitudes.

Worked example: measurement probabilities

Suppose

|ψ⟩ = (√3/2)|0⟩ + (1/2)|1⟩

The state is normalized because (√3/2)² + (1/2)² = 3/4 + 1/4 = 1. A computational-basis measurement gives 0 with probability 3/4 and 1 with probability 1/4. If the result is 0, the post-measurement state is |0⟩; if the result is 1, it is |1⟩.

Measurement in another basis

Measurement need not use the computational basis. The Hadamard basis consists of

|+⟩ = (|0⟩ + |1⟩)/√2, |−⟩ = (|0⟩ − |1⟩)/√2

The state |0⟩ gives equal probabilities for + and − when measured in this basis. However, |+⟩ gives a definite + result. Consequently, the meaning of a state depends on the measurement basis.

3. Bloch-Sphere Representation

Every pure single-qubit state can be represented, apart from a global phase, as

|ψ⟩ = cos(θ/2)|0⟩ + eiφsin(θ/2)|1⟩

where θ is a polar angle and φ is an azimuthal angle. The Bloch sphere provides a geometric representation of this state. The north and south poles correspond to |0⟩ and |1⟩. The equator contains equal-magnitude superpositions whose relative phase varies with φ.

The Bloch sphere is useful for visualizing single-qubit rotations, but it cannot directly represent arbitrary multi-qubit states. As the number of qubits increases, the state space grows exponentially and entanglement becomes important.

4. Multiple Qubits and Tensor Products

The joint state of two qubits is described using the tensor product. For example,

|0⟩⊗|1⟩ = |01⟩

The computational basis for two qubits is |00⟩, |01⟩, |10⟩, and |11⟩. A general two-qubit state is

|ψ⟩ = a|00⟩ + b|01⟩ + c|10⟩ + d|11⟩

with

|a|² + |b|² + |c|² + |d|² = 1

For n qubits, the state vector has 2ⁿ computational-basis amplitudes. This exponential state-space dimension is one source of quantum computational power, although it does not by itself guarantee an exponential speed-up.

A state is separable if it can be written as a tensor product of individual states. For example,

(|0⟩ + |1⟩)/√2 ⊗ |0⟩

is separable. A state that cannot be expressed this way is entangled.

5. Entanglement

An important entangled state is the Bell state

|Φ⁺⟩ = (|00⟩ + |11⟩)/√2

If the first qubit is measured in the computational basis and gives 0, the second is also 0. If the first gives 1, the second is also 1. Each individual result is random, but the results are perfectly correlated.

Entanglement is not equivalent to ordinary classical correlation. The correlations of entangled systems cannot, in general, be explained by assigning independent pre-existing classical values to each qubit. Experiments testing Bell inequalities support the quantum prediction, subject to careful treatment of experimental assumptions.

Entanglement is used in quantum teleportation, superdense coding, quantum error correction, distributed quantum computing, and several quantum algorithms. It is also a resource requiring control: unwanted interaction with the environment can create decoherence and destroy useful quantum correlations.

6. Unitary Transformations

An isolated quantum system evolves through a unitary operator U. A matrix is unitary when

U†U = UU† = I

where U† is the conjugate transpose and I is the identity matrix. If |ψ⟩ is normalized, then U|ψ⟩ is also normalized. This follows because

⟨ψ|U†U|ψ⟩ = ⟨ψ|ψ⟩ = 1

Unitary evolution is reversible: the inverse operation is U†. Quantum computation therefore applies reversible transformations until measurement or interaction with an environment occurs.

A general quantum operation involving noise may not be unitary on the system alone. It can be represented more generally by a quantum channel, often using Kraus operators. At diploma level, the circuit model usually treats ideal gates as unitary and noise as an additional physical imperfection.

7. Quantum Gates

A quantum gate is a controlled unitary transformation. Common single-qubit gates include:

GateMatrixMain action
X[[0,1],[1,0]]Exchanges
Y[[0,−i],[i,0]]Bit-and-phase transformation
Z[[1,0],[0,−1]]Changes the phase of
H(1/√2)[[1,1],[1,−1]]Creates or removes balanced superposition

The Pauli-X gate acts like a classical NOT gate. The Z gate leaves |0⟩ unchanged and maps |1⟩ to −|1⟩. The Hadamard gate satisfies H|0⟩ = |+⟩ and H|1⟩ = |−⟩.

Parameterized rotations are also important. For example, a rotation around the z-axis is

Rz(λ) = [[e^(−iλ/2), 0], [0, e^(iλ/2)]]

where λ is a real angle measured in radians. Different hardware platforms implement different native gate sets, but many gates can be compiled into available rotations.

Controlled gates

A controlled-NOT, or CNOT, acts on a control qubit and a target qubit. It flips the target if and only if the control is |1⟩:

|a,b⟩ → |a, b ⊕ a⟩

where a and b are bits and ⊕ denotes addition modulo 2. Thus |00⟩ maps to |00⟩, |01⟩ to |01⟩, |10⟩ to |11⟩, and |11⟩ to |10⟩.

Applying H to the first qubit of |00⟩ and then CNOT produces

|00⟩ → (|00⟩ + |10⟩)/√2 → (|00⟩ + |11⟩)/√2

which is the Bell state |Φ⁺⟩. This illustrates how a simple circuit creates entanglement.

8. No-Cloning Theorem

The no-cloning theorem states that no physical operation can perfectly copy an arbitrary unknown quantum state. Suppose a unitary copier U existed such that

U(|ψ⟩|0⟩) = |ψ⟩|ψ⟩

for every |ψ⟩. For two possible states |ψ⟩ and |φ⟩, preservation of inner products would require

⟨ψ|φ⟩ = (⟨ψ|φ⟩)²

This is generally false unless the states are identical or orthogonal. Therefore arbitrary unknown quantum states cannot be copied.

The theorem does not prohibit copying a known basis state when the set of possible states is orthogonal. A CNOT can copy computational-basis information when the target begins in |0⟩, but it does not copy an arbitrary superposition without entangling the systems. No-cloning is relevant to quantum cryptography, error correction, and the design of quantum memories.

9. Quantum-Circuit Notation

A quantum circuit is read from left to right. Horizontal wires represent qubits; boxes represent gates; measurement symbols indicate conversion to classical data. A controlled operation is shown by a control dot connected to a target symbol. Classical wires are often drawn separately from quantum wires.

A typical computation has four stages:

  1. Initialization: qubits are prepared, commonly in |0⟩ states.
  2. State preparation: gates create superpositions or entanglement.
  3. Oracle and processing: problem-dependent transformations and interference are applied.
  4. Measurement and post-processing: classical outcomes are recorded and interpreted.

Circuit depth is the length of the longest sequence of dependent gates. Gate count measures the number of gates, although weighted or hardware-specific costs may be more informative. Width is the number of qubits used. These resources contribute to the practical and theoretical complexity of a circuit.

10. Universal Gate Sets

A gate set is universal if circuits constructed from its gates can approximate any unitary transformation to arbitrary accuracy, subject to sufficient circuit length. Exact universality and approximate universality should be distinguished.

The set consisting of all single-qubit unitary gates together with CNOT is universal. A finite set such as Clifford gates plus the T gate is approximately universal. Clifford gates include H, S, and CNOT, where

S = [[1,0],[0,i]]

and the T gate is

T = [[1,0],[0,e^(iπ/4)]]

Clifford-only circuits can be efficiently simulated classically under important restrictions, a fact formalized by the Gottesman–Knill theorem. Adding a non-Clifford gate such as T enables universal quantum computation, although fault-tolerant implementations may require many resources for non-Clifford operations.

In practice, a compiler decomposes an abstract circuit into a device’s native gates. This process may increase depth, introduce SWAP operations to satisfy connectivity constraints, and affect error rates.

11. Oracle Models

An oracle is an abstract black-box operation that provides access to a function or structured information. Oracle models allow algorithm designers to count queries separately from other computation.

For a Boolean function f:{0,1}ⁿ → {0,1}, a standard reversible oracle is

Uf|x,y⟩ = |x, y ⊕ f(x)⟩

where x is an n-bit input, y is a one-bit target, and ⊕ is XOR. The transformation is reversible because applying U_f twice returns the original state.

If the target is prepared in

|−⟩ = (|0⟩ − |1⟩)/√2

then phase kickback occurs:

Uf(|x⟩|−⟩) = (−1)f(x)|x⟩|−⟩

The function value is transferred to the phase of the input register without directly measuring f(x). This mechanism appears in Deutsch–Jozsa, Bernstein–Vazirani, Simon’s, and Grover’s algorithms.

Oracle complexity counts how many times an algorithm invokes U_f. It is a query-complexity measure, not necessarily the total physical runtime. An oracle may conceal the cost of evaluating or implementing the function, so claims of speed-up must state clearly what is being counted.

12. Alternative Computational Models

The circuit model is the dominant language for quantum algorithms, but other equivalent or related models clarify different aspects of computation.

Quantum Turing machines

A quantum Turing machine extends the classical Turing-machine idea by allowing a superposition of configurations and unitary transitions. It is useful for defining computability and complexity classes, although it is less convenient for programming hardware directly.

Measurement-based quantum computation

In measurement-based quantum computation, a highly entangled resource state, commonly a cluster state, is prepared first. Computation proceeds through adaptive single-qubit measurements. Measurement outcomes determine later measurement bases, and classical feed-forward is essential. The model emphasizes entanglement as a computational resource.

Adiabatic and quantum annealing models

Adiabatic quantum computation encodes a problem in the ground state of a Hamiltonian and changes the Hamiltonian slowly enough that the system remains near its instantaneous ground state. In ideal conditions, the required runtime depends on the minimum spectral gap and the rate at which the Hamiltonian changes. Quantum annealing is related but may be designed as a heuristic optimization process and need not implement a universal fault-tolerant computation.

Topological models

Topological quantum computation stores information in nonlocal degrees of freedom associated with exotic quasiparticles called anyons. Computation is performed by braiding or measuring these excitations. The model aims to obtain intrinsic protection from certain local errors, although practical realization remains a major experimental challenge.

These models can simulate one another under suitable assumptions, but equivalence of computational power does not imply equal engineering cost, noise tolerance, or ease of programming.

13. Case Study: Creating and Using an Entangled Pair

Illustrative case. A laboratory team is developing a two-qubit educational demonstrator using superconducting qubits. The objective is to prepare a Bell state and verify its correlations.

Background and problem. Each qubit can be initialized in |0⟩, manipulated by calibrated microwave pulses, and measured in the computational basis. The team must create entanglement rather than merely produce two independently random bits.

Approach. The circuit applies H to qubit 1 followed by CNOT with qubit 1 as control and qubit 2 as target. Ideally, the final state is

|Φ⁺⟩ = (|00⟩ + |11⟩)/√2

The team repeats the circuit many times. In the computational basis, ideal results are 00 and 11, each with probability 1/2; 01 and 10 should not occur. The team then measures both qubits in another basis, such as the X basis, to test correlations that cannot be assessed using only one measurement setting.

Analysis and outcome. Real devices produce occasional 01 and 10 results because of gate error, readout error, decoherence, and imperfect initialization. The observed distribution is compared with the ideal distribution using a fidelity or correlation metric. Calibration may improve the result, but no finite experiment proves perfect entanglement; statistical uncertainty and experimental assumptions must be considered.

Learning points. The case distinguishes state preparation from measurement, demonstrates the role of CNOT in entanglement generation, and shows why theoretical circuits must be evaluated against hardware noise. It also illustrates that quantum advantage requires reliable control, not only a large Hilbert space.

14. Limitations, Engineering Issues, and Governance

Quantum information is fragile. Decoherence results from unwanted interaction with the environment and causes loss of phase relationships. Gate errors, leakage outside the computational subspace, crosstalk, measurement error, and limited qubit connectivity affect real circuits. Error correction can protect logical information, but it requires additional physical qubits and repeated syndrome measurements.

A practical quantum algorithm should therefore consider:

  • the number and type of qubits required;
  • circuit depth and two-qubit-gate count;
  • device connectivity and compilation overhead;
  • initialization and measurement fidelity;
  • error mitigation or fault-tolerant requirements;
  • the number of repetitions needed for statistical confidence;
  • whether the oracle or data-loading procedure dominates the cost.

Quantum technology also raises governance issues. Quantum computers may threaten some currently deployed public-key cryptosystems when sufficiently large fault-tolerant machines become available. Organizations should assess migration to post-quantum cryptography rather than waiting for a cryptographically relevant machine. Claims about quantum advantage should identify the benchmark, data-loading assumptions, error model, comparison baseline, and complete resource accounting.

Chapter Summary

A qubit is a normalized complex superposition of |0⟩ and |1⟩. Measurement probabilities are determined by squared amplitude magnitudes, and measurement generally changes the state. Multiple qubits are described using tensor products; entangled states cannot be decomposed into independent single-qubit states. Ideal quantum computation uses unitary, reversible transformations, while measurement produces classical outcomes.

Quantum gates such as X, Z, H, phase rotations, and CNOT form the building blocks of circuits. Universal gate sets can approximate arbitrary quantum transformations, and compiler decomposition connects abstract algorithms with hardware-native operations. The no-cloning theorem prevents perfect copying of unknown quantum states. Oracle models represent black-box access and support query-complexity analysis, but oracle speed-ups do not automatically imply practical speed-ups. Circuit, quantum-Turing-machine, measurement-based, adiabatic, annealing, and topological models provide different descriptions of quantum computation. Practical performance depends on noise, connectivity, compilation, error correction, and honest resource accounting.

Key Terms

Qubit: A two-level quantum information system.

Computational basis: The basis consisting of |0⟩ and |1⟩.

Superposition: A linear combination of basis states with complex amplitudes.

Probability amplitude: A complex coefficient whose squared magnitude determines measurement probability.

Normalization: The requirement that total measurement probability equals one.

Relative phase: The phase difference between components of a quantum state.

Measurement: A physical process that produces a classical outcome and changes the quantum state.

Tensor product: The mathematical operation used to combine quantum systems.

Entanglement: A nonseparable relationship between quantum systems.

Unitary operator: A reversible transformation U satisfying U†U = I.

Quantum gate: A controlled unitary operation in a quantum circuit.

CNOT: A controlled-NOT gate that flips a target when its control is 1.

No-cloning theorem: The result that arbitrary unknown quantum states cannot be perfectly copied.

Universal gate set: A collection of gates capable of approximating arbitrary quantum operations.

Quantum circuit: A time-ordered network of quantum gates, measurements, and wires.

Oracle: An abstract black-box operation used in algorithm and query-complexity analysis.

Phase kickback: Transfer of a function value into the phase of a quantum state.

Circuit depth: The longest sequence of dependent gate layers.

Decoherence: Loss of quantum coherence through environmental interaction.

Quantum channel: A general physical transformation that may include noise and measurement.

Review Questions

Short Answer Questions

  1. What is the normalization condition for a pure qubit state?
  2. How does measurement in the computational basis determine probabilities?
  3. What is the main difference between a separable and an entangled state?
  4. Why must an ideal quantum gate be unitary?
  5. What does an oracle represent in quantum algorithm analysis?

Long Answer Questions

  1. Explain superposition, relative phase, and measurement, and distinguish a quantum superposition from a classical probabilistic mixture.
  2. Describe how a Hadamard gate followed by a CNOT gate creates the Bell state |Φ⁺⟩.
  3. State and explain the no-cloning theorem, including why inner-product preservation leads to a contradiction.
  4. Compare universal gate sets with hardware-native gate sets and discuss the role of compilation.
  5. Compare the circuit, measurement-based, and adiabatic models of quantum computation.

Analytical / Application Questions

  1. A qubit is prepared as (√3/2)|0⟩ + (1/2)|1⟩. Calculate the probabilities of the two computational-basis outcomes and describe the post-measurement states.
  2. Design a reversible oracle for a Boolean function f(x) and explain why the transformation |x,y⟩ → |x,y ⊕ f(x)⟩ is reversible.
  3. A proposed quantum application uses a shallow algorithm but requires costly data loading and thousands of noisy two-qubit gates. Evaluate whether a claimed practical speed-up is justified and identify the additional evidence required.

Multiple Choice Questions with Answers

Question 1

Which condition must a pure qubit state α|0⟩ + β|1⟩ satisfy?

A. |α| + |β| = 1

B. |α|² + |β|² = 1

C. α + β = 0

D. αβ = 1

Correct Answer: B. |α|² + |β|² = 1

Question 2

What is the probability of measuring 1 in the state (√3/2)|0⟩ + (1/2)|1⟩?

A. 1/8

B. 1/4

C. 1/2

D. 3/4

Correct Answer: B. 1/4

Question 3

Which state is entangled?

A. |0⟩⊗|1⟩

B. |+⟩⊗|0⟩

C. (|00⟩ + |11⟩)/√2

D. |1⟩⊗|1⟩

Correct Answer: C. (|00⟩ + |11⟩)/√2

Question 4

What does the CNOT gate do when its control qubit is |0⟩?

A. It always flips the target

B. It measures the target

C. It applies a phase of −1 to the target

D. It leaves the target unchanged

Correct Answer: D. It leaves the target unchanged

Question 5

Which equation defines a unitary operator U?

A. U + U† = I

B. U†U = I

C. U² = 0

D. det(U) = 0

Correct Answer: B. U†U = I

Question 6

What does the no-cloning theorem prohibit?

A. Measuring a computational-basis state

B. Applying a Hadamard gate

C. Perfectly copying an arbitrary unknown quantum state

D. Preparing two identical known states

Correct Answer: C. Perfectly copying an arbitrary unknown quantum state

Question 7

What is the main purpose of a universal gate set?

A. To guarantee zero hardware noise

B. To perform only classical reversible computation

C. To approximate arbitrary quantum transformations

D. To eliminate the need for measurement

Correct Answer: C. To approximate arbitrary quantum transformations

Question 8

In the oracle transformation Uf|x,y⟩ = |x,y ⊕ f(x)⟩, what operation is ⊕?

A. Ordinary addition

B. Multiplication

C. Addition modulo 2

D. Complex conjugation

Correct Answer: C. Addition modulo 2

Question 9

What is phase kickback?

A. Copying a quantum state to a second register

B. Transferring function information into the phase of an input state

C. Removing all relative phases by measurement

D. Changing a unitary gate into a classical gate

Correct Answer: B. Transferring function information into the phase of an input state

Question 10

Which model performs computation through adaptive measurements on an entangled resource state?

A. Measurement-based quantum computation

B. Classical Boolean computation

C. Standard binary search

D. A deterministic finite automaton

Correct Answer: A. Measurement-based quantum computation
Quantum Algorithms and Complexity
Chapter 2 of 14