DasAtom: A Divide-and-Shuttle Atom Approach to Quantum Circuit Transformation
Yunqi Huang Dingchao Gao Shenggang Ying Sanjiang Li





DasAtom: A Divide-and-Shuttle Atom Approach to Quantum Circuit Transformation
    Yunqi Huang, Dingchao Gao, Shenggang Ying, and Sanjiang Li^*
        
Yunqi Huang and Sanjiang Li are with Centre for Quantum Software and Information (QSI), Faculty of Engineering and Information Technology, University of Technology Sydney, NSW 2007, Australia. Dingchao Gao and Shenggang Ying are with Institute of Software, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, Beijing, China
Corresponding author (E-mail: Sanjiang.Li@uts.edu.au)

    September 5, 2024
============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================



§ ABSTRACT 
Neutral atom (NA) quantum systems are emerging as a leading platform for quantum computation, offering superior or competitive qubit count and gate fidelity compared to superconducting circuits and ion traps. However, the unique features of NA devices, such as long-range interactions, long qubit coherence time, and the ability to physically move qubits, present distinct challenges for quantum circuit compilation. In this paper, we introduce DasAtom, a novel divide-and-shuttle atom approach designed to optimise quantum circuit transformation for NA devices by leveraging these capabilities. DasAtom partitions circuits into subcircuits, each associated with a qubit mapping that allows all gates within the subcircuit to be directly executed. The algorithm then shuttles atoms to transition seamlessly from one mapping to the next, enhancing both execution efficiency and overall fidelity. For a 30-qubit Quantum Fourier Transform (QFT), DasAtom achieves a 414x improvement in fidelity over the move-based algorithm Enola and a 10.6x improvement over the SWAP-based algorithm Tetris. Notably, this improvement is expected to increase exponentially with the number of qubits, positioning DasAtom as a highly promising solution for scaling quantum computation on NA platforms.


Keywords: neutral atom quantum computing, quantum circuit transformation, divide-and-conquer (DAC), subgraph isomorphism




§ INTRODUCTION


Quantum computing has the potential to revolutionise various fields, including cryptography <cit.>, chemistry <cit.>, and machine learning <cit.>. Among the diverse quantum hardware platforms under development, neutral atom (NA) quantum systems have garnered significant attention due to their inherent advantages in scalability, qubit connectivity, and gate fidelity <cit.>. Unlike other quantum platforms such as superconducting circuits, NA systems can leverage long-range interactions and native multi-qubit gates, which allow for the execution of complex quantum operations with fewer resources. Additionally, the ability to physically move qubits within NA systems introduces a new dimension in quantum circuit optimisation that is not present in more rigid architectures <cit.>.

Despite these advantages, the unique characteristics of NA devices present novel challenges in quantum circuit compilation. Specifically, the need to efficiently map qubits and execute operations while improving overall fidelity is a non-trivial problem. Existing quantum circuit compilation methods, such as SWAP-based <cit.> and move-based <cit.> algorithms, are not fully optimised for the capabilities of NA systems, often leading to suboptimal performance in terms of overall fidelity. 

The SWAP-based method, exemplified by Tetris  <cit.>, employs a fixed-atom array and transforms quantum circuits in a manner similar to compilers for superconducting devices <cit.>. This approach leverages the long-range interactions of NA systems to achieve denser qubit connectivity, which contrasts with state-of-the-art IBM superconducting quantum computers that typically have sparse qubit connections, with an average degree between 2 and 3. Tetris operates as a heuristic greedy algorithm, addressing both qubit connection constraints and parallel execution constraints. 

On the other hand, Enola <cit.>, the most recent and advanced move-based compiler, assumes sufficient separation between atoms to eliminate parallel execution constraints. As <cit.>, Enola exploits gate commutability in QAOA <cit.> circuits, aiming to scheduling gates from a commutation group in near-optimal number of Rydberg stages. For generic quantum circuits like Quantum Fourier Transform (QFT), CZ gates are often blocked by single-qubit gates (cf. Fig. <ref>). Enola executes each layer of CZ gates collectively. 
Empirical results on QFT circuits indicate that the slow atom movement (partially due to the large atom distance) is the primary factor contributing to overall fidelity loss. 


