Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Towards quantum template matching

Daniel Curtis, David Meyer

Published Feb 3, 2004• 43 citations
Publisher

Abstract

We consider the problem of locating a template as a subimage of a larger image. Computing the maxima of the correlation function solves this problem classically. Since the correlation can be calculated with the Fourier transform this problem is a good candidate for a superior quantum algorithmic solution. We outline how such an algorithm would work.

DOI
10.1117/12.506669

Related papers

Quantum algorithm for optical-template recognition with noise filtering

Gernot Schaller, Ralf Schützhold

We propose a probabilistic quantum algorithm that decides whether a monochrome picture matches a given template (or one out of a set of templates). As a major advantage to classical pattern recognition, the algorithm requires just a few incident photons and is thus suitable for very sensitive pictures (similar to the Elitzur-Vaidman problem). Furthermore, for a ${2}^{n}\ifmmode\times\else\texttimes\fi{}{2}^{m}$ image, $O(n+m)$ qubits are sufficient. Using the quantum Fourier transform, it is possible to improve the fault tolerance of the quantum algorithm by filtering out small-scale noise in the picture. For example images with $512\ifmmode\times\else\texttimes\fi{}512$ pixels, we have numerically simulated the unitary operations in order to demonstrate the applicability of the algorithm and to analyze its fault tolerance.

arXiv:quant-ph/0512057•Physical Review A•Jul 7, 2006•21 citations

A Hybrid Quantum Image-Matching Algorithm

Guo-Qiang Shu, Zheng Shan, Shiqin Di +2 more

Image matching is an important research topic in computer vision and image processing. However, existing quantum algorithms mainly focus on accurate matching between template pixels, and are not robust to changes in image location and scale. In addition, the similarity calculation of the matching process is a fundamentally important issue. Therefore, this paper proposes a hybrid quantum algorithm, which uses the robustness of SIFT (scale-invariant feature transform) to extract image features, and combines the advantages of quantum exponential storage and parallel computing to represent data and calculate feature similarity. Finally, the quantum amplitude estimation is used to extract the measurement results and realize the quadratic acceleration of calculation. The experimental results show that the matching effect of this algorithm is better than the existing classical architecture. Our hybrid algorithm broadens the application scope and field of quantum computing in image processing.

Entropy•Dec 13, 2022•3 citations

Pattern recognition on a quantum computer

Ralf Schützhold

By means of a simple example, it is demonstrated that the task of finding and identifying certain patterns in an otherwise (macroscopically) unstructured picture (dataset) can be accomplished efficiently by a quantum computer. Employing the powerful tool of the quantum Fourier transform, the proposed quantum algorithm exhibits an exponential speedup in comparison with its classical counterpart.

arXiv:quant-ph/0208063•Physical Review A•Jun 26, 2003•97 citations

A Fourier-Label Information-Loss Barrier for Dihedral Coset Algorithms

Aparna Gupte, Seyoon Ragavan, Mark Zhandry

We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower $n-1$ bits of the subset sum, the algorithm discards any $ω(\log n)$ bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.

quant-pharXiv:2609.40062•Oct 1, 2026•0 citations

Iterative Approach to Quantum Imaging Using Higher-Order Correlation Functions

Vadim Reut, Alexander B. Mikhalychev, Ilya L. Karuseychik +5 more

We demonstrate and discuss the quantum imaging technique based on the second and higher-order correlation functions, which enables correct reconstruction of objects with the pixel size much smaller than the classical resolution of the used optical system.

Quantum Information and Measurement (QIM)•Jan 1, 2017•0 citations

What is the optimum way to extract information from optical images at the standard quantum limit and beyond ?

Claude Fabre, Nicolas Treps, V. Delaubert +2 more

The problem of extracting a given piece of information from an image with the maximum sensitivity is solved in the general case. Implementations using image intensity processing techniques and homodyne measurements are given.

Conference on Lasers and Electro-Optics•Jan 1, 2006•0 citations
We consider the problem of locating a template as a subimage of a larger image. Computing the maxima of the correlation function solves this problem classically. Since the correlation can be calculated with the Fourier transform this problem is a good candidate for a superior quantum algorithmic solution. We outline how such an algorithm would work.
We propose a probabilistic quantum algorithm that decides whether a monochrome picture matches a given template (or one out of a set of templates). As a major advantage to classical pattern recognition, the algorithm requires just a few incident photons and is thus suitable for very sensitive pictures (similar to the Elitzur-Vaidman problem). Furthermore, for a ${2}^{n}\ifmmode\times\else\texttimes\fi{}{2}^{m}$ image, O(n+m)O(n+m)O(n+m) qubits are sufficient. Using the quantum Fourier transform, it is possible to improve the fault tolerance of the quantum algorithm by filtering out small-scale noise in the picture. For example images with $512\ifmmode\times\else\texttimes\fi{}512$ pixels, we have numerically simulated the unitary operations in order to demonstrate the applicability of the algorithm and to analyze its fault tolerance.
Image matching is an important research topic in computer vision and image processing. However, existing quantum algorithms mainly focus on accurate matching between template pixels, and are not robust to changes in image location and scale. In addition, the similarity calculation of the matching process is a fundamentally important issue. Therefore, this paper proposes a hybrid quantum algorithm, which uses the robustness of SIFT (scale-invariant feature transform) to extract image features, and combines the advantages of quantum exponential storage and parallel computing to represent data and calculate feature similarity. Finally, the quantum amplitude estimation is used to extract the measurement results and realize the quadratic acceleration of calculation. The experimental results show that the matching effect of this algorithm is better than the existing classical architecture. Our hybrid algorithm broadens the application scope and field of quantum computing in image processing.
We establish a no-go theorem for a broad class of quantum algorithms for the dihedral coset problem (DCP). We consider the Fourier-sampling and subset-sum-measurement template proposed by Regev (SIAM Journal on Computing, 2004), which is one of the main approaches to solving DCP. Suppose that, after measuring the lower n−1n-1n−1 bits of the subset sum, the algorithm discards any ω(log⁡n)ω(\log n)ω(logn) bits from each of the Fourier labels. Then we prove that the algorithm cannot succeed in solving DCP. This shows that any algorithm following this template must make extensive use of the Fourier labels, and thus serves as a useful guide for developing algorithms for DCP. As a main application, we show that the recent algorithm by Simon (IACR ePrint:2026/1591, August 11 2026) does not solve DCP. We show that after the subset-sum measurement, this algorithm can be implemented (up to exponentially-small error) using only the most-significant third of the Fourier labels, and is therefore subject to our general no-go theorem. To help with verifiability, we release Lean 4 code for our results.