Lightcone bounds for quantum circuit mapping via uncomplexity

Table of Contents

Quantum Circuit Mapping

Generally, quantum algorithms and their associated circuit-level descriptions are developed without considering the architecture-specific limitations of particular devices, i.e., they are developed in an architecture-free manner. For example, the elementary gate set (or primitives) for a particular device may differ significantly from what has been indicated at the level of a generic circuit description; as such, several actions must be performed in order to translate the quantum algorithm into a circuit that a quantum device can actually execute. Another example can be seen in the physical connectivity properties of a quantum processor, which must be considered to ensure that the necessary qubit-qubit interactions of the circuit can be performed on the device. Although certain exceptions may exist (in which several of the aforementioned steps may not necessarily be carried out), these procedures are collectively known as quantum circuit mapping¹¹.

The task of quantum circuit mapping itself is usually divided into several steps, which typify the process: A) elementary gate-set decomposition, which involves the translation of a circuit to a native gate set utilized by a quantum processor; B) scheduling, which concerns the formation of a logical time ordering for algorithm execution, and includes considerations for parallelism of operations and for the shortening of circuit depth; C) qubit assignment, which relates to the initial assignment of qubits from an algorithm to the physical qubits on a quantum architecture; and D) qubit routing, which examines the increase in gate overhead as extra operations are inserted into the algorithm as a function of physically moving qubits around the processor, such that the required two-qubit operations are realizable¹¹. Typically, operations such as SWAP gates are utilized in order to adapt the circuit to hardware; these amount to classical permutation operations on a product state, but other approaches exist as well^32,62,63.

As a simple example, consider the quantum circuit-mapping procedure in Fig. 1. The circuit on the left is decomposed into IG form (a)-(b), wherein we do not consider single-qubit gates for simplicity, and we assume that the two-qubit gates shown in the circuit diagrams are taken as general two-qubit operations. Upon comparing the IG with the available qubit-qubit interactions afforded by a quantum device, it is apparent that the connectivity available on the device and the connectivity required by the algorithm differ (the two-qubit interaction represented by the edge $e_d_0d_1$ is not possible, as shown in (b)-(c)). As such, this discrepancy can be compensated for by adding detrimental SWAP operations to the circuit’s initial assignment (d). This example provides an illustration of quantum circuit mapping based on an exact graph matching between IG and CG. Implicit to this example was the assumption that exactly such a mapping between the vertices of the IG and CG exists, which preserves all of the edge relationships of the IG; this is known as a graph isomorphism, and will be discussed in more detail in the Supplementary Material.

**Fig. 1: An example of the QCMP as a sequence of steps needed to assign qubits from an algorithm to a quantum device.**

In this paper, we formulate and solve a special case of the QCMP. In contrast to Fig. 1, our formalism exhibits three main simplifications. First, as is typical in the QCMP, we do not consider single-gate interactions in the formalism that we present starting in Section II B. Second, we assume the existence of a noiseless quantum device, as such an ideal scenario precisely allows for the emergence of a lower bound. Third, we assume that no further gate simplifications via quantum circuit-synthesis techniques can be further leveraged^64,65,66. Finally, in real quantum hardware, typically we only consider that one multiqubit gate can be performed on a given hardware qubit during a given moment; this necessitates the division of the quantum circuit into time slices. Instead, we consider the scenario in which all two-qubit gate interactions of the circuit can be performed within a single unit time slice, i.e. the causal structure of our circuits are taken to be indefinite^67,68, as essentially infinite parallelization of two-qubit gate operations can be implemented. We devote more detail to these concepts in Section III.

Graphs as density matrices

In quantum physics, the most general manner of describing a quantum state involves the use of density matrices^1,69. A density matrix ρ is a Hermitian, positive semidefinite matrix, whose trace is equal to unity. A system ρ is termed pure if and only if the bound $\rmTr[\boldsymbol\rho ^2]\le 1$ is saturated. The density matrix admits a spectral decomposition as

$$\boldsymbol\rho =\sum _jp_j\left\vert \psi _j\right\rangle \left\langle \psi _j\right\vert \,,$$

(1)

