Quantum Algorithms

Quantum algorithms make use of superposition, interference and entanglement to solve certain problems faster than classical methods. This page summarises several influential algorithms and suggests simple circuits you can try on the Quantum Simulator .

Several oracle algorithms below share a pattern: prepare a superposition, encode function information in relative phases, and use interference to change the probabilities of measurable outcomes. Other algorithms on this page, including phase estimation and variational methods, use different structures.

Phase Kickback and Oracles

Most of the algorithms below query a Boolean function $f$ through a reversible oracle

Prepare the output qubit in $|-\rangle = (|0\rangle-|1\rangle)/\sqrt{2}$ by starting it in |1⟩ and applying H. Then $|y\rangle \mapsto |y\oplus f(x)\rangle$ multiplies the branch by $(-1)^{f(x)}$:

The output qubit remains in $|-\rangle$ and is separable from the input, while the function value has been “kicked back” into the input branch’s phase. This trick enables the one-query Deutsch-Jozsa and Bernstein-Vazirani algorithms below.

Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm is given a promise: the function $f:\{0,1\}^n\to\{0,1\}$ is either constant (the same value on every input) or balanced (returns 0 on exactly half of the inputs). It decides which with a single query. A deterministic classical algorithm needs $2^{n-1}+1$ queries in the worst case, since seeing $2^{n-1}$ equal values still leaves both cases open. (A randomised classical algorithm gets the answer with high probability after a handful of queries, so the exponential separation here is specific to the deterministic setting; Simon’s problem below gives a stronger one.)

The circuit is:

1. Prepare $n$ input qubits in |0⟩ and one output qubit in |1⟩.
2. Apply H to all $n+1$ qubits, giving $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle \otimes |-\rangle$.
3. Apply the oracle once, which by phase kickback produces $\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle \otimes |-\rangle$.
4. Apply H to the $n$ input qubits and measure them.

The amplitude of the all‑zeros outcome is $\frac{1}{2^n}\sum_x (-1)^{f(x)}$. For a constant $f$ every term has the same sign and that amplitude is $\pm1$, so the measurement returns $0\cdots0$ with certainty. For a balanced $f$ the $+1$ and $-1$ terms cancel exactly and $0\cdots0$ is never observed. Measuring all zeros therefore means constant, and any other outcome means balanced.

Bernstein-Vazirani Algorithm

The Bernstein-Vazirani algorithm recovers a hidden bit string $s$ from an oracle computing $f(x) = s\cdot x \bmod 2$, the parity of the bits of $x$ selected by $s$. Classically each query reveals one bit of information, so $n$ queries are needed; the quantum algorithm needs only one.

The circuit is identical to Deutsch-Jozsa: Hadamards on the input register, one oracle call with the output qubit in $|-\rangle$, then Hadamards again. After the kickback the register holds $\frac{1}{\sqrt{2^n}}\sum_x (-1)^{s\cdot x}|x\rangle$, and the second Hadamard layer maps that state exactly onto $|s\rangle$; so measuring the input qubits reads the hidden string off directly, with probability 1.

Simon’s Algorithm

Simon’s problem provides a function $f$ with the promise that $f(x) = f(y)$ exactly when $y = x$ or $y = x \oplus s$, for an unknown non‑zero string $s$. Finding $s$ with bounded error classically requires $\Omega(2^{n/2})$ oracle queries, while the quantum algorithm uses $O(n)$ queries, an exponential separation.

Hadamard gates on the $n$ input qubits create a superposition, the oracle writes $f(x)$ into a second register of the same size, and a second round of Hadamards on the input register is followed by measurement. Every outcome $y$ that can appear satisfies

because the two branches $x$ and $x\oplus s$ share an output value and interfere destructively unless that condition holds. Each run therefore yields one linear equation over $\mathbb{F}_2$, drawn uniformly from the $2^{n-1}$ strings orthogonal to $s$. Collecting $n-1$ linearly independent equations takes $O(n)$ expected runs because some outcomes duplicate information already held. Gaussian elimination modulo 2 then leaves a one‑dimensional solution space $\{0, s\}$, whose nonzero member is $s$.

Quantum Fourier Transform

The Quantum Fourier transform (QFT) is the quantum analogue of the discrete Fourier transform. It maps computational basis states to phase‑encoded superpositions and is the engine behind phase estimation and Shor’s algorithm. For an $n$‑qubit input state $|x\rangle$, writing $N = 2^n$,

As a matrix, the entry in row $j$ and column $k$ (both indexed from 0) is $\omega^{jk}/\sqrt{N}$ with $\omega = e^{2\pi i/N}$:

