Fundamental Quantum Algorithms and Protocols

Introduction

Quantum programming becomes meaningful when abstract state vectors are organized into algorithms and communication protocols. A quantum algorithm is not simply a classical algorithm with quantum gates substituted for conventional instructions. Its advantage depends on carefully engineered interference, entanglement, measurement, and access to an oracle or physical process. This chapter develops several foundational algorithms and protocols that form the practical core of an introductory quantum-computing curriculum:

• quantum random-bit generation;
• quantum teleportation;
• superdense coding;
• Deutsch–Jozsa and Bernstein–Vazirani algorithms;
• Grover search;
• the quantum Fourier transform (QFT); and
• the foundations of quantum phase estimation (QPE).

The emphasis is on circuit construction, correctness, assumptions, implementation, and realistic claims about speedup. In each case, a quantum circuit is useful only when its input model, oracle cost, error model, and measurement requirements are specified.

Learning objectives

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

1. Explain how measurement can generate certified random bits.
2. Describe and implement teleportation and superdense coding circuits.
3. Distinguish exact, bounded-error, query, and practical runtime claims.
4. Construct Deutsch–Jozsa and Bernstein–Vazirani circuits using phase kickback.
5. Explain Grover amplification and its square-root query improvement.
6. Construct the QFT and relate it to phase estimation.
7. Identify assumptions, limitations, noise sources, and applications of these methods.

1. Computational foundations

A qubit is represented by a normalized state

where α and β are complex amplitudes satisfying

When the computational basis is measured, outcome 0 occurs with probability |α|² and outcome 1 with probability |β|². Measurement produces a classical result and generally changes the state. A register of n qubits has 2ⁿ computational-basis states:

Quantum gates are linear unitary transformations, represented by matrices U satisfying U†U = I. Reversible classical functions are commonly embedded in an oracle of the form

where f(x) is a bit and ⊕ denotes XOR. The oracle is reversible even when f itself is not one-to-one, because the input x is preserved.

A central mechanism is phase kickback. If the second register is prepared in

then

Thus, a function value can be written into the phase of the first register without being measured. Subsequent gates can cause these phases to interfere constructively or destructively.

2. Quantum random-bit generation

Principle

Prepare one qubit in |0⟩, apply a Hadamard gate, and measure:

The two outcomes have equal probability, so one measurement produces one ideal random bit. Repeating the circuit produces a sequence of independent bits, provided the state preparation, measurement, and device noise do not introduce bias or correlation.

A minimal pseudocode description is:

repeat N times:
    prepare qubit in |0⟩
    apply H
    measure in the computational basis
    record 0 or 1

For N ideal trials, the number K of ones follows a binomial distribution:

Its expected value and variance are E[K] = N/2 and Var(K) = N/4. These statements assume independent, identically distributed ideal measurements. In an implementation, a bias test may estimate p, the probability of a one, using p̂ = K/N. Statistical testing does not prove perfect randomness; it only detects certain departures from a model.

Applications and limitations

Quantum random-number generators can support cryptographic key generation, lotteries, scientific sampling, and Monte Carlo experiments. Security applications require more than a quantum circuit: the source must be characterized, outputs must be monitored, and appropriate randomness extraction and certification procedures should be used. A raw device output may contain classical noise, detector bias, or correlations. Randomness expansion and device-independent protocols address stronger security requirements but require additional assumptions and resources.

3. Quantum teleportation

Teleportation transfers an unknown qubit state using a shared entangled pair, two classical bits, and no transmission of the unknown quantum system itself. Let Alice possess

and let Alice and Bob share the Bell state

Teleportation does not duplicate |ψ⟩. Alice’s measurement destroys her original state, which is consistent with the no-cloning theorem.

Circuit procedure