However, even these advanced methods do not fully capitalise on the strengths of the NA platform, particularly the synergistic use of long-range interactions and atom shuttling, which can significantly enhance the efficiency and fidelity of quantum circuit execution. This gap highlights the need for a more comprehensive approach, leading to the development of DasAtom—a divide-and-shuttle atom algorithm specifically designed for NA systems. DasAtom combines the advantages of both Tetris and Enola while avoiding their shortcomings. Tetris effectively uses long-range interactions to enable dense qubit connectivity, but it does not utilise the ability to move atoms, limiting its flexibility. On the other hand, Enola leverages atom shuttling to adapt qubit mappings dynamically, yet it cannot take advantage of long-range interactions as atoms are far apart. DasAtom integrates both of these key capabilities: it partitions circuits into subcircuits, assigns an optimal qubit mapping for each subcircuit, and then shuttles atoms to smoothly transition between mappings. By doing so, it ensures that every gate in a subcircuit is directly executable, thereby enhancing overall fidelity and efficiency. 





We conducted empirical comparisons of DasAtom's performance against Tetris and Enola using the benchmark circuits used in <cit.>. This set of 33 benchmark circuits includes RevLib circuits as well as the quantum circuits Bernstein–Vazirani (BV), Quantum Volume (QV), and QFT, which range from 5 to 16 qubits with up to 3,089 CZ gates. In addition, we evaluated Deutsch-Jozsa (DJ), 3-regular MaxCut QAOA, Greenberger–Horne–Zeilinger (GHZ), QFT,  QV, two-local ansatz, and W-state circuits with qubit counts ranging from 5 to 50. Our experiments demonstrate that DasAtom consistently delivers significant performance gains in both overall fidelity and compiler runtime. 
For instance, DasAtom achieves a 414x improvement in fidelity over Enola and a 10.6x improvement over Tetris in a 30-qubit QFT, while the runtimes of Enola and Tetris are 9851x and 384x longer than DasAtom. Moreover, these improvements are expected to scale exponentially with the number of qubits, making DasAtom a highly promising solution for quantum computation on NA platforms.




The remainder of this paper is organised as follows: Section II provides a brief background and discusses related work. Sections III and IV offer a detailed description of the DasAtom algorithm, including its implementation and a comprehensive performance analysis across various quantum circuits. In Section V, we explain why DasAtom outperforms other algorithms and explore potential avenues for optimisation. The last section concludes the paper.





§ BACKGROUND AND RELATED WORK






 §.§ Neutral atom quantum hardware


In neutral atom quantum hardware, neutral atoms are trapped in arrays of tweezers <cit.> and the computational states |0⟩ and |1⟩ are encoded in the hyperfine ground states of an alkali or alkaline-earth-like atom.  
These atoms can be arranged in one, two, or even three-dimensional configurations <cit.>. In this work, we focus on a b× b regular grid G(b,b) with constant distance d>0. Fig. <ref> shows a 3× 3 grid G(3,3). In the following, we write q,q',q_i for program qubits in a circuit, and write p,p',p_i for nodes or their coordinates in G(b,b). 


Single-qubit gates are implemented through individual or global optical addressing of the atoms, and two-qubit gates are realised by exciting the atoms into a Rydberg state using laser beams.
The excitation to Rydberg states induces a strong dipole-dipole interaction between the atoms <cit.>. 
This interaction is governed by an interaction radius R_int, within which a CZ gate on two atoms p_i, p_j can be performed if the distance D(p_i, p_j) ≤ R_int, where D represents the Euclidean distance. 

One significant advantage of NA platform is its ability for long-range interaction. Two qubits can interact even if they are not neighbours in the grid. For instance, the interaction radius R_int can be r_int× d for 1≤ r_int≤ 3. Qubit connectivity of a quantum architecture is often captured by its architecture graph AG = (V, E), where the nodes in V correspond to the physical qubits (i.e., trapped atoms here), while the edges indicate the qubits capable of interacting with each other. For NA platform, each physical qubit p in V is assigned to the trap coordinates (x,y), and the edges E can be defined as:

    E = {(p_i, p_j) | p_i, p_j ∈ V, D(p_i, p_j) ≤ R_int}.

In the 3× 3 grid shown in Fig. <ref>, the black, red dotted, and blue edges are, respectively, those with distances d,  √(2)d, 2d. 




