Major Quantum Algorithms and Complexity

Introduction

Quantum computing is not simply classical computing performed with faster hardware. It uses quantum effects—superposition, interference, and entanglement—to alter how computational information is represented and processed. The most important quantum algorithms demonstrate this advantage in different ways. Grover’s algorithm accelerates unstructured search; the quantum Fourier transform (QFT) provides an efficient change of basis used in several algorithms; phase estimation extracts eigenphase information; and Shor’s algorithm uses period finding to factor integers efficiently in principle.

A central discipline in quantum computing is to distinguish three claims:

1. Asymptotic speedup: the running time grows more slowly as the input size increases.
2. Practical advantage: a real quantum device completes a useful task better, faster, cheaper, or more accurately than the best available classical alternative.
3. Quantum advantage under a stated model: a carefully defined comparison in which the quantum and classical resources, input access, error tolerance, and output requirements are specified.

The first claim is theoretical. The second is technological and economic. They may eventually coincide, but they are not equivalent.

Learning Objectives

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

• explain the search problem addressed by Grover’s algorithm;
• describe the roles of the oracle, phase inversion, and diffusion operator;
• state the complexity of classical and quantum unstructured search;
• explain the QFT and its relationship to the classical discrete Fourier transform;
• describe quantum phase estimation and its dependence on controlled unitary operations;
• explain how Shor’s algorithm reduces factoring to period finding;
• compare theoretical complexity with practical performance;
• identify implementation constraints, error sources, and responsible uses of quantum algorithms.

1. Complexity as a Basis for Comparison

For an input of size n, algorithmic complexity describes how resources grow with n. In quantum computing, resources may include:

• Query complexity: the number of calls to an oracle or black-box function;
• Gate complexity: the number of elementary quantum and classical operations;
• Circuit depth: the length of the longest dependent sequence of gates;
• Space complexity: the number of qubits or classical memory locations;
• Error or precision cost: resources required to obtain a specified accuracy or failure probability.

Big-O notation suppresses constant factors and lower-order terms. Thus, O(√N) means that the resource requirement is bounded by a constant multiple of √N for sufficiently large N. It does not indicate the actual runtime on a particular machine.

For a fair comparison, the input model must be stated. For example, Grover’s algorithm assumes oracle access to a function. Loading a large classical database into a quantum-accessible form may itself require substantial cost. Ignoring data loading can make a theoretical speedup appear more useful than it is in practice.

2. Grover’s Search Algorithm

2.1 The problem

Suppose a search space contains N possible items and a Boolean function f marks solutions:

Here, x is an index and f is an oracle that can be evaluated by a quantum circuit. The goal is to find an x for which f(x) = 1.

If there is exactly one marked item and no useful structure is available, a classical randomized algorithm requires an expected order of N/2 queries, and a worst-case search may require N queries. Grover’s algorithm finds the marked item using approximately

oracle queries in the ideal unique-solution case, with success probability close to one when the number of iterations is chosen appropriately. The asymptotic query complexity is O(√N).

2.2 State preparation and amplitude amplification

For n qubits, where N = 2ⁿ, applying a Hadamard gate to every qubit creates the uniform state

The oracle is commonly implemented as a phase oracle:

It leaves non-solutions unchanged and multiplies solution states by −1. This is not a measurement; it is a reversible phase transformation.

The diffusion operator is

where I is the identity operator. It reflects amplitudes about their average. One Grover iteration is

The oracle changes the phase of the solution component, and the diffusion operator converts this phase distinction into increased solution amplitude. Repeated iterations rotate the state toward the solution subspace.

2.3 Geometric interpretation

When there is one solution, the state can be represented in a two-dimensional space spanned by the normalized solution state |w⟩ and the normalized non-solution state |r⟩. If the initial success probability is 1/N, define an angle θ by

After k Grover iterations, the probability of measuring a solution is

The best integer k is close to

which is approximately (π/4)√N when N is large. Because k must be an integer, excessive iterations can reduce the success probability. This phenomenon is called over-rotation.