for an orthonormal basis $\\left\vert \psi _j\right\rangle \$, where p_j are non-negative eigenvalues summing to 1.

In this work, as in ref. ^39,40, we make use of the concept of a density matrix to describe a complex network (i.e. a graph with many edges and vertices, and assumed topological structure⁷⁰), by defining a matrix from a network, which fulfills the mathematical properties of a density matrix. One such candidate was previously shown in³⁹ to be promising for adhering to the property of subadditivity for the VNE; this equilibrium Gibbs state is defined as

$$\boldsymbol\rho _L=\frace^-\beta \bfLZ\,,$$

(2)

where ρ_L, e^(⋅), β, and Z represent: the density matrix of graph Laplacian L; the matrix exponential; the inverse temperature (or diffusion time⁴⁴); and the partition function, which is defined as $Z=\rmTr\left[e^-\beta \bfL\right]$, respectively. We define the graph Laplacian as L ≔ D − A, following^39,71. Throughout the text, we will refer to the graph Laplacians for the IG and CG using the notation L_IG, L_CG, respectively, and ρ_IG, σ_CG to refer to the corresponding IG and CG density-matrix forms, respectively. Additionally, we refer to edges in a graph-theoretic context as a line connecting two vertices; in the density-matrix formalism, we will make reference to this instead with the term subsystem interactions.

Using these objects to describe complex networks is advantageous for several reasons. Firstly, although it is known that the graph Laplacian is uniquely determined up to vertex-numbering assignments⁷², the eigenvalue spectrum of the graph Laplacian does not allow for unique identification of a graph. For example, two graphs can be cospectral, i.e. possessing the same eigenvalue spectrum, but with different connectivity⁷². As such, the approach we detail in this work is motivated by the fact that entropic divergence measures allow for a unique differentiation between two quantum states ρ and σ. Secondly, the VNE is permutation-invariant, i.e., the VNE is invariant under a reordering of subsystems. For example, suppose we have a state vector of five subsystems a, b, c, d, and e. If two such subsystem orderings give rise to density matrices $\eta =\sum _\mathttabcde\in \mathbbZ_2\left\vert \mathttabcde\right\rangle \left\langle \mathttabcde\right\vert$ and $\xi =\sum _{\mathttabcde\in \mathbbZ_2}\left\vert \mathttbaced\right\rangle \left\langle \mathttbaced\right\vert$, it can be shown that the equality $\mathcalS(\eta )=\mathcalS(\xi )$ holds⁴⁹. Lastly, as discussed in ref. ^39,40, previous attempts to calculate the classical entropy of a complex network fail, as these measures are dependent on a probability distribution resultant from a specific network descriptor. In contrast, the quantum approach we utilize does not depend on a specific network descriptor, but rather the entire network, rescaled and normalized as a Gibbs state.

Distance Measures in Quantum Information Theory

The task of distinguishing two quantum states is in general a highly non-trivial problem in quantum physics, with many interpretations useful for distinct scenarios^1,35,36,73. However, at the core of these distance measures lies a central object known as the quantum Fisher information⁵⁷, and is typically calculated as

$$\mathsfG_ij=\mathop\sum \limits_i,j=0^d-1\fracRe\left(\left\langle \lambda _i\right\vert \partial _i\boldsymbol\rho \left\vert \lambda _j\right\rangle \left\langle \lambda _j\right\vert \partial _j\boldsymbol\rho \left\vert \lambda _i\right\rangle \right)\lambda _i-\lambda _j\,,$$

(3)

where ∂_i = ∂ρ/∂i for some density matrix parameterized by a vector $\bar\theta =\\theta _1\ldots \theta _m\$, and we write i, j as shorthand for the parameters θ_i, θ_j. λ_i, λ_j represent the eigenvalues associated with ∂_iρ and ∂_jρ.

The quantum Fisher information is a fundamental object in quantum information theory, allowing for the derivation of an extended family of statistical inference measures that distinguish between parameterized quantum states in different settings^55,74. In particular, it is known that the quantum Fisher information is closely related to the Bures distance$\mathcalB_ij$^1,36,55, as well as to the quantum relative entropy as

