## 4 Quantum Exchange Lock Parallel Scheduler
### Quantum Circuit Hierarchical Strategy Based on Qelps
1: Begin
2: Initialize layers \(L\) as an empty list
3: Identify quantum gates in \(Q\) that do not satisfy CNOT constraints
4: Analyze SWAP gate insertions to form the first layer \(L[0]\)
5: While there are unassigned quantum gates in \(Q\) do
6: Create new layer \(L[i]\)
7: Fill \(L[i]\) with gates executable in parallel without conflicts
8: For each gate \(g\) in \(L[i]\) do
9: If \(g\) conflicts with assigned gates
10: Postpone \(g\) to \(L[i+1]\)
11: End If
12: End For
13: If execution time of \(L[i]\leq\) execution time of \(L[0]\)
14: Add \(L[i]\) to \(L\)
15: Else
16: Break
17: End If
18:End While
19: For each layer \(L[i]\) in \(L\) do
20: Simulate SWAP insertions for unassigned gates
21: Identify micro-conflicts
22: Lock gates in \(L[i]\), prioritizing CNOT gates
23: For each subsequent layer \(L[j]\) do
24: Search for gates in \(L[j]\) that do not conflict with SWAPs in \(L[i]\)
25: Insert these gates into \(L[j]\) ensuring execution time does not exceed \(L[0]\)'s time
26: End For
27: End For
28:Return C
29:End

### Example Analysis

As shown in the quantum circuit diagram in Figure 2, the nodes represent quantum bits, while the edges indicate the connectivity between them. The input circuit consists of \(\text{CNOT}q_{1},q_{4}\), \(\text{CNOT}q_{1},q_{2}\), \(\text{CNOT}q_{2},q_{5}\), \(\text{CNOT}q_{0},q_{4}\), \(\text{CNOT}q_{1},q_{3}\), and \(\text{H}q_{0}\). After introducing the QELPS algorithm, \(\text{CNOT}q_{0},q_{4}\), which requires a mapping adjustment for execution, is selected as the benchmark and placed in layer \(l_{0}\) The algorithm identifies both locally optimal and suboptimal solutions to resolve SWAP gate conflicts within the quantum circuit. During the layering process, a dynamic insertion and adjustment strategy for SWAP gates is applied to incrementally fill each layer with quantum gates while prioritizing gates in the front layers. Initially, the local optimal solution is considered, where \(\text{CNOT}q_{0},q_{4}\), \(\text{CNOT}q_{2},q_{5}\), and \(\text{CNOT}q_{1},q_{3}\) are placed in \(l_{0}\). However, after evaluating the insertion of four possible SWAP gates required to satisfy CNOT gate constraints, conflicts with qubits involved in the existing CNOT gates within the layer are detected. As a result, the local optimal solution is abandoned, and the local suboptimal solution is selected instead, consisting of \(\text{CNOT}q_{0},q_{4}\) and \(\text{CNOT}q_{1},q_{2}\). Following the SWAP conflict resolution process, the SWAP gates that satisfy the mapping conditions are \(\text{SWAP}q_{3},q_{4}\) and \(\text{SWAP}q_{0},q_{3}\). This approach is consistently applied to all subsequent layers. As a result, \(l_{0}\) contains \(\text{CNOT}q_{0},q_{4}\) and \(\text{CNOT}q_{1},q_{2}\), \(l_{1}\) consists of \(\text{CNOT}q_{2},q_{5}\), \(\text{CNOT}q_{1},q_{3}\), and \(\text{H}q_{0}\), while \(l_{2}\) includes \(\text{CNOT}q_{1},q_{4}\). In the secondary layering process, it is assumed that multiple gates cannot act on a single qubit simultaneously. A qubit that participates in a certain gate operation is considered to be in a locked state and remains locked for a duration of \(t\) before being unlocked. Based on this assumption, the operands of different quantum gates determine their locking durations, where the Hadamard (H) gate locks a qubit for \(\tau\), the CNOT gate for \(2\tau\), and the SWAP gate for \(6\tau\). Therefore, a reasonable assumption is made when \(t=\tau,2\tau,6\tau\), respectively. Following these constraints, the gate \(\text{CNOT}q_{0},q_{4}\) in layer \(l_{0}\) does not satisfy the mapping requirements for CNOT execution. As a result, a SWAP gate must be introduced to modify the quantum mapping. However, using \(\text{SWAP}q_{0},q_{1}\) and \(\text{SWAP}q_{1},q_{4}\) creates conflicts with \(\text{CNOT}q_{0},q_{4}\) and \(\text{CNOT}q_{1},q_{2}\) since these operations would act on qubits \(q_{0}\), \(q_{1}\) and \(q_{4}\) simultaneously. Therefore, these SWAP gates are not feasible and must be discarded.