If M items are marked rather than one, the initial success probability is M/N and the relevant angle satisfies

The query complexity becomes O(√(N/M)), provided M is known or can be estimated sufficiently well.

2.4 Worked example

Consider N = 16 items with one marked item. Then n = 4 qubits and

The approximate optimal iteration count is

Therefore, two or three iterations should be considered. Using k = 3 gives

Thus, the ideal circuit measures the marked item with approximately 96% probability. The example also shows why the exact number of iterations matters.

2.5 Applications and limits

Grover-style amplitude amplification can accelerate:

• constraint satisfaction when candidate verification is efficient;
• exhaustive key search against a symmetric cryptographic key;
• optimization procedures that can test whether a candidate meets a threshold;
• Monte Carlo and sampling subroutines in more advanced quantum algorithms.

For a cryptographic key of b bits, ideal exhaustive search has classical complexity proportional to 2^b and Grover search has query complexity proportional to 2^b/2. Consequently, quantum-resistant security practice often recommends increasing symmetric-key lengths. However, a quantum attacker must possess a sufficiently large, fault-tolerant computer, and the oracle circuit may be expensive.

Grover’s algorithm does not provide an exponential speedup for arbitrary search, nor does it automatically solve structured problems optimally. It requires coherent oracle evaluation, accurate reflections, repeated execution, and measurement. If the database is stored only in ordinary classical memory, constructing quantum access may dominate the total cost.

3. The Quantum Fourier Transform

3.1 Definition

The QFT over N basis states is the unitary transformation

where x and y are integers from 0 to N − 1, and i = √(−1). The inverse QFT changes the sign in the exponent:

The transformation preserves total probability because it is unitary. It is the quantum analogue of the discrete Fourier transform, but it acts on amplitudes of a quantum state rather than producing a classical list of all Fourier coefficients as explicit output.

If a state is

then the amplitude of |y⟩ after the QFT is

The probabilities observed in a measurement are |b_y|². A QFT does not allow all coefficients b_y to be read out simultaneously; measurement produces only a limited classical outcome.

3.2 Circuit structure

For N = 2^n, the QFT can be decomposed into Hadamard gates and controlled phase rotations. A rotation acting on a target qubit with angle 2π/2^m may be written as

where diag denotes a diagonal matrix. An n-qubit QFT circuit uses O(n²) elementary gates in a standard exact decomposition, followed by a reversal of qubit order. Approximate QFT circuits omit very small-angle rotations and can reduce gate count, at the cost of approximation error.

The classical fast Fourier transform requires O(N log N) arithmetic operations for N data points. The QFT circuit uses O((log N)²) gates when N = 2^n, but this comparison must be interpreted carefully. A quantum computer does not output N classical Fourier coefficients in one execution. The apparent exponential difference arises from compact quantum-state representation and restricted access to the output.

3.3 Periodic states

The QFT is valuable because periodicity becomes concentrated in measurable frequency information. Consider a state supported on values separated by period r:

where L is the number of terms and the indices are interpreted within the available range. Applying the QFT produces amplitudes concentrated near frequencies related to multiples of N/r. This property is central to phase estimation and Shor’s algorithm.

4. Quantum Phase Estimation

4.1 Purpose and setup

Quantum phase estimation (QPE) estimates an eigenphase of a unitary operator U. Suppose

where |ψ⟩ is an eigenvector and 0 ≤ φ < 1. The objective is to estimate φ to a chosen number of binary digits.

A typical QPE circuit contains:

1. an m-qubit counting register initialized to |0⟩;
2. a system register prepared in the eigenstate |ψ⟩, or a state having significant overlap with it;
3. Hadamard gates on the counting register;
4. controlled applications of U, U², U⁴, and so on;
5. an inverse QFT on the counting register;
6. measurement of the counting register.

After the controlled-unitary stage, the ideal state is

The inverse QFT transforms the phase-dependent pattern into a value near the integer 2^mφ. If φ has an exact m-bit binary representation, the result can be exact in the ideal noiseless circuit. Otherwise, measurement yields a nearby estimate with a probability distribution determined by the approximation error.

