Mathematical and Computational Foundations

Introduction

Quantum algorithms are not studied in isolation from mathematics or classical computation. A quantum circuit is described using vectors, matrices, complex numbers, and probability amplitudes; its performance is evaluated using algorithmic complexity; and many quantum procedures are designed by transforming classical computational problems into reversible forms. A firm command of these foundations is therefore essential before analysing algorithms such as Deutsch–Jozsa, Grover’s search, and Shor’s factoring algorithm.

This chapter develops the prerequisite language for quantum algorithm analysis. It reviews complex vectors and matrices, tensor products, measurement probabilities, asymptotic notation, classical algorithms, Boolean functions, reversible computation, and the principal classes of classical complexity. The emphasis is on interpretation and use rather than on advanced proof techniques.

Learning Objectives

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

1. Represent complex vectors and matrices and use inner products, norms, adjoints, and unitary matrices.
2. Explain tensor products and construct multi-qubit state spaces.
3. Calculate measurement probabilities and distinguish amplitudes from probabilities.
4. Use Big-O, Big-Ω, and Big-Θ notation appropriately.
5. Describe classical algorithms using inputs, outputs, correctness, and resource bounds.
6. Define Boolean functions and explain oracle-style access to them.
7. Explain why reversible computation is central to quantum computing.
8. Distinguish important classical complexity classes and relate them to quantum algorithm analysis.

1. Complex Numbers and Quantum State Vectors

A complex number has the form z = a + bi, where a and b are real numbers and i² = -1. The real part is a, and the imaginary part is b. The complex conjugate of z is z^* = a - bi, and its modulus is

The modulus measures the magnitude of a complex number. A useful identity is z z^* = |z|². Complex numbers are required in quantum mechanics because interference depends on both magnitude and phase.

A column vector with complex entries is written as

The notation |v⟩ is called ket notation. Its conjugate transpose, or bra, is written ⟨v|. For example, if |v⟩ = (1 + i, 2)ᵀ, then ⟨v| = (1 − i, 2).

The inner product of two vectors |u⟩ and |v⟩ is

where the sum ranges over corresponding components. The inner product is a complex scalar. The norm, or length, of a vector is

A quantum state must be normalized, meaning ‖ψ‖ = 1. For a single qubit, the computational basis states are

A general pure qubit state is

where α and β are complex amplitudes satisfying

The normalization condition is not optional: it ensures that the total probability of all measurement outcomes is one. Amplitudes may be negative or complex, whereas probabilities are real and non-negative. The probability of observing 0 is |α|², and the probability of observing 1 is |β|².

Worked Example 1: Normalizing a State

Consider the vector |v⟩ = (1, i)ᵀ. Its squared norm is

Therefore, the normalized state is

Measurement probabilities are 1/2 for 0 and 1/2 for 1. The factor i changes phase but not these immediate measurement probabilities; it can nevertheless affect later interference.

2. Matrices and Linear Transformations

A matrix is a rectangular array of numbers representing a linear transformation. If A is an m × n matrix and |v⟩ is an n-component vector, then A|v⟩ is an m-component vector.

The adjoint, or conjugate transpose, of A is denoted A†. It is obtained by transposing the matrix and taking the complex conjugate of every entry. A matrix is Hermitian if

Hermitian matrices have real eigenvalues and are important in quantum measurement theory. A matrix is unitary if

where I is the identity matrix. Unitary transformations preserve inner products and norms:

Thus, if a state is normalized before a unitary operation, it remains normalized afterward. Quantum gates are represented by unitary matrices. Common one-qubit gates include:

The Hadamard gate is

It maps basis states according to

The minus sign in the second expression is a phase difference. It does not alter the individual probabilities when measured immediately, but it can change the result after additional gates.

For matrices A and B, multiplication is defined only when the dimensions are compatible. In general, matrix multiplication is not commutative: AB ≠ BA. This matters in circuits because gate order matters.

3. Tensor Products and Multi-Qubit Systems

The tensor product, written ⊗, combines vector spaces. If |u⟩ = (u₀,u₁)ᵀ and |v⟩ = (v₀,v₁)ᵀ, then

The state space of one qubit has dimension 2. The state space of n qubits has dimension 2ⁿ. The computational basis is

where every xᵢ is either 0 or 1. There are 2ⁿ such basis states.

A general pure n-qubit state is

with normalization condition

