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/0507092 · Physical Review A

Quantum-state filtering applied to the discrimination of Boolean functions

János A. Bergou, Mark S. Hillery

Published Jul 5, 2005• 9 citations
arXivHTMLPDF

Abstract

Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the $N$ given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of $N$ nonorthogonal states, ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$, for distinguishing $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.

DOI
10.1103/physreva.72.012302

Related papers

Quantum Filtering and Discrimination between Sets of Boolean Functions

János A. Bergou, Ulrike Herzog, Mark S. Hillery

In quantum state filtering one wants to determine whether an unknown quantum state, which is chosen from a known set of states, [|psi(1)>, em leader,|psi(N)>], is either a specific state, say |psi(1)>, or one of the remaining states, [|psi(2)>, em leader,|psi(N)>]. We present the optimal solution to this problem, in terms of generalized measurements, for the case that the filtering is required to be unambiguous. As an application, we propose an efficient, probabilistic quantum algorithm for distinguishing between sets of Boolean functions, which is a generalization of the Deutsch-Jozsa algorithm.

arXiv:quant-ph/0209007•Physical Review Letters•Jun 25, 2003•75 citations

Optimal unambiguous filtering of a quantum state: An instance in mixed state discrimination

János A. Bergou, Ulrike Herzog, Mark S. Hillery

Deterministic discrimination of nonorthogonal states is forbidden by quantum measurement theory. However, if we do not want to succeed all the time, i.e., allow for inconclusive outcomes to occur, then unambiguous discrimination becomes possible with a certain probability of success. A variant of the problem is set discrimination: the states are grouped in sets and we want to determine to which particular set a given pure input state belongs. We consider here the simplest case, termed quantum state filtering, when the $N$ given nonorthogonal states ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ are divided into two sets and the first set consists of one state only while the second consists of all of the remaining states. We present the derivation of the optimal measurement strategy, in terms of a generalized measurement (positive-operator-valued measure), to distinguish $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. The results, but not the complete derivation, were presented previously [Phys. Rev. Lett. 90, 25901 (2003)] as the emphasis there was on appplication of the results to probabilistic quantum algorithms. We also show that the problem is equivalent to the discrimination of a pure state and an arbitrary mixed state.

arXiv:quant-ph/0504138•Physical Review A•Apr 11, 2005•29 citations

Quantum filtering of Boolean functions

János A. Bergou, Ulrike Herzog, Mark S. Hillery

We develop an efficient probabilistic quantum algorithm that can distinguish between sets of Boolean functions. The method is based on an exact solution to the quantum state filtering problem and can be considered to be an extension of the original Deutsch-Jozsa algorithm.

•Aug 31, 2002•0 citations

From unambiguous quantum state discrimination to quantum state filtering

János A. Bergou, Ulrike Herzog, Mark S. Hillery

Abstract Unambiguous discrimination among nonorthogonal but linearly independent quantum states is possible with a certain probability of success. Here, we consider a new variant of that problem. Instead of discriminating among all of the N different states, we now ask for less. We want to unambiguously assign the state to one of two complementary subsets of the set of N given non‐orthogonal quantum states, each occurring with given a priori probabilities. We refer to the special case when one subset contains only one state and the other contains the remaining N‐1 states as unambiguous quantum state filtering. We present an optimal analytical solution for the special case of N=3, and discuss the optimal strategy to unambiguously distinguish |ψ1〉 from the set {|ψ2〉,|ψ3〉}. For unambiguous filtering the subsets need not be linearly independent. We briefly discuss how to construct generalized interferometers (multiports) which provide a fully linear optical implementation of the optimal strategy.

Fortschritte der Physik•Feb 26, 2003•0 citations

Optimum unambiguous discrimination between subsets of nonorthogonal quantum states

Yuqing Sun, János A. Bergou, Mark S. Hillery

It is known that unambiguous discrimination among nonorthogonal but linearly independent quantum states is possible with a certain probability of success. Here, we consider a variant of that problem. Instead of discriminating among all of the different states, we shall only discriminate between two subsets of them. In particular, for the case of three nonorthogonal states, ${|{\ensuremath{\psi}}_{1}〉,|{\ensuremath{\psi}}_{2}〉,|{\ensuremath{\psi}}_{3}〉},$ we show that the optimal strategy to distinguish $|{\ensuremath{\psi}}_{1}〉$ from the set ${|{\ensuremath{\psi}}_{2}〉,|{\ensuremath{\psi}}_{3}〉}$ has a higher success rate than if we wish to discriminate among all three states. Somewhat surprisingly, for unambiguous discrimination the subsets need not be linearly independent. A fully analytical solution is presented, and we also show how to construct generalized interferometers (multiport) which provide an optical implementation of the optimal strategy.

arXiv:quant-ph/0112051•Physical Review A•Sep 23, 2002•72 citations

Optimum unambiguous discrimination between subsets of non-orthogonal states

Yuqing Sun, János A. Bergou, Mark S. Hillery

Unambiguous discrimination among non-orthogonal but linearly independent quantum states is possible with a certain probability of success. Here we consider a variant of that problem; rather than discriminating among all of the different states, we shall discriminate between two subsets of them. In particular, for the case of 3 states, we find the optimal strategy to distinguish one from the other two. This procedure has a higher probability of success than distinguishing all 3 states. We show how to construct generalized interferometers that provide an implementation of the optimal strategy.