4.2 Precision and resources

With m counting qubits, the natural phase resolution is approximately 1/2^m. Increasing m improves precision, but controlled powers of U become more demanding. In the standard implementation, the largest power is U^{2^{m−1}}. The total cost therefore depends strongly on how U and its powers are implemented.

If the input state is a superposition of eigenstates,

then phase estimation returns an estimate of φ_j with probability approximately |c_j|², subject to finite precision and circuit errors. Preparing a suitable eigenstate can be the main practical difficulty.

4.3 Applications

QPE is a central subroutine for:

• quantum simulation and estimating molecular energies;
• estimating eigenvalues of physical systems;
• quantum linear-system methods;
• amplitude estimation;
• order and period-finding procedures.

In quantum chemistry, for example, a Hamiltonian is represented through a unitary time-evolution operator or related block-encoding construction. An energy eigenvalue can be inferred from a corresponding phase. Practical implementations must address state preparation, Hamiltonian simulation, fault tolerance, and precision requirements.

5. Shor’s Factoring Algorithm

5.1 Factoring and computational significance

Given a composite integer N, integer factorization asks for nontrivial factors of N. No efficient classical factoring algorithm is known for general large integers, although classical methods continue to improve. Shor’s algorithm factors an integer in polynomial time in the number of bits of N under its computational model.

If n = ⌈log₂N⌉ is the bit length of N, the broad complexity classification of a fault-tolerant implementation is polynomial in n. Exact gate counts depend on the arithmetic design, error-correction architecture, precision, and implementation choices. It is therefore misleading to quote a single universal runtime for Shor’s algorithm.

5.2 Reduction to order finding

Choose an integer a satisfying 1 < a < N and gcd(a, N) = 1. The order r of a modulo N is the smallest positive integer satisfying

The function a^x mod N is periodic with period r. If r is even and

then factors of N can often be obtained from

and

The greatest common divisor, gcd, is computed classically using Euclid’s algorithm.

The quantum portion estimates the period r using a superposition of exponents, modular exponentiation, and the QFT. The classical post-processing uses continued fractions to infer r from a measured value close to a multiple of N/r.

5.3 Algorithmic outline

A simplified workflow is:

1. Select a random a coprime to N.
2. Use quantum period finding to estimate the order r of a modulo N.
3. If r is odd or the condition involving a^{r/2} fails, choose another a.
4. Compute the two gcd values.
5. Verify the proposed factors and repeat if necessary.

The algorithm is probabilistic: a particular choice of a or a particular measurement may fail. Repetition gives high overall success probability.

5.4 Illustrative example: factoring 15

This is a small illustrative example, not a performance demonstration. Choose a = 2. The powers of 2 modulo 15 are

Thus r = 4. It is even, and

The candidate factors are

and

Therefore, 15 = 3 × 5. For large N, the difficult step is not the classical gcd calculation but the reliable quantum period-finding computation.

5.5 Cryptographic implications

Many widely deployed public-key systems rely on the practical difficulty of factoring or solving discrete logarithms. A sufficiently large fault-tolerant quantum computer running Shor-like algorithms could undermine RSA and related systems. This is why organizations are migrating toward post-quantum cryptography—classical cryptographic schemes designed to resist known quantum attacks.

The threat is not immediate decryption of every current system, because large-scale fault-tolerant quantum hardware is not yet available. However, adversaries may collect encrypted information today for later decryption, an issue known as “harvest now, decrypt later.” Long-lived sensitive data requires timely cryptographic planning.

6. Comparing Classical and Quantum Complexity

Complexity comparisons must also consider lower bounds. Bennett, Bernstein, Brassard, and Vazirani established that unstructured quantum search cannot generally be performed with fewer than order √N queries, so Grover’s quadratic improvement is asymptotically optimal in the query model. It is not an exponential improvement.

For Shor’s algorithm, “polynomial versus best-known classical superpolynomial” is a major theoretical distinction. Yet asymptotic notation does not specify when a crossover occurs. A polynomial quantum algorithm with large constants and error-correction overhead may be slower than a classical algorithm for all problem sizes currently accessible.

