Quantum filtering of Boolean functions

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

Published Aug 31, 2002• 0 citations

Abstract

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.

Related papers

Quantum-state filtering applied to the discrimination of Boolean functions

János A. Bergou, Mark S. Hillery

arXiv:quant-ph/0507092Physical Review AJul 5, 20059 citations

Quantum Filtering and Discrimination between Sets of Boolean Functions

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

arXiv:quant-ph/0209007Physical Review LettersJun 25, 200375 citations

A Generalization of the Deutsch-Jozsa Algorithm to Multi-Valued Quantum Logic

Yale Fan

We generalize the binary Deutsch-Jozsa algorithm to n- valued logic using the quantum Fourier transform. Our algorithm is not only able to distinguish between constant and balanced Boolean functions in a single query, but can also find closed expressions for classes of affine functions in quantum oracles, accurate to a constant term.

arXiv:0809.0932IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 200726 citations

Comparing two quantum oracles using the Deutsch–Jozsa algorithm

Attila Kiss, Krisztián Varga

There are a lot of articles about quantum algorithms, which involve querying a black box function, often called an oracle.This paper proposes a way to combine two oracles and to determine how similar they are using the Deutsch-Jozsa algorithm.In this case being similar means, that the sets of marked states have just a few ones outside of their intersection.The new quantum algorithm is compared to its classical counterparts and a detailed analysis shows when it will outperform them.

Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatoricaJan 1, 20201 citation

Quantum Algorithms

Yorick Hardy, Willi-Hans Steeb

Deutsch’s problem [54] is given as follows. Suppose we have a boolean function f :→ {0,1} {0,1}.

Birkhäuser Basel eBooksJan 1, 20010 citations

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

arXiv:1603.06505Mar 21, 20168 citations

Quantum filtering of Boolean functions

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

Published Aug 31, 2002• 0 citations

OpenAlex

Abstract

Related papers

Quantum-state filtering applied to the discrimination of Boolean functions

János A. Bergou, Mark S. Hillery

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.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.

arXiv:quant-ph/0507092Physical Review AJul 5, 20059 citations

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.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/0209007Physical Review LettersJun 25, 200375 citations

A Generalization of the Deutsch-Jozsa Algorithm to Multi-Valued Quantum Logic

Yale Fan

arXiv:0809.0932IEEE International Symposium on Multiple-Valued Logic (ISMVL)May 1, 200726 citations

Comparing two quantum oracles using the Deutsch–Jozsa algorithm

Attila Kiss, Krisztián Varga

Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio computatoricaJan 1, 20201 citation

Quantum Algorithms

Yorick Hardy, Willi-Hans Steeb

Deutsch’s problem [54] is given as follows. Suppose we have a boolean function f :→ {0,1} {0,1}.

Birkhäuser Basel eBooksJan 1, 20010 citations

Characterizations of symmetrically partial Boolean functions with exact quantum query complexity

Daowen Qiu, Shenggen Zheng

We give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the promise problem (i.e., symmetric and partial Boolean function) $DJ_n^k$ defined as: $DJ_n^k(x)=1$ for $|x|=n/2$ , $DJ_n^k(x)=0$ for $|x|$ in the set $\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}$ , and it is undefined for the rest cases, where $n$ is even, $|x|$ is the Hamming weight of $x$ . The case of $k=0$ is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function $f$ has exact quantum 1-query complexity if and only if $f$ can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight $\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}$ and Hamming weight in the set $\{ 0, n\}$ for all odd $n$ . In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.We give and prove an optimal exact quantum query algorithm with complexity $k+1$ for computing the promise problem (i.e., symmetric and partial Boolean function) $DJ_n^k$ defined as: $DJ_n^k(x)=1$ for $|x|=n/2$, $DJ_n^k(x)=0$ for $|x|$ in the set $\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}$, and it is undefined for the rest cases, where $n$ is even, $|x|$ is the Hamming weight of $x$. The case of $k=0$ is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function $f$ has exact quantum 1-query complexity if and only if $f$ can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight $\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}$ and Hamming weight in the set $\{ 0, n\}$ for all odd $n$. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.

arXiv:1603.06505Mar 21, 20168 citations

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.

We give and prove an optimal exact quantum query algorithm with complexity

k+1

for computing the promise problem (i.e., symmetric and partial Boolean function)

DJ_n^k

defined as:

DJ_n^k(x)=1

for

|x|=n/2

DJ_n^k(x)=0

for

|x|

in the set

\{0, 1,\ldots, k, n-k, n-k+1,\ldots,n\}

, and it is undefined for the rest cases, where

n

is even,

|x|

is the Hamming weight of

x

. The case of

k=0

is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function

f

has exact quantum 1-query complexity if and only if

f

can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight

\{ \lfloor n/2\rfloor, \lceil n/2\rceil \}

and Hamming weight in the set

\{ 0, n\}

for all odd

n

. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.