|Ketcode⟩
Back to Learn

Quantum Computing 101

Quantum Algorithms

Algorithms use interference to make the right answer the likely answer before you measure.

In this lesson you will learn to

  • Describe the prepare, encode, interfere, measure pattern.
  • Explain oracles and phase kickback.
  • Walk through one Grover iteration using amplitudes.
  • Estimate how many Grover iterations a search needs.
  • Recognize where the Quantum Fourier Transform fits in.

The Recipe

Measurement returns one result, so a quantum computer cannot simply read out all of its amplitudes. Instead, an algorithm rearranges the amplitudes so that the answer you want becomes likely, and only then measures.

Most quantum algorithms follow the same four steps. Measurement still returns a single answer, so the whole point of the earlier steps is to make the right answer the likely one.

Oracles and Phase Kickback

An oracle is a black box that encodes a function f(x). A bit oracle maps |x⟩|y⟩ to |x⟩|y ⊕ f(x)⟩. If the helper qubit y starts in |−⟩, the oracle instead multiplies |x⟩ by (−1)^f(x): the answer is written into a phase. This is phase kickback.

The Deutsch–Jozsa algorithm uses exactly this. A single oracle call, surrounded by Hadamards, tells a constant function from a balanced one with certainty, where a classical computer might need to check half of all the inputs.

Worked example: one query decides "balanced"

One input qubit, the balanced function f(x) = x, and its oracle: a CX onto the helper.

Uf ∣x⟩∣−⟩=(−1)f(x) ∣x⟩∣−⟩U_f\,|x\rangle|-\rangle=(-1)^{f(x)}\,|x\rangle|-\rangle
∣+⟩∣−⟩→Uf∣0⟩−∣1⟩2∣−⟩=∣−⟩∣−⟩→H on input∣1⟩∣−⟩|+\rangle|-\rangle\xrightarrow{U_f}\frac{|0\rangle-|1\rangle}{\sqrt2}|-\rangle=|-\rangle|-\rangle\xrightarrow{H\text{ on input}}|1\rangle|-\rangle
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

qc = QuantumCircuit(2)
qc.x(1)
qc.h([0, 1])       # input |+>, helper |->
qc.cx(0, 1)        # oracle for f(x) = x
qc.h(0)

print(Statevector.from_instruction(qc).probabilities_dict(qargs=[0], decimals=3))
# {'1': 1.0}  -> the input reads 1: f is balanced
›Check yourself: With the helper in |−⟩, what does the oracle do to |x⟩ when f(x) = 0?

Nothing, because (−1)⁰ = 1. Only inputs with f(x) = 1 pick up a minus sign, which is how the oracle marks them.

Grover Search

Grover's algorithm finds a marked item among N possibilities. Start in the uniform superposition, flip the sign of the marked item with an oracle, then reflect every amplitude about the average. Each round moves more amplitude onto the marked item.

One Grover iteration on four items, drawn as amplitudes. The oracle flips the sign of the marked answer; the diffuser then reflects every amplitude about the average, which empties the wrong answers and pours everything into the marked one.

With N items the best number of rounds is about (π/4)√N, compared with about N/2 guesses for a classical search. For four items one round is exactly enough; for eight items two rounds reach about 94.5%.

Worked example: one Grover iteration for target |11⟩

With two qubits there are four candidates. One Grover iteration is enough to move all probability to the marked state.

1. Uniform preparation:[12121212]\text{1. Uniform preparation:}\qquad \begin{bmatrix}\frac12&\frac12&\frac12&\frac12\end{bmatrix}
2. Mark ∣11⟩:[121212−12]\text{2. Mark }|11\rangle:\qquad \begin{bmatrix}\frac12&\frac12&\frac12&-\frac12\end{bmatrix}
3. Mean amplitude=12+12+12−124=14\text{3. Mean amplitude}=\frac{\frac12+\frac12+\frac12-\frac12}{4}=\frac14
4. Unmarked: 2(14)−12=0Marked: 2(14)−(−12)=1\begin{aligned}\text{4. Unmarked: }&2\left(\frac14\right)-\frac12=0\\\text{Marked: }&2\left(\frac14\right)-\left(-\frac12\right)=1\end{aligned}
5. Final amplitudes:[0001]P(11)=∣1∣2=1\text{5. Final amplitudes:}\qquad \begin{bmatrix}0&0&0&1\end{bmatrix}\qquad P(11)=|1|^2=1
from qiskit import QuantumCircuit
from qiskit.quantum_info import Statevector

qc = QuantumCircuit(2)
qc.h([0, 1])       # uniform preparation
qc.cz(0, 1)        # oracle: mark |11>
qc.h([0, 1])       # diffuser: reflect about the mean
qc.x([0, 1])
qc.cz(0, 1)
qc.x([0, 1])
qc.h([0, 1])

print(Statevector.from_instruction(qc).probabilities_dict(decimals=3))
# {'11': 1.0}
›Check yourself: Roughly how many Grover rounds suit a search over N = 64 items?

About (π/4)·√64 = (π/4)·8 ≈ 6.3, so 6 rounds. A classical search would need about 32 guesses on average.

Fourier Patterns

The Quantum Fourier Transform (QFT) rewrites a state in terms of phases that wind around at different speeds. Periodic patterns hidden in the amplitudes turn into sharp peaks that a measurement can find.

The QFT is the core of phase estimation, which reads the phase of a gate's eigenvalue into a register of qubits. Shor's factoring algorithm uses phase estimation to find the period of modular multiplication.

The QFT in one line

QFT ∣x⟩=1N∑y=0N−1e2πi xy/N ∣y⟩N=2n\mathrm{QFT}\,|x\rangle=\frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi i\,xy/N}\,|y\rangle\qquad N=2^n
n=1:QFT∣0⟩=∣0⟩+∣1⟩2,QFT∣1⟩=∣0⟩−∣1⟩2(the one-qubit QFT is H)n=1:\quad \mathrm{QFT}|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt2},\quad \mathrm{QFT}|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2}\quad(\text{the one-qubit QFT is }H)

Key Takeaways

  • Algorithms prepare, encode, interfere and only then measure.
  • With a |−⟩ helper, an oracle marks answers by flipping their sign (phase kickback).
  • Grover's algorithm reflects amplitudes about the mean, needing about (π/4)√N rounds.
  • The QFT turns periodic patterns in amplitudes into peaks you can measure.

What To Practice

Build the pieces of real algorithms, from oracles up to full searches and phase estimation.