$$\mathsfG_ij=4\mathcalB_ij=8\left(1-\sqrt\mathcalF(\boldsymbol\rho _\boldsymboli,\boldsymbol\rho _\boldsymbolj)\right)\approx \sqrt \boldsymbol\rho _\boldsymbolj)\,,$$

(4)

where $\mathcalF(\boldsymbol\rho _\boldsymboli,\boldsymbol\rho _\boldsymbolj)={(\textTr[\sqrt\sqrt\boldsymbol\rho _\boldsymbolj\boldsymbol\rho _\boldsymboli\sqrt\boldsymbol\rho _\boldsymbolj])}^2$ represents the fidelity function, $\mathcalS(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)=\mathcalS(\boldsymbol\rho _\boldsymboli)+\mathcalS(\boldsymbol\rho _\boldsymbolj)$ is the quantum relative entropy (QRE), and $\mathcalS(\boldsymbol\rho _\boldsymboli)$ is the Von Neumann entropy (VNE).

From the quantum relative entropy, one can immediately define a similar divergence measure which will be useful to the present work, the quantum Jensen-Shannon divergence. It is defined, using the quantum relative entropy, as

$$\mathcalD_qJSD(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)=\frac12\left[\mathcalS\left(\boldsymbol\rho _\boldsymboli| | \frac\boldsymbol\rho _\boldsymboli+\boldsymbol\rho _\boldsymbolj2\right)+\mathcalS\left(\boldsymbol\rho _\boldsymbolj| | \frac\boldsymbol\rho _\boldsymboli+\boldsymbol\rho _\boldsymbolj2\right)\right]\,.$$

(5)

It is also well-known that the quantum Fisher information (and by extenstion, the quantum Jensen-Shannon divergence) is closely related to the quantum Wasserstein distance^56,73,75.

Quantum information theory & entropic divergence measures

The task of actually distinguishing two quantum states ρ_i and ρ_j can be accomplished through the use of the entropic divergence measures^{1,36,45,46,49,55,74,76,77}. In particular, we employ the quantum Jensen-Shannon divergence (qJSD), which is defined as

$$\mathcalD_qJSD(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)=\mathcalS\left(\frac\boldsymbol\rho _\boldsymboli+\boldsymbol\rho _\boldsymbolj2\right)-\frac12\left(\mathcalS(\boldsymbol\rho _\boldsymboli)+\mathcalS(\boldsymbol\rho _\boldsymbolj)\right)\,.$$

(6)

Here we defined the Von Neumann entropy^1,49 as

$$\mathcalS(\boldsymbol\rho _\boldsymboli)=-\rmTr(\boldsymbol\rho _\boldsymboli\log \boldsymbol\rho _\boldsymboli)\,,$$

(7)

where all logarithms are of natural base, and we utilize the convention $0\log _20:= 0$.

One may ask why we chose to utilize the qJSD, and not other quantum entropic measures, such as the mutual information or the quantum relative entropy^1,74. Our deference to the qJSD is due to several useful properties (partially originating from the VNE), but arguably the most important one originates from the square root of the qJSD lies in a metric space$\mathfrakD(x,y)$ for two objects x, y that we wish to distinguish. A metric space is endowed with the properties of:

Distance: Let x, y, z be the elements inside a set X, then the function $\mathfrakD:X\times X\mapsto \mathbbR$ upholds $\mathfrakD(x,y)\ge 0$, with the case of $\mathfrakD=0$ if x = y.
Symmetricity: The function $\mathfrakD(x,y)$ also obeys $\mathfrakD(x,y)=\mathfrakD(y,x)$.
Adherence to the Triangle inequality: lastly, $\mathfrakD(x,y)+\mathfrakD(x,z)\ge \mathfrakD(y,z)$.

If these conditions are all upheld, we say that $\mathfrakD(\cdot ,\cdot )$ is a metric space⁴⁶. More specifically, the qJSD defines a bounded metric space of the form

$$0\le \sqrt{\mathcalD_qJSD(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)}\le 1\,,$$

(8)