A state is a product state if it can be written as a tensor product of individual states. For example, |0⟩⊗|1⟩ is a product state. Some states cannot be expressed this way; they are entangled. The Bell state

is entangled. Its measurement outcomes are correlated: observing 0 on the first qubit guarantees 0 on the second, and similarly for 1. Entanglement is a property of the joint state, not merely a statement that two systems are individually random.

Tensor products also combine operators. If A acts on one subsystem and B on another, the combined operation is A ⊗ B. Its dimension grows rapidly, which explains both the expressive power and the simulation difficulty of quantum systems.

4. Measurement and Probability

For a state expressed in the computational basis,

measurement in that basis produces outcome x with probability

The probabilities satisfy 0 ≤ P(x) ≤ 1 and ∑ₓP(x)=1. Measurement generally changes the state. If a projective measurement produces outcome x, the post-measurement state is the corresponding basis state |x⟩, assuming an ideal computational-basis measurement and a non-degenerate outcome.

For a state |ψ⟩ and a projector P, the probability of that measurement result is

where P satisfies P²=P and P†=P. This expression applies to projective measurements and is consistent with the amplitude-squared rule for computational-basis projectors.

Classical probability describes uncertainty over alternatives. Quantum amplitudes additionally have phase, so alternatives can interfere before measurement. If two computational paths contribute amplitudes a and b, their combined probability is |a+b|², which equals |a|²+|b|²+2Re(a^*b). The final term is the interference term.

5. Asymptotic Notation and Resource Growth

Algorithm analysis studies how resource use grows with input size. Let f(n) and g(n) be non-negative functions for sufficiently large n.

We say f(n)=O(g(n)) if there are constants c>0 and n₀ such that

Big-O is an asymptotic upper bound. We say f(n)=Ω(g(n)) if there are constants c>0 and n₀ such that

Big-Ω is an asymptotic lower bound. Big-Θ means both bounds hold:

For example, 3n²+5n+7 = Θ(n²). The constants and lower-order terms do not affect the asymptotic class. Exponential growth, such as 2ⁿ, eventually dominates every polynomial n^k for fixed k.

Complexity claims must identify the resource being measured. Time may mean gate count, elementary operations, or bit operations. Space may mean classical memory cells or quantum qubits. A quantum algorithm can have a polynomial number of gates while requiring substantial classical memory to describe or control it.

A useful distinction is worst-case, average-case, and expected complexity. Worst-case complexity bounds the most expensive valid input of length n. Average-case complexity requires a specified input distribution. Expected complexity concerns a randomized algorithm’s average resource use over its internal randomness, and sometimes over its input distribution as well.

6. Classical Algorithms

An algorithm is a finite, precise procedure that maps permitted inputs to outputs. A rigorous algorithm specification normally includes:

• the input format and constraints;
• the output format;
• the sequence of operations;
• a termination condition;
• a correctness claim; and
• resource bounds.

Consider linear search through an array of n entries. It checks entries from left to right until the target is found or the array ends. Its worst-case time is Θ(n), because it may inspect every entry. Its best-case time is Θ(1), but a best-case claim does not replace a worst-case guarantee.

Binary search requires a sorted array. Each comparison eliminates approximately half the remaining candidates, giving worst-case time Θ(log n). The logarithm’s base is irrelevant in asymptotic notation because changing bases multiplies by a constant. Binary search illustrates an important principle: algorithmic speedups often depend on structural assumptions about the input.

A classical algorithm may be deterministic or randomized. A deterministic algorithm follows one computation path for a given input. A randomized algorithm uses random bits and may have a small probability of error. Quantum algorithms also produce probabilistic outcomes, but their probability distributions arise from amplitudes and unitary evolution rather than from ordinary random branching alone.

Correctness can be expressed using a loop invariant: a statement that remains true before and after each iteration. For binary search, an invariant is that if the target occurs in the input, it remains within the current search interval. In quantum algorithm analysis, correctness similarly requires specifying the desired output and bounding error probability.

7. Boolean Functions and Oracles

A Boolean variable takes a value in {0,1}. A Boolean function maps bit strings to bits:

Common operations include NOT, AND, and OR. XOR, written ⊕, returns 1 when its two inputs differ. A parity function is

A Boolean function may be represented by a truth table, a Boolean expression, a circuit, or an algorithm. The representation matters: a truth table for an n-input function has 2ⁿ rows, whereas a compact circuit may have polynomial size.

