Let $A$ be an $n \times m$ matrix, and $x$ be an $m \times 1$ vector and $q$ be a number such that $q$ is polynomial in $n$.
Let us be given both $A$, $q$, and $x$ as input and let us also have a 2D grid of qubits, each initialised to the state $|0\rangle$. The size of the grid is $poly(n, m)$. We can implement only nearest neighbour one and two qubit gates. What is the minimum depth of a quantum circuit that can compute $Ax$ modulo $q$?
There is a trivial algorithm that takes $poly(n,m)$ time, but can we reduce the depth someho and compile the circuit is polylogarithmic depth?