with a value of 0 signifying that ρ_i = ρ_j, and a value of 1 used for the case of ρ_i⊥ρ_j^76,78. As we are comparing the density matrices related to the IG and CG of a quantum circuit and processor, it is imperative to understand the closeness of one to the other, using some bounded distance measure. As a contrasting incentive, consider measuring the quantum relative entropy of two orthogonal states; in this case, the divergence is unbounded and gives $\mathcalS(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)\mapsto \infty$¹. In the practical setting of the QCMP, such a measure is therefore not useful and does not convey the necessary distance information.

In addition to the metric space property, the qJSD is symmetric. This property is concomitant to the previous property related to metric spaces, but we address it here separately. Symmetricity means that the qJSD obeys the relation

$$\mathcalD_qJSD(\boldsymbol\rho _\boldsymboli| | \boldsymbol\rho _\boldsymbolj)=\mathcalD_qJSD(\boldsymbol\rho _{\boldsymbolj}| | \boldsymbol\rho _{\boldsymboli})\,.$$

(9)

For the QCMP, we observe that this relation is desirable, as we wish for the notion of distance between two density matrices to stay the same, regardless of whether one is derived from L_IG or L_CG. As we will see in Section II E, it is in fact this distance quantity that we relate to the quantum circuit uncomplexity^42,43. Additionally, the concept of symmetricity is paramount, as it permits us to directly relate the qJSD back to the quantum Fisher information; indeed, it was shown using the quantum Fisher information that the qJSD exactly calculates the thermodynamic path length between two equilibrium quantum states, and lower bounds their divergence on a Riemannian manifold^{55,56,74,75,79,80,81}.

Finally, we note that the qJSD is non-increasing under the action of a CP map⁷⁶, which can be formally stated as

$$\mathcalD_qJSD(\boldsymbol\rho _{{\boldsymboli}}| | \boldsymbol\rho _{{\boldsymbolj}})\le \mathcalD_qJSD(\Lambda (\boldsymbol\rho _{{\boldsymboli}})| | \Lambda (\boldsymbol\rho _{{\boldsymbolj}}))\,,$$

(10)

where Λ( ⋅ ) represents the superoperator of a quantum operation. The most general form of a quantum operation can be written in several representations; in this work, we will concentrate on the Kraus representation (also known as the operator-sum representation), stated as

$$\Lambda (\cdot ):= \sum _iE_i\cdot E_i^\dagger \,,$$

(11)

where E_i is the i^th term in the sum of operators, and Λ( ⋅ ) is taken to be a general quantum operation superoperator, constrained to the completely positive (CP) condition^1,35,36.

We also introduce here the class of doubly-stochastic (DS) quantum channels, with the term quantum channel distinguishing from quantum operation in that, in addition to the CP constraint, we additionally impose trace preservation (TP)¹. In this work, we will refer to CPTP maps using Φ( ⋅ ). Moreover, doubly-stochastic quantum channels are unital, meaning that the fixed point of the channel upholds the equality $\Phi (\mathbbI_n)=\mathbbI_n$^47,49. In defining the class of doubly-stochastic quantum channels, we use the fact that any Kraus operator can be factorized, as all systems of Kraus operators implementing a quantum operation are related by a unitary transformation. A particular decomposition can be defined as

$$E_i=\sum _j\sqrt\theta _jP_j\,.$$

(12)

Here $P_j\in \mathbbP_n$ refers to permutation matrices from the set of n × n permutation matrices, and θ_j refers to a probability distribution⁴⁹ (we have also omitted the indices i on the right-hand side for clarity). The existence of this class of convex decomposition comes from the Birkhoff-Von-Neumann Theorem^36,49,54 for which it is known that such a decomposition can be found in polynomial time⁸².

Lastly, we present projective measurements for density matrices constructed from graph Laplacians. Following the treatment of ref. ⁴¹, we define a set of orthogonal projectors Π_k such that $\sum _k\mathcalM_k=\mathbbI_n$. The post-measurement state of a general density matrix is then

$$\mathcalM(\boldsymbol\rho )=\frac\mathcalM_k\boldsymbol\rho \mathcalM_k\rmTr[\mathcalM_k\boldsymbol\rho ]\,,$$

(13)