1. Prepare qubits 2 and 3 in |Φ⁺⟩ by applying H to qubit 2 and CNOT(2→3).
2. Place |ψ⟩ on qubit 1.
3. Apply CNOT(1→2), then H to qubit 1.
4. Measure qubits 1 and 2, obtaining classical bits m₁ and m₂.
5. Alice sends m₁ and m₂ to Bob.
6. Bob applies Z^{m₁}X^{m₂} to qubit 3.

The joint state immediately before Alice’s measurements can be rearranged as

The first two registers belong to Alice; the final register belongs to Bob. Therefore, after receiving the two classical bits and applying the corresponding correction, Bob obtains |ψ⟩ up to an irrelevant global phase.

The protocol respects relativity: Bob cannot recover the state before receiving the classical information. The entangled pair is a resource, not a classical communication channel. In practice, imperfect entanglement, gate error, measurement error, and decoherence reduce the fidelity of the teleported state.

Figure: Conceptual teleportation circuit. Alice measures two qubits and sends classical results to Bob, who applies conditional corrections.

4. Superdense coding

Superdense coding reverses the communication pattern. Alice and Bob share a Bell pair, and Alice can communicate two classical bits by transmitting only one qubit, assuming the prior entanglement has already been distributed.

Bob prepares |Φ⁺⟩ and sends one qubit to Alice. To encode a two-bit message ab, Alice applies one of four operations to her qubit:

Alice returns the encoded qubit. Bob applies CNOT followed by H and measures both qubits, distinguishing the four Bell states. The protocol does not violate the classical capacity of a physical channel without accounting for the entanglement resource. Its significance is operational: shared entanglement increases the information conveyed per transmitted qubit.

5. Deutsch–Jozsa algorithm

The Deutsch–Jozsa problem receives a function f:{0,1}ⁿ→{0,1} promised to be either:

• constant: f(x) has the same value for every x; or
• balanced: f(x)=0 for exactly half the inputs and 1 for the other half.

The task is to determine which case applies. Classically, a deterministic algorithm may need 2ⁿ⁻¹+1 queries in the worst case. The quantum algorithm makes one oracle query and is exact under the promise.

Circuit and correctness

Initialize n input qubits and one ancilla in

Apply H to all qubits. The ancilla becomes |−⟩, and phase kickback gives

Apply H to the first n qubits. The amplitude of |0ⁿ⟩ is

If f is constant, A₀=+1 or −1, so measuring gives 0ⁿ with certainty. If f is balanced, the positive and negative terms cancel, so A₀=0 and 0ⁿ never occurs. The algorithm therefore measures the first register: 0ⁿ means constant; any other result means balanced.

The speedup is a query-complexity result under a promise and an oracle model. It does not imply that every classical implementation requires exponentially more total time, because constructing or evaluating the oracle may dominate the cost.

6. Bernstein–Vazirani algorithm

The Bernstein–Vazirani problem hides an unknown n-bit string s in the Boolean function

where the dot product is bitwise modulo 2. A classical deterministic method generally requires n queries, one for each bit, whereas the quantum algorithm identifies s with one oracle query.

Prepare |+⟩^{⊗n}|−⟩, apply U_f, and use phase kickback:

Applying H to the first register transforms this state into |s⟩. A computational-basis measurement therefore returns s with certainty in the ideal model. The algorithm is exact and illustrates how a global phase pattern can encode all bits of a hidden linear function. As with Deutsch–Jozsa, its claimed advantage concerns oracle queries and assumes coherent access to U_f.

7. Grover search and amplitude amplification

Suppose an unstructured database has N=2ⁿ possible items and exactly M marked solutions. A phase oracle changes the sign of marked states:

Grover’s iterate consists of the oracle followed by the diffusion operator

where |s⟩ = (1/√N)∑_x |x⟩ is the uniform superposition. The diffusion step reflects amplitudes about their average, increasing marked amplitudes and decreasing unmarked amplitudes.

For one marked item, define θ by

After r Grover iterations, the probability of measuring a marked item is

For M≪N, a near-optimal iteration count is approximately

