Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1805.12570 · Quantum Information and Computation

On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity

Steven Herbert

Published Aug 1, 2020• 17 citations
arXivHTMLPDF

Abstract

This paper addresses the problem of finding the depth overhead that will be incurred when running quantum circuits on near-term quantum computers. Specifically, it is envisaged that near-term quantum computers will have low qubit connectivity: each qubit will only be able to interact with a subset of the other qubits, a reality typically represented by a qubit interaction graph in which a vertex represents a qubit and an edge represents a possible direct 2-qubit interaction (gate). Thus the depth overhead is unavoidably incurred by introducing swap gates into the quantum circuit to enable general qubit interactions. This paper proves that there exist quantum circuits where a depth overhead in Omega(\log n) must necessarily be incurred when running quantum circuits with n qubits on quantum computers whose qubit interaction graph has finite degree, but that such a logarithmic depth overhead is achievable. The latter is shown by the construction of a 4-regular qubit interaction graph and associated compilation algorithm that can execute any quantum circuit with only a logarithmic depth overhead.

DOI
10.26421/qic20.9-10-5

Related papers

Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint

Pei Yuan, Shengyu Zhang

In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.

arXiv:2402.02403•Quantum•May 28, 2025•4 citations

Does Qubit Connectivity Impact Quantum Circuit Complexity?

Pei Yuan, Jonathan Allcock, Shengyu Zhang

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(n^{2})$and size by$O(n)$. It is appealing to conjecture that this overhead is unavoidable—a random circuit on$n$qubits has$\Theta (n)$two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance$\Theta (n)$. While it is known that almost all$n$-qubit unitary operations need quantum circuits of$\Omega (4^{n}/n)$depth and$\Omega (4^{n})$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(4^{n}/n)$depth and$O(4^{n})$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(4^{n})$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.

arXiv:2211.05413•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Sep 4, 2023•17 citations

Interaction graph-based characterization of quantum benchmarks for improving quantum circuit mapping techniques

Medina Bandić, Carmen G. Almudéver, Sebastian Feld

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.

arXiv:2212.06640•Quantum Machine Intelligence•Oct 6, 2023•30 citations

Efficient implementation of quantum circuits with limited qubit interactions

STEPHEN D. BRIERLEY

The quantum circuit model allows gates between any pair of qubits yet physical instantiations allow only limited interactions. We address this problem by providing an interaction graph together with an efficient method for compiling quantum circuits so that gates are applied only locally. The graph requires each qubit to interact with 4 other qubits and yet the time-overhead for implementing any n-qubit quantum circuit is 4 log n. Building a network of quantum computing nodes according to this graph enables the network to emulate a single monolithic device with minimal overhead.

arXiv:1507.04263•Quantum Information and Computation•Nov 1, 2017•30 citations

Two-step approach to scheduling quantum circuits

Gian Giacomo Guerreschi, Jongsoo Park

Abstract As the effort to scale up existing quantum hardware proceeds, it becomes necessary to schedule quantum gates in a way that minimizes the number of operations. There are three constraints that have to be satisfied: the order or dependency of the quantum gates in the specific algorithm, the fact that any qubit may be involved in at most one gate at a time, and the restriction that two-qubit gates are implementable only between connected qubits. The last aspect implies that the compilation depends not only on the algorithm, but also on hardware properties like connectivity. Here we suggest a two-step approach in which logical gates are initially scheduled neglecting connectivity considerations, while routing operations are added at a later step in a way that minimizes their overhead. We rephrase the subtasks of gate scheduling in terms of graph problems like edge-coloring and maximum subgraph isomorphism. While this approach is general, we specialize to a one-dimensional array of qubits to propose a routing scheme that is minimal in the number of exchange operations. As a practical application, we schedule the quantum approximate optimization algorithm in a linear geometry and quantify the reduction in the number of gates and circuit depth that results from increasing the efficacy of the scheduling strategies.

arXiv:1708.00023•Quantum Science and Technology•Jun 26, 2018•75 citations