where $\rmTr[\mathcalM_k\boldsymbol\rho ]$ represents the probability of the k^th measurement outcome. Note that projective measurements are known as a specific example of a CP map^1,35,36. In Section II E, we shall use projective measurements to erase subsystem interactions from the density-matrix form of the IG, ρ_IG, as well as for selecting appropriate subsystem permutations of the CG density matrix σ_CG.

Thermodynamic path length & (un)complexity

As mentioned in Section II C, the quantum Fisher information defines an entire family of statistical distance measures, from which we have taken particular interest in the family of entropic divergences. However, it is still not clear how to connect this to the more profound notion of thermodynamic path length. In order to provide an answer, let us start from quantum thermodynamics^75,80,81: the distance between any two quantum states (in continuum spacetime) can always be described as the average work extracted over some path through configuration space ξ:

$$W=\int_\xidt\,\textTr\,\left[\dotH_t\boldsymbol\rho _t\right],$$

(14)

where we consider H_t = ∑_iλ_iX_i as a time-dependent Hamiltonian with time-dependent, experimentally controllable parameters λ_i and time-independent observables X_i, and ρ_t is the time-evolved density matrix from t ∈ [0, τ], following the work of^75,80,81.

We also generally know how ρ_t evolves in spacetime via the Lindblad master equation^80,81, which is given by

$$\fracd\boldsymbol\rho dt=i/\hslash \left[H,\boldsymbol\rho (t)\right]+\mathcalL(\boldsymbol\rho (t))\,,$$

(15)

where $\mathcalL(\boldsymbol\rho (t))=\sum _j\gamma _j\left(L_j\boldsymbol\rho L_j^\dagger -1/2\L_j^\dagger L_j,\boldsymbol\rho \\right)$, and ρ_t, ρ(t) represent the time-evolved density matrix at time t, as well as the time-dependence of the density matrix on t, respectively. L_j are known as jump operators, and describe the channel that the quantum system is subjected to as it interacts with external environmental degrees of freedom⁸¹. γ_j are known as the decoherence rates.

In the case of the QCMP, this machinery is not needed, as we simply wish to understand the optimal case of quantum circuit mapping. That is to say, we wish to consider a noiseless quantum processor, capable of infinite parallelization (as we described above and in the manuscript’s discussion section). In that case, there are no environmental factors nor decoherence to consider, and we can examine our problem from the standpoint of a closed quantum evolution; therefore, we set γ_j = 0 and recover the original Von Neumann equation. As is expected for a closed system of pure quantum states, the dynamics now depend only on the Hamiltonian.

In order to calculate thermodynamic path length⁸¹, considers the amount of work dissipated into the environment due to restricted thermodynamic transformations on Gibbs states. One can directly find this from Equation (15), by optimizing the geodesic equations and accompanying Christoffel symbols for λ_i⁸¹, ending with

$$W_\rmdiss=1/\beta \int_\xi dt\dot\lambda _i(\mathsfG_ij)_t\dot\lambda _j\,,$$

(16)

Where β here represents the inverse temperature related to the Gibbs state, as is standard. From W_diss, we can formally define thermodynamic path length as

$$\mathsfW_\rmpath=1/\beta \int_\xi dt\sqrt{\dot\lambda _i(\mathsfG_ij)_t\dot\lambda _j}\,.$$

(17)

In these previous two equations, we recognize the quantum Fisher information $\mathsfG_ij$ in the integral kernel. As we discussed previously in Section II C, it is known that thermodynamic path length and the Jensen-Shannon divergence compute the lower-bound distance between quantum states, and that this distance constitutes a geodesic in a configuration space of allowed transformations between equilibrium states^{56,57,73,75,79,80,81}. Lastly, we know that geodesics not only represent the shortest paths on a Riemannian manifold, but also that the distance between any two infinitesimally small intervals on the geodesic are locally the shortest path as well (i.e. the distance function we have defined must monotonically decrease along the thermodynamic path).

