On the Effect of Quantum Interaction Distance on Quantum Addition Circuits

Understand

We investigate the theoretical limits of the effect of the quantum interaction distance on the speed of exact quantum addition circuits.

• For this study, we exploit graph embedding for quantum circuit analysis.
• We study a logical mapping of qubits and gates of any $\Omega(\log n)$-depth quantum adder circuit for two $n$-qubit registers onto a practical architecture, which limits interaction distance to the nearest neighbors only and supports only one- and two-qubit logical gates.
• Unfortunately, on the chosen $k$-dimensional practical architecture, we prove that the depth lower bound of any exact quantum addition circuits is no longer $\Omega(\log {n})$, but $\Omega(\sqrt[k]{n})$.