Geometric Refactoring of Quantum and Reversible Circuits Using Graph Algorithms

Martin LUKAC, Saadat NURSULTAN, Georgiy KRYLOV, Oliver KESZOCZE, Abilmansur RAKHMETTULAYEV, Michitaka KAMEYAMA

Summary :

With the advent of gated quantum computers and the regular structures for qubit layout, methods for placement, routing, noise estimation, and logic to hardware mapping become imminently required. In this paper, we propose a method for quantum circuit layout that is intended to solve such problems when mapping a quantum circuit to a gated quantum computer. The proposed methodology starts by building a Circuit Interaction Graph (CIG) that represents the ideal hardware layout minimizing the distance and path length between the individual qubits. The CIG is also used to introduce a qubit noise model. Once constructed, the CIG is iteratively reduced to a given architecture (qubit coupling model) specifying the neighborhood, qubits, priority, and qubits noise. The introduced constraints allow us to additionally reduce the graph according to preferred weights of desired properties. We propose two different methods of reducing the CIG: iterative reduction or the iterative isomorphism search algorithm. The proposed method is verified and tested on a set of standard benchmarks with results showing improvement on certain functions while in average improving the cost of the implementation over the current state of the art methods.

• Publication: IEICE TRANSACTIONS on Information Vol.E107-D No.8 pp.930-939
• Publication Date: 2024/08/01
• Publicized: 2024/06/24
• Online ISSN: 1745-1361
• DOI: 10.1587/transinf.2023LOP0011
• Type of Manuscript: Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing)

1.  Introduction

The design of quantum circuits generally involves the selection of a set of quantum gates such as the \(T/T^\dagger/CNOT\), \(CZ/CH\), or Clifford-\(T\) gate sets and a particular set of constraints related to the synthesis process. These constraints can be related to the technology such as linear nearest neighbor constraints, 2D symmetric arrays of trapped ions or fault-tolerance in general.

The latest available technology showing most promises for the quantum computer is either the quantum gated computer or the fully connected ion-trap [1]. For gated quantum computers, the design of quantum circuits is focused on designing circuits under constraints with respect to planar interaction between qubits and the regular layout of qubits in the quantum processor [2]. Recently, the 2D arrays of Rydberg neutral atoms have also been popularized in [3] and require similar type of 2D nearest neighbor interactions. While new technologies are still in development and are being experimented with, all of them are expected to have constraints strongly impacting the circuit design and optimization tools.

As a result, the design of quantum circuits and algorithms has been quite active since late nineties but the actual physical design and placement of quantum circuits is related to specific constraints of various quantum technologies. For instance, the design of NMR quantum computer [4] required a specific mapping technique from the representation to a chloroform molecule. In the one-way quantum computer [5], the target algorithm has to be translated to a series of measurement operations giving the overall realization a very specific spatial pattern. In addition, from the general point of view, the original logical universality was demonstrated in [6] using the set of quantum gates designated as \(CNOT/CV\), while currently this gate set is not used due to its high cost of implementation. Currently in the logic design of quantum circuit the so called \(\text{Clifford}-T\) quantum gate set is used.

While the issue of technology mapping has been envisaged for various technologies, the mapping of logical and quantum circuits onto a quantum computer requires additional technological constraints. The first of such requirements is the limit on the size of a quantum gate that can be directly implemented in quantum computer [4], [6]. This means that every logical or quantum gate requiring more than two qubits must be broken into two qubit gates. Another constraint is the requirements of constructing quantum gates on physically adjacent qubits [4].

These constraints on placement and realization of the quantum physical architecture (called coupling map) have been used in various technologies. For instance, in [7], the layout of the one-way quantum computer [5] yields a NP-complete problem. The problem of creating nearest neighbor compliant circuits has already been considered in one or two dimensions (see, e.g., [8] or [9]). Recent studies [10]-[15] explored the application of the two-dimensional layout of quantum logical qubits to various existing realizations [16]-[18] of gated quantum computers.

The existing approaches have been exploiting various properties of logic, gate and implementation based local and global properties. In [10], the authors present a work where various quantum and reversible logic circuits are mapped specifically to individual architecture of the IBM Q quantum computers. The target of these studies is to demonstrate the maximum exploitation of the nearest neighbor requirements. In [9] the authors used a look-ahead method for placing qubits in a 1D and 2D quantum structure by estimating short term impact of qubit placement. In [8], the authors implemented a sifting method allowing to map a quantum circuit independently of hardware geometrical constraints to a Linear Nearest Neighbor (LNN) model by calculating the optimal cost of individual placement for each two consecutive quantum gates. A more specific constraints of a gated quantum computer was proposed in [11], [12]. The authors evaluated a method for reducing the number of inserted swap gates by replacing them with a less costly variant by inverting the CNOT gates required by some of the IBM Q architectures. In [19], the authors use a pre-processing of the quantum circuit that groups gates and places them using a direct, all-qubits-at-once mapping general layout heuristics. In [20], the authors propose a more complex method including qubits ordering combined with optimization of permutation between gates. The default algorithm of placement and layout of quantum circuits on the IBM Q computers uses a local graph arrangement algorithm that first generates sub-graphs linked by single edge and then places them optimally. In [15] the authors took a different approach where starting from an ideal circuit an iterative approach was implemented finding an optimal mapping to any given qubit coupling. These approaches are in general efficient but require the reformulation and application of local rules, which do not guarantee global minimization.

In parallel to these specific computer-architecture approaches there is a very large amount of work in general quantum circuit design and optimization. In [21] a method for optimization of quantum circuits with continuous parameters is presented, In [22] the authors minimize quantum circuits by a set of rules however they do not consider specific hardware constraints and in [23] a machine learning optimization of quantum circuits is proposed but the evaluation is limited to few circuits design. More general methodologies have been proposed using a variety of methods such as evolutionary approaches [24]-[26], logic minimization [8], [12], [27], [28] or heuristics [29]-[31].

