On the Effect of Quantum Interaction Distance on Quantum Addition Circuits

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 $\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.

accepted for ACM Journal on Emerging Technologies in Computing Systems

References in corpus (17)

• Non-Abelian Anyons and Topological Quantum Computation
• Scalable multi-particle entanglement of trapped ions
• Synthesis of Quantum Logic Circuits
• Topological fault-tolerance in cluster state quantum computation
• Measurement-Only Topological Quantum Computation
• Fast Quantum Modular Exponentiation
• Quantum Circuit Placement
• Local Fault-tolerant Quantum Computation
• Distributed Quantum Computation Architecture Using Semiconductor Nanophotonics
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• Six-qubit two-photon hyperentangled cluster states: characterization and application to quantum computation
• Threshold Error Penalty for Fault Tolerant Computation with Nearest Neighbour Communication
• Efficient generation of universal two-dimensional cluster states with hybrid systems
• Using error correction to determine the noise model
• Single spin measurement using cellular automata techniques
• Circuit Design for A Measurement-Based Quantum Carry-Lookahead Adder
• Demonstration of a programmable source of two-photon multiqubit entangled states

Cited by in corpus (7)

• Synthesis and Optimization of Reversible Circuits - A Survey
• Efficient Distributed Quantum Computing
• Compiler Design for Distributed Quantum Computing
• Optimized Surface Code Communication in Superconducting Quantum Computers
• An $\Theta (\sqrt{n})$-depth Quantum Adder on a 2D NTC Quantum Computer Architecture
• Linear and logarithmic time compositions of quantum many-body operators
• Quantum circuit compilation and hybrid computation using Pauli-based computation