If we restrict a quantum circuit to only have interactions between "nearby" qubits (for some connection topology that defines "nearby", as is the case in several actual quantum computers), (how) does that change the complexity?

Using swap operations, you can always move the qubits around to where you need them, so a general quantum circuit with $t$ gates and a connectivity graph of diameter $d$ can be simulated by one with $O(dt)$ gates, using the same number of qubits.

Can this dependency on $d$ be reduced, to $o(d)t$? Perhaps using additional ancilla qubits? Or is there a lower bound showing that this is not possible in general?

I'd even be interested in results for particular connectivity graphs, such a path, a cycle, or a square lattice.

(Feels like a basic question, but I've found it very hard to search for because "quantum" and "local" tends to bring up lots of stuff about local Hamiltonians, but that's not really what this question is about.)

  • $\begingroup$ Of course if you add more ancilla the question arises as to how they are connected to the rest. In the case of some natural graphs - path, cycle, square lattice - it is relatively (although not 100%!) clear how to do this. In general, there should be some requirement that the new ancilla qubits respect locality, e.g. by not altering distances by more than some additive amount (maybe O(1)? Or o(d)? A little unclear, but some restriction is necessary to make it interesting and capture the spirit of the queestion.) $\endgroup$ Feb 17, 2023 at 0:05
  • $\begingroup$ This doesn't precisely address your question, but might contain useful pointers: journals.aps.org/prxquantum/abstract/10.1103/… $\endgroup$
    – smapers
    Feb 17, 2023 at 10:34


Your Answer

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