### On the Effect of Quantum Interaction Distance on Quantum Addition CircuitsOn the Effect of Quantum Interaction Distance on Quantum Addition Circuits

Access Restriction
Subscribed

 Author Choi, Byung-Soo ♦ Van Meter, Rodney Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2011 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Quantum architecture ♦ Depth lower bound ♦ Graph embedding ♦ Interaction distance ♦ Quantum adder Abstract 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 $\textit{Ω}(log$ $\textit{n})-depth$ quantum adder circuit for two $\textit{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 $\textit{k}-dimensional$ practical architecture, we prove that the depth lower bound of any exact quantum addition circuits is no longer $\textit{Ω}(log$ $\textit{n}),$ but $Ω(^{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. ISSN 15504832 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2011-08-01 Publisher Place New York e-ISSN 15504840 Journal ACM Journal on Emerging Technologies in Computing Systems (JETC) Volume Number 7 Issue Number 3 Page Count 17 Starting Page 1 Ending Page 17

#### Open content in new tab

Source: ACM Digital Library