{'fraction_non_alphanumeric': 0.029779869567970282, 'fraction_numerical': 0.009898482514087925, 'mean_word_length': 4.571075837742504, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Qubit Mapping Toward Quantum Advantage

Qubit Mapping is a pivotal stage in quantum compilation flow. Its goal is to convert logical circuits into physical circuits so that a quantum algorithm can be executed on real-world non-fully connected quantum devices. Qubit Mapping techniques nowadays still lack the key to quantum advantage, scalability. Several studies have proved that at least thousands of logical qubits are required to achieve quantum computational advantage. However, to our best knowledge, there is no previous research with the ability to solve the qubit mapping problem with the necessary number of qubits for quantum advantage in a reasonable time. In this work, we provide the first qubit mapping framework with the scalability to achieve quantum advantage while accomplishing a fairly good performance. The framework also boasts its flexibility for quantum circuits of different characteristics. Experimental results show that the proposed mapping method outperforms the state-of-the-art methods on quantum circuit benchmarks by improving over 5% of the cost complexity in one-tenth of the program running time. Moreover, we demonstrate the scalability of our method by accomplishing mapping of an 11,969-qubit Quantum Fourier Transform within five hours.


Introduction
Research in quantum information processing has been flourishing for years. The established quantum algorithms or methods have covered various important technical areas [18], such as Quantum Computing [2], Quantum Communication [11], Quantum Cryptography [8], and Quantum Machine Learning [5]. However, these theories were only on paper. Fortunately, some technology companies (e.g. IBM and Google) have recently implemented and even scaled up noisy intermediate-scale quantum (NISQ) machines, thus igniting hope for implementing those quantum algorithms. In 2021, IBM unveiled the IBM Washington, a 127-bit machine, and their more ambitious goal is to launch a 1,121-bit machine by 2023. As the number of qubits in NISQ machines are expected to grow rapidly, building a sound quantum compiler for efficiently executing quantum algorithms on a real quantum device has become an important issue. Moreover, most quantum algorithms are only advantageous when the number of qubits is large, which makes the scalability with respect to the number of qubits a significant matter. Taking the RSA-1024 for example, we would need at least 2048 bits for the Quantum Fourier Transform (QFT) to break the encryption [25]. Quantum algorithm for discrete logarithms over elliptic curves such as Curve25519, which is used in Bitcoin encryption, needs 255 × 6 qubits [20]. Breaking the NIST Standard P-256 requires 255 × 9 qubits [21]. Hence, we can justify that the scalability of a quantum compiler is extremely substantial for achieving quantum computational advantage.
The general procedure for compiling quantum programs is divided into two stages [29]. In the first stage, the quantum algorithm is synthesized as a logical circuit consisting of a universal set. A common universal set contains ( ), a control-not gate with a control bit and a target bit, and , a unitary gate that rotates the quantum bits. In a logical circuit, there are no coupling constraints between qubits, i.e., all logical qubits can interact directly with one another. However, a severe issue is that contrary to the assumption of logical circuits (direct interaction with no coupling constraints), NISQ devices have a limited number of neighboring bits, see Fig. 1. Besides, in notable quantum algorithms such as Shor's algorithm [25] and QFT, every qubit will need to interact with all others, which manifests the importance of bridging the gap between logical circuits and physical devices. Therefore, to perform those algorithms on NISQ hardware, a second stage mapping must be applied to the logical circuits, which is our main focus. Hence, an efficient and scalable qubit mapping is essential to achieving quantum advantage on a non-fully connected quantum device.
Qubit mapping has several objectives, such as execution time and number of gates. The objectives are primarily to maintain the fidelity of the circuit. The fidelity of quantum algorithms is still fragile during execution in state-of-the-art technologies. Thus, quantum noise and experiment errors during computation or preparation should be tackled. In order to reduce those errors, the number of gates and the computation time would both need to be minimized [3,12,26]. In this work, our main focus is to minimize the execution time with parallelism [14].
This mapping procedure has been shown to be an NP-Complete problem [27]. Unfortunately, the scale of quantum algorithms should be large enough to beat classical algorithms, making qubit mapping a challenging problem on a large-scale quantum device. Early works minimized the numbers of additional SWAP gates by considering the Linear nearest neighbor (LNN) structures [7,15,16,[22][23][24]28]. Still, the following works modeled the mapping issues into mathematical problems and utilized solvers to obtain feasible results [6]. However, those approaches are not scalable. Namely, while these studies perform well on a small scale, when it comes to large-scale problems, the lengthy program execution time makes these methods impractical. On the other hand, some research obtained the result by heuristic search. However, most of them listed above considered devices with ideal 1D or 2D lattice structure, which has the least coupling issues compared to the real-world NISQ devices.
As IBM Qiskit (IBMQ) rapidly provided and scaled up NISQ devices, more research turned to focus on complex coupling constraints for IBMQ machines. In the early days of this field, the number of additional gates and circuit depth were considered. Siraichi et al. [27] presented the first ever work that considered the mapping problem for real-world superconducting devices. Zulehner et al. [30] next proposed an A* search algorithm to cope with this problem. Li et al. [14] proposed SABRE 1 by heuristic of shortest path cost and look-ahead technique. SABRE outperforms both two previous works and becomes a general baseline for circuit depth. However, in reality, the circuit depth is not precise enough. Deng et al. [9] proposed CODAR 2 specifically for the total circuit execution time. They first introduced the concept of lock time for the busy qubits. In addition, they proposed different time costs for common gates. Single qubit gates, double qubits gates and swap gates were assigned 1, 2 and 6 units, respectively. Zhang et al. further proposed Time Optimal Qubit Mapping (TOQM) [29] and gave a heuristic with algorithm estimated cost to achieve better results for circuit execution time. These works mentioned above deal 1 SWAP-based BidiREctional heuristic search algorithm 2 COntext-sensitive and Duration-Aware Remapping algorithm with the time complexity associated with gates; nevertheless, the time complexity of the algorithms that minimize the circuit execution time is still not fast enough in terms of the size of qubits. That is, the scalability concerning the size of physical qubits for the above-mentioned approaches still remains an issue. To sum up, previous work only dealt with the mapping problem with at most 50 qubits, which is much lower than the numbers required for quantum advantages, say a thousand qubits.
In this study, we propose a novel SWAP-insertion-based framework aiming the qubit mapping problem. The framework has an unprecedented scalability to deal with over 10,000 qubits, while accomplishing a fairly good performance at the same time. The framework, which consists of Placer, Scheduler, and Router, is flexible to different kinds of quantum circuit characteristics. The routing algorithm, Duostra, in the framework is not only proved to achieve local optimality but also efficient. Our method outperforms the IBM Qiskit Mapping on 127-qubit QFT by 33%, and ours can scale up to the problem size of 11,969 qibots within 5 hours (with time complexity ( 2.8 ), where represents the problem size). In the benchmark proposed by SABRE [14], our scheduler not only achieved average 5% cost improvement rate compared with the state-of-the-art TOQM [29], but also in much less runtime, i.e. one eighth of TOQM runtime. As a result, our proposed qubit mapping framework provides a solution toward quantum advantage via bridging the gap of efficiently implementing ideal quantum algorithms on a non-fully-connected quantum device. This paper is organized as follows. The background and related works are introduced in Section 2 and 3, respectively. The proposed framework is detailed in Section 4. We also list the experiment results in Section 5, including scalability, performance and flexibility. We conclude the paper in Section 6.

Gate Sets in Quantum Circuit
The basic quantum gates can be split into two groups, single qubit gates and double qubit gates. The general form of a single qubit gate can be written as while common single-qubit gates are listed as and the notable group of double-qubits gate is control-, with its normal form to be The control-U family has a control bit and a target qubit. When the control bit is 1, the unitary would be applied on the target qubit. The most common gate of control-family is ( ).
We say that a gate set is universal if we can construct any arbitrary state by applying a finite sequence of gates from the set. One of the universal set contains , , and .

Quantum Computers
Global technology giants such as Google, Microsoft, Intel, and IBM are developing their own quantum computer hardware and software with the ultimate goal of creating a worldclass quantum computer. Currently, quantum computers are in the NISQ generation. In this generation, the leading quantum processors are about a few hundred physical qubits but are not yet fault-tolerant or large enough to profit from quantum superiority [19]. The leading company IBMQ has introduced a 127-bit machine ibmq_washington [1], with its machine topology shown in Fig. 1. In the topology, a circle represents a physical qubit, and this qubit can only interact with the other qubits which share an edge with it. For the IBMQ devices, the universal gate set for running on the device is composed of , , ( ), , and , with being the only two-qubit gate.

Qubit Mapping
As shown in Fig. 1, the topology of a physical device has a finite number of adjacent qubits, violating the assumption in the synthesis phase that there are no coupling constraints. Therefore, in the second step of the compilation process, the purpose of qubit mapping is to convert the logical circuit without coupling constraints into a version with coupling constraints so that the circuit can be operated on a physical device. There are two inputs to the quantum circuit mapping process: the logical circuit and the topology of a physical device; then, we expect to obtain an output: a circuit that can be operated directly on the physical device.

SWAP Gate.
A common solution to the qubit mapping problems is to insert additional SWAP gates. A SWAP is composed of three consecutive s, where the middle with the opposite control and target bit. SWAP gates can swap qubit states. Hence, by inserting the additional SWAP  gates, we can transfer logical qubits from the current physical qubits to target physical qubits, where they can interact with their targets.
In the mapping flow, we add SWAPs to move the qubits only when mapping two-qubit gates, i.e. CX, since singlequbit gates would not violate the coupling constraints.

Dependency
Graph. If a gate operates on qubits 0 and 1 , it can only be executed after the previous gates containing 0 and 1 are all executed. We say that the gate depends on the previous gates. We can build a dependency graph of the quantum algorithm according to these dependencies between the gates.
A dependency graph is a directed acyclic graph (DAG) of operation dependencies with each edge showing the dependency between different operations. An edge → means that depends on . A gate can be executed only after all its parents are executed.

Device
Graph. The topology of a real-world device can be described by an undirected graph = ( , ), where denotes the physical qubits and is the set of edges representing the connectivity between physical qubits. A pair of qubits can be involved in the same operation only if there is a connection between the two qubits. In the qubit mapping problem, we see the physical qubits as carriers of the logical qubits of a quantum algorithm. When we apply a swap gate on a pair of qubits, we swap the logical qubits they carry.

Waitlist.
Inspired by the "front layer" concept from [14], the waitlist is the set of gates without any unexecuted parents. The gates should be executed following the dependency graph, indicating that a gate can only be executed if it is in the waitlist. In other words, the waitlist provides a solution space for selecting which gate to be executed.

Objectives.
The main objective of qubit mapping is to minimize error. There are many factors that cause error, including operation time, number of operations, and depth of qubit information. In this work, we aim to minimize the operation time in the qubit mapping process.

RELATED WORK
In this section, we listed some notable existing works of qubit mapping which focused on IBMQ machines chronologically.

Qubit Allocation [27]
Siraichi et al. proposed the first-ever work, which considered the IBMQ machines. They defined the qubit mapping problem in this scenario and introduced the concept of the coupling graph. To further discuss the qubit mapping problem on real-world devices in the NISQ era, they proved this problem to be NP-Complete, and proposed an exact but exhausted computation for obtaining the best solution, which was based on the squared qubit factorial of time complexity, (( !) 2 ).
To give a practical solution, they also proposed a heuristic search within the order of qubits dependency graph. A CX gate with control and target on 0 and 1 , respectively, would generate an edge starting from 0 and ending at 1 in the qubits dependency graph. The initial mapping was given according to matching results of logical qubit out degrees and physical qubit connectivity. In the mapping phase, Siraichi et al. coped with the double-qubit gates by finding the shortest path between their two qubits (control and target) and moved them by three approaches, swap, reversal, and bridge. Although this result is not guaranteed in terms of quality, it is the first to pay attention to the constraints of an NISQ machine.

Efficient Mapping of Quantum Circuits to the IBM QX Architectures [30]
Zulehner et al. proposed a heuristic based on the depth-based partitioning along with the A* search algorithm. They introduced a layer formed by all gates that could be applied concurrently. The procedure tried to find the mapping between two consecutive layers. The mapping procedure was determined by A* search by the shortest path, which was claimed to have optimal cost on the numbers of additional swap gates. They also proposed a look-head method, which incorporates the cost of the next layers, albeit sacrificing some optimality. They achieved an acceptable result; nevertheless, the partitioning used in their work may raise some problems. Unlike most classical circuits, many quantum algorithms or circuits, such as Shor's algorithm or QFT, require each signal to interact with all the others, turning the problem into a complete graph. Partitioning or slicing in such cases will lead to situations where there is only a single gate in one layer, thus weakening the strength of concurrent gates partition.

SABRE [14]
Li et al. proposed a SABRE algorithm. SABRE is based on a heuristic search based on the LNN cost, with linear complexity toward numbers of physical qubits (machine bits). They pointed out that, in the NISQ era, qubit lifetime and operation fidelity should be taken into consideration while mapping. For qubit lifetime, the circuit depth was considered. For fidelity, Li et al. wished to minimize the numbers of operations (gates) in the circuit.
To meet the above two conditions, they designed the SABRE algorithm. In the preprocessing stage, they computed All-Pairs-Shortest-Path (APSP) by the Floyd-Warshall Algorithm to obtain the shortest path between arbitrary two qubits on quantum devices. Also, the dependency graph, a Directly-Acyclic-Graph (DAG) on gates, was generated. The temporary initial mapping was generated randomly. Since the quantum circuit was reversible, they claimed that after the mapping result was done, the revised initial mapping could be generated by reversing the sequence of gates and starting the whole procedure from the final mapping. Iteratively doing the cycle would get a better initial mapping.
In the main flow, they also inserted swap gates by considering the layers mentioned in section 3.2. SABRE found the best candidate of swap insertion by the heuristic cost. The base cost was calculated by summation of the "remaining" number of swap gates in a layer after a specific swap gate was applied by APSP. The decay factor targeting reduces the circuit depth, and look-ahead layer were also considered to form the final cost. The solution of inserting a swap determined by the final cost. The result they proposed has been set as one of the notable baselines. However, SABRE was not suitable for rapidly scaled-up devices since iteratively computing all the costs of swap candidates in each step is time-consuming.

CODAR [9]
Deng et al. proposed a CODAR algorithm. In their research, they first introduced Multi-architecture Adaptive Quantum Abstract Machine (maQAM), which was a model that considered coupling graph with limited qubit connectivity and configurable durations of different qubit gates. The most novel concept was lock time of qubits, which handled the duration problem. A qubit should be locked when it is doing operation, and free while finished.
In CODAR, the executable gates formed a sequence. A swap could only be applied on two adjacent qubits if both of them were not locked. The heuristic cost function would decide where to add the swap. The cost of each potential candidate was calculated by the total differential distances when applied the swap. CODAR was the first work to detailly optimize the execution time on quantum circuits and also gave a common settings of durations, 1, 2, and 6 for single qubit gates, double qubit gates, and swap gates, respectively.

Time Optimal Qubit Mapping [29]
Zhang et al. presented the theoretically proved time-optimal SWAP insertion solution on mapping issues. They spotlight on the importance of time optimal rather than gate optimal, i.e. minimizing the execution time rather than additional gates. To fulfill the optimal result, they provided an scheduler based on coupling and dependency constraints, along with the cost formed by the minimum finished time of gates.
The coupling and dependency constraints were generated in preprocessing stage. For the framework, Zhang et al. introduced a node to represent the status of the circuit. The root node was the initial of logical circuit, where each qubit was not operated by any gate. A node could be expanded into children nodes. The children nodes, which were the search space, contained all possible circuit transformations after adding reasonable swap gates or following gates in the logical circuit. The process of this work was a loop. The candidate nodes would be extracted by priority queue, then expanding nodes for constructing the tree (finding possible children) with the three conditions considered, coupling constraint, dependency constraint, and redundancy elimination. The children would be pushed into the queue with their cost.
The cost was claimed admissible, which was formed by the time stamps from the root to the children node and a heuristic estimation. The heuristic was calculated by the remaining gates of the circuit, which followed the dependency graph iteratively and considered the ready time of the gate and execution time. The final heuristic cost was finished

THE PROPOSED FRAMEWORK
To tackle the main difficulty of scalability of qubit mapping, the underlying search space of a qubit mapping should be reduced. Unlike previous studies which treat the qubit mapping problem as a whole, we propose a framework that decomposes the problem into more manageable subproblems, placement, routing, and scheduling. From the beginning of the framework, a placer places the logical qubits onto the physical qubits. Then, the framework utilizes a router to find combinations of swap gates on the real-world device for operations/gates to be executable. A scheduler schedules the order of the gates that are assigned to the router. This framework can drastically reduce the search space. Unlike previous studies, the scheduler now has to only schedule the order of the gates assigned to the router instead of scheduling all the possibilities that can be operated on a real device. The required SWAP gates to handle the coupling constraint are now handled by routing algorithms, which are extremely efficient and well-developed, meaning that the quality of the solution is guaranteed. By designing proper placers, schedulers, and routers, the proposed framework can achieve great scalability without sacrificing too much solution quality. The framework also boasts flexibility. Users can choose their own combination of placer, scheduler, and router depending on what quantum circuits they are dealing with and the tradeoff between different metrics. Below we designed different kinds of algorithms for initial placement, scheduling, and routing.  Figure 3. Our framework of qubit mapping.

Initial Placement
We provide two heuristic placements, the static placement and the depth-first search (DFS) placement. The static placement will assign the index of logical qubits to the physical qubits with the same index. Second, the DFS placement assigns the logical qubits from the first physical qubit reached by DFS to the last. The DFS starts from an arbitrary physical qubit until tracing throught all the physical qubit on the device. The DFS placement makes each two input qubits required by the gates rather closer.

Routing: Duostra (Dual-source Dijkstra)
To solve the routing problem, we introduce a novel algorithm, Duostra (Dual-source Dijkstra) algorithm. The Duostra algorithm outputs a solution of SWAP sequence and calculates the finish time of the sequence; see 4.2.2 for the detailed calculation of the cost. Then the gate can be executed on a real-world device with the solution. We prove that the output of the algorithm is optimal in terms of minimizing the finish time given a gate on the dependency graph and a real device. We will also show that the time complexity of this algorithm is ( lg ), where is the number of qubits of the device.

Occupation.
We use the concept introduced by [9]. When a physical qubit is involved in an operation (e.g. SWAP, CX, etc), it is occupied by the operation. We can assign occupations to physical qubits according to the operations. If an operation is executed from 0 to 1 on a physical qubit , we have . = 1 , which means that the qubit cannot be assigned to another operation until 1 .

SWAP routing path.
Applying a SWAP gate to a pair of adjacent physical qubits will swap the logical qubits they carry. If we want to move the logical qubit from 0 to 3 in Fig. 4, we can apply a sequence of swap gates to swap the logical qubit. The sequence forms a routing path for the topological qubit from 0 to 3 . Assuming a swap path between starting qubit and terminating qubit has − 1 physical qubits, we have The cost of a swap gate, , is the finish time of the swap operation, which is calculated by where 0 . , 1 . and represent the occupation time of 0 , occupation time of 1 , and the duration of a swap gate. The maximum term represents the earliest possible start time of the swap gate. The cost is the end time of the swap gate. With equation (2), we can iteratively calculate the cost of each swap gate in a routing path as Note that the occupation of qubits will be updated through the calculation of the routing path. The cost of the last swap gate in the sequence is the final cost, i.e. finish time, of the routing path, which is For ℎ( 0 , 3 ), the routing path and the costs of the swap gates can be calculated as shown in Fig. 4 (c).

Concept of Duostra.
If two logical qubits on two physical qubits, 0 and 3 , see Fig. 4 for example, need to be executed but they are not connected by an edge on the realworld device, they should be swapped to a pair of adjacent physical qubits. Since operations on a quantum processor can be executed in parallel, the best strategy for finding a swap combination that minimizes total execution time is to swap the qubits closer to each other simultaneously. For instance, as illustrated in Fig. 4, if we want to execute a gate consisting of logical qubits on 0 and 3 , the best strategy is to swap the logical qubit on 0 to 1 and the one on 3 to 2 . However, how to find the best routing path to swap the qubits is the key point. Our mission is to find a pair of adjacent physical qubits such that we can swap our target qubits to the position in the shortest time possible. To achieve that, we borrow the concept of Dijkstra's algorithm [10]. Dijkstra's algorithm is a classic algorithm for finding a shortest-path tree from source . If two separate shortest-path trees were built from both 0 and 1 on the device graph, we can find a pair of adjacent vertices, 0 and 1 , such that the cost 0 to 0 and the cost 1 to 1 are minimal, as shown in Fig. 4 (c) and (d).
Also, the shortest-path trees can indicate the two separate routing paths ℎ( 0 , 0 ) and ℎ( 1 , 1 ). However, we do not have to build the whole shortest-path trees on the graph. First, the two trees can be generated by the same priority queue. The cost of a vertex in 0 's shortest-path tree is the cost of the routing path from 0 to . In Dijkstra's algorithm, the priority queue outputs the vertex with the minimal distance from the source. In this work, we design a priority queue to output the earliest qubit that can be applied with a swap gate. The costs, which are the finish times of the last swap operations on the routing paths, are general across two   For two initial sources 0 on physical qubit 0 and 1 on physical 3 , the Duostra algorithm will get the minimum cost blue edge 1 2 by the detailed procedure shows in (c) and (d), implicating the best routing path of 0 is 0 to 1 and path of 1 is 3 to 2 . We need a SWAP gate operate on 0 1 and another one on 3 2 . (c) The shortest path tree starts from source 0 . By equation (3), we can calculate cost of each node. (d) The shortest path tree starts from source 1 .
trees. Therefore, the same priority queue can be shared in the processes of both trees.
Second, the cost of a vertex does not change once the vertex is pushed into the priority queue. Thus, we can grow the two trees of 0 and 1 step by step by extracting the outputs of the same priority queue. The process terminates when the two trees meet each other at a pair of adjacent physical qubits. The routing paths from the two trees form the optimal sequence of swap gates in terms of the earliest finish time of this operation because the priority always outputs the earliest possible qubit to be swapped. If there exists another sequence that can be finished earlier, Dijkstra's algorithm can definitely find that better sequence earlier than the current sequence. See Appendix A for a proof.

Algorithm.
First, we initialize a priority queue, , and mark all ∈ as unseen and unvisited. After that, we set 0 and 1 as seen and visited. Then we put all the adjacent vertices of 0 and 1 into with the cost described by Eq. Visit( ) ⊲ Mark as visited 8: if there exists a visited neighbor s.t. . ℎ ≠ . ℎ then 9: ℎ 0 ← backtrace( ) 10: end if 13: putUnseenNeighbor( , , . ℎ) 14: end while 15: end procedure and mark them as seen and the path they are from. If a vertex is adjacent to 0 , then it is marked as ℎ 0 . We iteratively take the vertex with the lowest cost, , out from until is empty. When we take out, we mark as visited. If we find that one of the adjacent vertices of is visited and marked as a different path as , we trace back the routing path separately from and . Else, we mark all the unseen for ∈ Neighbor( ) and . do 3: . ℎ = 4: end for 6: end procedure 7: procedure nodeWithLowestCost( ) 8: return .pop() 9: end procedure adjacent vertices of as seen, push them into , and start the next iteration. The two paths of the traceback result are ℎ( 0 , * 0 ) and ℎ( 1 , * 1 ).

Scheduling
The goal of the scheduler is to optimize the objective by correctly assigning the sequence of gates to be routed. However, the order should follow the dependency graph (all gates should be executed after their parents). Since the gates are assigned one by one according to the Duostra algorithm, a waitlist is used to store all available gates. Therefore, the scheduler has to pick one gate from the waitlist at a time for the router to solve the gate. The design of the scheduler has two advantages: First, unlike previous studies who have to schedule all the executions on the physical device, our scheduler only has to schedule the order of the ready logical gates. Second, various strategies can be applied to guide the scheduler to pick the gate in the waitlist.
To describe the cost, we define which represents cost accumulated from step = + 1 to for trajectory , while is the cost at an integer step . We defined the trajectory as one of a legal permutation of gate sequence. Inspired by the A* search, we define the heuristic cost of scheduler Eq. (7) utilizes maximum operator instead of addition in traditional A* search for two purposes. First, The scheduler has to take the parallelism of the physical devices into consideration, which implies that the "later" scheduled gates in the waitlist may not necessarily be executed later than "previous" scheduled gates while running the real circuit. Second, we apply the greedy strategy here to pick the fastest possibly finished gate every time, not necessarily being the best operation since picking the real best operations each time may take too much computation. For the heuristic term ℎ( ), we introduce two different cost function as follows.
The scheduler will select the smallest ℎ( ) and route the corresponding gate.

Duostra Search.
The idea of Duostra is to find the best solution under the framework. By enumerating and routing all possible gate sequences following the dependency graph, the optimal solution in the search space of the framework can be achieved, thus leading to an acceptable global result. However, going through all the possibilities has been proved to be NP-Complete, which is not feasible in practical large-scale cases. Therefore, a better way is to limit the search depth of each decision. That is, a gate in the waitlist is picked by the scheduler based on the routing results of the next gates, where is the depth given by the user. With this concept, we defined heuristic cost Eq. (9) indicates that the heuristic would select the smallest cost of gate sequence with length being depth . If the depth equals 2, the heuristic first pre-executes all gates the in waitlist and update the corresponding states. Subsequently, the heuristic expands all possible second choices to get the costs and select the smallest one. As the result, the scheduler will execute the gate with the smallest size-2 sequences. If the depth is 1, we have min : +1 .

SP Estimation.
The main goal of SP Estimation is to generate a fast reference value for the scheduler. Each gate within the waitlist is associated with an SP cost by ( 0 , 1 ). The scheduler greedily picks the one with the lowest cost in each step.
SP is a simplification of Duostra. Ideally, if we apply the iteration Eq. (3) without considering any occupation , the cost is positive related to the routing path distance (multiplication of ). Therefore, we model this term by considering the shortest path problem between control qubits and target qubits. For the shortest path problem, Lao et al. [13] proposed a scheduler with cost based on a breadth-first search (BFS). The BFS procedure focuses on logical circuits. The procedure finds the cost of each gate by doing BFS from the physical qubit on device that carries the source qubit to the physical qubit that carries the target qubit. However, this BFS procedure will face a problem that in each sub-routine, the SWAPs will lead to movement of logical qubits. Therefore, after executing Duostra in our framework, we should recalculate the cost of each gate within the waitlist. In the waitlist, the number of gates is ( ), and we have to do ( ) Duostra iterations. To summarize, the total time complexity will become ( 2 ).
Therefore, to reduce the time complexity, we were inspired by Li et al. [14], who focused on the device graph. Since the logical qubits are not fixed, we turn to the fixed physical qubits. In this case, all path shortest paths only needed to be calculated once and stored in the lookup table from the start of the program. Therefore, the swapping cost of each gate here is calculated by finding the SP result of the two physical qubits that carry the two logical qubits. With the Floyd-Warshall Algorithm, we can implement the APSP in ( 3 ). For reasonable quantum circuits with > , the time complexity of the APSP is much smaller than the BFS-based solution.
To sum up, the heuristic function in SP Estimation is written by where is a gate in the waitlist, 0 , 1 are two physical qubits of the gate if the gate is a double-qubit gate. For single-qubit gates, the SP cost is 0. The first term retains the occupation information, while the second is the simplification of duostra path cost. The time complexity of the SP Estimation is ( ( + )), where is the number of gates in the waitlist and is the time complexity of the router. Compared with the scheduler guided by Duostra search, whose main focus is on optimizing the performance, the SP Estimation method trades some performance for better scalability.

EXPERIMENT
In this section, we conducted experiments to show our algorithm's three aspects, scalability, performance, and flexibility. First, in scalability, we enlarged the mapping problem up to 11,969 qubits, which is large enough to achieve quantum advantages (over 1,000 qubits). Our algorithm could finish the mapping of 11,969 qubit QFT in a short time (4h57m30s). Also, both the cost complexity and the running time complexity are less than ( 3 lg ), which ensured that our algorithm had the scalability as the qubit number increases so as to achieve quantum advantages. Second, we compared the cost of our results with that of the state-of-the-art mapping schemes to ensure that our proposed qubit mapping could achieve superior results. In particular, our AP Estimation method proposed up to 33% improvement compared with the IBM Qiskit Mapping [4] on 127 qubit QFT. On the other hand, our Duostra Search method had a 5% improvement in average compared with the Time Optimal Qubit Mapping (TOQM) [29] on the small quantum circuit benchmarks provided by SABRE [14]. Finally, as for flexibility, we involved some large Oracle circuits from classical Electronic Design Automation (EDA), indicating that our algorithm had the flexibility not only for specific QFT circuits but also for other Oracle circuits. Also, our algorithm could offer flexibility for different sizes of quantum circuits by choosing different schedule methods.
The cost computation followed the discoveries in CO-DAR [9] and computation from TOQM [29], that the execution time of single-qubit gates, double-qubit gates (CX), and SWAP gates were 1, 2, and 6, respectively. As for Ratio, we defined it as / , where Ideal represents performing circuits on the fully-connected ideal devices, indicating no SWAPs were needed to be added. We performed the experiments on Intel ® Xeon ® CPU E5-2630 v4 @ 2.20GHz with total 126G memory.

Scalability
We managed to investigate the scalability of the proposed mapping methods toward quantum advantages, in which the problem sizes should be at least 1,000 qubits. We chose QFT, which can be easily scaled up and is also regarded as one of the most difficult task sets, to examine the scalability of our method. Since each qubit interacts with all the other qubits in QFT circuits, the interaction graph of QFT is a complete graph. The QFT circuits were generated following the method proposed in [18]. Due to the limitation of basic gate set on IBMQ machines, we decomposed all CR and H gates in the circuit. For the devices, since the largest released IBMQ machine, _ ℎ , contains only 127 qubits, we followed the regular pattern and magnified the device graph to 11,969 qubits to enlarge our investigation of scalability.
We compared the scalability on three different methods, state-of-the-art TOQM 3 [29], our Duostra search, and our SP Estimation method. The time limit for the program running Table 3. The comparison between the costs of our SP Estimation scheduler and IBM Qiskit Mapping [4] on QFT circuits. The input QFT logical circuits were generated following [18]. For Only Mapping, before applying two mapping approaches, the and gates in the input circuits were decomposed into gates in the base set in order to satisfy IBMQ device constraints. For With Synthesis, the input circuits were subsequently synthesized by the Qiskit transpiler [4] before applying two mapping approaches.  Table 2, TOQM could only afford a very tiny number of 27 qubits, which was far from the goal of achieving quantum advantages. Compared to TOQM, our scheduler guided by search-based Duostra cost had improvement on both cost and size, which lowered the cost in most small cases and enlarged the scale to almost five times, 127 qubits. Moreover, despite of slightly inferior performance compared with the other two methods, only the quick and less time-consuming SP estimation could generate the mapping result when the scale grew up to a thousand. Still, for the result of 127 and 433 qubits, the Duostra search performed worse than SP estimation in the time limited 4 , proving that SP estimation could give an acceptable result.

#Q
Next, we give the analytical estimation and result and about scheduler guided by SP estimation. With Algorithm 1, the cost complexity should be ( 3 ) since each gate requires ( ) of cost and the number of gates in QFT is ( 2 ). The experiment result indicated that the cost was in the order of 1.3 with respect to the number of qubits. For the theoretical program running time, the time complexity is ( ( lg + )), where and is the number of gates of the dependency graph, and the maximum gates in the waitlist. Therefore, we have the time complexity ( 2 ( lg + )) = ( 3 lg ) for QFT circuits since QFT can only have at most ( ) gates in the waitlist simultaneously. By taking logarithm on numbers of qubit and experiment running time, the linear regression yields 2 = 0.995 with slope 2.83. Therefore, we have the real-time complexity ( 2.8 ). The polynomial order ensured the scalability of our method and finished the mapping of 11,969 qubit QFT in 5 hours (4h57m30s), indicating that our method can clinch the quantum advantage.

Performance
To justify our mapping performance, we compared the qubit mapping cost of our method with the state-of-the-art results in two test sets, the QFTs up to 127 qubits (larger size) and the quantum circuit benchmarks (smaller size) introduced by SABRE [14].

QFT.
We demonstrated two types of comparison with IBM Qiskit [4]: Only Mapping and With Synthesis. In Only Mapping, we directly use the data described in section 5.1. We applied Qiskit Mapping and our mapping methods scheduled according to SP heuristic straightforward on the data. In With Synthesis, we applied the Qiskit synthesis tool on circuits in Only Mapping to generate the input synthesized circuits. The two mapping approaches were subsequently applied on the synthesized circuits. We synthesized the circuits before mapping because synthesis is a normal step in the Qiskit compilation flow. For Qiskit Mapping in both cases, we set the optimized level to 0 in the Qiskit transpiler. For Qiskit Synthesis, we set the optimized level to 2.
As listed in Table 3, although our method (SP Estimation) was inferior to IBM Qiskit on small cases on Only Mapping, it surpassed Qiskit when the problem size grows larger, where the qubit mapping task is more demanding and practical toward quantum advantage. Shortly, our method provided more advantages with increasing qubit numbers. The improvement rates are 33.4% and 8.3% for Only Mapping and With Synthesis, respectively, on _ ℎ machine. Note that due to the greater numbers of sub-routines than numbers of gates, it is reasonable for the Only Mapping set to achieve a better improvement rate.

Quantum Circuit Benchmark.
We take the results of Zhang et al [29] as a baseline, which is state-of-the-art by exhaustive search on the benchmarks. Here, we guided our scheduler by two types of heuristic strategies, Duostra search and SP estimation. Also, to make a fair comparison, the experiment was all conducted on _ , the 16 qubit machine. 5 The results are listed in Table 4. In this table, we reported both results and program running time of the heuristic SP estimation, Duostra search (with depth set to 4), and the baseline from Time Optimal Qubit Mapping (TOQM) [29]. In the SP estimation, although our algorithm provided the cost slightly worse than the baseline (around 6 ∼ 9% in most cases), the program running time achieved a significant 5 In Time Optimal Qubit Mapping, the experiment was conducted on IBM Tokyo architecture. However, this device is no longer provided by IBMQ. Hence, we changed the device to _ and re-ran the source code. speedup. As for Duostra search, we stroke a balance between performance and program running time. As listed in Table 4, the results could be improved 2 ∼ 8% compared to the baseline TOQM and the running time was still slightly faster than the baseline. The result indicated that our searching algorithm based on the Duostra router could perform well within a reasonable time.
In conclusion, dealing with problems of different scales, the scheduler guided with suitable heuristics can produce good mapping results on both larger QFT circuits and smaller benchmarks.

Flexibility
Flexibility is also an indispensable condition in qubit mapping. The flexibility of our method is not only customizing components according to users' needs, but also running on various quantum circuits with quality performance. As mentioned in Section 5.1, Scalability, we would like to examine whether our methods worked on rather large cases other than QFT. Therefore, we simulated the Oracle family by adopting the classical EDA circuits as Oracles. The classical circuits were transformed to XOR-Majority Graph (XMG) by ABC tool [17], followed by performing technology mapping upon quantum circuits, which were the inputs for our experiment. We performed both the results of the scheduler guided by SP estimation and Duostra search with a depth is 1. Also, we compared the cost improvement rate and program running time between these two methods.
As listed in Table 5, we had ratios ranging from 2.94 to 6.40 for these large-scale oracle benchmarks for SP estimation and 2.83 to 5.85 for Duostra search. Since there was no other research for us to make a comparison, we compared the result quality with our experiment of scalability. The QFT with 433 and 1121 qubits were similar to these Oracle benchmarks with respect to the numbers of gates and qubits. As Table 2 indicated, these two QFT cases yielded ratios around 20 with SP estimation, which is much larger than those in Table 5. This showed that our scheduler not only works on QFT Table 5. Results of the oracles transformed from classical EDA circuits to XMG by ABC tool [17]. Our scheduler were guided by SP Estimation (baseline) and Duostra Search respectively. The depth is 1 in Duostra Search. #Gate denotes the number of gates in the transformed oracles. Ideal represents the mapping cost on a fully-connected ideal device. Δ represents the cost improvement rate comparing Duostra Search with SP Estimation, and represents the time improvement (Time /Time circuit, but also has good results on other arbitrary Oracle circuits. Furthermore, as Table 5, Table 4 and Table 2 indicated, the scheduler guided by the Duostra search has a fairly good cost reduction compared to the baseline SP estimation in most cases but with longer programming running time, showing that for these cases, our algorithm has the ability to trade programming running time to a better performance between these two guided methods. The results indicated that our scheduler guided by SP estimation provided a fast qubit mapping method which is more suitable for large cases. On the other hand, Duostra search can achieve a better cost in a longer but tolerable time which is more suitable for small cases. In conclusion, our method has the flexibility to deal with different kinds of circuits and also different sizes of circuits by switching different scheduler guides.

CONCLUSION
In this study, we provided a novel framework to tackle the need of large-scale quantum algorithms aiming for quantum advantage. This is achieved by decomposing the qubit mapping problem into simpler subproblems, placement, routing, and scheduling. With the new schedulers responsible for smaller search space and the proposed router being efficient and locally optimal, the framework can vastly speed up the process of solving the qubit mapping problem while maintaining solution quality. Further, with different schedulers that we proposed, the SP Estimation and Duostra Search scheduler, users can have flexible choices between performance and program running time. Besides, we found that initial placement has little impact on the final execution time.
We used the combination of our framework and Duostra to perform experiments and showed its performance and scalability. The combination outperformed both IBMQ and the prior work on circuit execution time within a considerably shorter program running time spans. Furthermore, the combination can scale up to the large-scale QFT problem with 11969 qubits, which has already far exceeded the scale to achieve quantum advantage. output the vertex with the smallest cost among all unvisited vertices.
In this scenario, the vertices of the two paths formed by the two sources are pushed into the same priority queue. With the property of priority queue demonstrated in Section A, the vertices of two sides would be popped according to the cost. Therefore, the first edge where the two sides meet first has the smallest cost, which would be * .
the two paths in the optimal solution must be found before the path with higher cost in the suboptimal solution due to the optimality of the priority queue. This means that Duostra can always find the optimal solution to the qubit mapping routing problem.