Hidden linear function problem

The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem.^[1] In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.^[2] While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes ${\displaystyle QNC^{0}}$ and ${\displaystyle NC^{0}}$ (${\displaystyle QNC^{0}\nsubseteq NC^{0}}$).^[1]

2D HLF problem statement

Given ${\displaystyle A\in \mathbb {F} _{2}^{n\times n}}$(an upper- triangular binary matrix of size ${\displaystyle n\times n}$) and ${\displaystyle b\in \mathbb {F} _{2}^{n}}$ (a binary vector of length ${\displaystyle n}$),

define a function ${\displaystyle q:\mathbb {F} _{2}^{n}\to \mathbb {Z} _{4}}$:

${\displaystyle q(x)=(2x^{T}Ax+b^{T}x){\bmod {4}}=\left(2\sum _{i,j}A_{i,j}x_{i}x_{j}+\sum _{i}b_{i}x_{i}\right){\bmod {4}},}$

and

${\displaystyle {\mathcal {L}}_{q}={\Big \{}x\in \mathbb {F} _{2}^{n}:q(x\oplus y)=(q(x)+q(y)){\bmod {4}}~~\forall y\in \mathbb {F} _{2}^{n}{\Big \}}.}$

There exists a ${\displaystyle z\in \mathbb {F} _{2}^{n}}$ such that

${\displaystyle q(x)=2z^{T}x~~\forall x\in {\mathcal {L}}_{q}.}$

Find ${\displaystyle z}$.^[1]

2D HLF algorithm

With 3 registers; the first holding ${\displaystyle A}$, the second containing ${\displaystyle b}$ and the third carrying an ${\displaystyle n}$-qubit state, the circuit has controlled gates which implement ${\displaystyle U_{q}=\prod _{1<i<j<n}CZ_{ij}^{A_{ij}}\cdot \bigotimes _{j=1}^{n}S_{j}^{b_{j}}}$ from the first two registers to the third.

This problem can be solved by a quantum circuit, ${\displaystyle H^{\otimes n}U_{q}H^{\otimes n}\mid 0^{n}\rangle }$, where H is the Hadamard gate, S is the S gate and CZ is CZ gate. It is solved by this circuit because with ${\displaystyle p(z)=\left|\langle z|H^{\otimes n}U_{q}H^{\otimes n}|0^{n}\rangle \right|^{2}}$, ${\displaystyle p(z)>0}$ iff ${\displaystyle z}$ is a solution.^[1]