<blockquote>
<p>If we restrict a quantum circuit to only have interactions between &quot;nearby&quot; qubits (for some connection topology that defines &quot;nearby&quot;, as is the case in several actual quantum computers), (how) does that change the complexity?</p>
</blockquote>
<p>Using swap operations, you can always move the qubits around to where you need them, so a general quantum circuit with <span class="math-container">$t$</span> gates and a connectivity graph of diameter <span class="math-container">$d$</span> can be simulated by one with <span class="math-container">$O(dt)$</span> gates, using the same number of qubits.</p>
<blockquote>
<p>Can this dependency on <span class="math-container">$d$</span> be reduced, to <span class="math-container">$o(d)t$</span>? Perhaps using additional ancilla qubits? Or is there a lower bound showing that this is not possible in general?</p>
</blockquote>
<p>I'd even be interested in results for particular connectivity graphs, such a path, a cycle, or a square lattice.</p>
<p>(Feels like a basic question, but I've found it very hard to search for because &quot;quantum&quot; and &quot;local&quot; tends to bring up lots of stuff about local Hamiltonians, but that's not really what this question is about.)</p>

CC BY-SA 4.0
2023-02-17T00:05:35.743Z
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.)
Joshua Grochow
CC BY-SA 4.0
2023-02-17T10:34:45.240Z
This doesn't precisely address your question, but might contain useful pointers: https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.4.010313
smapers
<quantum-computing><circuit-complexity>
Quantum circuits vs quantum circuits w/ only local interactions?
Joshua Grochow
# Quantum circuits vs quantum circuits w/ only local interactions?

(Asked by: username_0 on 2023-02-17)

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

**Tags:** quantum-computing, circuit-complexity

> **Comments:**
> **username_0**: 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.)  
> **username_1**: This doesn't precisely address your question, but might contain useful pointers: https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.4.010313  

---

## 0 answers