Quantum algorithm descriptions often use an oracle. A standard reversible oracle for a Boolean function is

Here x is an n-bit input, y is a target bit, and ⊕ denotes XOR. This transformation is reversible because applying it twice restores y:

The oracle does not erase the input x. This is essential because an operation that maps many inputs to the same output would not be reversible.

8. Reversible Computation

A classical function is reversible if each output uniquely determines its input. Equivalently, its mapping is one-to-one on the relevant state space. Ordinary gates such as AND are not reversible when considered alone: several input pairs produce the same output.

A reversible computation instead uses bijections on bit strings. The NOT gate is reversible, and the controlled-NOT (CNOT) gate is defined by

The control bit a is unchanged, while the target bit b is flipped when a=1. CNOT is its own inverse.

The Toffoli gate maps

where a·b is the AND of the two control bits. It performs a controlled-controlled-NOT and is reversible. With suitable ancillary bits, reversible gates can simulate ordinary classical circuits while preserving enough information to allow the computation to be undone.

Quantum evolution must be reversible between measurements because unitary operators have inverses. Consequently, a classical computation embedded in a quantum circuit must be converted into a reversible form. A typical strategy is “compute, copy or use the result, then uncompute.” Uncomputation removes temporary garbage and prevents unwanted entanglement with workspace registers.

Reversibility does not mean that every practical classical algorithm is automatically efficient when translated into a quantum circuit. The reversible simulation must be analysed for gate count, ancillary qubits, circuit depth, and implementation constraints.

9. Classical Complexity Classes

Complexity classes group decision problems according to resource-bounded computation models.

P is the class of decision problems solvable by a deterministic classical algorithm in polynomial time. Examples include graph connectivity and shortest-path decision versions.

NP is the class of decision problems for which a proposed solution, or certificate, can be verified in polynomial time by a deterministic classical algorithm. It is known that P ⊆ NP, but whether P=NP remains an open problem.

BPP is the class of decision problems solvable by a probabilistic classical polynomial-time algorithm with bounded error. “Bounded error” means the probability of an incorrect answer is separated from one-half by a fixed constant, which can often be reduced through independent repetition and majority voting.

BQP is the class of decision problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. Informally, BQP captures efficient quantum computation under a standard circuit model. The exact formal definition involves how circuits are generated and how acceptance probabilities are bounded, but the central ideas are polynomial resources and controlled error.

These classes should not be interpreted as a simple ranking of all problems. Known containments include P ⊆ BPP ⊆ BQP under standard definitions, while several relationships involving NP and BQP are not fully resolved. Quantum computing is not known to solve every NP-complete problem efficiently. Its strongest established algorithmic advantages arise in particular structures, such as periodicity and unstructured search.

For optimization and counting problems, decision versions are often used because complexity classes are most naturally defined for yes/no questions. A complete problem for a class is at least as hard as every problem in that class under an appropriate reduction. Reductions are used to transfer difficulty between problems and to justify claims of computational hardness.

10. A Framework for Analysing Quantum Algorithms

A useful analysis separates four layers:

1. Problem definition: Specify the input, output, promise conditions, and error requirement.
2. Mathematical representation: Encode data in qubit registers and identify the allowed states and operators.
3. Circuit resources: Count oracle calls, elementary gates, circuit depth, qubits, and repetitions.
4. Success analysis: Derive measurement probabilities and determine how many repetitions are needed to meet the error target.

The oracle-query model is especially useful when the cost of accessing a function dominates the cost of other operations. However, an oracle speedup may not translate directly into an end-to-end practical speedup if constructing, loading, or implementing the oracle is expensive.

Worked Example 2: Repetition and Error Reduction

Suppose an algorithm independently returns the correct answer with probability 0.75 on each run. If it is run three times and the majority answer is selected, the majority is wrong when at least two runs are wrong. The failure probability is

Thus the success probability is 0.84375. This calculation assumes independent runs and an odd number of repetitions. It illustrates error reduction, although practical quantum algorithms may use more sophisticated amplification and fault-tolerance methods.

11. Illustrative Application: Searching an Unstructured Database

Background

Suppose a database contains N items and exactly one item satisfies a search condition. The items have no exploitable ordering or structure. A classical deterministic search may require Θ(N) queries in the worst case.

Problem

