On the Effect of Quantum Interaction Distance on Quantum Addition Circuits

Byung-Soo Choi, Rodney Van Meter · 2008 · ACM J. Emerging Top. Comput. Syst.

| 编号 QA030 | 主题 加法与减法 | 链接 arXiv:0809.4317 |

摘要

摘要保留原文（英文）

摘要取自 arXiv / 出版方元数据，未作翻译，以保证与原文一致。

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})$. This result, the first application of graph embedding to quantum circuits and devices, provides a new tool for compiler development, emphasizes the impact of quantum computer architecture on performance, and acts as a cautionary note when evaluating the time performance of quantum algorithms.

本站词条在引用该文献时，会以 wikilink（sources/QA030）链接到本页；右侧「反向链接」面板自动列出所有引用它的词条。