Consider the problem where one is given black-box access to a function $f : \{0,1\}^n \to \{0,1\}$ such that $f(x)=\mathbf{a}\cdot \mathbf{x}$, where $\mathbf{a}\in \{0,1\}^n$ is unknown. Here $\mathbf{a}\cdot \mathbf{x} = a_1x_1+a_2x_2+\dots +a_n x_n (mod 2)$ is the dot product of $\mathbf{a}$ and $\mathbf{x}$ in modulo-$2$ arithmetic. The goal is to determine the $n$-bit string $a$.
The following classical algorithm solves this problem with $n$ queries. Let $\mathbf{x_k}\in\{0,1\}^n$ be the bit string $\mathbf{x_k}:=0\dots010\dots0$ which has a bit value of $1$ in the $k$th position and $0$ everywhere else.
For some fixed bitstring $\mathbf{a}\neq\mathbf{0}$, querying $f$ with some bitstring $\mathbf{x}$ gives $\mathbf{a}\cdot \mathbf{x} = a_1x_1+a_2x_2+\dots +a_n x_n (mod 2)$, which can be thought of as an equation in the $n$ unknowns given by the $a_i$. Then querying $f$ with another string $\mathbf{x'}$ will similarly yield another equation of the form $\mathbf{x'} = a_1x'_1+a_2x'_2+\dots +a_n x'_n (mod 2)$. Then after $k$ queries with $k<n$ there will be a system of $k$ equations in $n$ unknowns. It is a general fact of linear algebra that such a system cannot uniquely determine the values of all of the $a_i$ variables/bits that comprise the unknown string $\mathbf{a}$. Therefore, $\mathbf{a}$ cannot be uniquely determined. If $k$ queries have been made, and the resulting equations from each of these are independent, then at most $k$ bits of $\mathbf{a}$ can be determined. Thus, no classical algorithm can solve this problem with fewer than $n$ queries in order to uniquely determine $\mathbf{a}$ with certainty.
Presented here is a quantum algorithm for solving the problem. Begin with an $n+1$ qubits, where the first $n$ qubit registers are initialized in the state $\ket{0}$ and the last qubit in the state $\ket{1}$. Consider the following circuit:
Here the first and last gates apply the single qubit Hadamard gate to each of the $n+1$ registers. The second gate $U_f$ is defined as
\[
U_f: \ket{\mathbf{x}}\ket{y}\mapsto \ket{\mathbf{x}}\ket{y\oplus f(x)},
\]
where $\mathbf{x}\in\{0,1\}^n$ and $y\in\{0,1\}$. The last part of the circuit denotes a measurement on the first $n$ registers.
Consider the action of this circuit on the initial state $\ket{\mathbf{0}}\ket{1}$ up until the measurements are performed:
\[\begin{align*}
\ket{\mathbf{0}}\ket{1}\overset{H^{\otimes n+1}}\mapsto &
\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{0}-\ket{1})\\
\overset{U_f}\mapsto \ \ &\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{\mathbf{a}\cdot\mathbf{j}}-\ket{1\oplus\mathbf{a}\cdot\mathbf{j}})\\
&=\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}}\ket{\mathbf{j}}(\ket{0}-\ket{1}) \\
\overset{H^{\otimes n+1}}\mapsto &\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\end{align*}\]
The third line of this calculation gives the state that results after the Hadamard gates and $U_f$ gate is applied.
As computed in part (c), the state that results after the second set of Hadamard gates is applied is given by
\[
\ket{\varphi}:=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\]
Let the amplitude of the $\ket{\mathbf{k}}$ in this superposition be given by $\alpha_k$. Then
\[
\alpha_k=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}.
\]
The amplitude of the state $\ket{\mathbf{a}}$ in $\ket{\varphi}$ is
\[
\alpha_a=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}
=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{0}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}1=\frac{1}{2^{n}}2^n=1.
\]
Hence, the first $n$ registers in the state $\ket{\varphi}$ are in the state $\ket{\mathbf{a}}$ with probability $1$. Since $\ket{\varphi}$ must be a normalized state, this implies that the amplitudes $\alpha_k$ of the states $\ket{\mathbf{k}}$ for all $\mathbf{k}\neq\mathbf{a}$ in $\ket{\varphi}$ are $\alpha_k=0$. Therefore, when the first $n$ registers are measured in the computational basis the state $\ket{\mathbf{a}}$ will always be observed, which then determines the string $\mathbf{a}$.
The following classical algorithm solves this problem with $n$ queries. Let $\mathbf{x_k}\in\{0,1\}^n$ be the bit string $\mathbf{x_k}:=0\dots010\dots0$ which has a bit value of $1$ in the $k$th position and $0$ everywhere else.
- Set $k=1$.
- Query $f$ at $\mathbf{x_k}$ to get $f(\mathbf{x_k})=\mathbf{a}\cdot \mathbf{x_k}=a_k$.
- Set $k'=k+1$, if $k\leq n$ and proceed to step (4). If $k>n$, proceed to step (5).
- Repeat step (2)-(3) with $k'=k$.
- Construct the string $a_1a_2\dots a_n=\mathbf{a}$ using the bits obtained in step (2).
For some fixed bitstring $\mathbf{a}\neq\mathbf{0}$, querying $f$ with some bitstring $\mathbf{x}$ gives $\mathbf{a}\cdot \mathbf{x} = a_1x_1+a_2x_2+\dots +a_n x_n (mod 2)$, which can be thought of as an equation in the $n$ unknowns given by the $a_i$. Then querying $f$ with another string $\mathbf{x'}$ will similarly yield another equation of the form $\mathbf{x'} = a_1x'_1+a_2x'_2+\dots +a_n x'_n (mod 2)$. Then after $k$ queries with $k<n$ there will be a system of $k$ equations in $n$ unknowns. It is a general fact of linear algebra that such a system cannot uniquely determine the values of all of the $a_i$ variables/bits that comprise the unknown string $\mathbf{a}$. Therefore, $\mathbf{a}$ cannot be uniquely determined. If $k$ queries have been made, and the resulting equations from each of these are independent, then at most $k$ bits of $\mathbf{a}$ can be determined. Thus, no classical algorithm can solve this problem with fewer than $n$ queries in order to uniquely determine $\mathbf{a}$ with certainty.
Presented here is a quantum algorithm for solving the problem. Begin with an $n+1$ qubits, where the first $n$ qubit registers are initialized in the state $\ket{0}$ and the last qubit in the state $\ket{1}$. Consider the following circuit:
Here the first and last gates apply the single qubit Hadamard gate to each of the $n+1$ registers. The second gate $U_f$ is defined as
\[
U_f: \ket{\mathbf{x}}\ket{y}\mapsto \ket{\mathbf{x}}\ket{y\oplus f(x)},
\]
where $\mathbf{x}\in\{0,1\}^n$ and $y\in\{0,1\}$. The last part of the circuit denotes a measurement on the first $n$ registers.
Consider the action of this circuit on the initial state $\ket{\mathbf{0}}\ket{1}$ up until the measurements are performed:
\[\begin{align*}
\ket{\mathbf{0}}\ket{1}\overset{H^{\otimes n+1}}\mapsto &
\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{0}-\ket{1})\\
\overset{U_f}\mapsto \ \ &\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}\ket{\mathbf{j}}(\ket{\mathbf{a}\cdot\mathbf{j}}-\ket{1\oplus\mathbf{a}\cdot\mathbf{j}})\\
&=\frac{1}{\sqrt{2^{n+1}}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}}\ket{\mathbf{j}}(\ket{0}-\ket{1}) \\
\overset{H^{\otimes n+1}}\mapsto &\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\end{align*}\]
The third line of this calculation gives the state that results after the Hadamard gates and $U_f$ gate is applied.
As computed in part (c), the state that results after the second set of Hadamard gates is applied is given by
\[
\ket{\varphi}:=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{k}\in\{0,1\}^n}\displaystyle\left(\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}\right))\ket{\mathbf{k}}\ket{1}.
\]
Let the amplitude of the $\ket{\mathbf{k}}$ in this superposition be given by $\alpha_k$. Then
\[
\alpha_k=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}}(-1)^{\mathbf{a}\cdot\mathbf{j}}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{k}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}.
\]
The amplitude of the state $\ket{\mathbf{a}}$ in $\ket{\varphi}$ is
\[
\alpha_a=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{\mathbf{a}\cdot\mathbf{j}\oplus\mathbf{a}\cdot\mathbf{j}}
=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}(-1)^{0}=\frac{1}{2^{n}}\displaystyle\sum_{\mathbf{j}\in\{0,1\}^n}1=\frac{1}{2^{n}}2^n=1.
\]
Hence, the first $n$ registers in the state $\ket{\varphi}$ are in the state $\ket{\mathbf{a}}$ with probability $1$. Since $\ket{\varphi}$ must be a normalized state, this implies that the amplitudes $\alpha_k$ of the states $\ket{\mathbf{k}}$ for all $\mathbf{k}\neq\mathbf{a}$ in $\ket{\varphi}$ are $\alpha_k=0$. Therefore, when the first $n$ registers are measured in the computational basis the state $\ket{\mathbf{a}}$ will always be observed, which then determines the string $\mathbf{a}$.