Quantum Edge Detection

Encode an image into quantum amplitudes and detect edges with a single Hadamard sweep — the Quantum Hadamard Edge Detection (QHED) algorithm. It is often paraded as a showcase of quantum speedup, but its speedup claim comes with important fine print.

The problem it solves

Edge detection is a cornerstone of image processing: edges appear wherever the intensity of neighbouring pixels changes abruptly. The classical approach slides a detection kernel across the whole image, comparing adjacent pixels one by one — a cost that grows linearly in the number of pixels. For an image of 2ⁿ pixels, a classical scan needs O(2ⁿ) operations. Quantum edge detection asks a tantalising question: could a single operation acting on the entire quantum state compute all neighbour-differences at once?

Encoding an image — amplitude encoding (QPIE)

The first step is to load the image into a quantum state. Quantum Probability Image Encoding (QPIE) normalizes each pixel's intensity and writes it into the amplitudes of an n-qubit state: the normalized intensity of the k-th pixel becomes the amplitude (or part of it) of the basis state |k⟩. A measurement's probability is then tied to the square of the intensity rather than equal to it linearly, and when the pixel count is not a power of 2 the data must be padded or resampled to fit. In this way 2ⁿ pixels are carried by just n qubits — and this is precisely where the "exponential compression," and the allure, comes from. A megapixel image would in principle need only about 20 qubits.

But keep one thing in mind: these pixel values now live in the amplitudes, and you cannot read them out directly. Any single measurement collapses to one pixel with probability proportional to |amplitude|², so the vast majority of the information is lost the moment you read it out. This fact will haunt every trade-off discussed below.

The mechanism — one Hadamard is one neighbour-difference

The crucial insight is the algebraic effect of a Hadamard gate when it acts on amplitudes. Arrange the pixels along one coordinate axis as a row; a Hadamard applied to the lowest-order qubit, under that particular pairing, produces the sum and difference of adjacent amplitudes — for the pairs (0,1), (2,3), … And the difference between adjacent pixels is exactly the discrete gradient — which is where edges live.

So in flat regions (where neighbours are equal) the subtraction yields zero and the amplitudes cancel; at an edge (where neighbours jump) a non-zero amplitude survives. This is the kernel of QHED's speedup claim. But note: one Hadamard does not hand you a complete edge map. It only differences the pixels inside each fixed pair; recovering the full one-dimensional adjacency relation — or two-dimensional horizontal/vertical edges — generally still needs shifts, an ancilla qubit, a re-ordered encoding, or the two directions handled separately.

An honest look at that speedup claim

• State preparation can swallow the whole gain. Loading an arbitrary image into the amplitudes (i.e. the amplitudes step in QPIE) generally takes O(2ⁿ) gates — exactly the same order as the classical pixel-by-pixel scan. Unless the image has special structure that can be prepared efficiently, just "getting the data in" erases the advantage that one Hadamard bought you.
• Read-out is just as expensive. The gradients hide in the amplitudes, but a measurement only ever gives you a probability distribution: locations with a larger difference amplitude simply appear more often — a single measurement never returns the whole edge map. Reconstructing it requires an enormous number of samples — a count that again grows with the number of pixels, so an O(2ⁿ)-scale cost reappears at the output end.
• This is a textbook "data in / data out" bottleneck. The middle of the circuit (that one Hadamard) really is exponentially fast, but loading and reading out pinch the advantage to death at both ends. Many advertised quantum machine-learning and image-processing speedups stumble at exactly the same spot.
• Where it genuinely pays off. When the image already exists as a quantum state (say, as the output of some upstream quantum process), so that no classical state-preparation cost need be paid, and when we only care about some aggregate statistic of the edges rather than a pixel-by-pixel reconstruction — only then can QHED hold a real advantage.

The algorithm, step by step

1. Normalize the image's pixel intensities into a unit-norm state vector.
2. Use QPIE to prepare those amplitudes on an n-qubit state (2ⁿ pixels packed into n qubits).
3. Apply a Hadamard to the relevant qubit along the target axis; neighbouring amplitudes thereby become their sum and difference.
4. Measure; post-process the samples, reading the edges out of the differences between neighbouring amplitudes.

Seeing it in code — image encoding (QPIE)

Read this QPIE encoding against the theory above: the normalized pixel intensities amps are prepared into a state via qalgora.amplitudes(q, amplitudes) — and this is exactly the state-preparation step that can be expensive enough to swallow the speedup.

import qalgora
import numpy as np

# normalize pixel intensities into a statevector
img = load_image_gray()                 # shape (2^n,)
amps = img / np.linalg.norm(img)

@qalgora.kernel
def encode(amplitudes: list[complex]):
    q = qalgora.qvector(int(np.log2(len(amplitudes))))
    qalgora.amplitudes(q, amplitudes)   # state preparation

Seeing it in code — Hadamard edge detection

This kernel likewise prepares the amplitudes first, then applies a single h(q[0]) to q[0] — that one Hadamard which computes the gradient along one axis and turns neighbouring amplitudes into their sum and difference; the trailing comment spells out the post-processing: after measurement, the edges are read out of the differences between neighbouring amplitudes.

@qalgora.kernel
def qhed(amplitudes: list[complex]):
    q = qalgora.qvector(int(np.log2(len(amplitudes))))
    qalgora.amplitudes(q, amplitudes)
    h(q[0])                              # gradient along one axis
    mz(q)
# post-process: repeated sampling builds the probability distribution, then
# classically reconstruct the edge map from neighbouring amplitude differences