2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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})$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – BlackHat18
    Jan 15 at 4:56
  • $\begingroup$ @BlackHat18 If you're assuming that you can teleport in O(1) time via a path of entanglement, then you effectively have arbitrary connectivity. The space overhead is horrendous though; quadratic in the number of bits to ensure you have enough routing area. $\endgroup$ Jan 15 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.