Quantum Algorithms (part 1: 4.1–4.3)
Open in the Padhaiko app4.1 Quantum parallelism
Early quantum algorithms demonstrate how quantum computers can evaluate global properties of mathematical functions in far fewer oracle queries than any classical algorithm. The foundational mechanism enabling this is quantum parallelism, combined with phase kickback and quantum interference.
Quantum Oracle and Quantum Parallelism
Suppose is a classical Boolean function. Because arbitrary classical functions may be many-to-one (and therefore irreversible), cannot be implemented directly as a unitary gate on qubits. Instead, it is embedded into a reversible quantum oracle acting on an -qubit input (query) register and an -qubit output (target) register:
where denotes bitwise addition modulo (XOR). Since applying twice gives , the oracle satisfies and is strictly unitary.
Quantum parallelism arises when the input register is prepared in an equal superposition of all computational basis states using Hadamard gates () and the target register is initialized to :
A single evaluation of the circuit produces a quantum state that simultaneously encodes every input-output pair across all inputs.
The Measurement Bottleneck and Phase Kickback
Although the state contains information about all evaluations of , we cannot directly read out all values at once:
- If we measure both registers in the computational basis, the state collapses to a single pair chosen uniformly at random with probability .
- Thus, quantum parallelism alone yields no speedup over a single classical evaluation on a random input. Useful quantum algorithms must apply unitary transformations (such as Hadamard transforms) to induce constructive and destructive interference so that a global property of is concentrated into a measurable state.
4.2 Deutsch and Deutsch–Jozsa algorithms
Deutsch's Algorithm ()
Consider all possible Boolean functions mapping a single input bit to a single output bit. There are exactly such functions, partitioned into two classes:
- Constant functions: (equivalently, ).
- Balanced functions: (equivalently, ).
| Function | Classification | |||
|---|---|---|---|---|
| Constant | ||||
| Constant | ||||
| Balanced | ||||
| Balanced |
Classically, determining whether is constant or balanced requires evaluating both and — queries. In 1985, David Deutsch showed that a quantum computer decides this global property () in only query to .
Deutsch's Algorithm Circuit and State Evolution
Deutsch's circuit operates on two qubits initialized to :
- Initialization & Superposition: Apply to :
- Oracle Query with Phase Kickback: Apply :
Factoring out :
- If (constant), the first qubit is .
- If (balanced), the first qubit is .
- Interference (Final Hadamard) and Measurement: Apply to qubit 1:
Measuring the first qubit in the computational basis yields:
- with probability if is constant ().
- with probability if is balanced ().
The Deutsch–Jozsa Algorithm ( bits)
In 1992, David Deutsch and Richard Jozsa generalized Deutsch's problem to -bit Boolean functions under the promise that is either:
- Constant: returns the same value ( or ) for all inputs .
- Balanced: for exactly half () of the inputs and for the remaining inputs.
Deutsch–Jozsa Algorithm State Evolution
Initialize an -qubit system in :
- Superposition: Apply :
- Oracle Query: Apply using phase kickback:
- Final -Qubit Hadamard Transform: Using the -qubit Hadamard identity (where is the bitwise inner product modulo ):
- Measurement of the First Qubits: Consider the probability of observing the all-zero bitstring (where , so ):
- If is constant: Every term has the same sign ( or ), so and . The measurement always yields .
- If is balanced: Exactly terms equal and terms equal , so they cancel completely: . The measurement never yields (at least one qubit is ).
| Aspect | Classical Deterministic / Probabilistic | Deutsch–Jozsa Quantum Algorithm |
|---|---|---|
| Deterministic Worst-Case Queries | queries (exponential in ) | oracle query (constant ) |
| Deterministic Guarantee | certainty only after identical outputs | certainty in query |
| Bounded-Error Randomized | queries give error probability (exponential speedup disappears against BPP) | query with zero error |
| Circuit Depth / Gates | evaluations | Hadamard gates + oracle |
4.3 Bernstein–Vazirani
In 1993, Ethan Bernstein and Umesh Vazirani introduced a problem that demonstrates a clear polynomial separation between classical deterministic/probabilistic algorithms and quantum computers without needing a promise restriction on constant vs. balanced functions.
Problem Statement
Suppose we are given a quantum oracle for a linear Boolean function defined by an unknown secret bitstring :
The task is to determine the exact -bit secret string .
- Classical Query Complexity: Each classical query to returns only 1 bit of information (). By querying the standard basis vectors , , , , a classical algorithm recovers one bit per query, requiring queries (which is optimal classically, even for randomized algorithms).
Bernstein–Vazirani Algorithm
Remarkably, the Bernstein–Vazirani circuit is identical to the Deutsch–Jozsa circuit ( measure input register).
- After applying and querying via phase kickback:
- Applying the final -qubit Hadamard transform to the first register:
- Using the orthogonality identity of Walsh–Hadamard characters:
Every amplitude vanishes except for , collapsing the state deterministically to:
Measuring the first qubits yields the entire secret string with probability in a single oracle query ( vs. classical ).
| Algorithm | Function & Promise | Goal | Classical Queries | Quantum Queries |
|---|---|---|---|---|
| Deutsch | Constant vs. balanced | |||
| Deutsch–Jozsa | , constant or balanced | Constant vs. balanced | (det.) | |
| Bernstein–Vazirani | Find secret |
Worked Examples
4.1
Trace Deutsch's algorithm step-by-step for the balanced function on input , and determine the measurement outcome probabilities of the first qubit.
Evaluating the Function Values: For :
Since , the function is balanced.
Applying Initial Hadamard Gates: Starting from , applying produces:
Applying the Oracle ():
Thus, the state immediately after the oracle is:
Applying Final Hadamard and Measuring: Applying to the first qubit (recalling ):
Measuring the first qubit in the computational basis gives:
Outcome is measured with probability, confirming that is balanced in a single query.
The final state is , so measuring the first qubit yields outcome with probability (), correctly identifying as balanced.
4.2
Trace the Deutsch–Jozsa algorithm for qubits using the balanced function . Compute the amplitude of every two-qubit basis state before measurement.
Evaluating and Phase Factors : For :
State After Phase-Kickback Oracle: Initializing , applying , and querying yields:
Notice that the input register factors cleanly as .
Applying to the Input Register: Using the Deutsch–Jozsa amplitude formula :
- For :
- For :
- For :
- For :
Equivalently, .
The final input register state is with amplitudes and . Since and the measured string , the algorithm identifies as balanced with certainty.
4.3
Execute the Bernstein–Vazirani algorithm for qubits with hidden string , so that . Show explicitly how the final transform recovers .
Preparing Superposition and Applying the Oracle: Start with and apply :
Querying applies the phase to each basis vector :
Factoring as a Tensor Product of Single Qubits:
Applying Final Hadamard Gates : Since and :
Measuring the first three qubits yields with probability .
After , the state is , deterministically returning the secret string in a single query.
Practice Exercises
Practice Exercises — Quantum Parallelism, Deutsch–Jozsa, and Bernstein–Vazirani
Why does quantum parallelism alone not immediately provide an exponential speedup for evaluating all values of ? Explain the role of phase kickback and interference in overcoming this limitation.
Output of Quantum Parallelism: Applying to the uniform superposition produces the entangled state:
While all pairs exist simultaneously in superposition, quantum mechanics restricts readout to projective measurement.
The Measurement Limitation: Measuring in the computational basis collapses the entire register to a single randomly selected basis state with probability , destroying the remaining values. Thus, direct measurement extracts only one evaluation of , no better than a classical computer evaluating on a random input.
Role of Phase Kickback and Interference: To obtain a speedup, algorithms initialize the ancilla in so encodes into relative phases (phase kickback). Subsequent unitary transformations (such as ) cause these signed amplitudes to add constructively on states encoding a global property of and cancel destructively on all other states (quantum interference).
Direct measurement of yields only one random pair . Phase kickback encodes into relative phases , and interference (via Hadamard transforms) concentrates a global property of into a deterministic measurement outcome.
Apply Deutsch's algorithm to the constant function for . Write the state after each stage of the circuit and verify the measurement probabilities of the first qubit.
Stage 1 — Initial State and Hadamards: Starting from , applying gives:
Stage 2 — Oracle Evaluation: Since and , phase kickback multiplies both and by :
Stage 3 — Final Hadamard and Measurement: Applying (recalling ):
Measuring the first qubit yields and .
Final state: . The first qubit measures with probability , identifying as constant.
Consider the Deutsch–Jozsa problem for input bits.
- How many queries to does a deterministic classical algorithm require in the worst case to guarantee whether is constant or balanced?
- How many oracle queries does the Deutsch–Jozsa quantum algorithm require?
- Explain what measurement result distinguishes constant from balanced functions in the quantum algorithm.
Worst-Case Deterministic Classical Queries: There are possible inputs. A balanced function outputs on inputs and on inputs. In the worst case, a classical algorithm could receive the exact same output (e.g., ) on the first distinct inputs; only on the query can it distinguish a constant function from a balanced function:
Quantum Queries and Output Criterion: The Deutsch–Jozsa quantum algorithm requires only oracle query regardless of . After applying and measuring the -qubit input register:
- If the outcome is (), is constant.
- If the outcome is any string other than (), is balanced.
- Deterministic classical worst case: queries ().
- Quantum algorithm: query.
- Outcome indicates constant; any non-zero bitstring indicates balanced.
In a -qubit Deutsch–Jozsa circuit, suppose the oracle implements for all , except that due to a fault the oracle instead flips only when , i.e., and (neither constant nor balanced). Compute the probability of measuring at the output.
Computing the Phase Factors: For :
Evaluating the Amplitude of : Using the Deutsch–Jozsa amplitude formula for ():
Probability of Outcome : Squaring the amplitude:
Because violates the constant-or-balanced promise, neither nor holds.
The probability of measuring is .
In a -qubit Bernstein–Vazirani circuit implementing , the state immediately after the phase-kickback oracle (before the final transform) is measured to have signs corresponding to:
Determine the hidden string and verify the state obtained after applying .
Extracting Signs from : Comparing with the given state:
- : sign
- : sign
- : sign
- : sign (consistent)
Thus, .
Applying to Verify: Factoring the input register of :
Applying :
The hidden string is , and applying transforms the input register directly to .