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 Ω (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 Ω (log 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.
Abstract To execute quantum circuits on a quantum processor, they must be modified to meet the physical constraints of the quantum device. This process, called quantum circuit mapping , results in a gate/circuit depth overhead that depends on both the circuit properties and the hardware constraints, being the limited qubit connectivity a crucial restriction. In this paper, we propose to extend the characterization of quantum circuits by including qubit interaction graph properties using graph theory-based metrics in addition to previously used circuit-describing parameters. This approach allows for an in-depth analysis and clustering of quantum circuits and a comparison of performance when run on different quantum processors, aiding in developing better mapping techniques. Our study reveals a correlation between interaction graph-based parameters and mapping performance metrics for various existing configurations of quantum devices. We also provide a comprehensive collection of quantum circuits and algorithms for benchmarking future compilation techniques and quantum devices.
Research in the domain of quantum computation is mainly driven by their promising applications e.g., for factorization or database search. At the same time, physical developments for this emerging technology constantly lead to new constraints to be addressed by logic designers. The limited interaction distance between qubits, the elementary information storage in quantum circuits, is one of the most common restrictions, leading to the fact that, for many quantum architectures, computations can only be performed on adjacent (i.e., nearest neighbor) qubits. Motivated by that, optimization of quantum circuits with respect to this restriction has become an intensely considered research topic. In this paper, we briefly review existing approaches that have been proposed in the past for this purpose. We particularly consider that almost all existing solutions are of heuristic nature, i.e., do not guarantee an optimal solution. In order to address this, exact alternatives are introduced which make use of the deductive power of constraint solvers. By this, we are able to perform a qualitative evaluation of the performance of existing (heuristic) solutions for linear nearest neighbor quantum circuit optimization.
In this work, we propose an adder for the 2-Dimensional Nearest-Neighbor, Two-Qubit gate, Concurrent (2D NTC) architecture, designed to match the architectural constraints of many quantum computing technologies. The chosen architecture allows the layout of logical qubits in two dimensions with √ n columns where each column has √ n qubits and the concurrent execution of one- and two-qubit gates with nearest-neighbor interaction only. The proposed adder works in three phases. In the first phase, the first column generates the summation output and the other columns do the carry-lookahead operations. In the second phase, these intermediate values are propagated from column to column, preparing for computation of the final carry for each register position. In the last phase, each column, except the first one, generates the summation output using this column-level carry. The depth and the number of qubits of the proposed adder are Θ(√ n ) and O(n) , respectively. The proposed adder executes faster than the adders designed for the 1D NTC architecture when the length of the input registers n is larger than 51.
Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted
n-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by
O(n2)and size by
O(n). It is appealing to conjecture that this overhead is unavoidable—a random circuit on
nqubits has
Θ(n)two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance
Θ(n). While it is known that almost all
n-qubit unitary operations need quantum circuits of
Ω(4n/n)depth and
Ω(4n)size to realize with all-to-all qubit connectivity, in this article, we show that all
n-qubit unitary operations can be implemented by quantum circuits of
O(4n/n)depth and
O(4n)size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made
O(4n)as long as the graph is connected. For circuit depth, we study
d-dimensional grids, complete
d-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.
Motivated by the promises of significant speed-ups for certain problems, quantum computing received significant attention in the past. While much progress has been made in the development of synthesis methods for quantum circuits, new physical developments constantly lead to new constraints to be addressed. The limited interaction distance between the respective qubits (i.e. nearest neighbor optimization) has already been considered intensely. But with the emerge of multi-dimensional quantum architectures, new physical requirements came up for which only a few automatic synthesis solutions exist yet all of them of heuristic nature. In this work, we propose an exact scheme for nearest neighbor optimization in multi-dimensional quantum circuits. Although the complexity of the problem is a serious obstacle, our experimental evaluation shows that the proposed solution is sufficient to allow for a qualitative evaluation of the respective optimization steps. Besides that, this enabled an exact comparison to heuristical results for the first time.