•Dec 8, 2001•0 citations
Quantum-state filtering is a variant of the unambiguous state discrimination problem: the states are grouped in sets and we want to determine to which particular set a given input state belongs. The simplest case, when the NNN given states are divided into two subsets and the first set consists of one state only while the second consists of all of the remaining states, is termed quantum-state filtering. We derived previously the optimal strategy for the case of NNN nonorthogonal states, \ensuremath∣\ensuremathψ1⟩,…,\ensuremath∣\ensuremathψN⟩{\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}\ensuremath∣\ensuremathψ1​⟩,…,\ensuremath∣\ensuremathψN​⟩, for distinguishing \ensuremath∣\ensuremathψ1⟩\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩\ensuremath∣\ensuremathψ1​⟩ from the set \ensuremath∣\ensuremathψ2⟩,…,\ensuremath∣\ensuremathψN⟩{\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}\ensuremath∣\ensuremathψ2​⟩,…,\ensuremath∣\ensuremathψN​⟩ and the corresponding optimal success and failure probabilities. In a previous paper [Phys. Rev. Lett. 90, 257901 (2003)], we sketched an appplication of the results to probabilistic quantum algorithms. Here we fill the gaps and give the complete derivation of the probabilstic quantum algorithm that can optimally distinguish between two classes of Boolean functions, that of the balanced functions and that of the biased functions. The algorithm is probabilistic, it fails sometimes but when it does it lets us know that it did. Our approach can be considered as a generalization of the Deutsch-Jozsa algorithm that was developed for the discrimination of balanced and constant Boolean functions.
In quantum state filtering one wants to determine whether an unknown quantum state, which is chosen from a known set of states, [|psi(1)>, em leader,|psi(N)>], is either a specific state, say |psi(1)>, or one of the remaining states, [|psi(2)>, em leader,|psi(N)>]. We present the optimal solution to this problem, in terms of generalized measurements, for the case that the filtering is required to be unambiguous. As an application, we propose an efficient, probabilistic quantum algorithm for distinguishing between sets of Boolean functions, which is a generalization of the Deutsch-Jozsa algorithm.
Deterministic discrimination of nonorthogonal states is forbidden by quantum measurement theory. However, if we do not want to succeed all the time, i.e., allow for inconclusive outcomes to occur, then unambiguous discrimination becomes possible with a certain probability of success. A variant of the problem is set discrimination: the states are grouped in sets and we want to determine to which particular set a given pure input state belongs. We consider here the simplest case, termed quantum state filtering, when the NNN given nonorthogonal states ${\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ are divided into two sets and the first set consists of one state only while the second consists of all of the remaining states. We present the derivation of the optimal measurement strategy, in terms of a generalized measurement (positive-operator-valued measure), to distinguish $\ensuremath{\mid}{\ensuremath{\psi}}_{1}⟩$ from the set ${\ensuremath{\mid}{\ensuremath{\psi}}_{2}⟩,\dots{},\ensuremath{\mid}{\ensuremath{\psi}}_{N}⟩}$ and the corresponding optimal success and failure probabilities. The results, but not the complete derivation, were presented previously [Phys. Rev. Lett. 90, 25901 (2003)] as the emphasis there was on appplication of the results to probabilistic quantum algorithms. We also show that the problem is equivalent to the discrimination of a pure state and an arbitrary mixed state.
Abstract Unambiguous discrimination among nonorthogonal but linearly independent quantum states is possible with a certain probability of success. Here, we consider a new variant of that problem. Instead of discriminating among all of the N different states, we now ask for less. We want to unambiguously assign the state to one of two complementary subsets of the set of N given non‐orthogonal quantum states, each occurring with given a priori probabilities. We refer to the special case when one subset contains only one state and the other contains the remaining N‐1 states as unambiguous quantum state filtering. We present an optimal analytical solution for the special case of N=3, and discuss the optimal strategy to unambiguously distinguish |ψ1〉 from the set {|ψ2〉,|ψ3〉}. For unambiguous filtering the subsets need not be linearly independent. We briefly discuss how to construct generalized interferometers (multiports) which provide a fully linear optical implementation of the optimal strategy.
It is known that unambiguous discrimination among nonorthogonal but linearly independent quantum states is possible with a certain probability of success. Here, we consider a variant of that problem. Instead of discriminating among all of the different states, we shall only discriminate between two subsets of them. In particular, for the case of three nonorthogonal states, ${|{\ensuremath{\psi}}_{1}〉,|{\ensuremath{\psi}}_{2}〉,|{\ensuremath{\psi}}_{3}〉},$ we show that the optimal strategy to distinguish $|{\ensuremath{\psi}}_{1}〉$ from the set ${|{\ensuremath{\psi}}_{2}〉,|{\ensuremath{\psi}}_{3}〉}$ has a higher success rate than if we wish to discriminate among all three states. Somewhat surprisingly, for unambiguous discrimination the subsets need not be linearly independent. A fully analytical solution is presented, and we also show how to construct generalized interferometers (multiport) which provide an optical implementation of the optimal strategy.
Unambiguous discrimination among non-orthogonal but linearly independent quantum states is possible with a certain probability of success. Here we consider a variant of that problem; rather than discriminating among all of the different states, we shall discriminate between two subsets of them. In particular, for the case of 3 states, we find the optimal strategy to distinguish one from the other two. This procedure has a higher probability of success than distinguishing all 3 states. We show how to construct generalized interferometers that provide an implementation of the optimal strategy.