Before progressing, there are a few further points to mention. Firstly, when two CG vertices are adjacent to one another such that a corresponding IG two-qubit edge (gate) may be performed, we say that this edge is executable, and therefore should not factor further into the shortest-path calculation. Therefore, we compensate for this by performing Bell measurements on these edges, an operation already shown in⁴¹ to erase edges of simple graphs. We use the measurement scheme in quantum-operation form, as discussed at the end of Section II D. Secondly, in order to permute vertices on the CG, we make extensive utilization of the doubly-stochastic quantum channel forms which are also described in Section II D. However, we must make a slight modification due to the practical considerations of the QCMP. As we are limited to performing only nearest-neighbor SWAP gates on the CG, this signifies that, for the Kraus operators $E_i=\sum _j\sqrt\theta _jP_j$, we have that $P_j\in \mathbbP_n(\,\textCG\,)\subset \mathbbP_n$, where $\mathbbP_n(\,\textCG\,)$ is the subgroup of all nearest-neighbor permutations available on the CG at a given time instant.

Thirdly and lastly, the operations of a quantum circuit take place over the discrete configuration space of SU(2^k), with k = 2, 3 in most contexts, representing the number of qubits participating in a given gate⁴². Although it is the case that SU(2^k) is a Lie group and is therefore continuous, the permitted operations of the QCMP lie strictly within discrete configuration space, as we are restricted to only the set of Bell measurements $\\mathcalM_e\_e\in E_\rmIG$ on the IG, and doubly-stochastic quantum operations $\{\Lambda (\cdot )| E_i\in {\mathbbP}_n(\,\textCG\,)\}$ on the CG, both of which are represented by discrete simple graphs.

We can then discretize the integral over $\xi \in \langle {\\mathcalM_e\}_e\in E_\rmIG,\Lambda (\cdot )\rangle$ by considering infinitesimally small time translations t + Δt with Δ < < 1, such that

$$\boldsymbol\rho (t+\Delta t)\approx \mathcalE(\boldsymbol\rho (t))\,,$$

(18)

where $\mathcalE(\cdot )$ is the action of a quantum channel acting on ρ. If we then perform this action m times, then we have

$$\boldsymbol\rho (t+m(\Delta t))\approx \mathcalE_m\,\circ\, \cdots\, \circ\, \mathcalE_1(\boldsymbol\rho (t))\,.$$

(19)

Keeping all of these points in mind, we can re-write the integral from Equation (16) in discretized form as

$$W_\rmdiss=\sum _m\mathsf\Pi^l\left[\mathcalM_i^l\left[\arg \mathop\min \limits_{\mathsfG_ij}\left[\mathsf\Pi^m\left[\Lambda _j^m({\mathsfG}_ij)\right]\right]\right]\right]\,,$$

(20)

where $\Pi^l\left[\mathcalM_i^l(\cdot )\right]=\mathcalM_i^l\,\circ\, \cdots\, \circ\, \mathcalM_i^1(\cdot)$, i.e. the sequence of measurements executed on the IG when two-qubit gates are possible on the CG. Additionally, $\Pi^m\left(\Lambda _j^m\left(\cdot \right)\right)=\Lambda _j^m\,\circ\, \cdots\, \circ\, \Lambda _j^m\left(\cdot \right)$, i.e. the sequence of SWAP-gate permutations undertaken in order to move qubits on the CG such that IG two-qubit gates can be performed. We sum over all of the permutations performed as we are erasing IG edges. Finally, as we recognize from^56,73,79 and Equation (4) that the quantum Jensen-Shannon divergence is directed related to the quantum Fisher information matrix, we can directly substitute and obtain the form

$$W_\rmdiss=\sum _m\mathsf\Pi^l\left[{\mathcalM}_i^l\left[\arg \mathop\min \limits_\mathcalD_ij^\,\textqJS\,\left[\mathsf\Pi^m\left[\Lambda _j^m(\mathcalD_ij^\,\textqJS\,(\boldsymbol\rho _\rmIG| | \boldsymbol\rho _\rmCG))\right]\right]\right]\right]\,,$$

(21)