To minimise crosstalk between gates, parallel gate execution is feasible only if qubits corresponding to different CZ gates maintain a distance of at least the restriction radius R_restr≥ R_int from  all qubits involved in other simultaneously executed two-qubit gates. Specifically, for two CZ gates g on p_i, p_j and g' on p_a, p_b to be executed in parallel, the conditions 

    D(p_u, p_v) > R_restr
 
must be satisfied for any  u∈i,j and any v∈a,b. For example, suppose R_int=R_restr=1× d in Fig. <ref>. Let p_i,j be a physical qubit located at (i,j). Then  CZ(p_0,2,p_1,2) can be executed in parallel with CZ(p_0,0,p_1,0), but not in parallel with CZ(p_1,1,p_1,0).

The ability to move qubits is the most distinctive advantage of NA platforms <cit.>. In NA systems, qubits are captured in two types of traps. A spatial light modulator (SLM) generates an array of static traps, while a 2D acousto-optic deflector (AOD) creates mobile traps that can move within the plane. The AOD traps are formed at the intersection of a set of rows and columns. Each row/column coordinate can be activated, moved, and then deactivated, allowing for arbitrary rearrangements of the atoms, subject to the constraint that different columns (rows) must not cross each other. Atom movement is a high-fidelity operation and an atom can traverse a region for 2,000 qubits with only 0.1% coherence time <cit.>.



 §.§ Quantum circuit compilation




In quantum computing, a quantum circuit serves as a model that represents the flow of information and operations within a quantum algorithm. A quantum circuit is composed of qubits and quantum gates that manipulate the states of these qubits. In this work, we denote a quantum circuit by C, which consists of a sequence of quantum gates {g_1, …,g_m} acting on qubits in Q={q_1,…,q_n}. Fig. <ref> shows the well-known QFT circuit on five qubits.[For clarity, we have omitted the SWAP gates at the end of the circuit.]




Circuits like QFT-5 in Fig. <ref> often contain gates that are not native in a target quantum device. This means we need to decompose non-native gates in C into native gates. For example, let 𝒢=R_x,R_y,R_z, CZ be the set of native gates of the target quantum device. For QFT-5 in Fig. <ref>, we need decompose H and control phase gate CP(θ) in gates in 𝒢. The result is shown in Fig. <ref>. 

Due to the limited qubit connectivity, it is not often that we can execute the synthesised circuit directly: some CZ gates may act on two far away device qubits. For example, suppose the target quantum device has architecture graph as the graph in Fig. <ref> but with all blue edges being removed. Assume furthermore that we initially map the program qubits q_i (0≤ i≤ 4) as in Fig. <ref>(a). Then all but the last four CZ gates are directly executable,  because they act on physic qubits that are connected by a black or red-dashed edge in Fig. <ref>. Note that the fourth last CZ gate in C acts on q_0,q_2, which are mapped to p_0,2,p_0,0. Because p_0,2 is not connected to p_0,0 in the architecture graph, we cannot execute the CZ gate.





We next outline the general procedures for quantum circuit transformation. To execute a decomposed circuit C on an NA device, each program qubit q in C is first mapped to a physical atom, represented by a location p_i,j in the SLM layer of the device. With this initial mapping, as illustrated in Fig. <ref>(a), not all CZ gates are directly executable. If a CZ gate g is not directly executable, we need to bring the two qubits of g close together. In NA platforms, there are two methods for achieving this: SWAP gate insertion and atom shuttling (cf. <cit.>). One approach is to swap q_0 and q_4, or swap q_2 and q_4, by applying the corresponding SWAP gates. Alternatively, we can move the atom carrying q_0 from p_0,2 to one of the three neighbours of p_0,0. If a neighbouring position is already occupied, the occupying atom must be moved away. 




 §.§ Related work
 
Quantum circuit transformation (QCT) is the process of converting a program circuit into a form that is executable on a target quantum device, whether it be an IBM superconducting device or an NA quantum device. QCT is a crucial component of quantum circuit compilation. Since IBM launched its cloud-based quantum computing services, numerous  QCT algorithms have been proposed in the literature, including <cit.>. 