The query complexity is O(√(N/M)), compared with O(N/M) expected classical queries for uniform random search. If M is unknown, exact stopping is unavailable; randomized iteration counts or counting methods can be used. Too many iterations cause the success probability to decrease because the rotation continues past the optimum.

Grover search provides a quadratic, not exponential, speedup. It also requires a reversible, coherent oracle. In practical systems, oracle construction and error correction may outweigh the query advantage. For a database with structure exploitable by classical indexing, unstructured Grover search may not be the appropriate model.

Worked example

Let N=16 and M=1. Then sin²θ=1/16, so θ≈0.2527 radians. The approximate optimal count is

so three iterations are a practical integer choice. The ideal success probability is

The approximation illustrates why integer rounding and the exact value of M matter.

8. Quantum Fourier transform

The QFT on n qubits is the unitary transformation

where N=2ⁿ and x,y are integers from 0 to N−1. The inverse QFT changes the sign in the exponent. The transformation is the quantum analogue of the discrete Fourier transform, but it acts on amplitudes and can be implemented as a circuit rather than explicitly listing all output amplitudes.

For computational-basis input |x⟩, the output is generally a superposition. The QFT is most useful when the input has periodicity or when relative phases encode a measurable frequency. A standard circuit uses Hadamard gates, controlled phase rotations

and a final reversal of qubit order. The exact circuit uses O(n²) one- and two-qubit gates, while approximate QFT circuits omit very small-angle rotations and can reduce gate count at controlled accuracy.

A major conceptual caution is that the QFT does not by itself reveal all Fourier coefficients. Measurement returns only one sample. Algorithms gain value when the desired periodic or phase information is concentrated into outcomes that can be interpreted efficiently.

9. Quantum phase estimation foundations

Phase estimation estimates an eigenphase of a unitary operator U. If

where 0≤φ<1, then QPE estimates φ using a control register, controlled powers of U, an inverse QFT, and measurement.

Procedure

1. Prepare t control qubits in |0⟩^{⊗t} and an eigenstate |ψ⟩ in the target register.
2. Apply H to every control qubit.
3. Apply controlled-U^{2^j} operations, with one power for each control qubit.
4. Apply inverse QFT to the control register.
5. Measure the control register and interpret the resulting integer y as an estimate y/2ᵗ.

If φ has an exact t-bit binary representation, the ideal measurement returns that representation with probability 1. If φ is not exactly representable, the measurement distribution is concentrated near the nearest t-bit estimates; increasing t improves resolution. The target must be an eigenstate, or a superposition of eigenstates, for the standard analysis. If

then QPE samples the corresponding phases φ_k with probabilities |c_k|², subject to finite precision and implementation error.

QPE is foundational for order finding, quantum simulation, and estimating eigenvalues of Hamiltonians. Its practical cost can be substantial because controlled powers of U must be implemented accurately. In fault-tolerant settings, QPE is powerful; on noisy near-term hardware, variants such as iterative phase estimation and Bayesian phase estimation may reduce qubit requirements but introduce repeated experiments and classical processing.

10. Implementation practice and comparison

A useful development workflow is:

1. State the input model and promise.
2. Identify the oracle and count its queries separately from gate cost.
3. Simulate the ideal circuit and inspect probabilities.
4. Add noise and compare fidelity or success probability.
5. Verify classical post-processing and endianness conventions.
6. Test edge cases, including zero marked items, multiple solutions, and non-exact phases.

The phrase “quantum speedup” must always be qualified. Query complexity may improve while total runtime does not. Input loading, oracle synthesis, error correction, measurement repetition, and classical decoding can dominate. A fair comparison uses the same output-success requirement and includes relevant preprocessing and post-processing.

11. Illustrative applied case: quantum-assisted calibration search

Background

Consider a fictional laboratory calibrating a sensor with N=1,048,576 possible discrete parameter settings. A reversible simulator can mark settings that satisfy a specified calibration condition. The laboratory wants to examine whether a quantum search could reduce the number of simulator queries.

