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

arXiv:quant-ph/0102020 · Physical Review A

Quantum template matching

Masahide Sasaki, A. Carlini, Richard Jozsa

Published Jul 17, 2001• 62 citations
arXivHTMLPDF

Abstract

We consider the quantum analogue of the pattern-matching problem, which consists of classifying a given unknown system according to certain predefined pattern classes. We address the problem of quantum template matching in which each pattern class ${\mathcal{C}}_{i}$ is represented by a known quantum state ${g}_{i}$ called a template state, and our task is to find a template that optimally matches a given unknown quantum state $\mathrm{f\ifmmode \hat{}\else \^{}\fi{}}.$ We set up a precise formulation of this problem in terms of the optimal strategy for an associated quantum Bayesian inference problem. We then investigate various examples of quantum template matching for qubit systems, considering the effect of allowing a finite number of copies of the input state $\mathrm{f\ifmmode \hat{}\else \^{}\fi{}}.$ We compare quantum optimal matching strategies and semiclassical strategies to demonstrate an entanglement assisted enhancement of performance in the general quantum optimal strategy.

DOI
10.1103/physreva.64.022317

Related papers

Quantum learning and universal quantum matching machine

Masahide Sasaki, A. Carlini

Suppose that three kinds of quantum systems are given in some unknown states $|f{〉}^{\ensuremath{\bigotimes}N},$ $|{g}_{1}{〉}^{\ensuremath{\bigotimes}K},$ and $|{g}_{2}{〉}^{\ensuremath{\bigotimes}K},$ and we want to decide which template state $|{g}_{1}〉$ or $|{g}_{2}〉,$ each representing the feature of the pattern class ${\mathcal{C}}_{1}$ or ${\mathcal{C}}_{2},$ respectively, is closest to the input feature state $|f〉.$ This is an extension of the pattern matching problem into the quantum domain. Assuming that these states are known a priori to belong to a certain parametric family of pure qubit systems, we derive two kinds of matching strategies. The first one is a semiclassical strategy that is obtained by the natural extension of conventional matching strategies and consists of a two-stage procedure: identification (estimation) of the unknown template states to design the classifier (learning process to train the classifier) and classification of the input system into the appropriate pattern class based on the estimated results. The other is a fully quantum strategy without any intermediate measurement, which we might call as the universal quantum matching machine. We present the Bayes optimal solutions for both strategies in the case of $K=1,$ showing that there certainly exists a fully quantum matching procedure that is strictly superior to the straightforward semiclassical extension of the conventional matching strategy based on the learning process.

arXiv:quant-ph/0202173•Physical Review A•Aug 6, 2002•103 citations

Programmable quantum-state discriminators with simple programs

János A. Bergou, Vladimír Bužek, Edgar Feldman +2 more

We describe a class of programmable devices that can discriminate between two quantum states. We consider two cases. In the first, both states are unknown. One copy of each of the unknown states is provided as an input, or program, for the two program registers, and the data state, which is guaranteed to be prepared in one of the program states, is fed into the data register of the device. This device will then tell us, in an optimal way, which of the templates stored in the program registers the data state matches. In the second case, we know one of the states while the other is unknown. One copy of the unknown state is fed into the single program register, and the data state which is guaranteed to be prepared in either the program state or the known state, is fed into the data register. The device will then tell us, again optimally, whether the data state matches the template or is the known state. We determine two types of optimal devices. The first performs discrimination with minimum error, and the second performs optimum unambiguous discrimination. In all cases we first treat the simpler problem of only one copy of the data state and then generalize the treatment to $n$ copies. In comparison to other works we find that providing $n>1$ copies of the data state yields higher success probabilities than providing $n>1$ copies of the program states.

arXiv:quant-ph/0602164•Physical Review A•Jun 28, 2006•48 citations

Quantum learning: asymptotically optimal classification of qubit states

Mădălin Guţǎ, Wojciech Kotłowski

