Ex7 4
$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\def\tr{\mathord{\mbox{tr}}}\mathbf{Exercise\ 7.4}$
a) Prove that any classical algorithm requires at least two calls to $C_f$ to solve Deutsch's problem.
b) Prove that any classical algorithm requires $2^{n-1} + 1$ calls to $C_f$ to solve the Deutsch-Jozsa problem with certainty.
c) Describe a classical approach to the Deutsch-Jozsa problem that solves it with high probability using fewer than $2^{n-1} + 1$ calls. Calculate the success probability of your approach as a function of the number of calls.
page revision: 0, last edited: 18 Nov 2012 19:30
a)
In the classical setup no linear combinations are allowed, only 1-dimensional input to the algorithm.
So one call to the oracle $C_f$ can only have 0 or 1 as input, and the output can only be $f(0)$ or $f(1)$. In either case, there is no information about the other value and it cannot be determined if $f$ is constant or 'balanced' ($f(0) \neq f(1)$). Hence, at least two calls to $C_f$ are required.
Note that Cristian Calude has given a classical implementation of the solution to Deutsch's problem:
DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM
International Journal of Quantum Information Vol. 05, No. 03, pp. 409-415 (2007)
However, his solution uses 2-dimensional input to the oracle and 2-dimensional output (complex numbers), so the Calude solution is mathematically the same as the quantum algorithm.
This caused some debate, for example some remarks by Scott Aaronson on his blog and extensive comments to the Quanta Magazine article "Quantum Algorithms Struggle Against Old Foe: Clever Computers".
b)
If $f$ evaluates to 0 on half of the input values, which is $2^n/2 = 2^{n-1}$ calls, then $f$ can still be either constant or balanced. But one further call will settle the case, so $2^{n-1} + 1$ calls to the oracle are required to determine with certainty if $f$ is constant or balanced.
c)
(1)Let $N = 2^n$ be the number of input values to $f$ and assume we make $k < N/2$ calls to $f$.
We have the following events:
We want to determine the conditional probability $P(C\mid K)$ that $f$ is constant given $k$ zeroes in a row.
(2)From the definition of conditional probability we have
Since $B,C$ are disjoint events we also have from the law of Total Probability that
(3)We don't know anything about the probabilities of $B,C$, so we will just assume uniform probabilities:
(4)Obviously, $P(K \mid C) = 1$ and since there are $N/2$ zeroes when $f$ is balanced, we have the following expression for $P(K \mid B)$:
(5)Combining all this, we get for $P(C \mid K)$:
(6)Note that for $k=0$ we get back our assumption on the probability of $C$: $P(C \mid K) = \frac12$.
For $k$ approaching $N/2$ we have $\binom{N/2}{k} << \binom{N}{k}$ and $P(C \mid K)$ is close to 1.
Hence, with high probability it is possible to determine if $f$ is constant (or balanced) with fewer calls than $2^{n-1} + 1$.