The objective is to identify the marked item while reducing the number of queries to the search oracle. The database itself is treated abstractly; the oracle indicates whether a candidate is marked.

Analysis

A quantum search procedure begins with a uniform superposition over N candidates. An oracle changes the phase of the marked state, and a diffusion operation increases its amplitude while decreasing the amplitudes of unmarked states. Repeating these operations rotates the state toward the marked item.

For a single marked item and N possible items, the number of oracle applications required for a constant probability of success is Θ(√N). This is a quadratic query improvement over the classical worst-case bound. The result is not an exponential speedup, and the oracle and state-preparation costs must be included in a complete implementation analysis.

Approach and Outcome

After approximately a constant multiple of √N iterations, measurement returns the marked item with high, but not automatically perfect, probability. If necessary, the procedure can be repeated or its iteration count adjusted. The quadratic improvement is meaningful for large search spaces, but it does not eliminate the need for efficient data access, error control, and hardware execution.

Learning Points

The example demonstrates why asymptotic notation must identify the resource being improved: the quantum advantage is a query-complexity result. It also shows the role of amplitudes and interference. The oracle creates a phase distinction, and the diffusion operation converts that phase distinction into a larger measurement probability.

12. Limitations, Professional Practice, and Contemporary Context

Mathematical speedup does not guarantee practical advantage. Real systems incur costs for state preparation, measurement, error correction, communication, compilation, and limited connectivity. A fair comparison should use the same problem definition, include input and output costs, specify error tolerance, and state whether the comparison concerns queries, gates, depth, energy, or wall-clock time.

Quantum states are sensitive to noise and environmental interaction. At the algorithm-analysis level, noise may be represented by channels rather than ideal unitary matrices. At the engineering level, error mitigation and fault-tolerant error correction introduce additional resource overhead. Therefore, an ideal circuit complexity result should be distinguished from a fault-tolerant resource estimate and from a near-term hardware benchmark.

There are also governance and ethical considerations. Claims of quantum advantage should be reproducible and should distinguish theoretical results from experimentally demonstrated performance. Security professionals must track post-quantum cryptography because sufficiently capable quantum computers threaten some public-key systems based on factoring or discrete logarithms. Organisations should avoid overstating near-term capabilities, protect confidential data, and document assumptions behind technology evaluations.

Best practice for students and practitioners is to:

• define the computational model before counting resources;
• distinguish amplitude, probability, and observed frequency;
• verify normalization and dimensional consistency of matrices;
• state promise conditions and error bounds;
• include oracle, input-loading, and measurement costs where relevant;
• compare asymptotic and practical performance separately; and
• use simulations as validation tools rather than as substitutes for proofs.

Chapter Summary

Quantum algorithm analysis rests on linear algebra, probability, asymptotic analysis, and classical computation. Complex vectors represent quantum states, while unitary matrices represent reversible quantum evolution. Inner products and norms provide geometry and normalization; tensor products construct multi-qubit spaces whose dimension grows as 2ⁿ. Measurement probabilities are obtained from squared amplitude magnitudes, and interference arises because amplitudes combine before probabilities are calculated.

Asymptotic notation describes resource growth independently of machine-specific constants. Classical algorithms require precise input, output, correctness, termination, and resource specifications. Boolean functions provide a common language for decision problems and oracle models. Since quantum evolution is reversible, classical computations used in quantum circuits must be embedded into reversible transformations, often using CNOT, Toffoli, ancilla, and uncomputation techniques.

The classes P, NP, BPP, and BQP organise problems according to computational resources and error models. They help clarify what a quantum algorithm does and does not establish. Finally, the unstructured-search case shows how interference can produce a quadratic query improvement while also demonstrating the importance of implementation costs and carefully stated assumptions.

Key Terms

Complex number: A number of the form a+bi, with real a,b and i²=−1.

Complex conjugate: The number obtained by changing the sign of the imaginary part.

Ket: A column-vector representation of a state, written |ψ⟩.

Inner product: A complex-valued product ⟨u|v⟩ measuring relationships between vectors.

Norm: The length of a vector, defined by ‖v‖=√⟨v|v⟩.

Unitary matrix: A matrix satisfying U†U=I, preserving norms and inner products.

Hermitian matrix: A matrix satisfying A†=A.

Tensor product: An operation combining vector spaces or operators.

Amplitude: A complex coefficient whose squared modulus gives a measurement probability.