Pattern recognition is a central topic in learning theory, with numerous applications such as voice and text recognition, image analysis and computer diagnosis. The statistical setup in classification is the following: we are given an i.i.d. training set ( X 1 , Y 1 ), ... , ( X n , Y n ), where X i represents a feature and Y i ∊{0, 1} is a label attached to that feature. The underlying joint distribution of ( X , Y ) is unknown, but we can learn about it from the training set, and we aim at devising low error classifiers f: X → Y used to predict the label of new incoming features. In this paper, we solve a quantum analogue of this problem, namely the classification of two arbitrary unknown mixed qubit states. Given a number of 'training' copies from each of the states, we would like to 'learn' about them by performing a measurement on the training set. The outcome is then used to design measurements for the classification of future systems with unknown labels. We found the asymptotically optimal classification strategy and show that typically it performs strictly better than a plug-in strategy, which consists of estimating the states separately and then discriminating between them using the Helstrom measurement. The figure of merit is given by the excess risk equal to the difference between the probability of error and the probability of error of the optimal measurement for known states. We show that the excess risk scales as n −1 and compute the exact constant of the rate.

arXiv:1004.2468•New Journal of Physics•Dec 23, 2010•52 citations

Strategy optimization for Bayesian quantum parameter estimation with finite copies: Adaptive greedy, parallel, sequential, and general strategies

Erik L. André, Jessica Bavaresco, Mohammad Mehboudi

In this work, we study Bayesian quantum parameter estimation given a finite number of uses of the process encoding one or more unknown physical quantities. We analyze the performance of different kinds of quantum metrological protocols, including the conventional parallel, sequential, or general, which may involve an indefinite causal order. We also analyze a class of hybrid adaptive greedy strategies, which are based on classical feedforward between quantum protocols to optimize the next round. Within each class, the central question is to determine the optimal strategy -- namely, the choice of optimal input state, control operations, measurement, and estimators. Using the formalism of higher-order operations, we develop an algorithm that searches for the optimal solution, and we provide a numerical implementation based on semidefinite programming. Our benchmark cases, specifically those against existing analytical solutions, demonstrate how powerful and precise our method is. We further demonstrate the strength of our algorithm in several examples, from single to multiparameter estimation, and with various prior distributions. Particularly, we find examples where the adaptive greedy strategy matches the performance of general strategies with indefinite causal order, and at the same time examples that showcase a strict hierarchy between all different classes.

quant-pharXiv:2602.09655•Quantum Science and Technology•Feb 11, 2026•1 citation

Optimal Universal Learning Machines for Quantum State Discrimination

Marco Fanizza, Andrea Mari, Vittorio Giovannetti

We consider the problem of correctly classifying a given quantum two-level system (qubit) which is known to be in one of two equally probable quantum states. We assume that this task should be performed by a quantum machine which does not have at its disposal a complete classical description of the two template states, but can only have partial prior information about their level of purity and mutual overlap. Moreover, similarly to the classical supervised learning paradigm, we assume that the machine can be trained by n qubits prepared in the first template state and by n more qubits prepared in the second template state. In this situation, we are interested in the optimal process which correctly classifies the input qubit with the largest probability allowed by quantum mechanics. The problem is studied in its full generality for a number of different prior information scenarios and for an arbitrary size n of the training data. Finite size corrections around the asymptotic limit n → ∞ are derived. When the states are assumed to be pure, with known overlap, the problem is also solved in the case of d-level systems.

arXiv:1805.03477•IEEE Transactions on Information Theory•May 16, 2019•25 citations

Quantum Circuit Template Matching Optimization Method for Constrained Connectivity

Xiaofeng Gao, Zhijin Guan, Shiguang Feng +1 more