To solve the problem of hardware constrained quantum circuit design, and unlike previous approaches that target specifics of hardware we take a different approach. Instead of designing a quantum circuit for a particular quantum chip and coupling map, we start by designing an ideal virtual hardware architecture that is iteratively refined to match the target real physical model. Given a quantum circuit on \(n\) qubits, we start by generating the most accommodating quantum physical model (allowing arbitrary qubit interaction) \(\Upsilon\), spanning the \(n\) dimensional space by representing the interactions between every pair of qubits. Once \(\Upsilon\) is constructed, we apply iterative reductions allowing the mapping of \(\Upsilon\) onto an existing qubit coupling model \(\mathcal{C}\) of a quantum computer. This coupling is optimized by mapping the circuit onto the coupling map by minimizing the Dijkstra shortest distance on the qubit coupling. The reduction is driven by the minimization of the cost of the mapping, i.e. reducing the number of interactions between qubits. Alternatively, the model allows taking into account the noise model \(\Omega\) (such as correlated noise model [32] or [33]) of the qubits within the quantum chip. Combining the interaction model \(\Upsilon\) and the noise model \(\Omega\) permits the application of the multi-objective optimization and model-independent circuit placement optimization. Other work on exploring similar ideas exists (see, e.g. [10]), however, this research is uniquely characterized by the reduction rule set for the connectivity graph.

This paper is organized as follows: Sect. 2 introduces the necessary background to our method. Section 3 describes the proposed approach and Sect. 4 introduces the method of minimizing the proposed model. Section 5 describes the experiments performed and Sect. 6 concludes the paper.

2.  Method Background

Let \(C\) be a quantum circuit operating with \(p\) gates on \(l\) qubits. Let the circuit \(C\) be a sequence \(S_C=\langle s_1, \ldots, s_p \rangle\) of quantum gates \(s_j\) selected from a gate set \(\mathbb{G}\). The gate set Clifford-\(T\), for example, is given by \(\mathbb{G}~=~\{CNOT,T,T^\dagger,H\}\).

Also let, two qubit quantum gates such as \(CNOT\), \(CV/CV^\dagger\), \(CZ\), \(I_{ZZ}\), \(CH\) be referred to as Generalized Interaction (GI). Figure 1 shows three different circuit realizations of the Toffoli function. Each circuit uses a different quantum gate set and has a different number of \(GI\) gates.

Fig. 1  Three examples of Toffoli function realizations using different gate sets: a) \(CV/CV^\dagger/CNOT\), b) \(CH/CZ\) and c) Clifford-T gate sets.

Definition 1 (Circuit Skeleton (CS)). A quantum circuit’s skeleton is the structure that remains after removing all single qubit gates and any logic on the interaction gates.

For instance the circuit skeleton of the circuit shown in Fig. 1 (c) is shown in Fig. 2 (a).

Fig. 2  Circuit Skeleton (a) and CIG (b) for circuit in Fig. 1 (c).

Definition 2 (Circuit Interaction Graph (CIG)). The circuit interaction graph is a representation of a quantum circuit \(C\) as a weighted graph \(\Upsilon=(\mathbb{V},\mathbb{E})\) such that:

• Each qubit \(i\) in the circuit \(C\) is represented by a vertex \(v_i\in \mathbb{V}\)

• There exists an edge \(e_{ij}\) between vertices \(v_i\) and \(v_j\) if there is a gate operating on qubits \(\vert i\rangle\) and \(\vert j\rangle\).

• Each edge \(e_{ij}\) is associated with a weight \(w_{ij}={W}(e_{ij})\). \({W}(e_{ij})\) is equal to the number of GI gates operating on qubits \(\vert i\rangle\) and \(\vert j\rangle\).

The corresponding CIG to the circuit from Fig. 1 (c) is shown in Fig. 2 (b).

Let a coupling map be a specification of an gated quantum computer physical interactions. The coupling map \(\mathbb{M}\) is a set \(\{m_{0,1},\ldots,m_{k,l} \}\) of edges representing the physical connections between a set of physical qubits \(\mathbb{Q}\). An element \(m_{i,j}\) represents the existence of an physical connection between two physical qubits \(\vert i\rangle\) and \(\vert j\rangle\). We will denote a coupling map (un-directed graph) \(QC=\{\mathbb{Q},\mathbb{M}\}\) with \(\mathbb{Q}=\{q_0,\ldots, q_l\}\) being the set of physical qubits in the coupling. Examples of such architectures can be seen in Fig. 3. The coupling map indicates which qubits can be used to directly implement two qubit quantum operation. For instance qubits \(0\) and \(1\) in Fig. 3 (a) can interact directly but if qubits \(0\) and \(2\) must interact then their logical qubits must be moved to immediate proximity. This implies that for two qubits to interact they must be direct neighbors and be also connected by an edge in \(\mathbb{M}\).

Fig. 3  Example of some of the available architectures and their qubit couplings available in the IBM Q initiative [2].

3.  Circuit Interaction Graph Manipulation

To assist with representing the information about the graph, a notion of path is introduced. In this context, a path is a sequence of edges, connecting two vertices \(i\) and \(j\) in the graph.

Definition 3 (Path in CIG). A path \(\rho\) in a CIG and defined over \((\mathbb{V},\mathbb{E})\) is an ordered set \(\rho=\{e_{i,j}\preceq\ldots\preceq e_{k,l}\}\) of edges, such that each edge \(e_{i,j}\in \mathbb{E}\) is encountered only once, i.e. a simple path

We will denote a path linking a start vertex \(v_{start}\) and an end vertex \(v_{end}\) by \(\rho_{start,end}\). Evolving the definition further, the notion of a path \(\rho\) can be simply extended to the so called weighted path; a path that is associated with a single weight for each edge.

