# Multiplication using nearest neighbour quantum gates

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?

It's impossible to do it in polylogarithmic depth, because for a modular multiplication (or even just an increment!) the output value of the most significant bit is a function of every other input bit. One spot is affected by all the other spots. So your runtime has to be at least as long as the longest path between that spot and any one of the other used spots. If you're placing $$n$$ qubits on a 2d grid then that path length is at least $$\Omega(\sqrt{n})$$.
• I see how the number of gates to reach one spot from another spot should be $\Omega(\sqrt{n})$, but I do not see why that means the depth should also be $\Omega(\sqrt{n})$. For example, could ensure that there is at least one entangling gate applied to each pair of qubits that lies in the path between two spots in just constant depth. Jan 15 at 4:56