The rows are mutually orthogonal because the sum of the relevant powers of $\omega$ is zero for every pair of distinct rows. With the $1/\sqrt N$ normalization, this makes the matrix unitary. For a single qubit, $\omega = -1$ and the matrix is the Hadamard gate.

Product form and the circuit

Writing $x = x_1x_2\cdots x_n$ in binary ($x_1$ the most significant bit) and using the binary‑fraction notation $0.x_l x_{l+1}\cdots x_m = \frac{x_l}{2}+\frac{x_{l+1}}{4}+\cdots$, the transform factorises completely:

The QFT of each computational-basis state has the product form above and is therefore unentangled. The QFT can nevertheless create entanglement for other product inputs and can transform entanglement already present in its input.

This factorisation is exactly the circuit. Define the controlled phase rotation

so that $R_2 = S$ and $R_3 = T$. For each qubit $j = 1,\dots,n$ in turn, apply H to qubit $j$ and then a controlled‑$R_{m-j+1}$ on qubit $j$ for every later qubit $m > j$ acting as control. Because the product form builds the output bits in reverse order, the circuit finishes by reversing the register with $\lfloor n/2 \rfloor$ swap gates.

For two qubits this reads: H on the first qubit, a controlled‑$S$ between the two, H on the second qubit, and finally a swap. The controlled phase gate is diagonal, so it does not matter which of the two qubits you designate as the control.

The exact circuit uses $n$ Hadamards, $n(n-1)/2$ controlled rotations and $\lfloor n/2\rfloor$ swaps, for $O(n^2)$ elementary gates if those controlled rotations are available. A classical fast Fourier transform of an explicit list of $N = 2^n$ amplitudes costs $O(N\log N)$. These costs solve different input/output problems, so their comparison is not a drop‑in speedup for classical Fourier analysis: efficiently loading arbitrary classical amplitudes is not free, and measurement cannot reveal all $2^n$ output amplitudes. The QFT is useful as a coherent subroutine, for example when extracting periodicity through phase estimation.

Phase Estimation

Phase estimation estimates an eigenphase of a unitary $U$ when the corresponding eigenstate can be prepared. If $U|u\rangle = e^{2\pi i\varphi}|u\rangle$, the algorithm produces an estimate of $\varphi \in [0,1)$. It is a key subroutine in standard presentations of Shor’s algorithm and HHL.

The circuit uses two registers: $t$ counting qubits prepared in |0⟩ and put into superposition with Hadamards, and a second register prepared in the eigenstate $|u\rangle$. That second register is not simply initialised to |0⟩: the algorithm needs an eigenvector of $U$ to act on. For some unitaries a computational basis state happens to be one, but in general $|u\rangle$ has to be prepared. Feeding in a superposition of eigenstates also works; the measurement then returns the phase of one of them, chosen at random with probability given by its weight.

Controlled‑$U^{2^{j}}$ operations, one for each counting qubit $j = 0,\dots,t-1$, kick the phase back onto the counting register, leaving it in

If $2^t\varphi$ is an integer $m$, this phase-gradient state is exactly $\mathrm{QFT}|m\rangle$. In general it is not the QFT of a computational-basis state, but applying the inverse QFT still produces a distribution concentrated near the integers closest to $2^t\varphi$. Dividing a measured integer by $2^t$ estimates $\varphi$. Using the forward QFT with the same sign convention reflects the estimate to $-\varphi \bmod 1$, so the direction matters. If $\varphi$ has an exact $t$‑bit binary expansion, the result is deterministic. Otherwise, the probability of the nearest integer is at least $4/\pi^2 \approx 0.405$; using extra counting qubits and rounding to the desired precision can raise the success probability as high as required.

Shor’s Factoring Algorithm

Shor’s algorithm factors an $n$‑bit integer $N$ with bounded error in time polynomial in $n$. It combines classical pre‑ and post‑processing with a quantum routine for order finding. Related instances of Shor’s algorithm solve discrete logarithms, threatening widely used public-key systems based on factoring or discrete-logarithm assumptions.

Pick a random $a$ with $1 < a < N$; if $\gcd(a,N)\neq 1$ that gcd is already a factor. Otherwise the quantum routine finds the order $r$ of $a$ modulo $N$, the smallest $r>0$ with $a^r \equiv 1 \pmod N$. It does so by applying phase estimation to the unitary $|z\rangle \mapsto |az \bmod N\rangle$: a counting register of about $2n$ qubits is placed in superposition, modular exponentiation controlled by those qubits is applied, and the inverse QFT is performed.

