{'fraction_non_alphanumeric': 0.035470522992918696, 'fraction_numerical': 0.010280692773654124, 'mean_word_length': 4.530848177421258, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, '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}}
Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits

In this paper, we propose a novel quantum compiler optimization, named relaxed peephole optimization (RPO) for quantum computers. RPO leverages the single-qubit state information that can be determined statically by the compiler. We define that a qubit is in a basis state when, at a given point in time, its state is either in the X-, Y-, or Z-basis. When basis qubits are used as inputs to quantum gates, there exist opportunities for strength reduction, which replaces quantum operations with equivalent but less expensive ones. Compared to the existing peephole optimization for quantum programs, the difference is that our proposed optimization does not require an identical unitary matrix, thereby named `relaxed' peephole optimization. We also extend our approach to optimize the quantum gates when some input qubits are in known pure states. Both optimizations, namely the Quantum Basis-state Optimization (QBO) and the Quantum Pure-state Optimization (QPO), are implemented in the IBM's Qiskit transpiler. Our experimental results show that our proposed optimization pass is fast and effective. The circuits optimized with our compiler optimizations obtain up to 18.0% (11.7% on average) fewer CNOT gates and up to 8.2% (7.1% on average) lower transpilation time than that of the most aggressive optimization level in the Qiskit compiler. When running on real quantum computers, the success rates of 3-qubit quantum phase estimation algorithm improve by 2.30X due to the reduced gate counts.


I. INTRODUCTION
Quantum computing shows great potential in chemistry simulation [26], combinatorial optimization [18], cryptography [27], machine learning [8], etc. Recently, Google, IBM, and Intel have announced their quantum computers with 72, 53, and 49 qubits, respectively [20], [21], [25]. These noisy quantum computers are capable of running some quantum algorithms and would be helpful for exploiting the physics of many entangled particles [36]. However, state-of-the-art quantum computers do not have enough qubits to accommodate error correction codes, and the noise in the quantum computers hinders the development of quantum computing.
As quantum computers typically support a limited set of basic operations/gates, quantum compilers/transpilers are responsible for decomposing complex quantum gates into the basic ones that the quantum computer supports. Quantum compilers also optimize quantum circuits to reduce the overall gate count or circuit depth. Since the accuracy of the final result can be affected by the system noise, such optimization is extremely important for quantum computers. The existing quantum compilers [3], [38] exploit many optimization techniques. An important one is peephole optimization or operator strength reduction [38]. The peephole optimization is analogous to its homonym in classical computing. The compiler traverses through the quantum circuit to find specific patterns of sub-circuits and substitute them with equivalent ones that have less primitive operations or shorter depth. These substitutions keep the semantics of the quantum program as their unitary matrix representations are identical.
In this paper, we propose a new compiler optimization termed relaxed peephole optimization (RPO). It builds upon the fact that some of the qubit states for many quantum gates can be known or derived at compile-time. This presents opportunities for replacing quantum operations with equivalent but less expensive ones. But the difference from the existing peephole optimization is that the unitary matrix of the circuit may change although the circuit functionality remains the same. For example, for a CNOT gate, if the control qubit is in the |1 state, it is functionally equivalent to a NOT gate on the target qubit. After determining the state of the control qubit, our compiler optimization will replace the CNOT gate with a NOT gate. However, the unitary matrices of CNOT and NOT gates are different and the peephole optimization would not be able to take advantage of such opportunities. In other words, our optimization can be viewed as a relaxed type of peephole optimization, which finds functionally equivalent circuits under certain circumstances. In our paper, we derive RPO for a wide range of quantum gates when some of their inputs are in known basis/pure states.
In order to figure out the quantum states for RPO, we propose a quantum state analysis approach. With this analysis, we develop two optimization passes, namely the Quantum Basis-state Optimization (QBO) pass and the Quantum Pure-state Optimization (QPO) pass. In our paper, we define |0 , |1 , |+ , |− , |L , and |R as basis states. The QBO pass identifies these basis states for every qubit during execution and optimizes quantum gates accordingly. The QPO pass determines single-qubit pure states and performs corresponding quantum circuit optimization. We also introduce annotations such that the programmer can guide the compiler optimization. We experimented with several quantum benchmarks on IBM Q quantum simulators and quantum computers. The experiments show that the circuits optimized using our approach have up to 18.0% (11.7% on average) fewer CNOT gates with up to 8.2% (7.1% on average) less transpilation time than that of the most aggressive optimization level in the Qiskit compiler. Since other quantum compilers, e.g., t |ket [38] use a similar gate model to IBM Qiskit, we expect that our proposed idea is applicable to them as well.
The major contributions of this work are listed as follows: • We propose a new compiler optimization, relaxed peephole optimization (RPO). • We derive a comprehensive list of circuit optimizations for a wide range of quantum gates when some of their inputs are in known basis or pure states. • We present a quantum state analysis approach which identifies basis and pure states for each qubit in a quantum circuit. We also introduce annotations to enable users to provide information to facilitate state analysis. • We implement both QBO and QPO as compiler optimization passes in the IBM Qiskit transpiler. • We show that our proposed RPO achieves better results than the most aggressive optimization level in Qiskit. The remainder of the paper is organized as follows. Section II introduces the background of quantum computing and quantum compilers. Sections III and IV describe our findings on optimizing CNOT and SWAP gates with zero states and known pure states, respectively. Section V generalizes the optimization for a broad range of quantum gates. Section VI discusses our compiler scheme to determine the quantum states of each qubit in a quantum circuit. Section VII presents our compiler implementation using IBM Qiskit. Our experimental results are discussed in Section VIII. Finally, Section IX concludes the paper.

A. Quantum Computing
Qubit (quantum bit) is the basic unit of quantum information. Besides the classical states |0 and |1 , a qubit can stay in any superposition state. A superposition state can be represented as |ψ = a |0 + b |1 where a and b are complex numbers and |a| 2 + |b| 2 = 1. When measuring a superposition state |ψ in the computational basis, the probability of getting |0 and |1 states are |a| 2 and |b| 2 , respectively. The state of a quantum system is represented by a vector in a Hilbert space [33]: a complex vector space with an inner product. The state of multiple qubits can be expressed as the tensor product of each qubit state if they are not entangled: |ψ 12 = |ψ 1 ⊗ |ψ 2 = |ψ 1 ψ 2 . Entanglement is an unique property of quantum computing. When two qubits are entangled, their measurement results are correlated and the two-qubit state can not be expressed as the tensor product of individual qubits. For example, the two-qubit Bell state 1 √ 2 (|00 + |11 ) is an entangled state. When the measurement outcome of the first qubit is |0 , the measurement outcome of the second qubit must be |0 .
A pure quantum state can be represented by a single state vector |ψ in the Hilbert space. A mixed quantum state can not be represented in this way and corresponds to a probability mixture of pure states. A density matrix [9] ρ = i P i |ψ i ψ i | is used to describe the mixed states, where P i is the probability of the pure state |ψ i . Generally speaking, a qubit system is in a pure state when the qubits in the system are not entangled with qubits out side the system. When the qubits are entangled with others, they are in the mixed state. For example, the two-qubit bell state is a two-qubit pure state since these two qubits are not entangled with others. The state can be represented by state vector 1 √ 2 (|00 + |11 ). If we consider each qubit individually, however, since the two qubits are entangled, either qubit is in the mixed state with the density matrix as ρ = 1 2 (|0 0| + |1 1|). An n-qubit pure state |ψ can be generated by applying an n-qubit unitary gate U to n qubits, which are all in the |0 state: |ψ = U |0 ⊗n .
The proof is in Appendix A. A key conclusion from the proof is that when a qubit is not entangled with the others, it is in a single-qubit pure state and this state can be generated by applying a single-qubit gate to a qubit in the |0 state. For simplification purposes, we will refer to single-qubit pure states as pure state in the rest of this paper. A quantum program is essentially a sequence of instructions/gates operating on qubits. There are single-qubit gates such as Identity gate I or id , Hadamard gate H , Phase changing gate S and T , Pauli Gates X, Y , and Z, and twoqubit gates such as controlled-NOT (CNOT ) gate. The two qubits in the CNOT gate are termed as control and target qubit as illustrated in Figure 1. Instructions, unlike gates, are not necessarily reversible might include classical aspects in the quantum program. Example of such instructions include RESET , MEASURE , and conditional control. On this work only considers RESET for simplicity. The state-of-the-art quantum computers only support a set of basic gates/instructions. and the quantum compiler needs to decompose the quantum program into the supported primitives. For example, the IBM quantum computers support basis gates including four types of single-qubit gates u1, u2, u3, id, and a two-qubit CNOT gate cx [43].

B. Qiskit Framework
Qiskit [3] is an open-source quantum computing software development framework. One element, named Qiskit Aqua, allows programmers to write codes for quantum algorithms. Another element called Qiskit Terra provides a transpiler, which is responsible for quantum gate decomposition, logicalto-physical qubit mapping, and circuit optimization. The transpiler consists of modular transpiler passes for circuit transformations. The transpiler pass manager schedules the transpiler passes and allows them to communicate. The users can control the pass manager to perform selective optimizations to the circuit. The transpiler has four pre-defined pass managers corresponding to the optimization level from 0 to 3. The higher optimization level, the higher the transpiler effort to optimize the circuit at the cost of transpilation time.
The different optimization levels can be described as follows [3]: Level 0 maps the circuit to the quantum device, with no explicit optimization included. Level 1 maps the circuit and also performs light-weight optimizations such as collapsing adjacent gates. Level 2 and 3 include noise-aware optimizations. Level 2 chooses noise-adaptive layout for the mapping and performs gate-cancellation procedure based on gate commutation relationships. Level 3 extends the passes from level 2 to include re-synthesis of two qubit blocks in the circuit as well as more iterations in the stochastic routing process. The re-synthesis process is performed by the Collect2qBlocks and the ConsolidateBlocks passes in Qiskit. The Collect2qBlocks pass traverses the circuit and collects sequences of gates acting on two qubits. The ConsolidateBlocks pass calculates the unitary matrices of two-qubit blocks and re-synthesizes them to more optimized circuits. This transpiler pass is similar to the operator strength reduction or peephole optimization in classical computing. The difference between our proposed optimization and the ConsolidateBlocks pass is that we do not preserve the unitary matrix although we replace the circuits with the ones that have the same functionality.

C. Related Work
Prior works have been proposed to optimize quantum circuits at the gate level. Venturelli et al. [45] proposed an automated, architecture-aware software framework aided by constraint programming. Nam et al. [32] developed automated optimization methods using phase polynomials. There are also noise-adaptive compilers [30], [31], [42] which take advantage of the noise characteristics of the target backend to aid the optimization.
Circuit equivalence has been discussed in terms of quantum algorithms [46], quantum compiler optimization [35] and quantum compilation verification [4]. Two circuits are considered as equivalent when their unitary matrix representations are identical [5]. Garcia-Escartin et al. [14] proposed a list of equivalent rules for identifying equivalent circuits. In compiler optimization, the process of substituting sub-circuits with their equivalent ones is termed as peephole optimization. Peephole optimization [28] identifies small sets of instructions and substitutes them with equivalent sets that have better performance. Prasad et al. [35] proposed a quantum circuit optimization algorithm that relies on peephole optimization. Sivarajah et al. [38] introduced a compiler named t |ket for noisy quantum computers. The peephole optimization in t |ket compiler traverses through the circuit to find long sequences of single-/two-qubit gates and replaces them with the circuits generated by Euler and KAK decomposition [24]. The similar optimization exists in other quantum compilers. For example, the transpiler in Qiskit Terra [3] contains optimization pass Collect2qBlocks and ConsolidateBlocks, which collaboratively identify and substitute two-qubit blocks with equivalent circuits. The Cirq [1] framework also provides similar optimization for adjacent single-and two-qubit gates.
Hoare logic [19] has been used to optimize quantum circuits. The optimizer removes trivial operations based on postconditions of the subroutines and the triviality conditions. The postconditions can be derived from the hoare triples of quantum subroutines. While our approach shares a few common optimization cases with the prior work, our optimization is more generic as we include optimizations for the quantum gates that are not trivial, e.g., the one shown in Eq. 6. Besides generality, the quantum state analysis discussed in Section VI provides fine-grained analysis for quantum states and enables more quantum gate optimizations. Moreover, since the hoare logic pass requires a classical Z3 solver [11] to express the conditions, it significantly increases the transpilation time. In Section VIII, we show that our optimization pass is faster and more effective than the hoare logic pass.

III. ZERO STATE
We use a basic optimization, which only leverages a |0 state, as a stepping stone for more generic optimizations (see Section V). We also introduce some handful notations and concepts.
Consider the following situation: if a CNOT gate with the control qubit being in the |0 state, the CNOT gate has no effect and can be removed or replaced with a wire: The unitary matrices of the CNOT gate and the idle wire are obviously different, and they are not considered as equivalent in the existing compilers. However, they are functionally equivalent when the control qubit is in |0 state.
Although this special CNOT example may seem trivial, we can leverage it for optimizing SWAP gates. SWAP gates are often introduced during the logical-to-physical qubit mapping to allow quantum operations on qubits that not physically adjacent. Being symmetric gates, SWAP gates has two possible decompositions as showed in Figure 2.
Many times SWAP gates are introduced in the beginning part of a circuit, when there is a good chance that one of the qubits to be swapped is still in the initial ground state |0 . In such cases, we can take advantage of a reduced SWAP gate design, which only swaps any state |ψ with the state |0 : Let us introduce a notation for this special 2-CNOT -SWAP gate. It is referred to as SWAPZ (swap-zero) in the remaining of the paper: In summary, a SWAP gate that involves a |0 state can be replaced for a less expensive SWAPZ . This equivalence follows from Equations 2 and 3. The first CNOT gate from the SWAP decomposition can be removed as its control qubit is in |0 state. The resulting SWAPZ gate consists of two CNOT gates, one less compared to the generic SWAP gate:

IV. SWAP ON PURE STATES
It is possible to extend the explained zero-state optimization of a SWAP gate to any known single-qubit pure state.
A qubit is in a pure state up to a certain point if all the operations on that qubit up to that point do not entangle with other qubits. A pure state can be represented by a single state vector |π in the Hilbert space. Based on the derivation in Appendix A, the single-qubit pure state |π can be obtained by applying a single unitary gate U to the |0 state, |π = U |0 . Due to unitarity, we can apply the inverse gate U −1 to transform the qubit in the pure state |π back to the state |0 .
When a SWAP gate operates on two qubits |ψ and |π and one of them, e.g., |π , is in a known pure state generated with U |0 , the SWAP gate can be replaced with a SWAPZ gate. As shown in Equation 5, the inverse gate U −1 transforms the pure state |π to state |0 (and back to |π after the SW AP ). Then, the SWAP gate is to swap state |0 with state |ψ , thereby can be optimized.
Altogether, when a SWAP gate operates on an arbitrary state |ψ and a known pure state |π , we can optimize the SWAP gate into a SWAPZ gate along with two single-qubit gates. This reduces the number of CNOT gates by one and introduces two extra single-qubit gates. In the noisy quantum systems, the gate error of a CNOT gate is usually much higher than the accumulated error of two single-qubit gates. For example, on ibmq_16_melbourne, the single-qubit gate error rates range from 10 −4 to 10 −3 while the two-qubit CNOT gate's error rate is 10 −2 [43]. Moreover, the singlequbit gate U and U −1 may be canceled or merged during the subsequent compiler optimization passes where multiple single-qubit gates are fused into one single-qubit gate. In those cases, we essentially reduce the number of CNOT gates by one and do not introduce any additional gates.
Consider the special case where both |ψ and |π are in known pure states. We can always find a single-qubit unitary gate V to transform |ψ state to |π state, |π = V |ψ . Similarly, the inverse gate V −1 transforms the |ψ state to |π state, as shown in Equation 6. Therefore, we can substitute the SWAP gate with two single-qubit gates V and V −1 in this special case.

V. BASIS-STATE AND PURE-STATE OPTIMIZATION
Sections III and IV showcase that for CNOT and SWAP gates, if some input qubit states can be determined, the gates can be simplified. In this section, we generalize this optimization to more basis and pure states in the context of different types of quantum gates. We term such optimizations as quantum basis-state optimization (QBO) and quantum purestate optimization (QPO), respectively.

A. Optimizing Single-Qubit Gates
For single-qubit gates, if the input is in a particular basis state, they can be simplified. In particular, if the input state is an eigenstate of the gate and the eigenvalue is 1, i.e., |φ = U |φ the gate U can be removed, as shown in Equation 7. For example, an X gate with the input |+ has not effect and can be removed since |+ = X |+ .
Realistically speaking, the opportunity for such single-qubit gate optimization is limited in useful quantum programs. However, it lays the foundation for QBO for multi-qubit gates.

B. Optimizing CNOT
Since the CNOT gate is the essential component to entangle qubits, we first focus on the basis states that have special effect on CNOT gates. For CNOT gates, the observation from Equation 1 can be generalized to other basis besides |0 . These basis states include |0 , |1 , |+ , and |− . The CNOT gates can be optimized when their control qubits are in |0 or |1 state or when their target qubits are in |+ or |− state. We list all the possible combinations and the corresponding optimized circuits in Table I, where represents a state, which is not the X-or Z-basis (|+ , |− , |0 , |1 ).
When the target qubit is in the |+ state, i.e., |0 +|1 √ 2 , the X gate has no effect as |+ is its eigenstate with eigenvalue of 1, i.e., |+ = X |+ . Therefore, the CNOT gate can be replaced with wires no matter what state the control qubit is in. On the other hand, if the target qubit is in the state |− , i.e., |0 −|1 √ 2 , the CNOT gate may be replaced with a wire on the target qubit and a Z gate on the control bit. The derivation is in Appendix B.
Furthermore, the Z gate can be eliminated when the control qubit is known to be in |0 state. Since |0 state is the eigenstate of Pauli matrix Z with eigenvalue equals to 1, applying the Z gate will not change the state: Similarly, we derive the optimized SWAP gate for X-and Z-bases input combinations, which are shown in Appendix F. This optimization can be seen as a particular case of QPO, since a basis-state is also a pure-state. However, implementing QBO separately is more efficient, since it requires fewer changes in the circuit. We also derive similar simplifications to Table I for the controlled-Z gates with inputs in the Z-basis states (|0 , |1 ).

C. Optimizing Multi-Qubit Gates
Besides CNOT gates and SWAP gates, QBO and QPO can be generalized to optimize a broader range of quantum gates.
First, QBO for CNOT gates can be generalized to optimize the multi-controlled NOT gates. The optimization of multicontrolled NOT gates with some known inputs can be derived as follows. 1) If any of the control qubits is in the |0 state, we can remove the multi-controlled NOT gate. 2) If any of the control qubits is in the |1 state, we can remove the control qubit and substitute the gate using a multi-controlled NOT gate with one less control qubit. 3) If the target qubit is in |+ state, we can remove the multi-controlled NOT gate. 4) If the target qubit is in |− state, we can substitute the gate with a multi-controlled Z gate with the target on any of the previous control qubits. In our study, we find that Toffoli gates are widely used in quantum algorithms. A Toffoli gate is a NOT gate with two controlled qubits. Equation 8 presents the optimizations for the Toffoli gate. The open controlled NOT gates can also be optimized using a similar approach as discussed is in Appendix C.
Second, the optimization of multi-controlled NOT gates can be further generalized to multi-controlled unitary gates. When the control qubits are in |0 or |1 , the optimization rules are the same. Assume the unitary gate U has eigenstates |ψ + and |ψ − with eigenvalues of 1 and -1, respectively. We have |ψ + = U |ψ + and |ψ − = −U |ψ − . When the target qubit is in |ψ + and |ψ − the optimization rules are the same as the rules for multi-controlled NOT gates with respect to |+ and |− states.
|π |π |φ |φ |ψ |ψ Third, QBO/QPO for SWAP gates can also be extended to the Fredkin gate (aka CSWAP gate) and multi-controlled SWAP gates. A Fredkin gate is a controlled SWAP gate with a single control qubit. A Fredkin gate can be decomposed into two CNOT gates and a Toffoli gate. The decomposition is included in Figure 14 in Appendix D. In the same way, multicontrolled SWAP gates can be decomposed into two CNOT gates and a multi-controlled NOT gate. If the control qubit |ψ is in the |0 state, we can remove the Fredkin gate. If it is in the |1 state, we can substitute the Fredkin gate with a SWAP gate. If any of the target states |ψ or |π is in a known basis state, we can optimize the first CNOT gate accordingly. If both of the target states |ψ and |π are in known pure states, following the optimization in Equation 6, we can substitute the Fredkin gate with two controlled U gates, as shown in Equation 9, where gates U and U −1 have the relationship |π = U |ψ and |ψ = U −1 |π . Since a Toffoli gate can be implemented with six CNOT gates and eight single-qubit gates [37], the Fredkin gate would need eight CNOT gates and eight single-qubit gates following the decomposition in Figure 14. In comparison, a controlled-U gate can be implemented with at most two CNOT gates and four single-qubit gates [39]. Therefore, our optimized Fredkin gate in Equation 9 would require at most four CNOT gates and eight single-qubit gates. As a result, our proposed QPO reduces at least four CNOT gates for a Fredkin gate with known pure-state inputs.

D. Optimizing Qubit blocks
Our proposed QPO can be further generalized to optimize two-qubit blocks. A sequence of uninterrupted two-qubit gates is considered as a two-qubit block [3]. The Qiskit transpiler optimizes these blocks by calculating the unitary matrices of these blocks and resynthesizing them using the KAK decomposition [23], [24]. Generally speaking, a two-qubit block can decomposed to a circuit consisting of at most three CNOT s and eight single-qubit gates [47] as shown in Figure 3. If the two input qubit states |ψ and |π are in known pure states, the compiler can calculate the output state |φ statically. Existing research [29] has proved that any two-qubit state can be prepared by a CNOT gate and four single-qubit gates. It means that we can substitute the two-qubit block with the state preparation circuit shown in Figure 4. As a result, we reduce the number of CNOT gates by two and the number of single-qubit gates by four.

Fig. 4: Universal circuit for preparing quantum state |φ
The optimization of the two-qubit block can be generalized to n-qubit blocks. If we know the input state and the output state of an n-qubit block, we can use the state preparation circuit to substitute the original circuit. It has been proved that preparing a quantum state can require less CNOT gates than preserving the unitary matrix [34].

VI. QUANTUM STATE ANALYSIS A. Basis-State Analysis
For the purpose of applying QBO, we implemented a state automata, partially shown in Figure 5, to track the basis state of  Figure 5). Any other gate or operation (except special cases for SWAP , SWAPZ , and RESET ), denoted as U , would change the state of the qubit to the unknown non-basis state . That is represented in the automata graph only with the |0 example but the same applies to all the other states.
As quantum processors are initialized in its lowest-energy state known as ground state, all the qubits start in state |0 . The half-and quarter-turn gates transform basis states into basis states. For example, the Hadamard gate H (a half-turn gate) moves the Z-basis into the X-basis and vice versa. The loop transitions in each node indicate a gate with no effect on that state, i.e. it is the eigenstate with an eigenvalue of 1, as explained in Section V-A.
The instruction RESET turns any state into the zero state. In Figure 5, that is illustrated as the only transition able to downgrade from to |0 . The annotation instruction ANNOT , to be discussed in subsection VI-C, can transit between different states. Essentially, it can be used to change the state from to a basis state, as exampled with the edge between and |1 .
The basis-state analysis also considers the effect of SWAP and SWAPZ . When they are encountered, the states of the involved qubits are swapped, including . Fig. 6: Automata for pure-state analysis As QBO, QPO requires a pure-state analysis to track the single-qubit pure states. A single qubit is in pure state when it is not entangled with the other qubits. Any single-qubit pure state can be represented by a state vector with two parameters θ and φ, |ψ(θ, φ) = cos( θ 2 ) |0 + e iφ sin( θ 2 ) |1 . Knowing the pure state |ψ(θ, φ) , we can use a single-qubit gate u3(θ, φ, 0) to generate this state from |0 state, |ψ(θ, φ) = u3(θ, φ, 0) |0 . Therefore, we choose these two parameters to record the single-qubit pure state information. In our analysis, each qubit associates a tuple (θ, φ). When the qubit is not in pure state, the parameters are set to .
When a multi-qubit gate is applied to the qubits in pure state, the output might be in mixed state. Therefore, the resulting states are marked as for each implicated qubit. The RESET instruction will reset the qubit back to ground state (0, 0). The ANNOT (θ, φ) annotation, to be discussed in subsection VI-C, will transform the qubit to pure state (θ, φ). The transitions among these states are illustrated by the automata in Figure 6. Similar to the basis-state analysis, our pure state analysis considers SWAP and SWAPZ gates. When they are encountered, the pure states of the involved qubits are swapped, including .

C. State Annotation
Determining whether a generic quantum state is entangled is an NP-hard problem [17]. In general, it is hard to infer information about the states from a quantum circuit using a classical machine efficiently. However, based on the understanding of the quantum program, the programmer can provide information to facilitate state analysis. For example, in quantum networks for elementary arithmetic operations [44], the network uses reverse computation to unentangle and reuse qubits. The programmers know these qubits are unentangled after reverse computation and they can annotate that these qubits are in particular pure states. Another example is, "clean" ancilla qubits are commonly used in quantum computing. The "clean" ancilla qubits are in |0 state and can be reused after the gate. As shown in Figure 7, after the multi-controlled Toffoli gate, the ancilla qubit remains to be in state |0 . To leverage such user-level information, we introduce annotations, which inform the compiler that the qubits are in certain quantum states. For example, in the pure state analysis, we use the annotation ANNOT (θ, φ) to indicate a quantum state is  Fig. 7: 4-qubit Grover's algorithm using multi-controlled Z gates with "clean" ancilla qubits and annotations in pure state |ψ(θ, φ) . The programmer can insert annotations based on the understanding of the quantum program. The annotations can also be inserted by the compiler automatically. For example, when the programmer uses the gate design with "clean" ancilla qubits, the compiler may automatically insert annotations ANNOT (0, 0) for such ancilla qubits. By introducing the annotations, we can avoid the complex quantum state analysis and improve the scalability of our proposed optimization pass.

VII. METHODOLOGY A. Compiler Implementation
We implemented our QBO and QPO passes on the opensource quantum computing framework Qiskit 0.18 [3] and our implementation is publicly available 1 . Qiskit organizes the transpilation passes in pass managers and it currently includes four pass managers for each level of optimization. The level 3 provides the maximal optimization at the expense of longer transpilation time. As part of our implementation, we extended the pass manager for level 3 to include our optimizations. Figure 8 outlines the sequence of passes in level 3 and the additions (underlined) that we introduced. The input circuit is run through the QBO pass first. The effect of this early optimization cascades in the rest of the pass manager, since any reduction in the gate count will improve the speed and effectiveness of subsequent passes. Additionally, QBO checks basis states of the SWAPZ gates in the input circuit, if there are any. If the condition in Equation 4 does not hold for a specific SWAPZ gate, the gate is decomposed into 2 CNOT gates, following the definition from Equation 3. This guarantees that the SWAPZ gates from this point on are semantically equivalent to SWAP gates. After the SWAP gates are inserted during the routing process (line 4) a new pass of QBO (line 5) optimizes those inserted SWAP gates. In line 6 and 7, we reuse existing Qiskit functionalities, Unroller and Optimize1qGate to prepare for the QPO pass (line 8). The Unroller pass decomposes all the circuit gates into the list of gates defined by the parameter. The variable basis_gates is a list of the primitive gates supported by the quantum device. In line 8, the list is extended with the gates SWAP and SWAPZ , since QPO understands them. The Optimize1qGates pass merges the single-qubit gates into 1 QBO() 2 Unroller(basis_gates) 3 <layout selection> 4 <routing process> 5 QBO() 6 Unroller(basis_gates + swap + swapz) 7 Optimize1qGates() 8 QPO() 9 while not <fixed point>{ 10 <optimizations>}

B. Benchmarks and System configuration
To evaluate our proposed compiler optimization, we run our experiments upon the following algorithms: Bernstein-Vazirani algorithm: A blackbox function f (x) is guaranteed to be the dot product between x and a bit string s: f (x) = x · s. Given an oracle that implements f (x), the algorithm finds the hidden bit string s with a single evaluation.
Quantum Phase Estimation (QPE) algorithm: QPE estimates the phase of an eigenvector of a unitary matrix. Given a quantum state |ψ which is the eigenvector of a unitary matrix U , U |ψ = e 2πiθ |ψ , QPE estimates the phase θ.
VQE algorithm: Variational Quantum Eigensolver (VQE) is a hybrid quantum/classical algorithm which finds the eigenvalues of a matrix H . In the VQE algorithm, the circuit for preparing the quantum state is called anstaz. We use the VQE program and the hardware-efficient ansatz RY from Qiskit Aqua [3]. In our experiment, we use the VQE algorithm to solve the Max-Cut problem [15].
Quantum Volume: Quantum volume [10] is a metric for characterizing quantum system performance. It is calculated by taking various quantum computer features into account, such as gate error, and connectivity. The quantum volume circuit is randomly generated with a fixed but generic form.
Grover's search algorithm: Given a set X of N elements and a boolean function f : X → 0, 1, Grover's algorithm finds an element x i in X such that f (x i ) = 1.
Since the RESET is currently not supported by the IBMQ quantum hardware, none of the circuits used in our experiments include the RESET instruction. We run our experiments with connectivity maps and noise properties from three different quantum computers, a 15-qubit quantum computer ibmq_16_melbourne, a 20-qubit quantum computer ibmq_almaden, and a 53-qubit quantum computer ibmq_rochester. The connectivity maps of these three quantum computers are shown in Figure 9. We compare our optimization pass with the hoare logic pass [2] implemented in the Qiskit transpiler. For a fair comparison, we append the hoare logic pass to the level 3 pass manager. We also run our experiments on these real quantum computers to evaluate the fidelity rate improvement from our compiler optimization.
Each circuit was transpiled several times to mitigate the effect of corner cases given the non-deterministic nature of Qiskit transpiler. For example, the StochasticSwap routing pass included in Qiskit returns significantly different results depending on the random seed and the input circuit. The reported CNOT gate count and the transpilation time are the medians of twenty-five (25) transpilation results. The reported median CNOT gate count is very close to the average CNOT gate count. We use the geometric mean to calculate the average ratio of CNOT gate reduction.  In this section, we first show a case study on the Bernstein-Vazirani algorithm, for which our optimization pass will optimize the boolean oracle with CNOT gates into phase oracle with single-qubit gates. Then, we provide case studies on four widely used algorithms namely the quantum phase estimation (QPE) algorithm, variational quantum eigensolver (VQE) algorithm, quantum volume benchmark, and Grover's algorithm. Subsequently, we show the annotations improve the scalability of our optimization. Next, we study the impact of the backend connectivity on the optimization. In the end, we run the experiments on real quantum computers to show the success rate improvement with our optimization.

A. Bernstein-Vazirani Algorithm
Circuits implementing the Bernstein-Vazirani Algorithm are used extensively for benchmarking in recent quantum computing researches [40]- [42]. QBO has a particular effect on this algorithm implementations that is noteworthy.
The oracle that implements the function f (x) can be represented in two different ways. The boolean oracle method converts an irreversible computation to a reversible one [7]. The other method is to use phase oracles [22], encoding f (x) into phase amplitudes. The phase oracle for the Bernstein-Vazirani algorithm can be done with only Z gates [12]. Figure 10 shows two different implementations of 4-qubit Bernstein-Vazirani algorithm with hidden bit string s = 1011.
The first design requires an extra ancilla qubit and CNOT gates. The second design only includes single-qubit gates and  it is more feasible for noisy quantum systems. Notice that the ancilla qubit is in the |− state. Following the discussion in Section V-B, our QBO pass substitutes the CNOT gates with Z gates and the optimized circuit is the same as the design with phase oracle. In other words, QBO converts the design in Figure 10a into Figure 10b. We found that our optimization can optimize the costly boolean oracle to a design which has the same cost as the phase oracle. Besides the Bernstein-Vazirani algorithm, the boolean oracles for the Grover's algorithm [13] and general cases [33] can also be optimized by our pass. In comparison, such boolean oracles can't be optimized by the Qiskit compiler or the hoare logic pass.

B. Quantum Algorithms
In this section, we consider four practical quantum algorithms: quantum phase estimation, VQE, quantum volume, and Grover's search algorithm. We compare RPO against the Qiskit compiler with optimization level 3 and the optimization level 3 with hoare logic pass, using the backend properties from ibmq_16_melbourne, which has 15 qubits. The median of CNOT gate count and transpilation time are shown in Table II. For all of the circuits, the resulting CNOT gate count of our pass manager is less than or equal to that of level 3. For most of the circuits, the compilation time of our pass manager is shorter than that of level 3, even though we included extra optimization passes. This is due to the early QBO, which cascades its effect to the rest of the passes in the pass manager. Since any reduction in the gate count will improve the subsequent passes, the overall compile time can be reduced. Our RPO pass results in more efficient circuit design and less compile time compared to the hoare logic pass. By checking the optimized circuit, we found that all the gates that are optimized by the hoare logic pass can be captured by our RPO pass. The median of single-qubit gate count and circuit depth are shown in Table V in Appendix E. As we can see from Table V, both the single-qubit gate count and circuit depth are improved as a result of our optimization.
For the QPE algorithm, when the logical circuit is decomposed to the basic gates, some of the CNOT gate can be optimized by our compiler pass. Therefore, our optimized circuits have lower CNOT gate count for all different numbers of qubits. Notice that our optimization has a significant impact for the shallow circuits. For the 4-qubit QPE algorithm, our optimization reduced the CNOT gate count by 25%. On average, our optimization leads to 18.0% decrease in the CNOT gate count and 5.5% decrease in the transpilation time for the QPE algorithm.
For the VQE algorithm, we use the hardware-efficient ansatz RY as the circuit design. The hardware-efficient ansatz is concise which limits the possible optimizations. However, when mapped to the physical qubits, the compiler introduces extra SWAP gates. Therefore, it is still possible to optimize the circuit. As the number of qubit increases, the number of CNOT gate optimized by our pass also increases. However, when the qubit count is close to the total number of qubits in the device (for this case 15), all the qubit will quickly fall into the non-basis/pure state , and our optimization only optimized a small amount of CNOT gates. In the best case, our optimization reduced the CNOT gate count by 16% for the 4-qubit VQE algorithm. Our optimization leads to an average of 5.8% decrease in the CNOT gate count and 7.7% decrease in the transpilation time for VQE algorithm.
For the quantum volume benchmark, since it is a randomly generated benchmark, the qubits are entangled and it is difficult to analyze the quantum states. Nevertheless, our optimization remains effective.
Since the long compile time may cause compilation failure, we only compile one iteration of the Grover's algorithm. In the 14-qubit case, the hoare logic pass failed due to long compilation time. On average, our optimization reduces the SWAP gate count by 2.4% and the transpilation time by 7.3%.
Across these four benchmarks, our optimization reduces the CNOT gate count by 11.7%/4.5% and the transpilation time by 7.1%/40.0% on average compared to Qiskit level 3 and Hoare logic, respectively.

C. Quantum Algorithm with Annotations
In this section, we use the Grover's algorithm to demonstrate that annotations can significantly improve the scalability of our optimization. It is a common practice to use quantum gates with ancilla qubits. Introducing ancilla qubits can significantly reduce the circuit size. For example, when using the multi controlled Toffoli gate without ancilla qubits, the 8-qubit grover's algorithm circuit consists of approximately ∼ 1500 CNOT gates. We can use another design which requires six  Figure 7, we can add annotations for the "clean" ancilla qubit. The n-qubit Grover's algorithm requires O( √ 2 n ) iterations to maximize the probability amplitude of the correct output. Each iteration consists of an oracle and a diffusion operator. We use the multi-controlled Toffoli gate with ancilla qubits and test the 8-qubit Grover's algorithm with different number of iterations. The experiment results of different optimization passes are shown in Table III. Without annotations, after first few iterations, all the qubits will fall into the non-basis/pure state . Therefore, CNOT gate count reduced by RPO is ∼ 30 regardless of the number of iterations. By introducing annotations, the qubits can transfer from back to basis/pure state. For the 2-iteration case, our optimization reduced the CNOT gate count by 10.8%. When the number of iteration is greater than eight, our optimization reduced a constant fraction ∼ 7.4% of the CNOT gate count.   SWAP gates are introduced when the compiler performs the logical-to-physical mapping. When the backend has limited connectivity, the logical-to-physical mapping will introduce more SWAP gates. Therefore, our optimization pass has a higher chance to optimize the quantum circuit.
We compile the QPE program with connectivity maps from three different quantum computers. These connectivity maps are shown in Figure 9. Among these quantum computers, ibmq_16_melbourne has the best connectivity and ibmq_rochester has the worst. The experiment result of QPE on ibmq_16_melbourne is shown in Table II in the previous section. The results of QPE on ibmq_almaden and ibmq_rochester are shown in Table IV. 2 . From these results, we can see that our optimization is effective on all these quantum computers. Another interesting observation is that, the worse connectivity the quantum computer has, the higher total CNOT gate count, and the more CNOT gates will be optimized by our optimization. The percentage of CNOT gates reduced by our optimization are 18.0%, 15.2%, and 20.6% for ibmq_16_melbourne, ibmq_almaden and ibmq_rochester respectively. The percentage of transpiled time reduced by our optimization are 5.5%, 5.3%, and 4.6%.

E. Experiment on Real Quantum Computers
We ran the 3-qubit QPE algorithm on real quantum computers to highlight the effectiveness of reducing CNOT gates. The output distribution is shown in Figure 11. The correct output should be 111. Since the circuit depth for 3-qubit QPE is shallow, the different quantum computer connectivity doesn't lead to too much difference in the total CNOT count. The gate error and measurement error of different devices have higher impact on the final output distribution. Although the circuit running on ibmq_16_melbourne has the least CNOT count, the fidelity of that circuit is not the best. Without our optimization, we cannot even infer the correct result on both ibmq_16_melbourne and ibmq_almaden. Our optimization reduces the CNOT gate count by 33%, 29%, and 28% and leads to success rate improvements of 2.94X, 2.69X, and 1.53X on ibmq_16_melbourne, ibmq_almaden, and ibmq_rochester, respectively. The average success rate improvement (geometric mean) is 2.30X for 3-qubit QPE algorithm.

IX. CONCLUSIONS
In this paper, we propose a fast and effective compiler optimization named relaxed peephole optimization. Based on this optimization we designed two compiler optimization passes, QBO and QPO, and implemented them in the IBM's Qiskit transpiler. We show that our optimization pass is faster than the most aggressive optimization level in the Qiskit, and the circuits optimized by our optimization pass also have fewer CNOT gates. Our experiments on the real quantum computers highlight that the reduction in CNOT gate count leads to a significant improvement in the circuit success rate.  Figure 12, the CNOT gate is equivalent to a controlled-Z gate with two Hadamard gates on the target qubit. When the target qubit of the CNOT gate is in |− , after the Hadamard gate, the target qubit is in |1 state. The controlled-Z gate can be optimized into a Z gate, and the two Hadamard gates will be cancelled out. Therefore, the CNOT gate can be substituted with a Z gate on the control qubit.

APPENDIX C CLOSED AND OPEN CONTROL
An open control gate is equivalent to a closed control gate with two NOT gates on the control qubit, as shown in Figure 13. In our paper, we discussed the optimization for the closed control gates. For the open control gates, we can use this equivalence to convert them to the closed control gates and then apply our optimization. The decomposition of Fredkin gate is shown in Figure 14

APPENDIX E ADDITIONAL EXPERIMENT RESULTS
The detailed experiment results for QPE, VQE, quantum volume, and Grover's algorithms are included in Table V.