7. From Theoretical Speedup to Practical Advantage

A theoretical result normally assumes an abstract machine with exact gates, reliable qubits, and a specified input-access model. A practical evaluation must include:

• state preparation and data loading;
• quantum error rates and error correction;
• measurement and classical post-processing;
• circuit depth and connectivity constraints;
• compilation overhead;
• repetitions required for confidence;
• energy, capital, and operational costs;
• comparison with optimized classical software and hardware.

A quantum algorithm may have a strong asymptotic advantage but no practical advantage at today’s scale. Conversely, a hybrid quantum-classical method may offer useful performance without a clean asymptotic theorem, especially for heuristic optimization or simulation tasks.

7.1 Noise and fault tolerance

Current noisy intermediate-scale quantum devices have limited coherence and imperfect gates. Grover iterations, QFT rotations, controlled modular arithmetic, and phase-estimation circuits can all accumulate errors. Fault-tolerant quantum computing encodes logical qubits into many physical qubits and uses error-correction procedures. The overhead depends on the physical error rate, code, architecture, desired logical error rate, and circuit structure.

Small-angle QFT gates are especially relevant. Omitting rotations below a selected threshold can reduce circuit depth, but the resulting approximation must be included in the error budget. Similarly, approximate phase estimation may be adequate when the application tolerates bounded energy or parameter error.

7.2 Benchmarking responsibly

A meaningful benchmark should report:

• the precise problem instance and input representation;
• the classical baseline, including hardware and algorithm version;
• quantum circuit size, depth, and number of shots;
• error mitigation or correction methods;
• accuracy, confidence intervals, and failure probability;
• data-transfer and preprocessing time;
• total wall-clock and energy costs where possible.

Claims such as “quantum speedup” should specify whether they mean a speedup over a particular baseline, an asymptotic result, a query-complexity result, or an end-to-end application advantage.

8. Applied Case: Planning for Post-Quantum Cryptography

Background

This illustrative case concerns a financial institution that stores customer records requiring confidentiality for twenty years. Its public-key infrastructure uses RSA for key exchange and digital signatures.

Problem

The institution cannot assume that large-scale fault-tolerant quantum computers will remain unavailable throughout the retention period. It must determine whether to wait, increase key sizes, or migrate to post-quantum cryptography.

Analysis

Increasing RSA key sizes does not remove the fundamental vulnerability to Shor’s algorithm; it only changes the input size and resource requirement. Likewise, replacing a 128-bit symmetric key with a 256-bit key addresses the quadratic reduction associated with Grover search in an idealized model, but it does not protect RSA from polynomial-time quantum factoring.

The institution therefore distinguishes the threats:

• Symmetric encryption: Grover implies a quadratic search advantage, so longer keys provide a direct security margin.
• Public-key encryption and signatures based on factoring or discrete logarithms: Shor creates a qualitatively stronger threat, so migration to quantum-resistant schemes is required.

Approach and solution

The institution inventories cryptographic dependencies, identifies data with long confidentiality lifetimes, establishes crypto-agility, and pilots standardized post-quantum algorithms. It keeps classical fallback mechanisms during transition, validates implementation performance, protects private keys, and monitors standards and cryptanalytic developments.

Outcome

The organization reduces “harvest now, decrypt later” exposure and avoids treating the existence of Shor’s algorithm as equivalent to an immediate operational attack. Its planning is based on risk, migration time, data lifetime, and supply-chain dependencies rather than on a single speculative hardware date.

Learning points

1. Algorithmic complexity informs risk but does not determine immediate operational feasibility.
2. Grover and Shor have different effects on cryptographic systems.
3. Security planning must account for migration and information lifetime.
4. Quantum readiness is partly a governance and inventory problem, not only a hardware problem.

9. Best Practices and Limitations

When studying or implementing these algorithms:

