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?

Improve this question
$\endgroup$

1 Answer 1

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

Improve this answer
$\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, 2022 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$
    – Craig Gidney
    Jan 15, 2022 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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