A quantum-inspired solution to a CP problem
I came across a very interesting problem in a recent team contest. Given some array $a$, we were asked to transform it into $b$ where each element of $b$ was some weighted summation of the elements of $a$. Though its solution is very old and well-known, I found thinking of it as a quantum algorithm quite useful and enlightening.
§ Problem
Given $n (1 \le n \le 20)$, and a sequence $a = (a_0, \ldots, a_{2^n - 1})$ of length $2^n$, compute the following sequence:
\begin{equation} b_i = \sum_{j = 0}^{2^n - 1} (B(i \land j) \mod 2) a_j \end{equation}
where $B(x)$ is the number of $1$s in the binary representation of $x$.
§ Simplification
Let’s define $\langle i, j \rangle = B(i \land j) \mod 2$ (bonus: This is in fact an inner product for the space $\mathbb{F}_2^n$).
Now the problem reduces to $b_i = \sum_j \langle i,j \rangle a_j$.
Notice that $\langle i,j \rangle \in \{ 0, 1 \}$. Let us convert it to $\{-1, 1\}$ by using $f(x) = (-1)^x = 1 - 2x$.
\begin{align}
c_i &= \sum_{j=0}^{2^n-1} (-1)^{\langle i,j \rangle} a_j\\
&= \sum_{j=0}^{2^n-1} (1 - 2\langle i,j \rangle) a_j\\
&= S - 2 b_i
\end{align}
where $S = \sum_j a_j$.
§ Computing c
Does $c$ look familiar? Yes, it is the output of the Hadamard transform! This has been well studied as the Walsh-Hadamard Transform, but I shall use the quantum version to solve this problem.
Let $\ket{a} = \sum_i a_i \ket{i}$ and $\ket{c} = \sum_i c_i \ket{i}$. Remember that $H^{\otimes n} \ket{i} = \sum_j (-1)^{\langle i,j \rangle} \ket{j}$. On applying the Hadamard transform on $\ket{a}$, we have
\begin{align}
H^{\otimes n} \ket{a} &= H^{\otimes n} \sum_i a_i \ket{i}\\
&= \sum_i a_i (H^{\otimes n} \ket{i})\\
&= \sum_i a_i \left(\sum_j (-1)^{\langle i,j \rangle} \ket{j}\right)\\
&= \sum_j \left(\sum_i (-1)^{\langle i,j \rangle} a_i \right)\ket{j}\\
&= \sum_j c_j \ket{j}\\
&= \ket{c}\\
\end{align}
$c$ is just the Hadamard transform of $a$! We can now compute $b$ using $b = S - 2c$.
Caveat: The vectors $\ket{a}, \ket{c}$ are not normalized. This would be a problem if we wanted to actually use this in a quantum algorithm, but I am just using the braket notation to do linear algebra. So the math is still correct.
§ Fast Walsh-Hadamard Transform
This blog on CSAcademy explains FFT and FWHT quite nicely. Quoting the implementation from there:
using poly = vector<int>;
int degree(const poly& p) { return p.size(); }
poly FWHT(poly P, bool inverse) {
for (int len = 1; 2 * len <= degree(P); len <<= 1) {
for (int i = 0; i < degree(P); i += 2 * len) {
for (int j = 0; j < len; j++) {
u = P[i + j];
v = P[i + len + j];
P[i + j] = u + v;
P[i + len + j] = u - v;
}
}
}
if (inverse) {
for (int i = 0; i < degree(P); i++)
P[i] = P[i] / degree(P);
}
return P;
}
This can be computed in time $\mathcal{O}(N \log N)$, where $N$ is the length of the sequence. (In our case, $\mathcal{O}(n 2^n)$).
§ Fully quantum procedure
But what if we wanted to solve this purely using a quantum algorithm?
Problem 2
Given an input quantum state $\ket{\psi}$ proportional to $\sum_i a_i \ket{i}$, prepare a quantum state $\ket{\phi}$ proportional to $\sum_i b_i \ket{i}$.
Solution
Notice that the value of $a_0$ does not affect any $b_i$, because $\langle 0,i\rangle = 0$. So WLOG, we can choose $a_0$ in the problem, before preparing the state.
WLOG let $a_0 = -\sum_{i = 1}^{2^n - 1} a_i$ (i.e. sum of all $a_i$ becomes zero).
Now we get $b = -2c$, which means if $\ket\phi$ is proportional to $b$, it is proportional to $c$ as well. And we can prepare $c$ by $H^{\otimes n}\ket\psi$. Therefore, $\ket\phi = H^{\otimes n} \ket\psi$
Just $n$ gates and $n$ qubits, so we have a quantum log-time algorithm! (caveat: state preparation cost not accounted for, and we cannot extract the exact values of $b$ without some amplitude estimation/tomography procedure.)
\[\tag*{$\square$}\]Bonus: Assume we are given an quantum state ($\ket\psi$) for arbitrary $a$ (i.e. we cannot pick $a_0$ anymore), how would you modify the $\ket 0$ component of $\ket\psi$ to fit the above procedure?