where $\mathcalD_ij^\,\textqJS\,(\boldsymbol\rho _\rmIG| | \boldsymbol\rho _\rmCG)=\mathcalS(\frac{\boldsymbol\rho _\rmIG+\boldsymbol\rho _\rmCG}2)-\frac12\left(\mathcalS({{\boldsymbol\rho }}_\rmIG)+\mathcalS({{\boldsymbol\rho }}_\rmCG)\right)$, and the subscripts i, j denote quantum operations on the IG and CG, respectively. We have also absorbed the terms $\dot\lambda _i$ and $\dot\lambda _j$ into the description of their respective quantum channels, as these terms represent time-dependent, externally-controllable parameters in the first place. The equation above can be likened to the process of parallel transport on a Riemannian manifold^56,73, and preserves the structure of the metric, as well as the geodesic form.

As we sum over all of the m permutations performed, we eventually erase all of the edges of the IG, resulting in an effective distance between the original CG and the maximally mixed state (now the erased IG):

$$\beginarrayrW_{\rmdiss}=| | \mathbbI_\rmIG-\Pi^m\left[\Lambda _j^m({{\boldsymbol\rho }}_\rmCG)\right]| _{\mathcalO\in \langle {\{{{\mathcalM}}_e\}}_{e\in E_\rmIG},\Lambda (\cdot )\rangle }\\ =\mathcalC({\mathbbI}_\rmIG)-\mathcalC(\rho _\rmCG)=\mathsfU_\rmSWAP\,,\endarray$$

(22)

where $| | \cdot | _\mathcalO$ is a distance measure subject to the restrictions on transformations $\mathcalO$ for transporting ${{\mathcalD}}_ij^\,\textqJS\,({{\boldsymbol\rho }}_{{\rmIG}}| | {{\boldsymbol\rho }}_{\rmCG})$ along the geodesic. It is obvious from the lower half equalities of Equation (22) that our equation exactly coincides with the form of quantum circuit uncomplexity given by⁴² and expounded upon in⁴³. Additionally, Equation (22) is directly related to the quantum Wasserstein distance, another known distance measure for calculating the shortest path between two quantum states in terms of number of gates within some restricted set of allowed transformations^56,73.

Benchmark Results

In this section, we describe the numerical results obtained from comparing the SWAP uncomplexity against IBM’s Qiskit compiler⁸³*, as well as against a brute-force approach⁸⁴. These experiments were carried out for two main reasons. Firstly, we wish to subject the SWAP uncomplexity formalism and algorithm to a concrete, rigorous sanity check; after all, if the SWAP uncomplexity algorithm does in fact solve for the minimal SWAP-gate count, then the bounds we calculate should not be surpassed by any known compilation or brute-force optimization method in existence. By such logic, a compiler should be able to attain but not find fewer SWAP gates for an arbitrary IG / CG pair. In order to perform this empirical check, we chose to run our algorithm (Section IV A) against the Qiskit compiler, since it is considered to be the state-of-the-art approach at the moment. Secondly, to the best of our knowledge, there is scant literature on bounding required SWAP gates for an IG / CG pairing; at the moment, the latest work we are aware of addresses only up to quantum circuits of 6 qubits via a brute-force optimization algorithm^84,85. In contrast, our simulation results demonstrate scalability that greatly exceeds this brute-force optimization technique⁸⁴, as we achieved results for circuits of up to 16 qubits.

57 benchmark circuits were selected from the qbench suite⁵³. These benchmarks cover a range of 3 to 20 qubits and represent a wide spectrum of possible IG connectivities (47 different connectivities) encountered in quantum algorithms. More details about the selected benchmarks can be found in the Supplementary Material. As for the CGs, we chose connectivity graphs from a set of 16 in-use quantum devices, ranging from 5 to 72 qubits. The specific details of these devices are provided in the Supplementary Material. As some of the benchmarks are too large to be run on some of the smaller processors from our list, in total we devised 675 simulation experiments with the Qiskit compiler⁸³. In these simulations, we utilized Qiskit’s transpiler with the default circuit-optimization setting.

The results of our simulations are shown in Figs. 2-4. In Fig. 2, we display the normalized number of SWAP gates found by: the SWAP uncomplexity from Section II E (shown in green); the Qiskit compiler (denoted in orange); and the maximum SWAP-gate bound (depicted in blue). We observe clearly that the SWAP uncomplexity can be reached but never surpassed by the Qiskit compiler for select benchmark trials. As expected, the Qiskit compiler significantly outperforms the maximum SWAP-gate count calculated. Figure 3 also showcases the relation of the two-qubit gate count of the circuits (before compilation) and the bounds. The results in this figure, however, do not only depend on the circuit complexity, but also on the coupling graph.