Definition 4 (Weighted Path). A weighted path \(\gamma\) in a CIG defined over \((\mathbb{V},\mathbb{E})\) between two vertices \(i\) and \(l\), is an ordered set \(\gamma=\{\mathcal{W}(e_{i,j})\preceq\ldots\preceq \mathcal{W}(e_{k,l})\} = \{\gamma_0,\ldots,\gamma_k \}\) with \(\mathcal{W}(\cdot)\) being the weight function that returns the weight of any edge in the CIG.

As an example, the skeleton circuit from Fig. 4 (a) is shown in the CIG in Fig. 4 (b). Observe that the edges \(e_{ac}\), \(e_{ae}\), \(e_{be}\) and \(e_{ce}\) have weight \(w=1\) while the edge \(e_{ad}\) has a weight \(w=2\). The weights are obtained directly from the skeleton circuit in Fig. 4 (a).

Fig. 4  (a) skeleton of quantum circuit, (b) corresponding CIG, (c) CIG after consistent ER \(\mathcal{R}(e_{ce})\) and (d) CIG after inconsistent ER \(\mathcal{R}(e_{be})\), (e) reconnecting \(\vert c\rangle\) and \(\vert e\rangle\) through \(\vert a\rangle\) and f) reconnecting \(\vert b\rangle\) and \(\vert e\rangle\) through \(\vert d\rangle\) and \(\vert a\rangle\)

Note that the weight based ordering removes information about the order of visitation of vertices by the quantum gates. However the purpose of this ordering is to provide a priority to highly visited paths when allocating the physical qubits.

Definition 5 (Cost of Path). A cost of path \(cost(\rho)\) is defined as

\[\begin{align} cost(\rho)=\sum_{e\in \rho} \mathcal{W}(e) \tag{1} \end{align}\]

To manipulate the CIG, a set of robust operations must be defined. The first operation that is required for minimizing the CIG is the removal of an individual edge.

Definition 6 (Edge Removal (ER)). In a weighted graph \(\Upsilon=(\mathbb{V},\mathbb{E})\), ER is an operation \(\mathcal{R}(e_{jk})=\Upsilon(\mathbb{V},\mathbb{E}\setminus\{e_{jk}\})\).

The ER operation can create two different kind of graphs. Let \(\Upsilon=(\mathbb{V},\mathbb{E})\) and \(\mathcal{R}(e_{jk})\): if applying ER the resulting graph is not connected any more, we call the ER inconsistent, if the resulting graph is still connected we refer to it as consistent ER.

For instance for the CIG in Fig. 4 (b) constructed from the skeleton in Fig. 4 (a), the result of a consistent and inconsistent ER are shown in Fig. 4 (c) and Fig. 4 (d) respectively.