The unique features of NA devices introduce distinct challenges for quantum circuit compilation. Early efforts sought to leverage these features within fixed atom arrays. Baker et al. proposed the first compiler for NA devices, which accounted for long-range interaction  <cit.>. Multi-qubit gate support was subsequently incorporated in <cit.>. Inspired by the popular block puzzle game, Li et al. <cit.> proposed the heuristic algorithm Tetris, which effectively reduces qubit idle time while exploiting the rich qubit connections in NA device and adhering to parallel execution constraints. 

Different from the above SWAP-gate based shuttling method, Tan et al. <cit.> developed an SMT solver-based compiler, called OLSQ-DPQA, which utilises atom shuttling.  Nottingham et al. <cit.>  also explored the potential of using atom movement as an alternative to the costly SWAP-gate shuttling. Subsequently, several follow-up compilers were introduced to address the scalability challenge of OLSQ-DPQA. These include Atomique <cit.>, Q-Pilot <cit.>, and Enola <cit.>, all of which consider the dynamically field-programmable qubit arrays (DPQA) architecture <cit.>. In Enola, the compilation process is divided into scheduling, placement, and routing. It schedules a commutation group of CZ gates in a near-optimal number of Rydberg stages and, for a generic quantum circuit, it schedules each layer of parallel CZ gates as a Rydberg stage. Enola offers two placement methods: dynamic placement, which generates a new qubit mapping for each Rydberg stage, and static placement, which uses the same mapping throughout. When comparing with OLSQ-DPQA, Atomique, and Q-Pilot, Enola demonstrates superior fidelity improvement <cit.>.   

Combining the two methods described above is natural. Brandhofer et al. <cit.> proposed a compiler that integrates SWAP gates with a special atom movement technique called one-dimensional displacements, aimed at reducing circuit depth and improve circuit fidelity. Another hybrid compiler was proposed in <cit.>, where the NA hardware is grid-based, and atom can be moved from one grid point to another only if the target grid point is unoccupied. Experiments in <cit.> show that, for shuttling-favoured NA devices, the hybrid approach is essentially the same as the atom shuttling method in performance.


Interested reader may consult the recent review paper  <cit.> for more information.


Divide-and-conquer (DAC) is a natural approach for quantum circuit transformation, and several researchers have proposed DAC-based QCT algorithms, such as those in <cit.>. Siraichi et al. <cit.> introduced the BMT algorithm, which transforms circuits by combining subgraph isomorphism with token swapping. The algorithm partitions the gate list into maximal isomorphic sublists, constructs multiple embeddings for each sublist, and then uses token swapping to combine embeddings of consecutive sublists. The optimal transformation path is found using dynamic programming.  Similarly, Wu et al. <cit.> proposed a DAC approach that uses an SMT-based checker to verify if a sublist can be transformed without SWAP gate insertion. Their method partitions the circuit into sublists with a bounded number of 2-qubit gates, generates multiple embeddings for each sublist, and links pairs of embeddings with SWAP gates. The optimal transformation is selected based on minimising a heuristic distance cost. However, these algorithms, which rely on exhaustive search, struggle with circuits involving 20 or more qubits.




§ DASATOM TRANSFORMATION FRAMEWORK

In this section, we give a detailed description of our algorithm DasAtom.



 §.§ Overview

Let 𝒢 be an NA-native gate set, including the two-qubit CZ gate and local addressing rotation gates R_z, as well as R_x, R_y  (which can be locally or globally addressed). Given an input circuit C, we first synthesise C using gates from 𝒢.  In this work, we assume that single-qubit gates and CZ gates are executed in distinct stages; in each stage, either  single-qubit gates or CZ gates are executed, but not both. Fig. <ref> outlines the general compilation flow on NA devices. Note that whenever there is a single-qubit gate in the front layer, we execute (and remove) it and generate the new front layer. This implies that 2Q gates can, in principle, be executed layerwise.