Problem

The team initially claims that Grover search makes calibration exponentially faster. This claim is incorrect: the search space is unstructured, so the theoretical improvement is quadratic.

Analysis and approach

Assume one valid setting, an exactly implementable phase oracle, fault-tolerant gates, and negligible cost for preparing the uniform superposition. Since N=2²⁰, the approximate number of Grover iterations is

A classical uniform search would require about N/2=524,288 queries on average if each setting is tested without replacement. The ideal query comparison is therefore roughly 524,288 versus 804, not an exponential separation.

The engineering team then estimates oracle synthesis, error-correction overhead, parameter loading, and repeated runs. If the oracle requires a large circuit and the hardware cannot maintain coherence for approximately 804 iterations, the theoretical advantage may disappear. The team therefore prototypes the oracle in simulation, measures success probability after each iteration, and compares the complete workflow with a classical indexed method.

Outcome and learning points

The case demonstrates that algorithm selection depends on structure. Grover search is appropriate only when the condition can be evaluated coherently and no efficient classical structure is available. The correct professional conclusion is conditional: quantum search offers a quadratic query advantage under an oracle model, but not a guaranteed end-to-end advantage in a noisy implementation.

Challenges, governance, and best practices

Quantum programs are sensitive to convention errors, especially qubit ordering, control-target direction, phase signs, and whether a measurement result is interpreted as a binary integer in little-endian or big-endian order. Reproducible experiments should record the circuit, backend, basis conventions, number of shots, random seeds where relevant, and noise assumptions.

Security claims require particular care. Quantum random outputs should not be described as cryptographically secure without source validation. Teleportation does not transmit information faster than light, and superdense coding requires pre-shared entanglement. Algorithmic speedup claims should identify whether they concern asymptotic gate complexity, oracle queries, sample complexity, or demonstrated wall-clock performance.

Contemporary development focuses on fault-tolerant implementations of QPE and simulation, approximate Fourier circuits, error mitigation, hardware-efficient amplitude amplification, and quantum-classical hybrid workflows. These developments do not remove the need to state assumptions; they make explicit resource accounting even more important.

Chapter Summary

This chapter introduced foundational quantum algorithms and protocols through their state transformations and implementation assumptions. Hadamard-based measurement provides an ideal quantum random bit, although practical randomness requires source validation. Teleportation transfers an unknown state using entanglement and two classical bits, while superdense coding communicates two classical bits through one transmitted qubit when entanglement is pre-shared. Deutsch–Jozsa and Bernstein–Vazirani demonstrate exact one-query advantages under strong oracle promises. Grover search amplifies marked-state amplitudes and provides a quadratic query improvement for unstructured search. The QFT transforms phase and periodicity information, and inverse-QFT-based phase estimation provides a foundation for eigenvalue estimation. In all cases, speedup claims depend on oracle access, input preparation, error rates, measurement, and classical processing.

Key Terms

Qubit: A two-level quantum information system.

Amplitude: A complex coefficient whose squared magnitude determines measurement probability.

Unitary: A reversible linear transformation preserving inner products.

Oracle: A black-box or circuit implementation of a function used by an algorithm.

Phase kickback: Transfer of a function value into the phase of another register.

Bell state: A maximally entangled two-qubit state.

Teleportation: Transfer of an unknown quantum state using entanglement and classical communication.

Superdense coding: Communication of two classical bits by transmitting one qubit with shared entanglement.

Promise problem: A problem whose inputs are restricted to a specified valid subset.

Balanced function: A Boolean function producing each output equally often.

Diffusion operator: Grover’s reflection about the uniform superposition.

Amplitude amplification: Increasing the probability of desired states through reflections and interference.

Quantum Fourier transform: A unitary Fourier transformation on a quantum register.

Controlled operation: A gate applied conditionally on the state of another qubit.

Eigenstate: A state satisfying U|ψ⟩=λ|ψ⟩ for an operator U.

