Quantum Inner Product Estimation

69 concepts51 papers1 proposal

At the heart of almost every machine learning algorithm lies a simple question: how similar are these two pieces of data? Whether you are clustering customer profiles, classifying images, or computing attention scores in a Transformer, you are fundamentally calculating distances or inner products between high-dimensional vectors.

Classically, computing the dot product between two vectors $\mathbf{u}$ and $\mathbf{v}$ in a $d$-dimensional space requires multiplying their components element-by-element, a process that scales linearly with the dimension, $O(d)$. When dealing with millions of high-dimensional data points, this linear bottleneck quickly becomes an expensive computational wall.

Quantum computing offers a radically different way forward. By encoding data vectors into the quantum states of qubits, we can transform the algebraic problem of computing inner products into a physical problem of measuring quantum interference. This paradigm—quantum inner product estimation—allows us to evaluate data similarity with computational complexities that scale logarithmically with vector dimensions or bypass dataset-size bottlenecks entirely through quantum superposition.


The Core Engine: State Overlap and the Swap Test

To understand why quantum hardware can accelerate similarity metrics, we must look at how data is represented. If we normalize a classical vector, we can map its components directly to the probability amplitudes of a quantum state:

$$|\psi\rangle = \sum_{i=1}^d u_i |i\rangle$$

In this representation, the mathematical inner product between two classical vectors $\mathbf{u}$ and $\mathbf{v}$ corresponds exactly to the physical overlap, or fidelity, between their quantum state representations, $\langle \psi | \phi \rangle$.

But how do we extract this overlap without performing full state tomography, which would destroy any computational advantage? The most elegant solution is an ancilla-assisted measurement known as the Swap Test.

Ancilla |0⟩ ----[ H ]----•----[ H ]---- Measure
                         |
State 1 |ψ⟩ -------------x------------
                         |
State 2 |φ⟩ -------------x------------

The mechanism is beautifully simple. We introduce an extra "ancilla" qubit initialized to $|0\rangle$ alongside the two states we want to compare. The circuit executes three basic steps:

  1. Put the ancilla into a equal superposition of $|0\rangle$ and $|1\rangle$ using a Hadamard gate ($H$).
  2. Perform a Controlled-SWAP (Toffoli-like) operation, which swaps the target states $|\psi\rangle$ and $|\phi\rangle$ only if the ancilla is in the $|1\rangle$ state.
  3. Apply a second Hadamard gate to the ancilla and measure it.

The second Hadamard gate acts as an interferometer. If $|\psi\rangle$ and $|\phi\rangle$ are identical, the Controlled-SWAP does nothing, and the two paths interfere constructively, guaranteeing that the ancilla collapses back to $|0\rangle$ with $100\%$ probability. If the states are completely orthogonal, the paths do not interfere, and the outcome is completely random ($50\%$ chance of $|0\rangle$, $50\%$ chance of $|1\rangle$).

Mathematically, the probability of measuring the ancilla in the $|0\rangle$ state is exactly:

$$P(0) = \frac{1}{2} + \frac{1}{2}|\langle \psi | \phi \rangle|^2$$

As formalized by Daniel K. Park et al., this Hilbert-Schmidt inner product serves as a valid positive semi-definite kernel, allowing quantum hardware to natively implement classical kernel methods. This basic routine has wide applicability: Changqing Gong et al. utilize the Swap Test to offload similarity calculations in cloud-based clustering, while Peixun Long et al. leverage it as a black-box verification tool to check the equivalence of entire quantum programs by measuring the fidelity of their outputs.


Exploiting Superposition for Parallel Distance Calculation

The Swap Test tells us how to compare two states efficiently, but the true power of quantum computing emerges when we combine state overlap estimation with quantum superposition to compare multiple states simultaneously.

In classical nearest-neighbor or clustering algorithms, a query point must be sequentially compared against every single reference point in a dataset. If you have $N$ points, you must run $N$ separate distance calculations.

Quantum distance oracles, first introduced in this context by Esma Aı̈meur et al., bypass this linear scaling. By leveraging Quantum Random Access Memory (QRAM), we can prepare an entire dataset of $N$ points into a single, unified quantum superposition:

$$|\text{Dataset}\rangle = \frac{1}{\sqrt{N}} \sum_{j=1}^N |j\rangle |x_j\rangle$$

When we perform an interference circuit between a query state $|y\rangle$ and this superposition, the quantum hardware evaluates the similarity between the query and all data points in a single parallel step. As Daniel Silver et al. demonstrate, processing data pairs inside a global superposition allows quantum interference to yield explicit, collective signals regarding structural similarities without requiring individual, sequential inspections.