• define the oracle, input model, and output requirement explicitly;
• distinguish query complexity from total end-to-end cost;
• verify that the proposed unitary operations are reversible;
• select Grover iteration counts using the estimated number of solutions;
• include approximation error when using an approximate QFT;
• treat eigenstate preparation as a first-class resource in phase estimation;
• test modular arithmetic and gcd post-processing independently in Shor implementations;
• compare against strong classical baselines;
• report confidence, repetitions, and hardware limitations;
• avoid claiming practical quantum advantage from asymptotic notation alone.

These algorithms also have structural limitations. A quantum state cannot generally be copied, measurement reveals limited information, and interference helps only when amplitudes are engineered to encode a useful answer. Quantum algorithms are not universal replacements for classical algorithms; they are specialized procedures whose benefit depends on mathematical structure and implementation conditions.

Chapter Summary

Grover’s algorithm provides a quadratic improvement for unstructured search by repeatedly applying a phase oracle and a diffusion operator. For N items and one solution, the ideal query complexity is approximately (π/4)√N, and for M solutions it is O(√(N/M)).

The QFT transforms amplitudes according to a Fourier basis and can be implemented on n qubits with an exact standard circuit of O(n²) gates. Its usefulness comes from converting periodic or phase structure into measurable information, not from exposing every Fourier coefficient simultaneously.

Quantum phase estimation estimates φ when a unitary satisfies U|ψ⟩ = e^2πiφ|ψ⟩. It combines controlled powers of U with the inverse QFT, and its precision depends on the number of counting qubits and the quality of eigenstate preparation and controlled operations.

Shor’s algorithm reduces factoring to order finding. The quantum period-finding stage and classical continued-fraction and gcd procedures together yield a polynomial-time quantum factoring method in the ideal fault-tolerant model. Its cryptographic significance is substantial, although practical deployment requires large-scale error-corrected hardware.

Finally, asymptotic speedup is not the same as practical advantage. Data loading, circuit depth, noise, error correction, compilation, repetitions, and classical alternatives must be included in a responsible comparison.

Key Terms

Amplitude amplification: Increasing the probability of desired outcomes through controlled interference.

Classical Fourier transform: A transformation of a classical data sequence into frequency components.

Controlled unitary: A unitary operation applied conditionally on the state of a control qubit.

Diffusion operator: The Grover operation that reflects amplitudes about their average.

Eigenphase: The phase φ associated with an eigenvalue e^{2πiφ} of a unitary operator.

Eigenstate: A state that changes only by a scalar phase when a linear operator acts on it.

Fault tolerance: The ability to perform reliable logical computation despite imperfect physical components.

Grover oracle: A reversible quantum operation that marks solutions, often by a phase change.

Interference: Combination of probability amplitudes that can enhance or suppress outcomes.

Order: The smallest positive r for which a^r ≡ 1 mod N.

Phase estimation: A quantum algorithm for estimating the eigenphase of a unitary operator.

Period finding: Determining the repeating interval of a function such as a^x mod N.

Quantum advantage: A demonstrated performance benefit of a quantum system under a specified comparison.

Quantum Fourier transform: A unitary Fourier-basis transformation on quantum amplitudes.

Query complexity: The number of calls to an oracle or black-box operation.

Shor’s algorithm: A quantum algorithm for factoring integers through order finding.

State preparation: The process of creating the quantum input state required by an algorithm.

Theoretical speedup: An asymptotic improvement predicted under an explicit computational model.

Unstructured search: Search in which no exploitable organization among candidate items is assumed.

Unitary operator: A reversible linear transformation that preserves inner products and total probability.

Review Questions

Short Answer Questions

1. What problem does Grover’s algorithm solve, and what is its asymptotic query complexity?
2. Why is the diffusion operator important in Grover’s algorithm?
3. State the mathematical definition of the QFT over N basis states.
4. What information does quantum phase estimation attempt to obtain?
5. Why is period finding central to Shor’s factoring algorithm?

Long Answer Questions

1. Explain Grover’s algorithm using the oracle-and-diffusion framework, including the effect of multiple marked items.
2. Compare the QFT with the classical fast Fourier transform and explain why their complexity comparison requires care.
3. Describe the complete workflow of quantum phase estimation and discuss the effects of finite precision.
4. Explain how Shor’s algorithm obtains factors from the order of a modulo N.
5. Discuss why an asymptotic quantum speedup may not produce practical advantage on current hardware.

Analytical / Application Questions

1. A search space has N = 1,024 items and exactly one marked item. Estimate the ideal number of Grover oracle queries using the approximation (π/4)√N. What practical factors could make the total computation more expensive?
2. An organization uses RSA for data that must remain confidential for twenty years and uses 128-bit symmetric encryption for short-lived data. Analyze how Shor’s and Grover’s algorithms affect its migration priorities.
3. A phase-estimation experiment requires approximately 10 bits of phase precision. Determine the approximate number of counting-register basis states required and identify two additional resources that may dominate the implementation cost.

Multiple Choice Questions with Answers

Question 1

For unstructured search of N items with one marked item, what is Grover’s asymptotic query complexity?

A. O(log N)

B. O(√N)

C. O(N)

D. O(N log N)

Correct Answer: B. O(√N)

Question 2

What does the Grover oracle typically do to a solution basis state?

A. It measures the state immediately

B. It changes its phase by a factor of −1

C. It deletes the state from the superposition

D. It copies the state into a second register

Correct Answer: B. It changes its phase by a factor of −1

Question 3

Which expression correctly defines the QFT over N basis states?

A. QFT_N|x⟩ = ∑_y |x + y⟩

B. QFT_N|x⟩ = N∑_y e^{xy}|y⟩

C. QFT_N|x⟩ = (1/√N)∑_y e^{2πixy/N}|y⟩

D. QFT_N|x⟩ = |x⟩ for every x

Correct Answer: C. QFT_N|x⟩ = (1/√N)∑_y e^{2πixy/N}|y⟩

Question 4

If an n-qubit system has N = 2^n basis states, what is the standard exact QFT gate complexity in n?

A. O(n²)

B. O(2^n)

C. O(n!)

D. O(1)

Correct Answer: A. O(n²)

Question 5

Given U|ψ⟩ = e^{2πiφ}|ψ⟩, what quantity does phase estimation estimate?

A. The number of qubits in |ψ⟩

B. The eigenphase φ

C. The determinant of U only

D. The classical runtime of U

Correct Answer: B. The eigenphase φ

Question 6

In standard phase estimation, what operation is applied after the controlled powers of U?

A. A quantum teleportation protocol

B. An inverse QFT on the counting register

C. A measurement of every system qubit before interference

D. A non-unitary deletion operation

Correct Answer: B. An inverse QFT on the counting register

Question 7

What is the order r of a modulo N?

A. The largest divisor of N

B. The smallest positive integer satisfying a^r ≡ 1 mod N

C. The number of qubits needed to represent N

D. The value of gcd(a,N)

Correct Answer: B. The smallest positive integer satisfying a^r ≡ 1 mod N

Question 8

For Shor’s algorithm, why are gcd(a^{r/2} − 1,N) and gcd(a^{r/2} + 1,N) computed?

A. To prepare the QFT input state

B. To obtain candidate nontrivial factors of N

C. To estimate the number of physical qubits

D. To eliminate all measurement noise

Correct Answer: B. To obtain candidate nontrivial factors of N

Question 9

For N = 16 items with one marked item, which approximation gives the ideal Grover query count?

A. (π/4)√16 = π

B. (π/4)16 = 4π

C. √16/π = 4/π

D. log₂16 = 4

Correct Answer: A. (π/4)√16 = π

Question 10

Which statement best distinguishes theoretical speedup from practical quantum advantage?

A. They are always identical once a complexity theorem is proved

B. Theoretical speedup concerns an abstract resource model, while practical advantage includes hardware and end-to-end costs

C. Practical advantage ignores classical baselines

D. Theoretical speedup can occur only for noisy devices

Correct Answer: B. Theoretical speedup concerns an abstract resource model, while practical advantage includes hardware and end-to-end costs