Entanglement: A joint-state property in which a state cannot be factored into subsystem states.

Projector: An operator P satisfying P²=P, representing a projective measurement outcome.

Big-O: An asymptotic upper bound on resource growth.

Big-Ω: An asymptotic lower bound on resource growth.

Big-Θ: A tight asymptotic bound.

Boolean function: A function mapping bit strings to bit strings, often with binary inputs and outputs.

Oracle: An abstract operation providing access to a function or predicate.

Reversible computation: Computation using one-to-one transformations that can be inverted.

Ancilla: An additional workspace qubit used during a computation.

Uncomputation: Reversing temporary calculations to remove workspace information.

BQP: The class of decision problems solvable by polynomial-size quantum circuits with bounded error.

Review Questions

Short Answer Questions

1. Why must a quantum state vector have unit norm?
2. What is the difference between a complex amplitude and a measurement probability?
3. State the condition that makes a matrix unitary.
4. Why is the ordinary AND operation not reversible by itself?
5. What does f(n)=Θ(g(n)) mean?

Long Answer Questions

1. Explain how tensor products construct the state space of multiple qubits. Include an example involving two qubits.
2. Describe measurement in the computational basis and explain how interference differs from ordinary classical probability.
3. Explain the reversible oracle transformation U_f|x,y⟩=|x,y⊕f(x)⟩ and prove informally why it is reversible.
4. Compare P, NP, BPP, and BQP, including the role of polynomial resources and bounded error.
5. Discuss the practical limitations that must be considered when converting a theoretical quantum speedup into an engineering implementation.

Analytical / Application Questions

1. A state is given by |ψ⟩=a|0⟩+b|1⟩, where a=1/2 and b=i/2. Determine whether it is normalized. If not, produce a normalized state and calculate the measurement probabilities.
2. An algorithm takes 4n²+3n+10 elementary operations, while another takes 2ⁿ. Explain which is asymptotically preferable and why the conclusion may depend on the actual input sizes used in practice.
3. Design a reversible Boolean circuit for copying a classical bit into a target bit initially set to 0. Identify the gate used, write its input-output rule, and explain why the original bit is preserved.

Multiple Choice Questions with Answers

Question 1

A qubit is in the state |ψ⟩=(|0⟩+i|1⟩)/√2. What is the probability of measuring 1 in the computational basis?

A. 0

B. 1/4

C. 1/2

D. 1

Correct Answer: C. 1/2

Question 2

Which condition defines a unitary matrix U?

A. UᵀU=0

B. U†U=I

C. U†=−U

D. det(U)=0

Correct Answer: B. U†U=I

Question 3

What is the dimension of the state space of n qubits?

A. n

B. n²

C. 2n

D. 2ⁿ

Correct Answer: D. 2ⁿ

Question 4

Which statement correctly describes Big-Θ notation?

A. It gives only an upper bound

B. It gives only a lower bound

C. It gives both an asymptotic upper and lower bound

D. It applies only to constant functions

Correct Answer: C. It gives both an asymptotic upper and lower bound

Question 5

Why is the transformation U_f|x,y⟩=|x,y⊕f(x)⟩ reversible?

A. It discards x

B. Applying it twice restores y

C. It maps every input to zero

D. It uses measurement

Correct Answer: B. Applying it twice restores y

Question 6

Which class consists of decision problems solvable by deterministic classical algorithms in polynomial time?

A. P

B. NP

C. BPP

D. BQP

Correct Answer: A. P

Question 7

What is the worst-case asymptotic time of binary search on a sorted array of n entries?

A. Θ(1)

B. Θ(log n)

C. Θ(n)

D. Θ(n²)

Correct Answer: B. Θ(log n)

Question 8

For the Bell state (|00⟩+|11⟩)/√2, what is the probability of measuring 00?

A. 0

B. 1/4

C. 1/2

D. 1

Correct Answer: C. 1/2

Question 9

Which gate maps |a,b⟩ to |a,b⊕a⟩?

A. NOT

B. Hadamard

C. CNOT

D. Toffoli with no controls

Correct Answer: C. CNOT

Question 10

What is the query complexity of quantum search for one marked item among N unstructured items, up to asymptotic factors?

A. Θ(1)

B. Θ(log N)

C. Θ(√N)

D. Θ(N²)

Correct Answer: C. Θ(√N)