Eigenphase: The phase φ in an eigenvalue e^{2πiφ}.

Query complexity: Resource count measuring oracle calls.

Fidelity: A measure of similarity between ideal and implemented quantum states.

Fault tolerance: Techniques for reliable computation using error correction and protected operations.

Review Questions

Short Answer Questions

1. Why does measuring H|0⟩ produce an ideal random bit?
2. What classical information must Alice send in quantum teleportation?
3. State the promise in the Deutsch–Jozsa problem.
4. What is the purpose of Grover’s diffusion operator?
5. Why is an eigenstate important in standard quantum phase estimation?

Long Answer Questions

1. Explain quantum teleportation, including state preparation, measurement, classical communication, and correction operations.
2. Derive the amplitude of |0ⁿ⟩ in the Deutsch–Jozsa algorithm and explain why it distinguishes constant from balanced functions.
3. Compare the resource assumptions and information capacities of teleportation and superdense coding.
4. Explain the QFT circuit structure and discuss why measurement does not reveal every Fourier coefficient.
5. Describe the complete QPE procedure and explain the effects of finite precision and a superposition of eigenstates.

Analytical / Application Questions

1. A search space contains 65,536 items and one marked item. Estimate the number of Grover iterations using r≈(π/4)√N, and compare it with the average classical uniform-search queries.
2. A proposed quantum database project claims an exponential speedup from Grover search. Identify at least three missing assumptions or resource costs that must be evaluated before accepting the claim.
3. Design an experiment to test whether a quantum random-bit generator is biased. Specify the data collected, an appropriate statistical model, and why passing a statistical test does not prove perfect randomness.

Multiple Choice Questions with Answers

Question 1

After applying a Hadamard gate to |0⟩ and measuring in the computational basis, what is the ideal probability of obtaining 1?

A. 0

B. 1/4

C. 1/2

D. 1

Correct Answer: C. 1/2

Question 2

How many classical bits must Alice send to Bob in the standard quantum teleportation protocol?

A. One

B. Two

C. Three

D. None

Correct Answer: B. Two

Question 3

What promise defines the Deutsch–Jozsa problem described in this chapter?

A. The function is linear

B. The function is either constant or balanced

C. The function has exactly one marked input

D. The function is reversible as a classical map

Correct Answer: B. The function is either constant or balanced

Question 4

What does the Bernstein–Vazirani algorithm identify with one oracle query under its stated model?

A. The number of qubits

B. The hidden string s

C. The number of marked items

D. The eigenphase of an operator

Correct Answer: B. The hidden string s

Question 5

For Grover search with N items and M marked items, the approximate query complexity is:

A. O(log N)

B. O(MN)

C. O(√(N/M))

D. O(N²)

Correct Answer: C. O(√(N/M))

Question 6

Which operation follows the oracle in a standard Grover iterate?

A. A diffusion operator

B. A measurement of every qubit

C. An inverse classical lookup

D. A SWAP of all registers

Correct Answer: A. A diffusion operator

Question 7

What is the principal role of the inverse QFT in standard quantum phase estimation?

A. To prepare the target eigenstate

B. To convert encoded phase information into measurable computational-basis information

C. To erase the oracle

D. To create classical randomness

Correct Answer: B. To convert encoded phase information into measurable computational-basis information

Question 8

Which condition is required for the simplest exact interpretation of standard QPE?

A. The target register is an eigenstate of U

B. The unitary U is non-reversible

C. The phase is always zero

D. No controlled operations are used

Correct Answer: A. The target register is an eigenstate of U

Question 9

Why does superdense coding not violate classical communication limits?

A. The transmitted qubit is never measured

B. It requires pre-shared entanglement as a resource

C. It sends only one classical bit

D. It uses an irreversible gate

Correct Answer: B. It requires pre-shared entanglement as a resource

Question 10

For N=16 and one marked item, the approximate Grover iteration count is:

A. 1

B. 2

C. 3

D. 16

Correct Answer: C. 3