The result of these two ER operations can be analyzed further. Assume that the logical qubits from the skeleton circuit in Fig. 4 (a) are mapped to the physical qubits of the coupling model from Fig. 3 (a) as follows: \(\vert a\rangle \rightarrow 6\), \(\vert b \rangle\rightarrow 12\), \(\vert c \rangle\rightarrow 1\), \(\vert d \rangle\rightarrow 5\), \(\vert e \rangle\rightarrow 7\). As can be observed there is no available direct physical coupling between the \(\vert c\rangle\) and \(\vert e\rangle\) logical qubits located on physical qubits 1 and 7 respectively. The lack of physical coupling is represented in this case as a consistent ER operation resulting in the CIG from Fig. 4 (c). The result of the consistent ER is the disconnection of the qubit \(\vert c\rangle\) and \(\vert e\rangle\). It requires the re-routing of the logical qubit \(\vert c\rangle\) and \(\vert e\rangle\) to near proximity so that the GI gate can be applied. This can also be represented in terms of paths. In the original CIG the path \(\rho_{ce}=\{e_{ce}\}\) and the \(\mathcal{R}_{ce}\) resulted in \(\rho_{ce}=\{\}\), i.e. empty path. One possible solution is shown in Fig. 5 (a). In this case the logical qubits \(\vert a\rangle\) and \(\vert e\rangle\) were swapped using a SWAP gate, then the GI gate can be directly applied because the physical qubit \(\vert a\rangle\) and \(\vert c\rangle\) are directly linked. Finally, their respective location was restored using again a SWAP gate. As a result of these operations a new path \(\rho'_{ce}=\{e_{ac},e_{ce}\}\) was created.

Fig. 5  (a) The logical to physical qubits mapping, (b) reconnecting \(\vert c\rangle\) with \(\vert e\rangle\) by exchanging the position of logical qubits \(\vert a\rangle\) and \(\vert c\rangle\), (c) an inconsistent ER resulting in \(\vert b\rangle\) being an unconnected qubit.

Theorem 1. In order to ensure the functionality of the original circuit, a consistent ER operation \(R(e_{ij})\) from a path \(\rho_{hk}\), requires the insertion of a maximum of \(2\vert \rho'_{hk}\vert-1\) SWAP gates.

A consistent ER operation therefore implies, that for all weights in the new path \(\rho_{il} = \{e_{ij}\preceq\ldots\preceq e_{kl}\}\), we have that each edge weight is increased by \(2\), i.e. for all \(e_{ij}\in \rho_{il}\) we have \(\mathcal{W} (e_{ij})^{new} = \mathcal{W}(e_{ij}) +2\). For instance, if the edge \(e_{ce}\) in CIG from Fig. 4 (b) is removed and resulting in Fig. 4 (c), then two swap gates have to be inserted on the edge \(e_{ac}\) in order for \(\vert e\rangle\) and \(\vert c\rangle\) interact directly (Fig. 4 (e)). Note that one SWAP is to make the interaction possible and the other to restore the original qubit placement. The corresponding circuit is depicted in Fig. 5 (b). Observe that in Fig. 5 (b) first the two logical qubits \(\vert a\rangle\) and \(\vert c\rangle\) have been swapped. This represents the swapping of the logical values between the physical qubits. Then the interaction between \(\vert a\rangle\) and \(\vert e\rangle\) is applied: despite that the interaction looks crossing more qubits it actually represents an existing physical connection between the physical qubit on top and on the bottom of the quantum circuit. Once the interaction is performed the logical qubits \(\vert a\rangle\) and \(\vert c\rangle\) are swapped back.

Figure 5 (c) illustrates the result of the inconsistent ER. The qubits \(\vert b\rangle\) and \(\vert e\rangle\) are disconnected and cannot be reconnected anymore because according to Fig. 4 (d) there are no more connections between logical qubit \(\vert b\rangle\) (mapped to 12, Fig. 5 (a)) and other qubits of the circuit. To reconnect the logical qubits \(\vert b\rangle\) and \(\vert e\rangle\) either the logical qubit \(\vert b\rangle\) should be placed on a different physical qubit or from the current physical qubit a new path to the logical qubit \(\vert e\rangle\) should be found.

Let the qubit \(\vert b\rangle\) be placed on physical qubit \(2\) instead of \(12\). The possible paths to connect \(\vert b\rangle\) to \(\vert e\rangle\) can be either by directly swapping the logical qubits \(\vert b\rangle\) with \(\vert c\rangle\) and then with \(\vert a\rangle\) or to swap the logical qubit through a set of unused physical qubits \(3\) and \(8\). The second solution requires to move the logical qubit \(\vert b\rangle\) from physical qubit 2 to 8 (by using four SWAP gates) and then interact with logical qubit \(\vert e\rangle\).

Theorem 2. An inconsistent ER operation \(R(e_{ij})\), requires the insertion of a maximum of \(2(\vert \rho_{ik}\vert-1)+2\) SWAP gates into a path \(\rho_{ik}\).

In order to normalize the outcome of the edge removal operations, we impose the condition that any ER must preserve the logical structure of the circuit.

Definition 7 (Canonical Edge Removal (CER)). A Canonical Edge Removal is an operation on a CIG that contains the following steps:

• 1. a consistent or inconsistent edge removal
  2. the insertion of appropriate number of SWAP gates to preserve the logic circuit structure

4.  \(\Upsilon\) Reduction

When a CIG is created, it represents the ideal or completely expanded geometrical model of a quantum circuit. Each qubit is connected in CIG to another qubit if an interaction or CNOT gate is applied to both of them. Once the coupling model is provided, the CIG of the quantum circuit is mapped to physical qubits and physical couplings. However, at this stage the CIG is oblivious to real hardware requirements (i.e., the coupling map) as with more qubits more edges will be generated, meanwhile a particular architecture will allow for a limited and constant connectivity between qubits. Therefore the mapping from the CIG to the quantum coupling is referred here to as \(\Upsilon\) Reduction.

Definition 8 (\(\Upsilon\) Reduction). Let there be

• \(\forall v_i\in \mathbb{V}\) a unique mapping \(\Sigma: v_i\rightarrow q_i\) such that \(q_i\in\mathbb{Q}\) and

• \(\forall e_{ij}\in \mathbb{E}\) a unique mapping \(\Delta: e_{ij}\rightarrow m_{ij}\) such that \(m_{ij}\in\mathbb{M}\)

then, given a \(CIG=(\mathbb{V}, \mathbb{E})\), a \(QA=(\mathbb{M},\mathbb{Q})\) and mappings \(\Sigma: \mathbb{V} \rightarrow \mathbb{Q}\) and \(\Delta: \mathbb{E} \rightarrow \mathbb{M}\), the \(\Upsilon\) reduced \(CIG^\Upsilon\) is implicitly defined by being isomorphic to \(QA_{CIG}=(\Sigma(\mathbb{V}), \Delta(\mathbb{E})).\)

As an example the \(CIG\) from Fig. 2 (b) is \(\Upsilon\) reduced to \(QA\) in Fig. 3 (b) but is not \(\Upsilon\) reduced to \(QA\) in Fig. 3 (a). The \(CIG\) is isomorphic to the \(QA\) from Fig. 3 (b) for the mapping \(\vert a\rangle \rightarrow 0\), \(\vert b\rangle \rightarrow 1\) and \(\vert c\rangle \rightarrow 2\) for instance. However as can be seen, this \(CIG\) cannot be mapped directly to Fig. 3 (a).

The \(\Upsilon\) reduction of the \(CIG\) from Fig. 6 (a) to the \(CIG\) in Fig. 6 (b) results in the \(CIG\) from Fig. 6 (b) have the logical qubits directly to physical qubits of the \(QA\) in Fig. 6 (c): the \(CIG\) from Fig. 6 (b) is isomorphic to the \(QA\) in Fig. 6 (c) using the following mapping \(\vert a\rangle \rightarrow 1\), \(\vert b\rangle \rightarrow 7\) and \(\vert c\rangle \rightarrow 6\). The resulting CIG is shown in Fig. 6 (b).

Fig. 6  Example of (a) \(CIG\), (b) its \(\Upsilon\) reduced form, (c) its mapping to the part of the Singapore architecture from Fig. 3 (a)

The \(\Upsilon\) reductions represent a heuristic method for mapping a CIG to a QA by iterative application of consistent or inconsistent ER and recalculating the number of required of SWAP gates. However, in order not to search all possibilities to match \(CIG\) to a \(QA\) on all possible mappings \(\Sigma\), several optimizations were implemented. The first step in all of the qubit mapping approaches start by first identifying qubits in \(QA\) that match the logical qubits that have edges with highest weight in the \(CIG\). Then for each remaining logical qubit in the \(CIG\) a search for the closest match among the direct neighbors of all previously mapped physical qubits is performed. Another alternative in mapping the qubits is to map the \(CIG\) qubits in order of decreasing weight of edges connecting qubits. Note that such a mapping is an implicit \(\Upsilon\) reduction: mapping qubits one after another one forces the removal of certain edges between qubits and thus requires the insertion of SWAP gates.

4.1  Qubit \(\Sigma\) Mapping

Once the CIG of a circuit is constructed, the algorithm searches for the best physical qubit in \(QA\) for each logical qubit in \(CIG\). As already introduced, two orderings by which the qubits are mapped were explored: branching factor (direct edges) or direct neighbors. Searching for the next best candidate physical qubit for the next logical qubit will have different results based on the ordering. For instance the let’s consider the \(CIG\) from Fig. 7 (a) and the \(QA\) from Fig. 3 (a). The edge based ordering and the nearest neighbor ordering gives \(s_w =\{\vert a\rangle, \vert e\rangle, \vert b\rangle, \vert c\rangle, \vert d\rangle \}\) and \(s_n =\{\vert a\rangle, \vert b\rangle, \vert e\rangle , \vert c\rangle, \vert d\rangle \}\) sequence respectively. The first qubit is mapped as follows: \(\vert a\rangle\rightarrow 1\).

Fig. 7  Example of (a) \(CIG\), (b) its mapping using the \(s_w\) sequence and (c) its mapping using \(s_n\) sequence on a part of the Singapore architecture from Fig. 3

Using the sequence of qubits \(s_w\) one possible mapping is \(\vert e\rangle\rightarrow 3\), \(\vert b\rangle\rightarrow 2\) \(\vert c\rangle\rightarrow 8\) and \(\vert d\rangle\rightarrow 4\) with a total cost of SWAP gates being 8. This is because the edges \(v_{\vert b\rangle, \vert e\rangle}\), \(v_{\vert c\rangle, \vert e\rangle}\) and \(v_{\vert a\rangle, \vert b\rangle}\) are directly mapped to direct connections between physical qubits of \(QA\). However the edges \(v_{\vert a\rangle, \vert c\rangle}\) and \(v_{\vert a\rangle, \vert d\rangle}\) require at least four SWAP gates each. Thus the total overhead is at least 8 (Fig. 7 (b)).

Using the sequence \(s_n\) a possible mapping is \(\vert b\rangle\rightarrow 6\), \(\vert e\rangle\rightarrow 7\) \(\vert c\rangle\rightarrow 8\) and \(\vert d\rangle\rightarrow 1\). The cost of required SWAP gates comes from the unsatisfied direct edges \(v_{\vert a\rangle, \vert c\rangle}\) and \(v_{\vert e\rangle, \vert d\rangle}\). Each edge requires four SWAP gates resulting in the total of 8 or more (Fig. 7 (c)).

In order to determine the best cost for placing individual qubits, we prepare a complete map of shortest distances between any two physical qubits in \(QA\) using Dijkstra algorithm. The placement of each qubit during the mapping is navigated so as to select the shortest distance between all currently placed qubits.

4.2  Weighted Mapping

The mapping so far is based simply on the distance between the individual qubits. However, to provide a more accurate estimation of SWAP gates required, the weights of the \(CIG\) are considered. Every weight \(\mathcal{W}(v_{ij})\) represents the number of times two qubits have to interact in the quantum circuit. This implies that every time two qubits should interact, they should be in adjacent position in \(QA\). Therefore during the qubits mapping, the weights will be indicating which edges are preferred to be directly mapped to adjacent qubits.

The \(CIG\) from Fig. 7 (a) has five edges of cost \(1\) and one edge of cost \(2\). Taking into account the weights of individual edges in the \(CIG\), the number of SWAP gates required for the mapping from Fig. 7 (b) now becomes 12 while the number of required gates for the mapping in Fig. 7 (c) remains the same at 8.

The inclusion of weights into the \(\Upsilon\) reduction is represented by giving a priority to direct mapping of edges with high weight. Therefore independently of the sequence of placement of the qubits, the algorithm maps qubits with high weight edges first and in direct adjacency.

4.3  Additional Mapping Constraints

The constraints imposed so far on the \(CIG\) here are only partial. In addition to the connectivity, the placement and the cost (number of quantum gates), a noise model of each qubit as well as possible edge orientation requirements must be integrated for some of the specific requirements of the gated quantum computers.

Because the \(\Upsilon\) reduction is a constraint satisfaction based algorithm, adding new constraints does not change the processing flow. The default solution is the result of fulfilling the constraint on qubit connections. Therefore, the \(\Upsilon\) reduction and the mapping of logical onto physical qubits can easily be modified to take care of additional constraints while searching for the solution. This reformulation is taken care of by first merging all the constraints into a single expression and then by formulating a minimization function over the set of all constraints. Let \(C_{cost}\), \(C_{placement}\), \(C_{noise}\) and \(C_{edges}\) be the respective constraints describing the cost, the placement, the noise and the edges of the \(CIG\), respectively.

• \(C_{cost}\) is a scalar constraint equal to the costs of a path as defined in Eq (1).

• The \(C_{placement}\subseteq V\) is the set of vertices of the \(CIG\) that violate the placement constraints (the number of edges vs. the number of physical neighbors).

• \(C_{noise}\) is a constraint that can take several forms depending on the used noise model. It represents the circuit reliability obtained by simulating the circuity on a set of allocated physical qubits on a quantum computer. It can also represent the additive noise per gate or per qubit added.

• \(C_{edges}\) is specific constraint indicating - if necessary - the properties of the physical connections between qubits. Example of such constraint is the direction of application of the control signal in a two qubit quantum gate.

First, let \(\theta\) represent parameters of the \(CIG\) model. That is, \(\theta\) is the set of physical qubits selected for the placement of the \(CIG\) with an associated layout scheme. Then, using the four constraints a minimization criterion can be formulated and is shown in Eq (2).

\[\begin{align} \mathcal{C}(CIG, QA) = \min_\theta (C_{cost},C_{placement},C_{noise},C_{edges}) \tag{2} \end{align}\]

Observe that Eq (2) is a specification that can be applied to standard SAT solvers or any other CSP problem solver. However, due to the physical nature of the \(CIG\) to \(QA\) mapping several constraints can be relaxed by providing knowledge about \(QA\) ahead of time. For instance, one can order the qubits according to daily tomography calibration (such as provided by Rigetti [18]) in order to minimize the space search with respect to the least noisy location.

Another minimization can be provided by using the knowledge that the circuit scaling is noise-monotonous; adding more qubits always increases the noise of the whole system. Knowing the set of least noisy qubits, the relative distance between them, and increase in noise of the system caused by extra qubits, one can argue about optimal placement and number of qubits required for realization of a given circuit on the target machine.

4.4  Algorithm Implementation

Our software reads the gates from a file in RevLib format [34] to a format provided by Qiskit API. Then, it retrieves a coupling map, that is physical qubit connectivity, from available quantum computers. We define a default layout to map qubits in alphabetical order - i.e. logical qubit A is mapped to physical qubit a, B gets mapped to b, etc. The actual algorithm is shown in the pseudo code 1. It starts by finding a coupling map, a graph of the connectivity of logical qubits \(QA\) (line 1). Then it pre-computes distances between all physical qubits using Dijkstra algorithm (line 2) and then it builds a CIG of the circuit (line 4). Next it creates a ordered set \(\mathbb{L}\) of all logical qubits ordered by their branching factors (line 5). The algorithm then proceeds to iteratively match the current CIG to any isomorphic sub-graph of the \(QA\) graph (line 7). If no such isomorphism is found the qubit with the smallest branching degree is removed from the \(CIG\) and from the \(\mathbb{L}\) set and is added to the \(Qubits\) container. This process is iterated until the \(CIG\) is mapped to the \(QA\) (line 6 to 14). When this process is finished, then the qubits accumulated in \(Qubits\) are mapped back to the QA using the \(consistentER\) operation one at a time (line 16 to 20). Finally the cost of the resulting mapping is calculated.

5.  Experiments

To verify the proposed method, we use the Qiskit SDK [35]. The SDK provides an access to physical quantum computers through API called IBM Q Experience. For data, we use the RevLib [34] for both only reversible or truly quantum functions.

5.1  Assumptions

At this stage of experimentation, the following generalizations have been adopted:

• We minimize the whole circuit over the set of physical qubits without any edge direction: the direction of the coupling map is not taken into account

• The insertion of SWAP gates is bi-directional without any local optimization. This means that for a path \(\rho_{ik}\) between two vertices \(v_i\) and \(v_k\) in CIG, the number of inserted SWAP gates is equal to \(2\cdot cost(\rho_{ik})\).

• Where possible, the gates provided by Qiskit API were used, otherwise we provide a macro implementation using decomposition to available gates. this mainly concerns the decomposition of \(C^nMOT\) gates with \(n>2\): we use the decomposition introduced in [6].

Most of our experiments were conducted for the IBM Q QPU Melbourne 16 that has a qubit coupling map as shown in Fig. 3 (c). This machine provides access to 14 physical qubits.

5.2  Results

Table 1 shows the results of our applied graph-based synthesis method for the IBM Melbourne Quantum architecture (14 qubits).

Table 1  Results of the CIG based quantum layout method

The first four columns show the function name, the number of inputs, outputs and total number of qubits respectively. Columns five to eight show the result of CIG based algorithm and columns nine to twelve show the results using the IBM provided synthesis algorithm. The last column shows relative improvement of CIG vs IBM algorithm. The best result in each row is highlighted in bold.

The CIG-based approach was evaluated using the IBM circuit compiler using various levels of optimization. In Qiskit three levels of optimization are available from the weakest to the strongest. The results of not optimized design are entitled \(qCost\) and the three levels of optimization using IBM native support are entitled \(qCost_i\). Similarly the CIG approach was applied directly or has been combined with IBM optimization of all three levels.

On average the CIG improvement over the best IBM result is \(24.6\%\) with the lowest improvement being \(-29\%\) for the function hwb6 and the highest improvement was \(64\%\) for the function 4mod5-v124. In addition it can also be seen that out of 22 displayed benchmark functions, the CIG algorithm without using the IBM optimization performs the best in 8 cases.

In addition to the above experiments we also compared our results to the results from [20] that also use CIG based approach. However unlike in the proposed method, the work [20] is not reporting SWAP gates counts and in addition optimizes the gates. In order to evaluate our approach we also applied a set of optimizing transformations. The implemented transformations are single gate concatenation, gate movement and re-ordering. Each operation is by the rules below. The implemented transformations are similar to the transformations in [20] and from [36]. These optimizations combine multiple single-qubit quantum gates into one single qubit gate according to simple rules:

• two single qubit quantum gates can be approximated by a single quantum gate resulting form the multiplication of respective matrices of each quantum gate.

• Up to three distinct \(R\) quantum gates rotations can be combined by creating a single qubit gate with parameters on rotation about individual axes from the \(R\) rotations

• CNOT gates defined on same logical qubits can be eliminated if there is no any quantum gate in between their control terminals

The results of these experiments are shown in Table 2. The first column is the name of the evaluated function, the second column shows the number of total qubits in the quantum circuit. The third column shows the count of quantum gates in the circuit as proposed by [20] and in the fourth column are the results obtained by our proposed method. The last column shows the percentage of change.

Table 2  Comparative results with similar approaches.

The presented results show that on the evaluated benchmarks the proposed method using the isomorphism algorithm in average outperforms the similar method from [20]. The iterative method performed better on various circuits with up to 61.8% of improvement in the count of the gates for cm82a and with the worse result for misex1 circuit where our approach performed worse by 20%.

The reason for the improvement observed are most probably due to the following algorithmic differences. First, our algorithm starts by constructing an ideal CIG that is then reduced to the smallest graph matching the largest sub-graph on the quantum computer architecture. Second, the iterative approach allows to perform an incremental improvements by searching for better qubits location. Finally, the proposed approach allows to optimally reconnect and place the logical qubits using a gradient based method allowing for optimal placement.

6.  Conclusion

In this paper we presented a general approach to solve the placement of quantum circuit on a two-dimensional regular structure quantum computer. The proposed method was applied to only existing architectures but is directly extensible to \(n\)-dimensional regular structure. We showed a heuristic method for placement of arbitrary quantum circuit taking into account the noise model and presented a heuristic algorithm allowing to place a given circuit based on the required constraints. Additionally, we proposed a formulation that allows the application of local search algorithms such as genetic algorithm or iterative optimization.

Our proposed method improved in some cases the default cost on the IBM Q approach. This is possibly due to the fact that our layout mapping uses guided global optimization and for a subset of circuits, does better job search for the qubit placements, accompanying the randomized qubits placement algorithms used in Qiskit API compilers. Another fact worth mentioning is that the improvement was achieved on the circuit that can be directly mapped to an IBMQ16 computer (with our assumptions considered). Therefore the use of an algorithm for optimizing circuits that can be directly mapped to existing methods is one of the areas for research and extension of the proposed method.

In the future we plan to provide a full set of functions integrated into a library that can be integrated in others algorithm solving the quantum layout problem. Our implementation could alternatively find its place as one of optimization layers for quantum object compilation. The next steps in the final developments are as follows: include the direction of coupling sensitive synthesis, noise related optimization, SAT solver for the optimal mapping, local minimization. Once all these features are implemented a testing and comparative analysis with other state of the art algorithms is to be performed.

References

[1] N.M. Linke, D. Maslov, M. Roetteler, S. Debnath, C. Figgatt, K.A. Landsman, K. Wright, and C. Monroe, “Experimental comparison of two quantum computing architectures,” Proceedings of the National Academy of Sciences, vol.114, no.13, pp.3305-3310, 2017.

[2] IBM, “IBM makes quantum computing available on IBM cloud to accelerate innovation,” 2016.

[3] K. Wintersperger, F. Dommert, T. Ehmer, A. Hoursanov, J. Klepsch, W. Mauerer, G. Reuber, T. Strohm, M. Yin, and S. Luber, “Neutral atom quantum computing hardware: performance and end-user perspective,” EPJ Quantum Technology, vol.10, no.1, Aug. 2023.

[4] M.A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010.

[5] R. Raussendorf and H.J. Briegel, “A one-way quantum computer,” Phys. Rev. Lett., vol.86, no.22, pp.5188-5191, May 2001.

[6] A. Barenco, C.H. Bennett, R. Cleve, D.P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J.A. Smolin, and H. Weinfurter, “Elementary gates for quantum computation,” Phys. Rev. A, vol.52, no.5, pp.3457-3467, Nov. 1995.

[7] Y. Lin, B. Yu, M. Li, and D.Z. Pan, “Layout synthesis for topological quantum circuits with 1-D and 2-D architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.37, no.8, pp.1574-1587, Aug. 2018.

[8] M. Lukac, P. Kerntopf, and M. Kameyama, “An analytic sifting approach to optimization of lnn reversible circuits,” 2017 International Conference on Information and Digital Technologies (IDT), pp.240-245, July 2017.

[9] R. Wille, O. Keszocze, M. Walter, P. Rohrs, A. Chattopadhyay, and R. Drechsler, “Look-ahead schemes for nearest neighbor optimization of 1D and 2D quantum circuits,” Asia and South Pacific Design Automation Conference, pp.292-297, 2016.

[10] M. Thornton and K.N. Smith, “Mustang-q: A technology dependent quantum logic synthesis and compilation tool,” Design Automation for Quantum Computers Workshop, IEEE International Conference on Computer Aided Design (ICCAD-QCEDA), Nov. 2017.

[11] A. Matsuo, W. Hattori, and S. Yamashita, “Reducing the overhead of mapping quantum circuits to IBM Q system,” 2019 IEEE International Symposium on Circuits and Systems (ISCAS), pp.1-5, 2019.

[12] G.W. Dueck, A. Pathak, M.M. Rahman, A. Shukla, and A. Banerjee, “Optimization of circuits for IBM’s five-qubit quantum computers,” CoRR, vol.abs/1810.00129, 2018.

[13] A. Zulehner and R. Wille, “Compiling SU(4) quantum circuits to IBM QX architectures,” Proceedings of the 24th Asia and South Pacific Design Automation Conference, ASPDAC ’19, New York, NY, USA, pp.185-190, ACM, 2019.

[14] A. Paler, I. Polian, K. Nemoto, and S.J. Devitt, “A fully fault-tolerant representation of quantum circuits,” Reversible Computation, ed. J. Krivine and J.B. Stefani, Cham, pp.139-154, Springer International Publishing, 2015.

[15] M. Lukac, S. Nursultan, G. Krylov, and O. Keszöcze, “Geometric refactoring of quantum and reversible circuits: Quantum layout,” 23rd Euromicro Conference on Digital System Design, DSD 2020, Kranj, Slovenia, pp.428-435, IEEE, Aug. 2020.

[16] J. Koch, T.M. Yu, J. Gambetta, A.A. Houck, D.I. Schuster, J. Majer, A. Blais, M.H. Devoret, S.M. Girvin, and R.J. Schoelkopf, “Charge-insensitive qubit design derived from the cooper pair box,” Phys. Rev. A, vol.76, no.4, p.042319, Oct. 2007.

[17] J.A. Schreier, A.A. Houck, J. Koch, D.I. Schuster, B.R. Johnson, J.M. Chow, J.M. Gambetta, J. Majer, L. Frunzio, M.H. Devoret, S.M. Girvin, and R.J. Schoelkopf, “Suppressing charge noise decoherence in superconducting charge qubits,” Phys. Rev. B, vol.77, no.18, p.180502, May 2008.

[18] C. Rigetti, J.M. Gambetta, S. Poletto, B.L.T. Plourde, J.M. Chow, A.D. Córcoles, J.A. Smolin, S.T. Merkel, J.R. Rozen, G.A. Keefe, M.B. Rothwell, M.B. Ketchen, and M. Steffen, “Superconducting qubit in a waveguide cavity with a coherence time approaching 0.1 ms,” Phys. Rev. B, vol.86, no.10, p.100506, Sept. 2012.

[19] A. Zulehner, A. Paler, and R. Wille, “An efficient methodology for mapping quantum circuits to the IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.38, no.7, pp.1226-1236, 2019.

[20] A. Kole, S. Hillmich, K. Datta, R. Wille, and I. Sengupta, “Improved mapping of quantum circuits to IBM QX architectures,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.39, no.10, pp.2375-2383, 2020.

[21] Y. Nam, N.J. Ross, Y. Su, A.M. Childs, and D. Maslov, “Automated optimization of large quantum circuits with continuous parameters,” npj Quantum Information, vol.4, no.1, p.23, May 2018.

[22] T. Itoko, R. Raymond, T. Imamichi, and A. Matsuo, “Optimization of quantum circuit mapping using gate transformation and commutation,” Integration, vol.70, pp.43-50, 2020.

[23] A. Paler, L. Sasu, A.-C. Florea, and R. Andonie, “Machine learning optimization of quantum circuit layouts,” ACM Transactions on Quantum Computing, vol.4, no.2, pp.1-25, Feb. 2023.

[24] C.P. Williams and A.G. Gray, “Automated design of quantum circuits,” Quantum Computing and Quantum Communications, ed. C.P. Williams, Berlin, Heidelberg, pp.113-125, Springer Berlin Heidelberg, 1999.

[25] F.Z. Hadjam and C. Moraga, “Rimep2: Evolutionary design of reversible digital circuits,” ACM J. Emerg. Technol. Comput. Syst., vol.11, no.3, pp.27:1-27:23, 2014.

[26] G. Krylov and M. Lukac, “Quantum encoded quantum evolutionary algorithm for the design of quantum circuits,” Proceedings of the 16th ACM International Conference on Computing Frontiers, CF ’19, New York, NY, USA, pp.220-225, Association for Computing Machinery, 2019.

[27] C. Moraga, “Hybrid GF(2) - boolean expressions ..for quantum computing circuits,” International Workshop on Reversible Computation, 2011.

[28] F.S. Khan and M. Perkowski, “Synthesis of multi-qudit hybrid and d-valued quantum logic circuits by decomposition,” Theoretical Computer Science, vol.367, no.3, pp.336-346, 2006.

[29] D.M. Miller, D. Maslov, and G.W. Dueck, “A transformation based algorithm for reversible logic synthesis,” Proceedings of the 40th Annual Design Automation Conference, DAC ’03, New York, NY, USA, pp.318-323, Association for Computing Machinery, 2003.

[30] W. Hattori and S. Yamashita, “Mapping a quantum circuit to 2D nearest neighbor architecture by changing the gate order,” IEICE Transactions on Information and Systems, vol.E102-D, no.11, pp.2127-2134, 2019.

[31] R. Wille, S. Hillmich, and L. Burgholzer, “Decision diagrams for quantum computing,” Design Automation of Quantum Computers, pp.1-23, Springer International Publishing, Aug. 2022.

[32] C.D. Wilen, S. Abdullah, N.A. Kurinsky, C. Stanford, L. Cardani, G. D’Imperio, C. Tomei, L. Faoro, L.B. Ioffe, C.H. Liu, A. Opremcak, B.G. Christensen, J.L. DuBois, and R. McDermott, “Correlated charge noise and relaxation errors in superconducting qubits,” Nature, vol.594, no.7863, pp.369-373, June 2021.

[33] A. Agarwal, L.P. Lindoy, D. Lall, F. Jamet, and I. Rungger, “Modelling non-markovian noise in driven superconducting qubits,” vol.9, no.3, 2023.

[34] R. Wille, D. Große, L. Teuber, G.W. Dueck, and R. Drechsler, “RevLib: An online resource for reversible functions and reversible circuits,” Int’l Symp. on Multi-Valued Logic, pp.220-225, 2008. RevLib is available at http://www.revlib.org

[35] C.C. Moran, Mastering Quantum Computing with IBM QX: Explore the world of quantum computing using the Quantum Composer and Qiskit, Packt Publishing Ltd, 2019.

[36] M. Lukac, M. Perkowski, H. Goi, M. Pivtoraiko, C.H. Yu, K. Chung, H. Jeech, B.G. Kim, and Y.D. Kim, “Evolutionary approach to quantum and reversible circuits synthesis,” Artificial Intelligence Review, vol.20, no.3, pp.361-417, Dec. 2003.

Authors

Martin LUKAC
  Hiroshima City University

Saadat NURSULTAN
  Nazrbayev University

Georgiy KRYLOV
  University of New Brunswick

Oliver KESZOCZE
  Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU)

Abilmansur RAKHMETTULAYEV
  Nazarbayev Intellectual School

Michitaka KAMEYAMA
  Tohoku University

Keyword

quantum circuits,  qubuit layout,  graph algorithms