What kind of boolean functions are faster to compute on qc?

Question

Deutsch-Jozsa algorithm can compute if some function $f : \{0,1\}^n \rightarrow \{0,1\} $ is constant. This goes exponentially faster than on classical computers.

If we consider the set of all boolean functions $f : \{0,1\}^n \rightarrow \{0,1\} $ is there a characterizations or intuition about the properties of boolean functions, which achieve such a speedup compared to classical computations?

Consider for example the AND gate, which ANDs all $n$ inputs. I don't know if this is faster on quantum computer, but if yes what does both functions share in common and if not what is different here compared to the constant testing function?

Answer 1

Following up on @luciano's answer, I think you are envisioning a quantum computer as being fast at evaluating functions, when in actuality, quantum computers are better at evaluating global properties of functions (and not, necessarily, the function themselves.)

For example referring to the Deutsch-Jozsa problem, consider two separate bags containing Boolean functions on $n$ variables.

• In one bag (called "constant") we put in the $2$ functions that either evaluate to $0$ for all $2^n$ inputs, or to $1$ for all $2^n$ inputs; and
• In another bag (called "balanced") we put in the functions that evaluate to $0$ for precisely $2^{n-1}$ inputs (and $1$ otherwise).

If we were to scramble the bags and choose a random function, classically we'd have to evaluate the function a couple of times (and worse-case up to $2^{n-1}+1$ times) to know from which bag we grabbed our function. But following the Deutsch-Jozsa algorithm, we only need to evaluate the function once on a quantum computer.

This "balanced" vs. "constant" property is a global property of the functions, closer to what a Fourier transform evaluates.

ADDED

There are $2^{2^n}$ individual Boolean functions with $n$ inputs and $1$ output. However, of all of these, there is only $1$ function on $n$ variables that performs the $\mathsf{AND}$ of all inputs (namely the $\mathsf{AND}$ function), and only $1$ that performs the $\mathsf{XOR}$ of all inputs (namely the $\mathsf{XOR}$ function).

Furthermore it's hard to get one's head around the size of the problems to which quantum algorithms provide a significant speedup. But it's my understanding that there's a theorem (modulo a lot of asterisks and extra hypothesis and other details) that the one weird trick that quantum computers can do that classical computers cannot is to quickly take a Fourier transform of the output of some function, and sample the Fourier transform with a probability given by the (square of the) amplitude of the FT. The Deutsch-Jozsa algorithm determines whether the "DC component" of the FT is large ("constant") or small ("balanced").

Answer 2

Deutsch-Jozsa algorithm is about classifying an oracle $f$ as constant/balanced. The complexity of executing the oracle $f$ itself is not directly relevant for that classification. What it is relevant is how many executions of the oracle $f$ are needed to answer the constant/balanced question.

An example: Let's take an $f$ with $n=2$. You don't know it yet, but $f$ is defined as the classical XOR gate, therefore it is balanced. You need, classically, to execute $f$ 3 times ($2^{{n-1}}+1$, in the general case) with different inputs in order to have enough information to know that is balance. In contrast, a quantum implementation needs a single execution. Note that the fact that XOR is linear does not play a role here.