This parallelized evaluation forms the backbone of several quantum machine learning speedups:

  • Clustering: In the q-means algorithm developed by Iordanis Kerenidis et al., distances between high-dimensional data points and multiple cluster centroids are calculated simultaneously in superposition. Combined with amplitude estimation, this allows the algorithm's time complexity to scale logarithmically with the number of data points ($O(\log N)$).
  • Nearest Neighbors: William Bonvini et al. use parallel superposition encoding to compute Euclidean distances between a query face and multiple stored templates simultaneously, using a quantum minimization routine to instantly find the closest match.
  • Data Reduction: Suzhen Yuan utilizes this single-step superposition overlap to accelerate "granular-ball" generation, replacing massive point clouds with representative geometric spheres by evaluating global point distances at once.

Accelerating High-Dimensional Kernels via Amplitude Estimation

While superposition targets the dataset size ($N$), another family of quantum algorithms targets the vector dimensionality ($d$).

In classical machine learning, non-linear problems are often solved using the "kernel trick"—mapping data into an ultra-high-dimensional feature space where the data becomes linearly separable. However, computing inner products in these massive spaces is computationally prohibitive. Quantum systems naturally occupy an exponentially large Hilbert space, making them ideal for quantum kernel estimation.

To extract these high-dimensional inner products with high precision, researchers combine interference circuits with Quantum Amplitude Estimation (QAE). Instead of repeatedly running the Swap Test and counting samples to approximate probabilities (which suffers from standard statistical sampling error), QAE uses quantum phase estimation to read out the overlap value with a quadratic speedup.

Naixu Guo et al. show that using QAE to approximate the inner products of a kernel matrix reduces the computational complexity from linear to square-root scaling ($O(\sqrt{d})$) relative to the data dimension. Similarly, Debbie Lim et al. apply amplitude estimation and amplification to calculate the inner products between weight vectors and feature vectors during the prediction phase of online learning algorithms, achieving sub-linear scaling in dimensionality.

To make these operations practical on near-term hardware, Hao Xiong et al. designed concrete hybrid architectures that pair the Hadamard test with Quantum Phase Estimation, enabling flexible 1-to-1, 1-to-N, and M-to-N inner product evaluations by directly mapping the geometric inner product into a measurable quantum phase.

Data Vectors (x, y) ──► [ Parameterized Quantum Circuit ] ──► State Overlap ──► Quantum Kernel Matrix

Versatility Across the Quantum Landscape

Because inner product estimation is a fundamental mathematical primitive, its quantum acceleration acts as a drop-in replacement across a vast spectrum of machine learning frameworks:

Support Vector Machines & Classification

By mapping input features into complex quantum states—either via analog simulators like the trapped-ion platform proposed by Rodrigo Martínez-Peña et al. or parameterized circuits—quantum support vector machines leverage state overlaps to resolve patterns that are intractable for classical kernels. Jingbo Wang et al. successfully applied this to complex bioinformatics tasks like peptide classification, while Zekun Ye et al. achieved an exponential speedup in training and prediction for Twin Support Vector Machines by evaluating class membership purely through state overlap rather than full vector reconstruction.

Generative Models & Autoencoders

In generative frameworks, state fidelity serves as a natural loss function. Samuel A. Stein et al. introduced QuGAN, which replaces classical log-likelihood loss functions with raw Swap Test outputs, stabilizing training and reducing parameters by 95%. For unsupervised anomaly detection, Sophia Rebello et al. developed a zero-training framework (Quorum) that uses quantum reconstruction fidelity—measuring how closely an autoencoder's output state overlaps with its original input state—to flag anomalous data points without encountering gradient optimization issues.

Alternative Primitives for Near-Term Hardware

While calculating exact continuous inner products is powerful, near-term noisy quantum devices sometimes struggle with the deep circuits required for high-precision amplitude estimation. To circumvent this, Ren-Xin Zhao et al. proposed an alternative approach for Quantum Self-Attention Networks (QSAN). Instead of standard inner products, they substitute similarity scores with bitwise logical operations (like AND and XOR) executed via digital Toffoli and CNOT gates. This allows similarity scores to be computed entirely within the quantum state, avoiding intermediate measurements and preserving quantum superposition for longer durations on noisy hardware.

Ultimately, whether through digital gate-based swap tests, analog fidelity tracking, or specialized phase estimation, translating data similarity into quantum state overlaps allows machine learning algorithms to break free from the linear constraints of classical vector arithmetic.

Key Foundational Work

RGU at ImageCLEF2010 Wikipedia Retrieval Task (2010) — contributed 2 concept elements to this direction.
Quantum speed-up for unsupervised learning (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_quantum_inner_product_estimation_b13771f0,
  title = {quantum inner product estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-inner-product-estimation/rdr_b13771f0a96c4b698aa3f2e7f48765a2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_quantum_inner_product_estimation_b13771f0_v1,
  title = {quantum inner product estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/quantum-inner-product-estimation/rdr_b13771f0a96c4b698aa3f2e7f48765a2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake