Notes - Quantum Information HT24, The Deutsch-Jozsa game
Flashcards
Describe the Deutsch-Jozsa game, and give the worst case query complexity for both a classical oracle and a quantum oracle.
A referee picks a Boolean function $f : \{0, \cdots, M-1\} \to \{0, 1\}$ with $M$ even, and promises that the function $f$ has one of two properties:
- $f$ is constant, or
- $f$ is balanced, i.e. the number of inputs where $f(x) = 0$ equals the number of inputs where $f(x) = 1$
Alice wants to find out which of the properties holds.
- With a classical oracle, this takes at most $M/2 + 1$ queries.
- With a quantum oracle, this can be done in $1$ query.
Suppose Alice is playing the Deutsch-Jozsa game, i.e.
A referee picks a Boolean function $f : \{0, \cdots, M-1\} \to \{0, 1\}$ with $M$ even, and promises that the function $f$ has one of two properties:
- $f$ is constant, or
- $f$ is balanced, i.e. the number of inputs where $f(x) = 0$ equals the number of inputs where $f(x) = 1$
Alice wants to find out which of the properties holds.
Quickly prove that the Deutsch-Jozsa algorithm solves this problem with only $1$ query to the reduced oracle $V _ f$, implemented as follows:
- Prepare the Fourier state $ \vert e _ 0 \rangle = \frac{1}{\sqrt M} \sum^{M-1} _ {x = 0} \vert x\rangle$
- Apply the reduced oracle $V _ f$
- Measure the output in the Fourier basis $\{ \vert e _ k\rangle\}^{M-1} _ {k = 0}$
- If the measurement is $k = 0$, declare that $f$ is constant. Otherwise, declare that $f$ is balanced.
A referee picks a Boolean function $f : \{0, \cdots, M-1\} \to \{0, 1\}$ with $M$ even, and promises that the function $f$ has one of two properties:
- $f$ is constant, or
- $f$ is balanced, i.e. the number of inputs where $f(x) = 0$ equals the number of inputs where $f(x) = 1$
Alice wants to find out which of the properties holds.
- Prepare the Fourier state $ \vert e _ 0 \rangle = \frac{1}{\sqrt M} \sum^{M-1} _ {x = 0} \vert x\rangle$
- Apply the reduced oracle $V _ f$
- Measure the output in the Fourier basis $\{ \vert e _ k\rangle\}^{M-1} _ {k = 0}$
- If the measurement is $k = 0$, declare that $f$ is constant. Otherwise, declare that $f$ is balanced.
\[\begin{aligned}
p(0) &= \left|\langle e_
0| V_
f |e_0 \rangle\right|^2 \\\\
&= \left|\langle e_
0| \frac{1}{\sqrt M} \sum^{M-1}_
{m = 0} V_
f |m\rangle \right|^2 \\\\
&= \left|\langle e_
0| \frac{1}{\sqrt M} \sum^{M-1}_
{m = 0} (-1)^{f(m)} |m\rangle \right|^2 \\\\
&= \left|\langle e_
0| \frac{1}{\sqrt M} \left(\sum_
{m \colon f(m) = 0} |m\rangle - \sum_
{m \colon f(m) = 1} |m\rangle\right) \right|^2 \\\\
\end{aligned}\]
Then we see that
\[p(0 \mid f\text{ constant}) = 1\]and
\[p(0 \mid f\text{ balanced}) = 0\]