On the Effect of Quantum Interaction Distance on Quantum Addition Circuits

Byung-Soo Choi, Rodney Van Meter

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.

arXiv:0809.4317•ACM Journal on Emerging Technologies in Computing Systems•Aug 1, 2011•18 citations
This paper addresses the problem of finding the depth overhead that will be incurred when running quantum circuits on near-term quantum computers. Specifically, it is envisaged that near-term quantum computers will have low qubit connectivity: each qubit will only be able to interact with a subset of the other qubits, a reality typically represented by a qubit interaction graph in which a vertex represents a qubit and an edge represents a possible direct 2-qubit interaction (gate). Thus the depth overhead is unavoidably incurred by introducing swap gates into the quantum circuit to enable general qubit interactions. This paper proves that there exist quantum circuits where a depth overhead in Omega(\log n) must necessarily be incurred when running quantum circuits with n qubits on quantum computers whose qubit interaction graph has finite degree, but that such a logarithmic depth overhead is achievable. The latter is shown by the construction of a 4-regular qubit interaction graph and associated compilation algorithm that can execute any quantum circuit with only a logarithmic depth overhead.
In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. Compilation of a quantum circuit into one compliant to such qubit connectivity constraint results in an increase of circuit depth. Various compilation algorithms were studied, yet what this depth overhead is remains elusive. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph, a graph-theoretic measure which has been studied for 3 decades. We also give reduction algorithms between different graphs, which allow compilation for one graph to be transferred to one for another. These results, when combined with existing routing algorithms, give asymptotically optimal compilation for all commonly seen connectivity graphs in quantum computing.
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 unrestrictednnn-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth byO(n2)O(n^{2})O(n2)and size byO(n)O(n)O(n). It is appealing to conjecture that this overhead is unavoidable—a random circuit onnnnqubits hasΘ(n)\Theta (n)Θ(n)two-qubit gates in each layer and a constant fraction of them act on qubits separated by distanceΘ(n)\Theta (n)Θ(n). While it is known that almost allnnn-qubit unitary operations need quantum circuits ofΩ(4n/n)\Omega (4^{n}/n)Ω(4n/n)depth andΩ(4n)\Omega (4^{n})Ω(4n)size to realize with all-to-all qubit connectivity, in this article, we show that allnnn-qubit unitary operations can be implemented by quantum circuits ofO(4n/n)O(4^{n}/n)O(4n/n)depth andO(4n)O(4^{n})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 madeO(4n)O(4^{n})O(4n)as long as the graph is connected. For circuit depth, we studyddd-dimensional grids, completeddd-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.
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.
The quantum circuit model allows gates between any pair of qubits yet physical instantiations allow only limited interactions. We address this problem by providing an interaction graph together with an efficient method for compiling quantum circuits so that gates are applied only locally. The graph requires each qubit to interact with 4 other qubits and yet the time-overhead for implementing any n-qubit quantum circuit is 4 log n. Building a network of quantum computing nodes according to this graph enables the network to emulate a single monolithic device with minimal overhead.
Abstract As the effort to scale up existing quantum hardware proceeds, it becomes necessary to schedule quantum gates in a way that minimizes the number of operations. There are three constraints that have to be satisfied: the order or dependency of the quantum gates in the specific algorithm, the fact that any qubit may be involved in at most one gate at a time, and the restriction that two-qubit gates are implementable only between connected qubits. The last aspect implies that the compilation depends not only on the algorithm, but also on hardware properties like connectivity. Here we suggest a two-step approach in which logical gates are initially scheduled neglecting connectivity considerations, while routing operations are added at a later step in a way that minimizes their overhead. We rephrase the subtasks of gate scheduling in terms of graph problems like edge-coloring and maximum subgraph isomorphism. While this approach is general, we specialize to a one-dimensional array of qubits to propose a routing scheme that is minimal in the number of exchange operations. As a practical application, we schedule the quantum approximate optimization algorithm in a linear geometry and quantify the reduction in the number of gates and circuit depth that results from increasing the efficacy of the scheduling strategies.
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.