Given an input circuit C on n qubits, an NA-native gate set 𝒢, an interaction radius R_int≥ d, and a restriction radius R_restr≥ R_int, where d is the distance between atoms, DasAtom operates as follows:

    
  * Synthesise C using gates from 𝒢 and remove single-qubit gates. The resulting circuit consists of only CZ gates. We still write C for this CZ circuit.
    
  * Partition the remaining circuit into layers L_1,…,L_m, where each L_i contains only CZ gates.
    
  * Divide the CZ circuit C into subcircuits such that (i) each layer L_i is fully contained within a subcircuit; (ii) the interaction graph  of each subcircuit is embeddable in Grid(b,b), where b = √(n). The precise meaning of the interaction graph and embeddable graph will be defined in the next subsection.
    
  * For each subcircuit C_i, construct a mapping f_i that embeds the interaction graph IG(C_i) to Grid(b,b). For each CZ gate g=CZ(q,q') in C_i, we execute g by interacting f_i(q) and f_i(q'). Since D(f_i(q),f_i(q')) ≤ R_int, the gate can be executed directly. However, due to parallel execution constraints, not all gates in the same layer can be executed simultaneously. 
    
  * Perform routing based on atom shuttling (instead of inserting SWAP gates). This can be achieved by modifying the routing algorithm provided in <cit.> or that in <cit.> or <cit.>. This process transforms f_i into f_i+1.

The flowchart of DasAtom is shown in Fig. <ref>.



In addition, we assume that CZ gates are executed by applying Rydberg laser individually. Note that to exploit long-range interaction, we always assume in DasAtom that the atom distance d ≤ R_int. This is different from DPQA <cit.>, where the atom distance is 2.5× R_int. 


In the following, we discuss the implementation of the above procedures in detail.









 §.§ Circuit division


Qubit interaction in a quantum circuit C can be simply represented by a graph.

For a quantum circuit C with qubit set Q, its interaction graph, denoted as IG(C), is an undirected graph (Q,E_int), where:

    
  * each node represents a qubit of C. 
    
  * Two nodes q,q'∈ Q are connected if there is a two-qubit gate in C acting on q,q'. 


If the interaction graph of C matches well with the architecture graph AG=(V,E), there is no need to route the qubits: what we need is an embedding f from IG(C) to AG. Here a 1-1 mapping f:Q→ V is an embedding if (f(q),f(q')) is an edge in AG for any edge (q,q') in IG(C). In this case, f is also called a subgraph isomorphism.


After decomposing gates in the circuit C into NA-native gates and removing single-qubit gates, we partition C into CZ layers L_1,⋯,L_m. It is straightforward to see that each CZ layer corresponds to an executable front layer (i.e., the `Execute 2Q gates' node) in Fig. <ref>.  Furthermore, we divide C into subcircuits C_1,…,C_k so that each C_i is composed of consecutive CZ layers of C and the interaction graph of C_i is embeddable in AG with some embedding f_i. For convenience, we write C_i = C[ℓ_i : m_i] if C_i is composed of layers L_ℓ_i,…,L_m_i. Apparently, we have 1=ℓ_1≤ m_1<ℓ_2≤ m_2 < … < ℓ_k ≤ m_k=m.

Unlike the methods in <cit.> and <cit.>, our division scheme is coarse-grained, requiring significantly fewer calls to the costly subgraph isomorphism check. For circuit division, we employ the Rustworkx implementation of VF2 <cit.>. When partitioning the circuit into layers, the number of VF2 calls is at most O(depth), where depth is the number of CZ layers in C. 




For our running example, if we set R_int=√(2)d, then the QFT-5 circuit can be partitioned into two subcircuits, see Fig. <ref>. The interaction graphs and their embeddings to AG=G(3,3) of these two subcircuits are shown in Fig. <ref>. 

To minimise qubit idling time, we aim to execute as many CZ gates in parallel as possible, ensuring they satisfy the previously mentioned restriction constraint. In our example, R_restr = 2× R_ini = 2√(2)d. The first sub-circuit includes, for instance, a CZ layer consisting of gates CZ(q_1, q_3) and CZ(q_0, q_4), with the qubit mapping f shown in Fig. <ref>(a). While these gates can be executed in parallel on superconducting devices (albeit with potential crosstalk noise), on an NA device, D(f(q_3), f(q_4)) = d < R_restr, meaning CZ(q_1, q_3) and CZ(q_0, q_4) cannot be executed in parallel due to the restriction constraint. 





 §.§ Atom shuttling


Suppose we have divided the CZ circuit C into subcircuits C_1,…,C_m with corresponding embeddingspa f_1,…,f_m. How do we transition from one mapping to the next? In superconducting quantum devices, this is typically done by inserting SWAP gates. As we have seen in Section <ref>, atom shuttling is more desirable in NA quantum devices.


Let Q=q_1,…,q_n be the set of logical qubits in the input circuit. Suppose f,f' are two 1-1 mappings from Q to grid points in G(b,b) (b = √(n)). Our task is to transition the old mapping f into the new mapping f'. To this end, we need to move each q_i∈ Q from its current position f(q_i)=(x_i,y_i) in G(b,b) to a new position f'(q_i)=(x'_i,y'_i), also in G(b,b).[In contrast, Enola only requires moving the atom at (x_i,y_i) closer to the atom at (x'_i,y'_i), allowing for bidirectional movement.] 

Let M={m_i (x_i,y_i,x'_i,y'_i) | 1≤ i≤ n}, where each m_i represents a target movement. Two movements m_i,m_j are said to conflict if the following condition is violated:

    
  * (x_i * x_j) ⟺ (x'_i * x'_j) and (y_i * y_j) ⟺ (y'_i * y'_j) for all * in <,=,>.

If m_i and m_j do not conflict, they are considered compatible. A set of movements is compatible if every pair within the set is compatible. We aim to find a sequence of parallel and compatible movements (not necessarily all from M) that move each (x_i,y_i) to (x'_i,y'_i) efficiently, minimising the total movement time. Several existing routing algorithms can be used for this purpose, such as those in <cit.>. For ease of comparison, we adapt the routing algorithm from Tan et al. <cit.> for our needs. 


We construct a conflict graph for M, where each node represents a movement in M, and two nodes are connected if their movements are incompatible. This reduces the problem to finding a maximum independent set (MIS) in the conflict graph, as described in <cit.>. Instead of moving two qubits close together, we move each atom from its current position (as specified by the old mapping f) to the next as specified by the new mapping f', meaning no dual movements  exist in our conflict graph.  Since the MIS problem is NP-hard, we use the same greedy algorithms implemented in Enola to approximate a solution. 









§ EVALUATION

We implemented our proposed algorithm in Python. Note we adapted the routing algorithm introduced in <cit.> for transiting two consecutive mappings. All experiments for DasAtom and Enola, which were programmed in Python, were conducted on a MacBook Pro featuring a 2.3 GHz Intel Core i5 processor and 16 GB memory, while all experiments for Tetris, which was programmed in C++, were conducted on an Ubuntu 20.04 server with 40 cores of Intel Xeon Gold 5215 @ 2.50GHz, 512 GB of RAM. Our source code will be made publicly available on the authors' GitHub repository. 



 §.§ Parameters setting

In our experiments, we assume the following NA hardware parameters. 

    
  * Atom distance d: 3 μm
    
  * CZ gate duration: 0.2 μs
    
  * CZ gate fidelity: 0.995
    
  * Coherence time T_2: 1.5s

    
  * Moving speed: 0.55μm/μs
    
  * Trap swapping duration: 20μs
    
  * Atom transfer fidelity: 1
    
  * Coupling graph size:  √(n)×√(n)




  §.§.§ Comparing different interaction and restriction radii

We begin by comparing the performance of DasAtom with various interaction radii. As can be observed from Fig. <ref>, setting r_int=2 provides slightly better results than other configurations. In the following, we choose the following settings, which is also suggested in <cit.>:  

    
  * R_int = 2d, R_restr = 4d.
 
Note that a larger restriction radius always has a negative impact on performance.





  §.§.§ Assumptions for Tetris and Enola

For both Tetris and Enola, we assume that the input circuit is decomposed in the same manner, with all single-qubit gates  removed before applying the algorithms. For Tetris, we assume that CZ gates are executed by individually applying the Rydberg laser; while for Enola, CZ gates are executed using a global Rydberg laser without exploiting gate commutativity. Consequently, the atom distance is set to d=3μm for Tetris and d=7.5μm for Enola. It is worth noting that Tetris adopts a definition of variable restriction area, which depends on the inter-qubit distance of the gate.



 §.§ Fidelity


For easy of comparison among algorithms across different quantum computing platforms, and following <cit.>, we use the approximate success probability as a proxy for circuit fidelity. Let g_i| 0≤ i≤ m be the set of gates in the transformed circuit, and F_g_i the  fidelity of gate g_i. The approximate success probability of the compiled circuit is 
    
    P(C) = exp(-T_idle/T_2) ∏_i=0^m F_g_i,

where T_2 is the atom dephasing time, T_idle=nT-∑_i=0^mt(g_i), n is the number of qubits in the circuit, T is the total circuit execution time, and t(g_i) is the execution time of gate g_i.

Given our hardware parameters settings (cf. Section <ref>), the cost of inserting a SWAP gate can be approximated by F_g^3=0.995^3=0.985, where F_g is the fidelity of a CZ gate. In contrast, the cost of moving an atom at a speed of 0.55μm/μs over a distance x μm can be roughly calculated as exp(-2× T_trans+x/0.55/T_2), where 2 · T_trans represents the time taken for the atom to transition between SLM to AOD traps at both the initial and target positions. A simple calculation shows that the fidelity drops to 0.985 when x≈ 12384 μm. Additionally, if we want to swap the positions of two atoms, the distance can be as large as 6202 μm for the fidelity to remain at 0.985. This illustrates why SWAP gates are costly in terms of fidelity. However, it is important to note that SWAP gates could be 10x or more faster than atom movement.




 §.§ Overall fidelity comparison with Tetris and Enola




  §.§.§ Results on benchmark circuits used in  <cit.>

In <cit.>, the authors evaluated, among others, 33 benchmark circuits from RevLib and IBM Qiskit. After proper decomposition, these circuits include qubit counts ranging from 5 to 16 and up to 3,089 CZ gates. We empirically evaluated the performance of the three algorithms on these benchmarks, and the results are summarised in Table <ref>.


During compilation, we assume that each SWAP gate inserted by Tetris is decomposed into three CZ gates and several single-qubit gates. It is important to note that, in our calculation of Tetris's overall fidelity, we completely disregard the presence of additional single-qubit gates in the compiled circuit. As a result, the calculated fidelity is slightly higher than the actual value. 

Recall that Enola operates in both static and dynamic modes. For these benchmark circuits, the two modes produce similar overall fidelity, with the dynamic mode performing slightly better. However, this improvement comes at the cost of a significantly increased runtime. So we set a time out of 3600 seconds if the dynamic method does not complete within this time frame, which is the case for all circuits with CZ depth ≥ 30.


From Table <ref>, we observe the following:

    
  * DasAtom consistently outperforms Tetris and Enola in both fidelity and runtime. For the 15-qubit `square_root_7' circuit, DasAtom achieves a fidelity that is 27x higher than Tetris's, while Tetris's runtime is 178x longer than DasAtom's. For the 16-qubit `ising_model_16', the fidelity of DasAtom is 1.6x of that of Enola (dynamic), with Enola's runtime being 17,490x longer.
    
  * The fidelity of Tetris (Enola) deteriorates rapidly with the increasing number of SWAP gates (CZ-depth).
    
  * The runtime of Enola (dynamic) is highly related to the CZ-depth of the circuit. It takes around one hour to transpile a circuit with CZ-depth 30 and becomes extremely slow for circuits with CZ-depth ≥ 300. Indeed, it takes (dynamic) Enola 68 hours to finish the 6-qubit `sf_276' circuit, which has CZ depth 300.





  §.§.§ Results on practical quantum circuits with varying qubit number and topologies
 The benchmark circuits evaluated above involve a relatively small number of qubits. To assess the scalability of our algorithm, we also evaluated the performance of the three algorithms on larger circuits, extracted from MQTBench[https://www.cda.cit.tum.de/mqtbench/] and <cit.>. These circuits include DJ, GHZ, QFT, W-state, QV, two-local random circuits, and 3-regular MaxCut QAOA circuits, which have very different interaction graphs. Since Enola (dynamic) performs exponentially better than Enola (static) as the number of qubits increases, we focus solely on Enola (dynamic) in these experiments.  


Table <ref> summarises circuit information and performance details of the three algorithms on seven 20-qubit circuits. From the table we can see that DasAtom consistently outperforms Tetris and Enola in overall fidelity. In addition, the fidelity of DasAtom has strong relation with the number of CZ gates in the circuit.



  
QFT circuits These circuits have complete interaction graphs, see Fig. <ref>(b). In Fig. <ref>(a), the y-axis denotes the ratio of DasAtom's fidelity compared to that of Tetris and Enola, plotted on a logarithmic scale. The results clearly demonstrate that the ratio increases exponentially with the number of qubits, ranging from 5 to 50. In terms of runtime, Fig. <ref>(c) shows that Enola and Tetris are three and two orders of magnitude slower than DasAtom, respectively.





  
Two-local random circuits These circuits have complete interaction graphs. Fig. <ref> shows that the  performance ratios of DasAtom's fidelity against that of Tetris and Enola also increases exponentially with number of qubits, ranging from 5 to 30. Note that here we only show results of circuits with up to 30 qubits, as Enola is very slow. 





  
Quantum Volume circuits  These circuits have (nearly) complete interaction graphs. Fig. <ref> shows that the  performance ratios of DasAtom's fidelity against that of Tetris and Enola also increase exponentially with number of qubits.




  
3-Regular MaxCut QAOA circuits These circuits have 3-regular interaction graphs. Fig. <ref> shows that the fidelity decreases as the number of qubits increases for the algorithms and DasAtom significantly outperforms the other two.





  
Deutsch-Jozsa circuits These circuits have star-like interaction graphs.  Fig. <ref> shows how the fidelity decreases as the number of qubits increases for the three algorithms. DasAtom significantly outperforms both Tetris and Enola by a large margin.





  
GHZ circuits and W-state circuits These circuits have linear interaction graphs.  Fig.s <ref> and <ref> show how the fidelity decreases as the number of qubits increases for the three algorithms. DasAtom significantly outperforms both Tetris and Enola by a large margin.











§ FURTHER DISCUSSIONS

The evaluation above demonstrates that the DAC scheme, despite its simplicity, is highly effective. This effectiveness can be attributed to two key factors: first, long-range interaction results in dense qubit connections; second, atom shuttling is significantly less costly than SWAP gate insertion (cf. Section <ref>). However, it is important to note that our implementation is not yet fully optimised. Specifically, the mappings for each subcircuit could be designed to enable smoother transitions, making the process more efficient. For example, the mapping of the second part of QFT-5 shown in Fig. <ref>(c) is not optimal. A better approach would be to place q_4 at (0,2) and q_1 at (1,0), requiring only an exchange between the positions of q_0 and q_4. 

Although our algorithm relies on subgraph isomorphism checks, which are theoretically NP-hard, this has not proven to be a significant obstacle in most cases. By leveraging the Rustworkx implementation of VF2, we successfully compiled the 500-qubit QFT in about one hour. However, this implementation does not perform as well on certain circuits, like QV, especially when the number of qubits exceeds 25. To handle circuits with thousands of qubits, more efficient (though potentially approximate) subgraph isomorphism algorithms will be necessary. Given that our target architecture is grid-based, this should not pose a major challenge. However, as shown in the fidelity ratio curves in Fig. <ref>(a), the primary concern for compilation on NA hardware should be low fidelity rather than scalability.

Furthermore, in our implementation of DasAtom, we adopted Enola's atom movement routing algorithm, which requires dropping the atom to the SLM layer to execute two-qubit gates. However, this step is not strictly necessary, as two-qubit gates can be executed between qubits across the SLM and AOD layers <cit.>, potentially reducing the number of atom transfers and movements required and hence further improving the overall fidelity.




§ CONCLUSION

In this paper, we introduced DasAtom, a novel algorithm designed to optimise the execution of quantum circuits on neutral atom platforms by exploiting long-range interactions and atom shuttling. Unlike previous methods such as SWAP-based Tetris and atom move-based Enola, DasAtom achieves significant fidelity improvements through partitioning circuits into subcircuits and dynamically adjusting qubit mappings. Our results demonstrate that for a 30-qubit QFT,  DasAtom outperforms Enola by 414x and Tetris by 10.6x, illustrating the substantial gains in fidelity that can be achieved with this method.


The ability of DasAtom to scale its performance with the increasing number of qubits highlights its potential as a crucial tool in the future of neutral atom quantum computing. As quantum circuits grow in complexity and size, the exponential improvement in fidelity offered by DasAtom will become increasingly valuable. This work not only provides a pathway to more efficient quantum circuit execution on neutral atom platforms but also sets the stage for further research and development in the field. Future work will focus on expanding the capabilities of DasAtom to handle even larger and more complex quantum circuits.



IEEEtran 


