Hidden linear function problem

The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem. 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.
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 formula_1 and formula_2 (formula_3).
2D HLF problem statement.
Given formula_4(an upper-triangular binary matrix of size formula_5) and formula_6 (a binary vector of length formula_7),
define a function formula_8:
and
There exists a formula_11 such that
Find formula_13.
2D HLF algorithm.
With 3 registers; the first holding holding formula_14, the second containing formula_15 and the third carrying an formula_7-qubit state, the circuit has controlled gates which implement 
formula_17 from the first two registers to the third.
This problem can be solved by a quantum circuit, formula_18, where "H" is the Hadamard gate, "S" is the S gate and CZ is CZ gate. It is solved by this circuit because with formula_19, formula_20 iff formula_13 is a solution.