SWAP Test

Overview

The SWAP test is a small quantum circuit that measures how similar two quantum states are. It uses one extra qubit, called the ancilla, and a controlled swap of the two states. Measuring the ancilla gives 0 with a probability that depends on the overlap between the states: it is one half when the states are completely different and one when they are identical.

The test is simple, but it appears inside many larger algorithms. It is used for quantum fingerprinting, quantum clustering and classification, kernel estimation, and for measuring properties such as the purity of a state. Its role in quantum computing is similar to that of a dot product in classical computing.

The problem it solves

Determining how similar (or different) two quantum states are — a building block used inside many other quantum algorithms, especially in quantum machine learning.

History and background

Buhrman, Cleve, Watrous, and de Wolf introduced the SWAP test in 2001 in their paper on quantum fingerprinting, which showed that two parties can test whether their n-bit strings are equal by exchanging only about log n qubits with a referee, while classical communication in the same model needs about the square root of n bits. The circuit builds on the controlled-swap gate studied by Barenco and coauthors and earlier by Fredkin.

Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek showed in 2002 that the same circuit can estimate nonlinear functions of a state, such as its purity, without full tomography. Later researchers developed variations, including the destructive SWAP test that uses Bell measurements and fewer gates, and the closely related Hadamard test for estimating the real and imaginary parts of expectation values. Small SWAP tests have been run on photonic, ion trap, and superconducting devices.

How it works

Uses an auxiliary qubit and a controlled-swap gate between the two states being compared; measuring the auxiliary qubit gives a probability directly related to the overlap between the two states.

The SWAP operation exchanges two states. The symmetric combination of two states, which is unchanged by swapping, and the antisymmetric combination, which flips sign, are the two eigen-subspaces of the swap. Any pair of states can be written as a mix of a symmetric part and an antisymmetric part, and identical states are purely symmetric.

The circuit uses the ancilla to measure whether the pair is symmetric or antisymmetric. A Hadamard gate puts the ancilla in a superposition, a controlled swap exchanges the two states when the ancilla is 1, and a second Hadamard converts the phase information into a measurable bit. The ancilla reads 0 with probability one half plus one half of the squared overlap.

Identical states always give 0, since they are symmetric and the swap does nothing. Orthogonal states give 0 or 1 with equal chance, because their symmetric and antisymmetric parts are equally weighted. The probability therefore carries the squared overlap, which can be estimated from many repetitions.

Step by step

1. Prepare an ancilla qubit in the state 0 and two registers holding the states psi and phi to be compared.
2. Apply a Hadamard gate to the ancilla.
3. Apply a controlled swap, with the ancilla as the control, exchanging the contents of the two registers when the ancilla is 1.
4. Apply a second Hadamard gate to the ancilla.
5. Measure the ancilla. The probability of outcome 0 is one half plus one half times the squared overlap of psi and phi.
6. Repeat the whole procedure many times, and estimate the squared overlap as 2 times the observed frequency of 0 minus 1.

A worked example

Let psi be the state 0 and phi be the state that is an equal superposition of 0 and 1. Their overlap is one over the square root of 2, so the squared overlap is one half. The ancilla reads 0 with probability one half plus one quarter, which is three quarters.

If you run the test 1,000 times and observe the outcome 0 about 750 times, you estimate the squared overlap as 2 times 0.75 minus 1, which is 0.5. The statistical error in the overlap estimate falls like one over the square root of the number of runs, so reaching a precision of 0.01 takes about 10,000 runs.

Complexity and resources

What hardware it needs

• A controlled swap gate, which requires several two-qubit gates, or the destructive variant with Bell-basis measurement.
• Two copies of the states to compare, which can be costly to prepare.
• High-fidelity operations, because errors lower the measured overlap.

Applications

• Quantum fingerprinting and equality testing in communication complexity.
• Computing distances and similarities in quantum k-means, quantum nearest-neighbor, and quantum support vector machine algorithms.
• Estimating the purity and other nonlinear functionals of quantum states.
• Evaluating the fidelity between a prepared state and a target state in variational algorithms and kernel estimation.

Limitations and caveats

• Many repetitions are needed for high precision, with the number growing as one over the square of the target error.
• It requires two copies of the states being compared and cannot compare a single unknown state to a classical description without preparing it.
• It measures only the squared overlap, not the phase of the overlap, which the Hadamard test can provide.

Common misconceptions

• The SWAP test does not read out the states. It only estimates their overlap.
• It does not give an exponential speedup by itself. Its value comes from being a cheap building block.
• A single run does not tell you whether states are equal. You need many runs for a statistical estimate.

How it compares

• The Hadamard test measures the real or imaginary part of an expectation value of a unitary, while the SWAP test measures the squared overlap of two states.
• Full state tomography reconstructs the whole state but costs exponentially more in the number of qubits.
• Classical dot products are exact and cheap but need the vectors to be stored explicitly.

Real-world impact

A foundational subroutine used inside quantum machine learning algorithms (like quantum k-means and quantum SVMs) for similarity comparison, rather than a standalone application.

Why it matters

The SWAP test is one of the most commonly used primitives in quantum algorithm design. It shows how quantum states can be compared without learning them, which is the basis of quantum fingerprinting and of the distance computations in quantum machine learning.

It also provides a good first example of a measurement that extracts a global property from a state, a theme that runs through phase estimation and amplitude estimation.

Frequently asked questions

Keep learning

• Related algorithm: Quantum k-Means Clustering
• Related algorithm: Quantum Kernel Estimation
• Related algorithm: Quantum Support Vector Machine
• Related algorithm: Quantum Anomaly Detection

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database