The execution of quantum algorithms requires two key considerations. On the one hand, it should meet the connectivity constraint requirements of quantum circuit mapping for quantum architectures, and on the other hand, it needs to consider reducing the probability of errors in the execution of quantum circuits as much as possible. This paper proposes a novel optimization technique based on template matching that to satisfy both requirements. The template matching optimization method can significantly reduce the number of gates in a quantum circuit and further enhance its practicality. It stands as advanced optimization technology available today. Our method optimizes quantum logic circuits mapped onto quantum architecture by initially selecting their linear substructure. We then zone the circuit according to the gate dependency graph and optimize each block through template matching. Finally, we reorganize the circuit to obtain the optimized version as the final result. Our proposed method is amenable to various quantum architectures. To evaluate its efficacy, we conduct a comparative analysis with the t|ket⟩ and Qiskit compiler using a set of benchmark test circuits. Specifically, compare to the t|ket⟩ compiler method, the highest average optimization rate of our method can reach 25.75%. Compare with the Qiskit compiler method, the highest average optimization rate can reach 32.72%. Overall, our approach has significant optimization advantages.

Axioms•Jul 14, 2023•8 citations
We consider the quantum analogue of the pattern-matching problem, which consists of classifying a given unknown system according to certain predefined pattern classes. We address the problem of quantum template matching in which each pattern class Ci{\mathcal{C}}_{i}Ci​ is represented by a known quantum state gi{g}_{i}gi​ called a template state, and our task is to find a template that optimally matches a given unknown quantum state f\ifmmode^\elseˆ\fi.\mathrm{f\ifmmode \hat{}\else \^{}\fi{}}.f\ifmmode^\elseˆ\fi. We set up a precise formulation of this problem in terms of the optimal strategy for an associated quantum Bayesian inference problem. We then investigate various examples of quantum template matching for qubit systems, considering the effect of allowing a finite number of copies of the input state f\ifmmode^\elseˆ\fi.\mathrm{f\ifmmode \hat{}\else \^{}\fi{}}.f\ifmmode^\elseˆ\fi. We compare quantum optimal matching strategies and semiclassical strategies to demonstrate an entanglement assisted enhancement of performance in the general quantum optimal strategy.
Suppose that three kinds of quantum systems are given in some unknown states $|f{〉}^{\ensuremath{\bigotimes}N},$ $|{g}_{1}{〉}^{\ensuremath{\bigotimes}K},$ and $|{g}_{2}{〉}^{\ensuremath{\bigotimes}K},$ and we want to decide which template state ∣g1〉|{g}_{1}〉∣g1​〉 or ∣g2〉,|{g}_{2}〉,∣g2​〉, each representing the feature of the pattern class C1{\mathcal{C}}_{1}C1​ or C2,{\mathcal{C}}_{2},C2​, respectively, is closest to the input feature state ∣f〉.|f〉.∣f〉. This is an extension of the pattern matching problem into the quantum domain. Assuming that these states are known a priori to belong to a certain parametric family of pure qubit systems, we derive two kinds of matching strategies. The first one is a semiclassical strategy that is obtained by the natural extension of conventional matching strategies and consists of a two-stage procedure: identification (estimation) of the unknown template states to design the classifier (learning process to train the classifier) and classification of the input system into the appropriate pattern class based on the estimated results. The other is a fully quantum strategy without any intermediate measurement, which we might call as the universal quantum matching machine. We present the Bayes optimal solutions for both strategies in the case of K=1,K=1,K=1, showing that there certainly exists a fully quantum matching procedure that is strictly superior to the straightforward semiclassical extension of the conventional matching strategy based on the learning process.
We describe a class of programmable devices that can discriminate between two quantum states. We consider two cases. In the first, both states are unknown. One copy of each of the unknown states is provided as an input, or program, for the two program registers, and the data state, which is guaranteed to be prepared in one of the program states, is fed into the data register of the device. This device will then tell us, in an optimal way, which of the templates stored in the program registers the data state matches. In the second case, we know one of the states while the other is unknown. One copy of the unknown state is fed into the single program register, and the data state which is guaranteed to be prepared in either the program state or the known state, is fed into the data register. The device will then tell us, again optimally, whether the data state matches the template or is the known state. We determine two types of optimal devices. The first performs discrimination with minimum error, and the second performs optimum unambiguous discrimination. In all cases we first treat the simpler problem of only one copy of the data state and then generalize the treatment to nnn copies. In comparison to other works we find that providing n>1n>1n>1 copies of the data state yields higher success probabilities than providing n>1n>1n>1 copies of the program states.
Pattern recognition is a central topic in learning theory, with numerous applications such as voice and text recognition, image analysis and computer diagnosis. The statistical setup in classification is the following: we are given an i.i.d. training set ( X 1 , Y 1 ), ... , ( X n , Y n ), where X i represents a feature and Y i ∊{0, 1} is a label attached to that feature. The underlying joint distribution of ( X , Y ) is unknown, but we can learn about it from the training set, and we aim at devising low error classifiers f: X → Y used to predict the label of new incoming features. In this paper, we solve a quantum analogue of this problem, namely the classification of two arbitrary unknown mixed qubit states. Given a number of 'training' copies from each of the states, we would like to 'learn' about them by performing a measurement on the training set. The outcome is then used to design measurements for the classification of future systems with unknown labels. We found the asymptotically optimal classification strategy and show that typically it performs strictly better than a plug-in strategy, which consists of estimating the states separately and then discriminating between them using the Helstrom measurement. The figure of merit is given by the excess risk equal to the difference between the probability of error and the probability of error of the optimal measurement for known states. We show that the excess risk scales as n −1 and compute the exact constant of the rate.
In this work, we study Bayesian quantum parameter estimation given a finite number of uses of the process encoding one or more unknown physical quantities. We analyze the performance of different kinds of quantum metrological protocols, including the conventional parallel, sequential, or general, which may involve an indefinite causal order. We also analyze a class of hybrid adaptive greedy strategies, which are based on classical feedforward between quantum protocols to optimize the next round. Within each class, the central question is to determine the optimal strategy -- namely, the choice of optimal input state, control operations, measurement, and estimators. Using the formalism of higher-order operations, we develop an algorithm that searches for the optimal solution, and we provide a numerical implementation based on semidefinite programming. Our benchmark cases, specifically those against existing analytical solutions, demonstrate how powerful and precise our method is. We further demonstrate the strength of our algorithm in several examples, from single to multiparameter estimation, and with various prior distributions. Particularly, we find examples where the adaptive greedy strategy matches the performance of general strategies with indefinite causal order, and at the same time examples that showcase a strict hierarchy between all different classes.
We consider the problem of correctly classifying a given quantum two-level system (qubit) which is known to be in one of two equally probable quantum states. We assume that this task should be performed by a quantum machine which does not have at its disposal a complete classical description of the two template states, but can only have partial prior information about their level of purity and mutual overlap. Moreover, similarly to the classical supervised learning paradigm, we assume that the machine can be trained by n qubits prepared in the first template state and by n more qubits prepared in the second template state. In this situation, we are interested in the optimal process which correctly classifies the input qubit with the largest probability allowed by quantum mechanics. The problem is studied in its full generality for a number of different prior information scenarios and for an arbitrary size n of the training data. Finite size corrections around the asymptotic limit n → ∞ are derived. When the states are assumed to be pure, with known overlap, the problem is also solved in the case of d-level systems.
The execution of quantum algorithms requires two key considerations. On the one hand, it should meet the connectivity constraint requirements of quantum circuit mapping for quantum architectures, and on the other hand, it needs to consider reducing the probability of errors in the execution of quantum circuits as much as possible. This paper proposes a novel optimization technique based on template matching that to satisfy both requirements. The template matching optimization method can significantly reduce the number of gates in a quantum circuit and further enhance its practicality. It stands as advanced optimization technology available today. Our method optimizes quantum logic circuits mapped onto quantum architecture by initially selecting their linear substructure. We then zone the circuit according to the gate dependency graph and optimize each block through template matching. Finally, we reorganize the circuit to obtain the optimized version as the final result. Our proposed method is amenable to various quantum architectures. To evaluate its efficacy, we conduct a comparative analysis with the t|ket⟩ and Qiskit compiler using a set of benchmark test circuits. Specifically, compare to the t|ket⟩ compiler method, the highest average optimization rate of our method can reach 25.75%. Compare with the Qiskit compiler method, the highest average optimization rate can reach 32.72%. Overall, our approach has significant optimization advantages.