Measuring the counting register yields an integer $y$ for which $y/2^{t}$ is likely to approximate $k/r$ for some integer $k$. Continued fractions generate a candidate denominator; it must be checked because a sample may reveal only a divisor of $r$. If the recovered order $r$ is even and $a^{r/2} \not\equiv -1 \pmod N$, then $\gcd(a^{r/2}\pm1,\,N)$ yield non‑trivial factors. After easy classical cases such as even integers and prime powers are handled, random choices of $a$ and repeated quantum samples give a bounded-error polynomial-time algorithm.

Grover’s Search Algorithm

Grover’s algorithm finds a marked item in an unstructured search space of size $N$ using $O(\sqrt{N})$ queries, a quadratic improvement over the $\Theta(N)$ classical query complexity. For a uniformly located item checked without replacement, a classical search uses $(N+1)/2$ queries on average. Grover’s scaling is optimal in the quantum black-box query model: any bounded-error quantum algorithm for this problem needs $\Omega(\sqrt{N})$ queries.

Starting from the uniform superposition $|s\rangle = H^{\otimes n}|0\rangle$, each Grover iteration applies two reflections:

1. The oracle flips the sign of the marked state, $|w\rangle \mapsto -|w\rangle$, leaving all others alone.
2. The diffusion operator $2|s\rangle\langle s| - I$ reflects every amplitude about the mean, converting the sign flip into an increase in magnitude.

Together they rotate the state vector by a fixed angle towards $|w\rangle$ in the two‑dimensional plane spanned by $|w\rangle$ and the uniform superposition. After $k$ iterations the success probability is $\sin^2\!\big((2k+1)\theta\big)$ where $\sin\theta = \sqrt{1/N}$, which is maximised at roughly $\lfloor\frac{\pi}{4}\sqrt{N}\rfloor$ iterations. Note that this is a rotation, not a ratchet: running too many iterations rotates past the target and the success probability falls again.

The two‑qubit version is the nicest one to build on the Quantum Simulator: with $N = 4$ a single iteration rotates the state exactly onto the marked item, so one oracle plus one diffusion step finds it with probability 1.

Grover’s algorithm generalises to amplitude amplification, which boosts the success probability of any procedure that prepares a state with some amplitude on a “good” subspace, and this in turn underpins quantum counting and amplitude estimation.

Variational Algorithms

Noisy intermediate‑scale quantum devices often employ variational algorithms. Here a parameterised quantum circuit is optimised using classical feedback. Examples include the Variational Quantum Eigensolver for estimating molecular ground‑state energies and the Quantum Approximate Optimisation Algorithm for combinatorial problems. These approaches are well suited to interactive exploration because the circuits are relatively small but depend on tunable parameters.

A cost function, such as the expectation value $\langle\psi(\vec\theta)|\hat{H}|\psi(\vec\theta)\rangle$ of a Hamiltonian, is estimated from repeated measurements of the circuit. A classical optimiser then updates the parameters to reduce this cost, and the process iterates until convergence. For a normalized trial state and an exact expectation value of the intended Hamiltonian, the variational principle makes that expectation an upper bound on the true ground-state energy. A finite-shot or noise-biased estimate can fall below the exact energy and is not automatically a rigorous bound. Unlike the algorithms above, these methods have no general proven speedup; performance is problem- and implementation-dependent, and training can stall on flat regions of the parameter landscape.

HHL

The Harrow-Hassidim-Lloyd algorithm prepares a quantum state proportional to the solution of $A\vec{x} = \vec{b}$. Its complexity can depend only polylogarithmically on the dimension under strong input and output assumptions, but it also depends polynomially on parameters such as sparsity, condition number and inverse precision. Efficient access to $A$, efficient preparation of $|b\rangle$, and a well-conditioned system are therefore essential. With $A$ Hermitian (a general matrix can be embedded in a larger Hermitian one), the original algorithm uses phase estimation on $e^{iAt}$, a controlled rotation whose successful branch weights an eigencomponent by approximately $1/\lambda_k$, and uncomputation.

The output is a quantum state proportional to the solution vector rather than a classical list of coefficients. Reconstructing all $N$ components generally removes an exponential-in-dimension advantage, so applications must extract a property of the solution state efficiently, such as an observable expectation value. The resulting end-to-end advantage depends on the data-access, conditioning, precision and measurement costs.

These algorithms illustrate several ways quantum gates can manipulate amplitudes and phases. Their speedups and practical requirements differ substantially, and small-scale simulator examples are useful for understanding their state transformations rather than demonstrating large-scale computational advantage.

Simulator Lab: Use Small Instances to Debug Algorithms

The Quantum Simulator  includes Oracle, Diffusion, controlled phase and rotation gates as well as a Grover (2) preset. These are best used to inspect amplitude flow on small registers, not to benchmark a claimed quantum speedup in a classical browser.