**Fig. 2: Simulation results for various IG / CG benchmark pairs.**

**Fig. 3: Subset of simulation results from Fig. 2 where only one CG is shown (Google Bristlecone).**

In order to more thoroughly scrutinize our results, we have included the relative graph-theoretic edge complexity for the benchmark circuits and have depicted them in Fig. 3, Here, results are plotted for only one device, the Google Bristlecone device, and for a circuit size of up to six qubits. Two subgraphs are shown, relating the normalized number of SWAP gates to two different measures: in a) the relation between the bounds and the number of two-qubit gates and in b) the relation between the bounds and the IG size of the circuit, shown as nodes-edges pairs with correspondingly small IG figures as guides for the reader. It is evident that, while the number of IG nodes or qubits has the biggest influence on the results, the number of edges and gates is also important. We refer the reader to the Supplementary Material in order to locate the circuit corresponding to points labeled on either of the horizontal axes of Fig. 3.

The non-triviality of the maximal and minimal SWAP-gate counts becomes evident in Fig. 4, where we present a covariance matrix with correlation coefficients ranging as [−1, 1], with 0 indicating no correlation⁸⁶. This matrix compares the results that we obtained throughout the simulation; in particular, we compare the effective correlation between the SWAP uncomplexity; the Qiskit compiler SWAP calculation results; and the maximal bound as calculated in the Supplementary Material. Notably, both of our bounds (i.e., those obtained from our minimal bound with the SWAP uncomplexity algorithm, as well as the maximum SWAP-gate count) exhibit a substantial positive correlation (34% and 73%, respectively) with the actual results obtained from the compiler. The correlations here exemplify the non-triviality of the bounds; in other words, the SWAP uncomplexity and maximal bounds grow proportionally with the actual compilation results. The results at best coincide with each other, meaning that the lower bound equals the actual SWAP-gate count from the presence of a graph isomorphism; in this case, the SWAP uncomplexity, Qiskit result, and the maximal bound all obtain the same amount (which is zero if a graph isomorphism is present). These checks provide not only hard evidence for the usability of our methods, but additionally serve as a crucial sanity test that was passed for the algorithmic realization of the SWAP uncomplexity.

**Fig. 4: The Pearson correlation matrix⁸⁶ between the critical parameters measured for our benchmark investigation.**

Although not shown in Fig. 4, it is also worth observing the considerable impact of the initial placement on the resulting bounds; this particularly depends on the GED and the number of missing edges in the chosen CG partition compared to the IG. We therefore calculated the correlation coefficients of these two parameters (as well as the case when compared to our retrieved bounds), resulting in correlations of 79% and 61% for the SWAP uncomplexity and maximal bounds, respectively. Using the same initial placement for the Qiskit compiler resulted in a 45% correlation with the parameters related to initial placement.

The qubit-assignment strategy was initially tested with 729 benchmarks, showing a success rate of 92.6%. The remaining 7.4% of the benchmarks could not be finished due to insufficient computing resources. Recognizing the limited scalability of the approach (up to 16 circuit qubits), we developed a more relaxed method for complete graphs, mentioned in Section IV B. Indeed, the scalability of our exact algorithm already exceeded that of the exact state-of-the-art algorithms, which struggled beyond 6 qubits⁵¹. Furthermore, our initial placement encountered no difficulties in exploring a vast search space. It successfully executed circuits on all tested devices, extending up to a size of 72 physical qubits in our case.

Lastly, Fig. 5 shows a comparison between our SWAP uncomplexity algorithm (Section IV A) and the brute-force optimization results from⁸⁴. In this approach, the authors utilize an optimizer, which essentially tries every permutation of SWAP placements possible while respecting the gate-dependency graph and weighted IG of the original quantum circuit. In all cases, we see clearly that the brute-force algorithm only achieves but never surpasses the SWAP uncomplexity bound.