Birkhäuser Basel eBooks

Quantum Algorithms

Yorick Hardy, Willi-Hans Steeb

Published Jan 1, 2001• 0 citations

Publisher

Abstract

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

DOI: 10.1007/978-3-0348-8366-5_21

Related papers

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, 20020 citations

Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions

Subhamoy Maitra, Partha Mukhopadhyay

arXiv:quant-ph/0410042Oct 6, 20044 citations

Some extensions of the Deutsch problem

A. M. Grassi, G. Strini

In the search for useful trick for quantum algorithms, a study has been made on the possible global properties of the standard logic functions of two and more logical variables. This gives an algorithm exponentially faster than the corresponding classical one.

Mysteries, Puzzles, and Paradoxes in Quantum MechanicsJan 1, 19990 citations

De-Quantising the Solution of Deutsch's Problem

Cristian S. Calude

arXiv:quant-ph/0610220Oct 26, 20061 citation

Deutsch and Jozsa's Algorithm Revisited

J. Cooper

A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed

arXiv:quant-ph/0603231Mar 27, 20060 citations

Polynomial-time quantum algorithms for finding the linear structures of Boolean function

Wanqing Wu, Huanguo Zhang, Houzhen Wang +1 more

Quantum Information ProcessingFeb 3, 20156 citations

Birkhäuser Basel eBooks

Quantum Algorithms

Yorick Hardy, Willi-Hans Steeb

Published Jan 1, 2001• 0 citations

Publisher

Abstract

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

DOI: 10.1007/978-3-0348-8366-5_21

Related papers

Quantum filtering of Boolean functions

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

Aug 31, 20020 citations

Deutsch-Jozsa Algorithm Revisited in the Domain of Cryptographically Significant Boolean Functions

Subhamoy Maitra, Partha Mukhopadhyay

Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$ -variable Boolean function and its Walsh spectra is denoted by $W_f(ω)$ at the point $ω\in \{0, 1\}^n$ . The Boolean function is available in the form of an oracle. We like to find an $ω$ such that $W_f(ω) \neq 0$ as this will provide one of the linear functions which are correlated to $f$ . We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$ . We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.Boolean functions are important building blocks in cryptography for their wide application in both stream and block cipher systems. For cryptanalysis of such systems one tries to find out linear functions that are correlated to the Boolean functions used in the crypto system. Let $f$ be an $n$-variable Boolean function and its Walsh spectra is denoted by $W_f(ω)$ at the point $ω\in \{0, 1\}^n$. The Boolean function is available in the form of an oracle. We like to find an $ω$ such that $W_f(ω) \neq 0$ as this will provide one of the linear functions which are correlated to $f$. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in $n$. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.

arXiv:quant-ph/0410042Oct 6, 20044 citations

Some extensions of the Deutsch problem

A. M. Grassi, G. Strini

Mysteries, Puzzles, and Paradoxes in Quantum MechanicsJan 1, 19990 citations

De-Quantising the Solution of Deutsch's Problem

Cristian S. Calude

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called {\it Deutsch's problem}. Consider a Boolean function $f: \{0,1\} \to \{0,1\}$ and suppose that we have a (classical) black box to compute it. The problem asks whether $f$ is constant (that is, $f(0) = f(1)$ ) or balanced ( $f(0) \not= f(1)$ ). Classically, to solve the problem seems to require the computation of $f(0)$ and $ f(1)$, and then the comparison of results. Is it possible to solve the problem with {\em only one} query on $f$ ? In a famous paper published in 1985, Deutsch posed the problem and obtained a ``quantum'' {\em partial affirmative answer}. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be {\it de-quantised} to a deterministic simpler solution which is as efficient as the quantum one. The use of ``superposition'', a key ingredient of quantum algorithm, is--in this specific case--classically available.Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called {\it Deutsch's problem}. Consider a Boolean function $f: \{0,1\} \to \{0,1\}$ and suppose that we have a (classical) black box to compute it. The problem asks whether $f$ is constant (that is, $f(0) = f(1)$) or balanced ($f(0) \not= f(1)$). Classically, to solve the problem seems to require the computation of $f(0)$ and $ f(1)$, and then the comparison of results. Is it possible to solve the problem with {\em only one} query on $f$? In a famous paper published in 1985, Deutsch posed the problem and obtained a ``quantum'' {\em partial affirmative answer}. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be {\it de-quantised} to a deterministic simpler solution which is as efficient as the quantum one. The use of ``superposition'', a key ingredient of quantum algorithm, is--in this specific case--classically available.

arXiv:quant-ph/0610220Oct 26, 20061 citation

Deutsch and Jozsa's Algorithm Revisited

J. Cooper

A classical analogue of Deutsch and Jozsa's algorithm is given and its implications on quantum computing is discussed

arXiv:quant-ph/0603231Mar 27, 20060 citations

Polynomial-time quantum algorithms for finding the linear structures of Boolean function

Wanqing Wu, Huanguo Zhang, Houzhen Wang +1 more

Quantum Information ProcessingFeb 3, 20156 citations

f

be an

n

-variable Boolean function and its Walsh spectra is denoted by

W_f(ω)

at the point

ω\in \{0, 1\}^n

. The Boolean function is available in the form of an oracle. We like to find an

ω

such that

W_f(ω) \neq 0

as this will provide one of the linear functions which are correlated to

f

. We show that the quantum algorithm proposed by Deutsch and Jozsa (1992) solves the above mentioned problem in constant time. However, the best known classical algorithm to solve this problem requires exponential time in

n

. We also analyse certain classes of cryptographically significant Boolean functions and highlight how the basic Deutsch-Jozsa algorithm performs on them.

Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called {\it Deutsch's problem}. Consider a Boolean function

f: \{0,1\} \to \{0,1\}

and suppose that we have a (classical) black box to compute it. The problem asks whether

f

is constant (that is,

f(0) = f(1)

) or balanced (

f(0) \not= f(1)

). Classically, to solve the problem seems to require the computation of

f(0)

and $ f(1)$, and then the comparison of results. Is it possible to solve the problem with {\em only one} query on

f

? In a famous paper published in 1985, Deutsch posed the problem and obtained a ``quantum'' {\em partial affirmative answer}. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be {\it de-quantised} to a deterministic simpler solution which is as efficient as the quantum one. The use of ``superposition'', a key ingredient of quantum algorithm, is--in this specific case--classically available.