QSim does not expose arbitrary custom unitaries, modular-arithmetic blocks or a general controlled-$U^{2^j}$ constructor. Consequently, Grover search and a small QFT map directly onto the current palette, while full phase estimation, Shor and HHL would first require nontrivial decompositions into supported gates. A conceptual section appearing on this page does not imply that its complete scalable circuit is available as one QSim preset.

Use this compatibility guide before trying to translate an algorithm into the builder:

The built-in Oracle is a diagonal phase operation that multiplies one selected computational-basis state by $-1$. It is exactly the form needed for the single-marked-item Grover exercise. It should not be substituted silently for an arbitrary Boolean oracle, a Simon oracle or modular exponentiation, since those operations have different input and output registers and different promises.

Build Bernstein-Vazirani without a preset

The linear oracle for Bernstein-Vazirani decomposes particularly simply. To recover a three-bit string $s=s_2s_1s_0$:

1. Create four qubits. Use q0,q1,q2 as the input and q3 as the output ancilla.
2. Toggle q3 to 1. The initial integer is 8 and QSim displays |1000⟩ because q3 is the leftmost displayed bit.
3. Add H to all four qubits.
4. For every position $j$ where $s_j=1$, add CNOT targets j,3. These CNOTs implement $y\mapsto y\oplus s\cdot x$.
5. Add H to q0,q1,q2 and run.

For example, for $s=101$, add CNOT 0,3 and CNOT 2,3. The input qubits finish as q2q1q0 = 101 with probability 1. The output ancilla remains in $|-\rangle$, so the complete computational-basis result table has two equally likely rows that differ only in q3. Read the three rightmost displayed bits, or inspect the input-qubit Z components, rather than expecting the entire four-qubit result to be one basis state.

This construction is a useful debugging exercise because each hidden-string bit corresponds to exactly one optional CNOT. Export the zero-string circuit first, then add one CNOT at a time and confirm that only its associated recovered input bit changes.

Compare constant and balanced Deutsch-Jozsa oracles

A two-input example also fits the available gates. Use q0,q1 for the inputs and q2 for the output ancilla:

1. Toggle q2 to 1, giving initial integer 4 and displayed ket |100⟩.
2. Add H to all three qubits.
3. Insert one of the small oracle decompositions below.
4. Add H to q0,q1 and run.

The algorithm’s decision rule uses only whether the two input bits are 00; it does not require identifying which balanced function was supplied. As in the Bernstein-Vazirani exercise, the ancilla remains $|-\rangle$, so two complete three-qubit basis rows can appear. Ignore the leftmost displayed ancilla bit when applying the constant-versus-balanced decision rule.

These examples do not turn QSim’s marked-state Oracle button into a Deutsch-Jozsa oracle. They explicitly decompose a few $U_f$ operations using X and CNOT, which is why their behavior matches the oracle definition at the start of this page.

Grover search with a visible marked state

Load Grover (2) and run it. One basis state should have probability 1 after the single Grover iteration. Then rebuild the circuit manually:

1. Add H to q0 and q1 to prepare the uniform superposition.
2. Enter targets 0,1, select Oracle, and set Oracle marked state (int) from 0 through 3. The integer is interpreted within the selected target list.
3. Select Diffusion for the same two qubits.
4. Run after each marked-state change and confirm that the probability-one output moves accordingly.

For an Oracle acting on targets 0,1, marked integer 2 has local bits 10 with the first selected qubit carrying the least significant local bit. Because the displayed ket places q0 on the right, always use the output table rather than guessing from the integer’s printed binary form.

One iteration succeeds exactly for $N=4$. Adding a second Oracle and Diffusion pair reduces the success probability again, which directly demonstrates Grover’s rotation rather than monotonic amplification.

Build a two-qubit QFT

QSim displays q1 as the most significant bit in a two-qubit ket. To implement the convention used in the formula above, add H to q1, controlled phase on targets 0,1 with angle $\pi/2$, H to q0, and Swap on 0,1. Target order does not affect the symmetric controlled-phase gate. Test all four initial basis states by changing Initial basis state and rerunning.

The computational-basis probabilities are uniform for every basis input, so they cannot verify the phases by themselves. Inspect the local Bloch angles or append an inverse-QFT circuit and check that each input is recovered. This is a recurring simulator lesson: a probability histogram can validate magnitudes while missing phase errors.

Use JSON as an algorithm test fixture

Export a known-good circuit before experimenting. For each modification, record:

• register size and displayed initial ket;
• operation changed and its target order;
• expected nonzero outputs or expected deterministic output;
• shot count if sampled branches are involved.

Importing the same JSON before each trial prevents accidental gate accumulation. Export CSV is useful for comparing full basis-state probabilities numerically, while Export PNG is useful for documenting the gate order. Use both when an exercise needs to be reproducible and readable.