: Identifying the Most-Critical
Gate Operations in Quantum Circuits
via Amplified Gate Reversibility

Tirthak Patel
Northeastern University
Boston, MA, USA
Daniel Silver
Northeastern University
Boston, MA, USA
Devesh Tiwari
Northeastern University
Boston, MA, USA

Author's copy (but also published in SC'22)

When quantum programs are executed on noisy intermediate-scale quantum (NISQ) computers, they experience hardware noise; consequently, the program outputs are often erroneous. To mitigate the adverse effects of hardware noise, it is necessary to understand the effect of hardware noise on the program output and more fundamentally, understand the impact of hardware noise on specific regions within a quantum program. Identifying and optimizing regions that are more noise-sensitive is the key to expanding the capabilities of NISQ computers.

Toward achieving that goal, we propose , a novel technique to pinpoint specific gates and regions within a quantum program that are the most affected by the hardware noise and that have the highest impact on the program output. Using 's methodology, programmers can obtain a precise understanding of how different components of their code affect the output and optimize those components without the need for non-scalable quantum simulation on classical computers.

Quantum Computing, NISQ Computing, Quantum Error Detection, Quantum Error Mitigation

§ INTRODUCTION TO

The field of quantum computing, which has applications in many areas, such as high-performance computing (HPC), has seen considerable advancement recently. While the hardware has been increasing in size, individual qubits still remain quite noisy. These noise effects include errors that are generated due to qubit state decoherence, qubit state preparation and measurement, gate operation, and cross-talk among neighboring qubits [43, 39]. Due to these noise effects, when a quantum program is executed on these noisy intermediate-scale quantum (NISQ) computers, the program output experiences a considerable error [43, 39, 30, 8, 59].

As practical hardware error correction has not been widely implemented on NISQ computers in a cost-effective manner [55, 53, 48, 24], recent software efforts have attempted to reduce the output error using software-level compiler optimizations [27, 6, 50, 14]. These software efforts rely on relatively simple noise models – for example, individual-qubit noise data generated during qubit calibration [52, 40] – to obtain the decoherence times and error rates of gate operations on individual qubits. This data is then used to perform just-in-time compilation to best map the logical quantum program to the physical quantum computer in a manner that reduces the number of gate operations and potentially reduces the overall error in the output of the program [58, 38, 52, 35, 40].

[Location of Two-Qubit Gates][Error of Each Gate]

(a) The same two-qubit gate run on the same qubits for the Quantum Fourier Transform (QFT) program. (b) The gate has a different error impact on the program output each time it is run (expressed as Total Variation Distance (TVD) on the Y-axis – refer to Sec. <ref> for more methodological details).

However, due to the difficult-to-model complex interactions of the different noise characteristics, how different quantum program components contribute to the overall output error of a quantum program can vary from program to program and program region to program region [39, 30, 8, 59]. Fig. <ref> shows the error impact of a two-qubit gate being run on the same pair of physical qubits at five different times during the program execution. These results show that the magnitude of impact on the program output of the same gate is quite different depending on its position in the program (i.e., the TVD changes depending on the location of the erroneous two-qubit gate operation). The fundamental reason behind our observation is that the crosstalk and interference from gates being applied to neighboring qubits affects a particular gate operation's impact on the error in the program output. Unfortunately, quantifying, characterizing and modeling this complex effect is challenging, and currently, the HPC quantum systems community does not have the appropriate methodology and tools to determine how the specific components/regions of a quantum program contribute to its output error. Novel methods and tools in this domain will enable further program-specific compiler optimizations and debugging support.

: In order to address the above challenges, this paper proposes , a simple yet effective method to compute how specific gates within a program contribute to its overall output error.  enables the programmer to pinpoint specific gate operations and regions within a quantum program that are the most affected by the hardware noise and that have the highest impact on the output error of the program. The spirit of this effort is similar to development of program vulnerability factor (PVF) and architecture vulnerability factor (AVF) for classical computing systems [47, 34] – however, developing similar closed-form models for highly accurate vulnerability assessment for quantum circuits is not possible.

The key insight behind  is to leverage the reversibility property of quantum computing to understand the impact of individual quantum gate operations on the observed error in the program output.  is the first method to leverage the quantum circuit reversal to identify and quantify the criticality of individual quantum gate operations on the program output error (Sec. <ref>).  demonstrates how to systematically reveal the impact of individual quantum gate operations without the need to perform quantum simulation on classical computers, which is not scalable to large programs [12, 23, 22, 25].  breaks this barrier and demonstrates how quantum programmers can identify the most critical operations on erroneous NISQ hardware without relying on expensive simulation of quantum programs. Using 's methodology, programmers can identify particularly problematic program regions and focus their debugging and optimization efforts on those areas.

A prior technique, Qraft [41], demonstrated the use of the quantum circuit reversibility toward improving the answer fidelity of quantum programs on the NISQ computers (i.e., circuit reversal as a noise-mitigation technique). This work, , demonstrates another unique and useful application of quantum circuit reversibility – estimating the high-impact quantum circuit components. Qraft reverses the full quantum circuit to mitigate the noise and estimate correct program output [41]. Unlike, Qraft,  considers the quantum circuit as a series of smaller circuit gate operations, and applies quantum circuit reversal at the gate-level.  demonstrates the significance of applying circuit reversals multiple times for a given circuit gate and across multiple circuit gates – which is necessary to identify the high-impact program components.

The contributions of this work are as follows:

* The proposed technique, , is a simple and effective way to determine high-error-impact gate operations and regions in any given quantum program using quantum reversibility property. It gives programmers a scalable utility to perform optimizations that are specific to their program structure, as opposed to relying on simplistic assumptions and noise models.

*  is evaluated using multiple quantum programs of varying characteristics and sizes. These results have revealed some surprising, interesting, and useful trends:

+ While most existing works have primarily focused on ranking the criticality of qubits based on their error rates [58, 38, 52, 35, 40],  demonstrates that prior approaches alone are not always sufficient and complete. Type and location of gate operations are equally critical. Across different algorithms, the top 25% high-impact gates are located on almost all qubits used to run the program, which indicates that criticality of gates varies more based on the gate's position in the circuit.

+ Prior techniques have largely focused on specifically reducing two-qubit gates [46, 65, 56, 3, 42], as they generally have a high error in isolation. Interestingly,  reveals that, in some cases, one-qubit gates can have worse impacts on the output error.

+  demonstrates that the error impact of specific gates can vary depending on the input to the program. For example, input $i$ can increase the error impact of gates in a certain region of a quantum program, while input $j$ can affect a different region. This observation opens up the opportunity for input-aware quantum compilation.

+ We provide a technique to identify the program input with the highest impact on the output error by extending  to multi-gate reversals. Based on this identification, we propose the use of selective serialization of high-impact gates to reduce the effect of crosstalk, which reduces output error by up to 7% points.

+  shows that the gates near the end of the program do not always have the worst impact, although some existing techniques optimize those regions due to the assumed impact of qubit state decoherence [28, 45], which increases as program length increases [32, 54].

* 's code to apply reversals and use them for characterization, and its evaluation datasets are  open-sourced at .

§ RELEVANT BACKGROUND FOR

[Quantum Gates][Quantum Circuit]

(a) A set of one- and two-qubit basis gates is used to perform universal quantum computation on IBM computers. (b) An example three-qubit quantum circuit with gates applied from left to right. The qubit state evolution is represented using horizontal lines; at the end of the quantum computation, the measurement operations are applied to read the qubit state.

Quantum States, Gates, and Circuits. The computational state of a qubit can be represented using a superposition of the $\ket{0}$ and $\ket{1}$ basis states: $\ket{\psi} = \alpha_1\ket{0} + \alpha_2\ket{1}$. Here, $\ket{\psi}$ is the superposed state of the qubit and $\alpha_1$ and $\alpha_2$ are complex coefficients such that $\norm{\alpha_1}^2 + \norm{\alpha_2}^2 = 1$. Similarly, the superposed and entangled state of an $n$-qubit quantum system can be represented as: $\ket{\psi} = \sum_{k=0}^{k=2^n-1}\alpha_k\ket{k}$ such that $\sum_{k=0}^{k=2^n-1}\norm{\alpha_k}^2 = 1$. When the qubit state is measured, the state superposition collapses and it can be found in one of the $2^n$ states, with the probability of finding it in state $k$ being $\norm{\alpha_k}^2$.

Qubit states are prepared by applying quantum gates or operations. Quantum gates are unitary operations that evolve the state of the qubit from one state to another. For example, the  quantum gate flips the state of the qubit from $\ket{0}$ to $\ket{1}$ and from $\ket{1}$ to $\ket{0}$. A set of universal quantum basis gates can be used to represent all quantum gates. The specific choice of basis gates depends on the hardware. For example, the IBM quantum computing hardware, which is used to evaluate , uses the , , , and  gates to form the universal basis set. As Fig. <ref>(a) shows, , , and  are one-qubit gates, and  is a two-qubit gate. The  gate is the qubit-flip gate, the  gate performs the square root operation of the  gate, and the  gate is a virtual gate that changes the frame of reference of the quantum system (it is not performed on the physical hardware). The two-qubit entangling  gate performs the  operation on the “target” qubit depending on the state of the “control” qubit as shown in Fig. <ref>(a).

When these quantum gates are performed in succession of one another on an $n$-qubit system they form a quantum program, also known as a quantum circuit. While a quantum program can be written using any high-level quantum logic gates, the program then has to be mapped to the hardware-compatible physical basis gate set in order to execute the circuit on a quantum computer. Fig.  <ref>(b) shows an example three-qubit quantum circuit with nine operations. Once all the operations are executed, the measurement operator is applied to all the qubits to generate the output state.

Different types of noise effects that NISQ computers experience when running a quantum circuit.

Noise Type     Description

Operation Errors [15, 44]     Errors caused by inaccuracies in applying a specific desired quantum gate.

State Preparation and Measurement Errors [51]     Errors caused when initializing and preparing the qubit state and measuring the final state after execution.

Decoherence Effects [32, 54]     Errors caused due to the prepared qubit superposition state decaying over time to the ground (i.e., $\ket{0}$) state.

Crosstalk Effects [36, 60, 61]     Errors caused to a qubit due to interference effects from neighboring qubits.

(a) The Total Variation Distance (TVD) between two probability distributions is measured by summing the differences in state probabilities of the two distributions and dividing by two. (b) The reverse versions of the basis gates are depicted with dashed borders in this paper.

Hardware Noise Effects. A NISQ computer experiences a variety of noise effects when a quantum program is initialized, executed, and measured. These noise effects have been summarized in Table <ref>. These noise effects are challenging to model; especially the impact of their combined expression is difficult to simulate or predict [15, 43, 8]. When a quantum circuit is run, these individual noise effects compound and accumulate to cause error in the output of the program.

Quantum Output and Output Error. The output of a quantum program is obtained as a probability distribution over its output states. The same quantum state is prepared and measured multiple times (each measurement producing one output state), which then generates the probability distribution over the output states. However, because of the hardware noise effects, this observed output distribution can be quite different from the ideal or correct output distribution. A typical metric that is used to measure the deviation of the observed output distribution from the ideal output distribution is the Total Variation Distance or TVD [17]. As shown in Fig. <ref>(a), the TVD between two probability distributions is calculated by summing up the absolute differences in the probabilities of the individual states and dividing by two. With a value between 0 and 1, the closer the TVD is to 0, the more the two probability distributions are similar. We will use this metric going forward to compare two probability distributions.

Quantum Reversibility Property. Unlike classical gates, all quantum gates are reversible. The input state can be obtained by applying the inverse of the original gate to the output state. Because all quantum gates can be represented using unitary matrices $U$, their inverse is simply the complex conjugate transpose (also known as the Hermitian adjoint) of $U$, which can be represented as $U^\dagger$. Therefore, for any initial state $\ket{\psi}$, if $U$ is applied to it, the initial state can be recovered by applying $U^\dagger$ ($\ket{\psi} = U^\dagger U\ket{\psi}$). In this paper, we represent the inverse of a quantum operation using a dashed line as shown in Fig. <ref>(b). QRAFT has leveraged this property for improving the answer fidelity of quantum programs on NISQ machines [41].  leverages this quantum reversibility property to identify high-impact circuit components.

§ 'S METHODOLOGY FOR EXPERIMENTS

Qubit connectivity layout of quantum computers (a)  and (b) .

Algorithms and benchmarks used for the design, evaluation, and analysis of .

Algorithm     Description

HLF     Hidden Linear Function [7]

QFT     Quantum Fourier Transform [37]

QAOA     Quantum Alternating Operator Ansatz [16]

VQE     Variational Quantum Eigensolver [33]

Adder     Quantum Adder Program [13]

Multiplier     Quantum Multiplier Program [18]

Heisenberg     Time-independent Heisenberg Hamiltonian [4]

TFIM     Transverse Field Ising Model [4]

XY     XY Quantum Heisenberg Model [4]

[ Gate Reversal][ Gate Reversal][Two  Gate Reversals]

Example of applying a reversed pair to one of the (a)  and (b)  gates. (c) Example of applying two reversals to the  gate. “Barriers” are used to ensure that other operations are not run in parallel with the reversed pair in order to isolate for the error impact of the gate in question (other qubits are kelp idle when the reversed pair is being executed).

Before we describe the design of , we first discuss the methodology to construct and execute the experiments used for the design, evaluation, and analysis of .

Experimental Setup. We use the IBM quantum cloud platform [11] to execute the experiments to evaluate . We use the corresponding Python-based (Python version 3.9.7) Qiskit programming language [1] (Qiskit version 0.17.4) to program the quantum algorithms and benchmarks and apply reversals for . We run the experiments on the 7-qubit  quantum computer and the 16-qubit  quantum computer (computer qubit layouts shown in Fig. <ref>), depending on the size of the algorithm being executed; algorithms of size seven qubits or less are run on  and the rest are run on . The quantum volume of both computers is 32; this metric measures the performance of gate-model quantum computers in terms of the size (width and depth) of the circuits they can run. Each experiment is run with 32,000 trials to generate the output probability. We use Qiskit's StateVector simulator to run simulations of the quantum programs on classical computers to get the ideal output of the programs. Note that this output is only used to validate the effectiveness of  and is not a part of the  technique. In fact,  is specifically designed to not rely on classical simulations in order to ensure scalability to large quantum algorithms. Python's SciPy package [21] is used to calculate statistical metrics such as correlation for the design and analysis of .

Quantum Algorithms and Benchmarks.  uses algorithms and benchmarks listed in Table <ref>, which have a variety of sizes (3-16 qubits) and use cases for high-performance computing. HLF is a search algorithm, while QFT is the quantum version of the Fourier transform. QAOA and VQE are quantum variational algorithms, and Adder and Multiplier are standard quantum arithmetic circuits. Heisenberg, TFIM, and XY are time-evolution Hamiltonian programs for material simulations. The TFIM model has non-zero coupling interaction between nearest neighbor spins along the $z$ axis, XY has for $x$ and $y$ axes, and Heisenberg has for all three axes. All algorithms are mapped to the physical quantum hardware using all of the compiler optimizations available via Qiskit, including noise-aware logical-to-physical mapping, gate routing and SWAP insertion depending on hardware connectivity, gate cancellation based on commutativity and combination, gate deletion by detecting redundancy, and gate re-synthesis for two-qubit unitary blocks (peep-hole optimization) [1]. All algorithms are converted to the {, , , } basis gate set (Fig. <ref>) during the mapping process to run on the IBM hardware. Once 's techniques are applied to the circuit, the compiler optimization level is set to 0 to ensure that the techniques are not optimized out, because  is applied to pre-mapped circuit and no additional compilation steps necessary.

Metrics. We use the TVD (described in the previous section: Sec. <ref>) to measure the difference between two probability distributions. To measure the correlation relationship between two random variables, we use the Pearson correlation [5], which is the square-root of the coefficient of linear regression ($R^2$). A value of 1 indicates a perfect positive linear correlation, $-1$ indicates a perfect negative linear correlation, and 0 indicates no correlation. We also show the $p$-value to show the significance of the correlation (a $p$-value $<0.01$ indicates a statistically strong correlation).

§ : DESIGN AND TECHNIQUE

Pearson correlation between the TVD of the output of the $r$-reversal runs with the output of the ideal simulation and the TVD of the output of the $r$-reversals runs with the output of the original run for different number of reversals ($r$). The number in brackets next to the algorithm name shows the number of qubits. The highest correlation is seen with five reversals.

2|c|One Reversal     2|c|Three Reversals     2|>[RGB]255, 200, 200c|Five Reversals     2|c|Seven Reversals

Algorithm     Correlation     $p$-value     Correlation     $p$-value     Correlation     $p$-value     Correlation     $p$-value

HLF (5)     0.02     0.91     0.08     0.58     0.40     6.85$e-$3     0.17     0.26

HLF (10)     0.11     0.06     0.18     0.12     0.49     3.04$e-$3     0.13     0.62

QFT (3)     0.43     3.69$e-$3     0.96     3.78$e-$24     0.99     2.18$e-$35     0.99     2.93$e-$40

QFT (7)     0.61     3.18$e-$31     0.61     9.21$e-$31     0.64     3.32$e-$34     0.63     2.93$e-$34

Adder (4)     0.52     3.29$e-$7     0.94     9.57$e-$41     0.98     3.97$e-$61     0.99     5.40$e-$68

Adder (9)     0.43     5.12$e-$56     0.89     5.89$e-$23     0.94     4.12$e-$43     0.95     2.31$e-$30

Multiply (5)     0.76     2.98$e-$17     0.96     1.32$e-$48     0.99     1.04$e-$67     0.99     7.85$e-$75

Multiply (10)     0.89     7.35$e-$221     0.89     1.45$e-$219     0.89     3.16$e-$220     0.88     7.20$e-$217

QAOA (5)     0.82     4.34$e-$35     0.70     1.13$e-$21     0.79     6.02$e-$31     0.80     1.80$e-$31

QAOA (10)     0.38     6.65$e-$15     0.35     4.21$e-$13     0.38     2.46$e-$10     0.30     1.11$e-$9

VQE (4)     0.51     1.69$e-$29     0.38     4.11$e-$16     0.21     9.97$e-$6     0.19     6.83$e-$5

Heisenberg (4)     0.69     2.29$e-$28     0.74     2.27$e-$29     0.90     4.75$e-$36     0.91     4.50$e-$47

TFIM (4)     0.70     1.09$e-$18     0.78     1.67$e-$25     0.88     4.70$e-$38     0.92     1.50$e-$49

TFIM (8)     0.38     1.37$e-$20     0.53     7.67$e-$16     0.71     7.05$e-$14     0.60     1.07$e-$12

TFIM (16)     0.42     2.73$e-$19     0.55     4.69$e-$18     0.72     8.14$e-$16     0.59     2.61$e-$13

XY (4)     0.49     6.50$e-$7     0.84     1.54$e-$26     0.91     2.13$e-$36     0.92     6.70$e-$39

XY (8)     0.67     0.11     0.76     3.87$e-$4     0.80     9.87$e-$6     0.89     5.44$e-$11

The core of 's design is grounded in the reversibility principle of quantum computing.  leverages this property by applying a pair consisting of the “reversed” gate and the “original” gate to each of the gates in the quantum circuit (referred to as the “reversed pair”). Fig. <ref> shows how this pair is applied to different operations: (a) the first  gate on qubit 0 and (b) the first  gate on qubits 1 and 2. This is done for each of the gates in the circuit. The original circuit has nine gates; therefore, a total of nine “reversed circuits” are generated, each with one reversed pair of gates corresponding to one of the gates in the original circuit. In general, $g$ reversed circuit are generated for a circuit with $g$ gates.

employs this method for two useful reasons. First, applying the pair of the reversed gate + the original gate to a gate $U$ does not alter the ground truth output of the circuit (on an ideal quantum computer). This is because of the reversible principle of unitary matrices: $U(U^\dagger U) = UI = U$. Therefore, applying this pair does not alter the mathematical functionality of the quantum program, and does not affect the output of the program. (2) However, due to the introduction of additional two operations within the reversed pair, this will impact the output error of the circuit when it is run on a real noisy quantum computer. This impact on the output error will be the amplified, but it will be proportional to the impact of the original gate. This is because the two gates in the reversed pair are operationally similar to the original gate, meaning they will experience the same operation errors. Moreover, the two gates in the reversed pair are also applied at the same location of the original gate, which means that they will also experience the same decoherence effects. Thus, the output of the original circuit (i.e., the circuit with no reversals) and the output of the circuit with the reversed pair can be compared to gauge the impact of the gate in question.

These outputs are compared in the following manner. Let $O_{orig}$ be the output of the original circuit. $O_{orig}$ is a probability distribution with probabilities $p^k_{orig}$ for each of the $k^{th}$ state in the $2^n$ states, where $n$ is the number of qubits. Similarly, let $O_{rev}$ be the output of the reversed circuit for a particular gate with $p^k_{rev}$ probabilities for each of the  $2^n$ states. The difference in these outputs can then be calculated using the total variation distance: $TVD\big{(}O_{orig},O_{rev}\big{)} = \frac{1}{2}\sum^{k=2^n-1}_{k=0} \Big{|}p^k_{orig}-p^k_{rev}\Big{|}$. Using this TVD,  can estimate the impact that a particular gate has on the output of a circuit. Note that this TVD is calculated between the noisy outputs of the original circuit and the reversed circuit. It does not rely on the output of an ideal quantum simulation, which is not scalable as it has to be executed on classical computers [12, 23, 22, 25]. Instead,  solely relies on noisy outputs of real-computer runs. To get the error impact of all the gates, the TVD can be calculated between the output of the original circuit and the reversed circuits corresponding to all the gates. Going forward, we refer to gates whose circuits have high TVD with the original circuit as “high-impact” gates as these are the ones of particular importance.

As a note, the TVD measures the relative error between the two output probability distributions. As a result, the absolute rates of errors unrelated to gate operations, including state preparation and measurement errors, remain the same for both of the circuits and therefore, do not affect 's results. Note also that this methodology of CHARTER is not affected by intermediate measurements and resets. For example, to gauge the impact of a particular gate before an intermediate measurement, one can apply reversals before the measurement. A gate can similarly be reversed after the intermediate measurement and its impact will be observed in the succeeding measurement.

Next, we look at why identifying high-impact gates in noisy environments is a challenge and how  mitigates it.

The number and percentage of  and  gates in different algorithms and their corresponding depths. The percentage of  gates in a circuit is high across algorithms.

Algorithm     Num. s     % s     Num. s     % s     Depth

HLF (5)     14     41%     10     29%     31

HLF (10)     62     22%     171     61%     79

QFT (3)     18     42%     9     21%     28

QFT (7)     121     42%     88     30%     141

Adder (4)     35     41%     24     28%     61

Adder (9)     99     28%     212     60%     209

Multiply (5)     32     37%     29     34%     58

Multiply (10)     206     31%     332     51%     321

QAOA (5)     51     37%     55     40%     84

QAOA (10)     107     26%     222     53%     173

VQE (4)     172     40%     132     31%     264

Heisenberg (4)     171     33%     201     39%     338

TFIM (4)     48     41%     33     28%     62

TFIM (8)     223     41%     137     25%     168

TFIM (16)     1032     36%     1000     35%     499

XY (4)     35     37%     31     33%     64

XY (8)     178     36%     149     30%     183

§.§ : Multiple Reversals for Noise Mitigation

While designing , we discovered that although the idea of gate-specific reversed circuits is intuitive and promising, it is often not as effective as expected in practice. This is because, due to the high noise levels on NISQ computers, applying one pair of reversals does not help us effectively identify the differences between the outputs of the two circuits with high statistical confidence – the TVD between the original circuit and the reversed circuit may be close to zero in some cases. This is especially true for large circuits with many qubits and gates as there is a large enough accumulated impact from other gates, so as to obscure the impact of one particular gate. To overcome this challenge,  designs a novel multiple-reversal technique.  applies the reversed pair multiple times in succession of one another. Fig. <ref>(c) shows how “two reversals” can be applied to the first  gate on qubit 0. We note that 's design does not require any additional effort in terms of calculating more reversals or running more circuits. In fact, only one reversed circuit still needs to be run per gate. However, the reversed circuit now contains multiple reversals in order to amplify the error impact of a particular gate on the output of large high-noise circuits.

However, the questions is: are multiple reversals effective and can we determine the number of reversals that are the most effective? We answer this question with experimental evidence. We compare the success of identifying the impact of gates for different reversals across the different algorithms and benchmarks. The success is measured by calculating the Pearson correlation between the TVD obtained by comparing the output of the original circuit and the reversed circuit (the metric we saw above: $TVD\big{(}O_{orig},O_{rev}\big{)}$) and the TVD obtained by comparing the ideal output with the output of the reversed circuit ($TVD\big{(}O_{orig},O_{ideal}\big{)}$). Because getting $O_{ideal}$ requires simulation, it is not practical to calculate as a part of 's technique. However, here we use it to validate the success of the technique. If  $TVD\big{(}O_{ideal},O_{rev}\big{)}$ is correlated with $TVD\big{(}O_{orig},O_{rev}\big{)}$ across all gates in a circuit, it means that both metrics produce the same relative impact scores for all the gates. This in turn implies that $O_{orig}$ can be used as a scalable alternative to $O_{ideal}$. So we calculate this correlation for different number of reversals and identify the number for which the correlation is the highest.

Table <ref> shows the results of these correlations across all the algorithms and benchmarks used for evaluating  for one reversal, three reversals, five reversals, and seven reversals (i.e., seven back-to-back reversed pairs). As the table shows, the correlation values for one reversal are low across different algorithms. In general, the three reversals observe a higher correlation than one reversal and five reversals observe a higher correlation than three reversals. Beyond five reversals, the correlation values either remain steady or drop slightly due to noise. For example, for the 5-qubit Multiply algorithm, the one reversal correlation is 0.76, for three reversals, it is 0.96, and for five and seven reversals, it is 0.99. On the other hand, for the 8-qubit TFIM algorithm, the one reversal correlation is 0.38, the three reversal correlation is 0.53, the five reversal correlation is 0.71, but for seven correlations, it drops down to 0.60. Based on this empirical evidence,  selected five reversals as it was experimentally confirmed to be effective at identifying the impact of the gates on the final output error. However, we note that 's design allows the number of reversals to be configurable and changed if needed. In our experience, the insights and trends generated by  are consistent for number of reversal beyond three.

As the above results show,  requires one run per gate in the circuit, which adds up as the number of gates increases. Therefore, next we look at how we can reduce the number of runs required to figure out the impact of gates.

Summary of the steps used for applying the  methodology to identify high-impact error-prone quantum gate operations in a quantum program circuit using individual-operation reversals.

§.§ : Reducing the Number of Runs

As  only takes $g$ circuit runs for $g$ gates operations, it only scales linearly in terms of the number of gate operations: its time complexity is $O(g)$. However, the number of runs can be further reduced if we consider the gate type. Recall that on IBM computers, the basis gates are , , , and . While , , and  are physical gates that are implemented on the quantum computers, the  gate performs a frame-of-reference change virtually and is not implemented on the
physical quantum computers [10]. Therefore, these gates have negligible to no impact on the output error of a quantum program (as we will also see in the evaluation section: Sec. <ref>). As a result, they can be disregarded for the purposes of characterizing the error impact of different gates and their reversed runs can be eliminated from consideration.

Table <ref> shows the percentage of all quantum gate operations that are the  operation across different quantum algorithms. The table also shows the percentage of  gates (the remaining gates are  or ) and the circuit depth (number of gates in the critical path of the algorithm circuit) for completeness. The table demonstrates that in general, around 20-40% of the gates in quantum algorithm tend to be  gates. For example, for algorithms like QFT (7) and TFIM (8), this the percentage of  gates can be as high as 42%. This directly implies that the number of runs required by  can be reduced by 20-40% in practice depending on the algorithm, even though the complexity remains $O(g)$ in the worst case.

Next, we summarize the overall approach of .

§.§ : Putting it All Together

In Fig. <ref> we summarize the different steps of .  takes the quantum program and maps it on to the quantum hardware and converts it into the hardware basis gates. Then for each of the gates, it generates reversed circuits, each with their own pair of the reversed gate + the original gate applied right next to the original gate. The pair application is repeated five times over to generate the best success in terms of identifying the high-impact gates in the circuit. This is done for all gates except for the  gates as these gates are virtual and have negligible error impact. The next step is to run the original circuit and all the reversal circuits on the quantum computers. Once the runs are completed, the TVDs between the original circuit and the reversed circuits can be calculated and the high-impact gates can be determined by identifying the reversed circuits with high TVDs.

In the following section, we evaluate the effectiveness of  in identifying such high-impact gates and derive some surprising and interesting insights in the process.

[QFT (3) Circuit for Output Hamming Weight One]

[QFT (3) Output Hamming Weight Zero][QFT (3) Output Hamming Weight One]

[QFT (3) Output Hamming Weight Two][QFT (3) Output Hamming Weight Three]

(a) The circuit structure of the three-qubit QFT algorithm. TVD of the three-qubit QFT circuits between the reversed circuits and the original circuit when it is run with input such that the output has a hamming weight of (b) 0, (c) 1, (d) 2, and (e), 3. The results show that depending on the input, the impact of the different gates in the circuit can vary.

§ : EVALUATION, ANALYSIS, AND INSIGHTS

This section is organized as following: we perform different types of analyses and present a summary of observations and insights for each of those. These analyses are performed for all the algorithms and benchmarks used for evaluation and general trends are highlighted. We also note diverging patterns when they are significant, and we provide strategies to mitigate the error impact of high-impact gates.

Before we present these general results, we first perform a detailed case study using the three-qubit QFT algorithm, in order to better appreciate the insights derived from the combined trends presented later. This case study includes a breakdown of the error impact of individual gates in the QFT algorithm and an examination of how this error impact varies with the input provided to the algorithm.

QFT(3) Case Study and the Influence of the Input. Fig. <ref>(a) shows the circuit structure of the three-qubit QFT algorithm. We see that the algorithm has 39 operations in total: 9 , 18 , 12 . So we run 39 reversed circuit runs + 1 original circuit run $=$ 40 runs (combined runtime of $<0.5$ hours on the IBM computers). We also see that the 39 operations are organized in 27 layers of parallel executions. Note that for this algorithm we also run the reversed runs for the  gates to demonstrate that the  gates have negligible impact (but, in general we do not need to execute the runs corresponding to the  gates). We calculate the 39 TVDs of the output of the reversed runs to the output of the original run.

Fig. <ref>(b) shows these TVDs. For easier interpretation, the figure has been structured into three sub-figures that show the results for the three qubits (qubit 0 at the top, 1 in the middle, and 2 at the bottom). The x-axis shows the layer at which the operation took place, corresponding to the layers indicated at the bottom in Fig. <ref>(a). The bars show the TVD for the individual gates on different qubits. The positions of the bars correspond to the positions of the gates in Fig. <ref>(a) (the bar colors also correspond to the operation colors). For two-qubit  gates, the bar is drawn twice on both the qubits. For example, the bar corresponding to the  gate on qubits 0 and 1 in layer 12 is drawn twice: at layer 12 on qubit 0 and at layer 12 on qubit 1. As the TVD ranges between 0 and 1, the y-axis of all three figures is from 0 to 1.

The first observation we make is that the  gates have negligible impact. The bars corresponding to the  gates are not visible due to the TVD being very low. For example, there are two  gates in layer 0 and layer 2 on qubits 1 and 2 in Fig. <ref>(a). However, when we look at layers 0 and 2 in Fig. <ref>(b), the bars are not visible due to their low impact. The lack of a visible bar can be verified for all  gates in the circuit. This demonstrates that the runs corresponding to the  gates can be eliminated from the characterization process. In the case of the three-qubit QFT algorithm, this means that the number of runs can be reduced from 40 to $40-18=22$, which is a reduction of 45% in terms of the execution overhead.

Next, we identify the gates with the highest impact on the output error. In Fig. <ref>(b), we ran the three-qubit QFT circuit with input specified to ensure that the output has a hamming weight of zero (i.e., “000”). Fig. <ref>(c), (d), and (e) shows what happens for other inputs. In Fig. <ref>(c), we ran the three-qubit QFT circuit for a hamming weight of one (i.e., “001” or “010” or “100”). Similarly, Fig. <ref>(d) shows the results for hamming weight of two (i.e., “011” or “101” or “110”), and Fig. <ref>(e) shows the results for hamming weight of three (i.e., “111”). Note that the different inputs may change the circuit structure at the beginning of circuit, but the main section of QFT (starting at layer 3 in Fig. <ref>(a)) remains the same.

Changing the input for the QFT algorithm has a considerable effect on the impact that different gates have on the overall output error of the circuit. For example in Fig. <ref>(b), the gates with the highest impact include the  gate on qubits 0 and 1 in layer 28. However, the  gate on qubit 0 in layer 13 has a higher impact. In fact, in general,  gates in the middle and end sections tend to have a high impact in Fig. <ref>(b). It is notable that in terms of the physical implementation, the same  gate is being applied to qubit 0 in layers 11, 13, 16, 25, and 26. However depending on its position, it has a varying impact on the output error. On the other hand, in Fig. <ref>(c), the tallest TVD bars exist corresponding to four  gates: (I) qubit 1 and 2 in layer 19, (II) qubits 1 and 2 in layer 21, (III) qubits 0 and 1 in layer 22, and (IV) qubits 0 and 1 in layer 24.  gates are not high-impact for this input. In contrast, in Fig. <ref>(d), the  and  gates in the middle section of the circuit (layers 9 to 15) on qubits 0 and 1 have the highest impact compared to the  gates at the end, and in Fig. <ref>(e), the  and  gates all across the length of the circuit (layers 1-2, 10-16, and 21-23) on qubits 0 and 1 have a high impact on the overall output error.

Use case: for Discovering High-Impact Inputs. To figure out which input has the highest impact on the output error,  is leveraged as a technique to apply reversals to all input-related gates together (instead of one gate a time) to estimate their combined impact. All input related gates are bunched together and reversed within the same circuit, instead of in different circuits. Applying this technique produces TVDs of the outputs of the reversed circuits to the output of the original circuit as following: TVD $=$ 0.06 for hamming weight zero input (Fig. <ref>(b)), 0.02 for hamming weight one input (Fig. <ref>(c)), 0.06 for hamming weight two input Fig. <ref>(d), and 0.07 for hamming weight three input (Fig. <ref>(e)).  reveals that the input in Fig. <ref>(e) (hamming weight of three) has the highest impact, which is also evidenced by the fact that it is the only input with high-impact gates in layers 1-2.

Observation I. Previous works that focus on reducing the output error on noisy quantum computers using compiler optimizations focus on high-level optimizations based on simplistic assumptions [58, 38, 35, 40]. As an instance, previous works have focused on optimizing the mapping to hardware based on error information of the gates obtained during computer calibration in isolation or via micro-benchmarking, that is, one number is used per physical gate type [58, 50, 52]. However,  has shown that the same physical gate can have very different impact based on its position within the circuit – this requires critical consideration for compiler optimizations which is currently lacking in existing quantum compiler solutions.

Observation II. Using , we also showed that depending on the changes in the input, which changes the gate structure at the beginning of the circuit, the impact of the different gates will vary even if the rest of the circuit structure is the same. This means optimizations that are based purely based on circuit structure [27, 6, 14] (e.g., gate deletion and synthesis [49, 42, 2, 57] and layout mapping and routing [63, 64, 26]) may be sub-optimal due to the lack of input-awareness. An effective demonstrated use case of 's includes performing a combined reversal on all input-related gates to identify the inputs with the highest impact on the output error.

The Effect of Gate Position Along the Length of the Circuit. In the three-qubit QFT examples for different inputs, we saw that gates in any layer position along the circuit length can be high-impact gates (e.g., Fig. <ref>(e)). However, conventional wisdom suggests that error impacts are especially worse near the end of the circuits due to the qubit state losing coherence. Recall that over time, the qubit state tends to lose its phase and amplitude and decay to the ground (i.e., the $\ket{0}$) state [32, 54]. So this effect gets particularly worse at the end layers of a quantum circuit execution.

While previously there did not exist a way to test the above conventional wisdom, now  enables us to determine if this conventional wisdom is true. To perform this test, we correlate the impact of the gates (i.e., the TVD between the reversed circuit corresponding the gate and the original circuit) with the layer in which it is positioned. If the correlation is high, it suggests that as the layer index increases, the gate impact also increases, that is, it suggests that the assumption is true. For example, say we have gates $G = \{g_1, g_2, g_3, g_4, g_4\}$ with TVDs $T = [0.1, 0.2, 0.3, 0.32, 0.4]$; the gates are positioned in layers $L = [1, 2, 3, 3, 4]$. If we correlate the TVD vector $T$ with the layers vector $L$, we would observe a high correlation. If instead, $T = [0.2, 0.1, 0.1, 0.2, 0.1]$, we would observe a low correlation.

Pearson correlation between the error impact of a gate and its position within the program (the layer number). The correlation is low or insignificant for most algorithms.

Algorithm     Corr.     $p$-value     Algorithm     Corr.     $p$-value

HLF (5)     -0.04     0.79     QAOA (5)     0.43     2$e-$7

HLF (10)     0.14     0.05     QAOA (10)     0.29     9$e-$9

QFT (3)     0.17     0.27     VQE (4)     0.21     1$e-$5

QFT (7)     $-$0.66     4$e-$37     Heisen. (4)     0.27     2$e-$10

TFIM (4)     0.12     0.20     Adder (4)     $-$0.02     0.84

TFIM (8)     0.33     2$e-$15     Adder (9)     0.05     0.78

TFIM (16)     0.26     1$e-$9     Multiply (5)     0.1     0.36

XY (4)     -0.14     0.18     Multiply (10)     0.58     4$e-$60

XY (8)     0.42     1$e-$22     -     -     -

performs this correlation for all evaluated algorithms and the results are reported in Table <ref>. The table shows the Pearson correlation numbers along with the corresponding $p$-values. As the table shows, for most algorithms (e.g., HLF (5), QFT (3), Adder (9), Multiply (5), TFIM (4), and XY (4)), the correlation numbers are not high and the $p$-value numbers are high ($>0.01$), which indicates that no strong correlation exists between the impact of a gate and the layer in which it is located. The highest correlation among all algorithms of 0.58 can be seen for the Multiply (10) algorithm. On the other side of the spectrum, the QFT (7) algorithm has a correlation of $-$0.66. The negative correlation indicates that most of its high impact gates are located in the front section of the circuit.

Overall, the results highlight that for most quantum algorithms, the high-impact gates can be distributed somewhat evenly across the entire length of the circuit. While some algorithms may have a concentration of high-impact gates at the back of the circuit, some others may have these gates concentrated at the beginning of the circuit. The behavior varies from algorithm to algorithm with circuit structure.

Analysis of Multiple Architectures using VQE. To demonstrate that 's analysis are applicable to different quantum computing architectures and topologies, we run the VQE circuit on , along with the default execution on . As the VQE circuit is a four-qubit circuit, we choose the first four qubits of the two computers for execution to make use of different topologies; Fig. <ref> shows qubits 0, 1, 2, and 3 form a T-shape on  and a line on . Due to this difference in topologies, when VQE is mapped to , it has 135  gates – as opposed to the the default of 172 on  – and 74  gates – as opposed to 132 on . However, in spite of these differences, the correlation between the error impact of a gate and its position within the program is 0.41 ($p-$value: $1e-13$) on ; it is 0.21 on . The low correlation on both computers shows that 's analysis is applicable to different computer architectures and topologies.

Observation III. Due to the property of NISQ qubits of losing their coherence over time, it has been assumed that a large portion of the output error is accumulated near the end of the circuit based on the study of decoherence effects in isolation [32, 54]. In fact, some previous works have proposed software-level compiler optimizations that are especially catered toward the end or the beginning of the quantum circuit [28, 45].

demonstrate that these conventional assumptions do not hold true for many real-world quantum algorithms with complex circuit structures that face the combined effect of all different types of hardware noises, when they are executed on different quantum computer architectures and topologies. Depending on the circuit properties of the algorithm, the high-impact gates can be evenly distributed, they can be bundled in the front section of the circuit, or they can be bundled in the back section.

Percentage of all program qubits that appear in top 5%, 10%, 25% and 50% of high-error-impact gates. High-impact gates can exist across different qubits for all algorithms.

Algorithm     Top 5%     Top 10%     Top 25%     Top 50%

HLF (5)     40%     40%     60%     100%

HLF (10)     70%     100%     100%     100%

QFT (3)     67%     67%     100%     100%

QFT (7)     57%     71%     86%     100%

Adder (4)     100%     100%     100%     100%

Adder (9)     78%     100%     100%     100%

Multiply (5)     40%     60%     100%     100%

Multiply (10)     90%     100%     100%     100%

QAOA (5)     40%     60%     60%     100%

QAOA (10)     90%     90%     100%     100%

VQE (4)     100%     100%     100%     100%

Heisenberg (4)     100%     100%     100%     100%

TFIM (4)     75%     100%     100%     100%

TFIM (8)     88%     100%     100%     100%

TFIM (16)     94%     100%     100%     100%

XY (4)     50%     50%     100%     100%

XY (8)     100%     100%     100%     100%

The Impact of Individual Qubit's Error Rates. In the QFT (3) results in Fig. <ref>, we observed that most of the high-impact gates were situated on qubit 0, then there were a few on qubit 1, and there were no high-impact gates on qubit 2. This example is a good representation of the common way of performing noise characterization of quantum computers. Many works focus on characterizing the noise effects at the level of individual qubits or at the level of specific types of operations performed on individual qubits [15, 44, 39, 30, 8, 59]. For example, previous works have relied on data obtained during computer calibration to estimate the error rates of qubits to perform noise-aware compilation and reduce the gate count on high-error qubits [58, 52, 38, 35, 40].

's novel methodology enables us to investigate if this broad classification of qubits as being high-error or low-error based on simplistic noise models or isolation noise analysis holds true when we look at the impact of individual gates. In other words, we want to study if all the high-impact gates are concentrated on a few qubits (which would encourage us to broadly classify those qubits as high-error) or if these high-impact gates are distributed across the different qubits that are involved in the quantum circuit.

First, we note that, unlike the case of studying the concentration of high-impact gates across the length of the circuit, we cannot use correlation to perform this check as the actual qubit ids are not of relative significance. For example, layer 1 is after layer 0 for a correlative study but qubit ids have no relative relationship. Therefore, instead, in Table <ref>, we show the percentage of all qubits in a circuit that are involved in the top 5% (i.e., gates with the top 5% highest TVD between the corresponding reversed circuits and the original circuit), 10%, 25%, and 50% of high-impact gates. Note that we do not use just one threshold to define high impact, as this threshold may vary from algorithm to algorithm and use-case to use-case.

As the results show, for most of the algorithms, a majority of the qubits are involved in top 5% of the high-impact gates and a 100% of the qubits are involved in the top 25% of high impact gates. Even for relatively larger algorithms like TFIM (16), 15/16 qubits (94%) are involved in the top 5% of high impact gates. If we look at the top 50% column, we see that a 100% of the qubits are involved in high-impact gates across all of the evaluated algorithms. These results suggest that most qubits can have gates that have a high-impact on the output error and it is preferable to identify the error of specific gates, than to broadly classify qubits as being high error or low error.

Observation IV. General characterization and calibration work in the NISQ computing regime tries to broadly characterize the error rates of individual qubits on a quantum computer [15, 44, 39, 30, 8, 59]. Compiler-level optimization works then try to use these board classifications to perform noise-aware mapping and routing of quantum algorithms to the quantum computers [58, 38, 52, 35, 40].

's unique methodology has helped us reveal that the gates that have a high-impact on the output error of a quantum program can exist at different places within the circuit and on any qubit. In addition, we have demonstrated that the top 25% of high-impact operations are distributed across all the qubits for most quantum algorithms.  shows that simply classifying qubits based on their error rate and focusing software optimizations around this classification may not be sufficient and complete – criticality of gate operations is equally important and they can occur on low-error qubits too.

The Role of One-Qubit Gates in Output Error. In the QFT (3) results in Fig. <ref>, we observed that both  and  gates can be high-impact gates, depending on the input to the program. However, due to the fact that  gates tend to have an order of magnitude higher error rate than  or  gates when measured in isolation [40, 39], many software-level compiler works have specifically focused on minimizing the number of  gates in the circuits. This has been in the form of directing trying to reduce the  gates using mathematical equivalencies based on the commutativity and unitary properties of gates within the circuit [46, 65], and in the form of trying to reduce the number of  operations, each of which is implemented using three  gates [56, 3].

While these techniques are effective at reducing the number of  gates, they also have a significant compilation time overhead.  can be used to study if these techniques are worth the overhead considering that they only focus on  gates, which are assumed to be high-impact due to their relatively higher isolation error rates. We also saw for the QFT (3) example, that some  gates can have a much higher impact than  gates. To investigate if this is the case across different algorithms, in Table <ref>, we present the percentage of one-qubit  and  gates in the circuit that have a greater error impact than the  gate with the least error impact compared to other  gates in the circuit. We compare to the  gate with the least error impact as all  gates are targeted for compiler optimizations regardless of their specific error impact. So the one-qubit  or  gates that have a higher impact than that  gate can be judged to have a high impact overall – this can be caused by potentially higher crosstalk effects and neighboring gate operations around the qubits where  and  gates are being performed.

Number and percentage of one-qubit  and  gates that have a greater error impact than the  gate with the least error impact (compared to other  gates). A large portion of one-qubit gates have a higher impact than  gates.

Algorithm     Num. +     %+     Algorithm     Num. +     %+

HLF (5)     7     70%     QAOA (5)     22     71%

HLF (10)     45     92%     QAOA (10)     58     89%

QFT (3)     9     56%     VQE (4)     119     98%

QFT (7)     78     98%     Heisenberg (4)     141     96%

TFIM (4)     30     83%     Adder (4)     20     74%

TFIM (8)     179     95%     Adder (9)     35     78%

TFIM (16)     772     98%     Multiply (5)     20     80%

XY (4)     21     75%     Multiply (10)     117     100%

XY (8)     158     98%     -     -     -

The results in the table show that across different algorithms, 50% to over 90% of all  +  gates tend to have a higher impact than the  gate with the least error impact in the circuit. For example, for the XY (8) algorithm, 98% of the  +  gates have a higher error impact. These results highlight the need to focus on impact-aware compiler optimizations for gates instead of type-aware.

's Mitigation Strategy. This above observation about high-impact one-qubit gates is also evidenced by the fact that the  gates on qubit 0 in layers 1 and 2 have some of the highest impact in Fig. <ref>(e). This is because there are parallel  gates on qubits 2 and 3 in layers 1 and 2 for this input, which causes increased crosstalk effect on qubit 0. As a mitigation strategy, we inserted barriers to make sure the gates in these two layers are executed serially instead of in parallel and observed the output error (TVD of the observed output to the ideal output) drop from 0.19 to 0.12 (i.e., 7% points reduction). Note that all operations in a circuit cannot be serialized as this would increase circuit depth and decoherence effects. However, this strategy is effective when used selectively for the highest-impact gates.

Observation V. Due to the fact that  gates have an order of magnitude higher error rate when the error rate is measured in isolation [40, 39], it is often assumed that these gates also have the highest error impact in quantum circuits when run on NISQ computers [3, 49, 46]. Previous works have focused on minimizing the impact of  gates by trying to reduce their number in quantum circuits [65, 56, 42, 2, 57].

In contrast, we have leveraged  to demonstrate an interesting insight: one-qubit  and  gates also have a high impact on the output error, and in some cases this impact is higher than that of  gates. In fact, across different quantum algorithms, 50%-98% of all  +  gates have a higher error impact than the  gate with the least error impact in the algorithm circuit.  serves as a useful utility for the programmer to not rely on generalized assumptions and determine gate-specific error impact. As show by , identification and selective serialization of gates can act as an effective mitigate strategy for reducing the impact of high-impact gates.

§ WORK RELATED TO

Previous works relevant to  are as following:

Noise Characterization. Previous works have focused on characterizing different aspects of the noise on NISQ computers, from examining a specific type of noise such as decoherence effects [32, 54], to benchmarking and micro-benchmarking different gates and algorithms on quantum computers to figure out the kinds of errors they experience [39, 30, 8, 15, 44, 59]. For example, Erhard et al. [15] perform cycle benchmarking on quantum computers to figure out how their noise characteristics manifest in different algorithms. However, none of these works characterize the impact that a specific gate has on the output error of a quantum program.  makes a novel contribution in that space.

Program Debugging. Previous works have introduced debugging techniques for quantum code [20, 29, 31, 62, 19]. Some of these works propose the use of statistical assertions to debug the functionality of the circuits [20, 29, 31], while others propose new programming interfaces and frameworks for semantics-based debugging [62, 19]. A concurrent work [9] shares the goal with  of debugging and sensitivity analysis of quantum circuit implementations leveraging the idea of gate reversal. This work can also be used to locate bugs at different levels of a quantum-program specification. We note that  was submitted to SC for peer review on April 1, 2022 (the submission deadline for full technical paper for SC), prior to the appearance of the arXiv article (the arXiv article was first uploaded on April 12, 2022 [9]). But, the arXiv article was brought to our attention after  was published online in mid-November, 2022 as a part of the SC proceedings. Therefore, we are uploading this version to acknowledge and credit the authors of the arXiV article for their idea and contributions to the field. The concurrency of these ideas further demonstrates the potential of reversing gates and circuits for various purposes.  can further enhance the capability of these works by enabling gate-specific debugging of errors.

Compiler Optimizations. Different types of software-based compiler optimizations have been proposed to reduce the impact of noise when quantum algorithms are run on quantum computers, including works that mitigate the effect of crosstalk [36, 60], perform noise-optimal compilation using isolation noise characteristics [58, 38, 52, 35, 40], synthesize circuits to reduce their length
[49, 42, 2, 57], perform layout-aware routing and mapping [63, 64, 26], leverage optimizations targeting specific circuit regions (e.g., end of the circuit) [28, 45], reduce the number of  gate operations [46, 65, 56, 3, 42], perform optimizations without considering the input [27, 6, 50, 14], and even use the reversibility property at the circuit level to improve the output error (although, it requires ideal simulations on classical computers) [41]. While none of these works provide a methodology like 's to help programmers learn about the impact that specific gates have on the output of their program, many of them can benefit from this functionality to further improve the compiler optimizations that are applied.

§ : CONCLUDING REMARKS

In this paper, we proposed , a simple and effective technique that leverages reversibility property of quantum circuits to identify high-impact error-prone gate operations in quantum programs.  demonstrates the usability of quantum operation reversibility for identifying most critical quantum operations – extending the application of quantum operation reversibility beyond estimating and improving answer fidelity of quantum programs [41].

By applying  to a variety of quantum algorithms and benchmarks with different characteristics, we highlighted several surprisingly and counter-intuitive trends, such as the observation that high-impact error-prone gates can be located anywhere within a quantum program. 's open-source implementation and dataset is available to future innovations in compiler optimization and algorithm debugging techniques.

§ ACKNOWLEDGEMENT

We thank the anonymous reviewers for their constructive feedback. This work was also supported by Northeastern University, NSF Award  1910601 and 2144540. IBM Q was also used for this work. The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Q team.

[1]
G Aleksandrowicz, T Alexander, P Barkoutsos, L Bello, Y Ben-Haim, D Bucher,
et al.
Qiskit: An Open-source Framework for Quantum Computing.

[2]
Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler.
A meet-in-the-middle algorithm for fast synthesis of depth-optimal
quantum circuits.
IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 32(6):818–830, 2013.

[3]
Abdullah Ash-Saki, Mahabubul Alam, and Swaroop Ghosh.
QURE: Qubit Re-allocation in Noisy Intermediate-Scale Quantum
In Proceedings of the 56th Annual Design Automation Conference
2019, page 141. ACM, 2019.

[4]
Lindsay Bassman, Connor Powers, and Wibe A de Jong.
ArQTiC: A Full-Stack Software Package for Simulating Materials on
Quantum Computers.
arXiv preprint arXiv:2106.04749, 2021.

[5]
Jacob Benesty, Jingdong Chen, Yiteng Huang, and Israel Cohen.
Pearson Correlation Coefficient.
In Noise reduction in speech processing, pages 1–4. Springer,

[6]
Debjyoti Bhattacharjee, Abdullah Ash Saki, Mahabubul Alam, Anupam
Chattopadhyay, and Swaroop Ghosh.
MUQUT: Multi-Constraint Quantum Circuit Mapping on NISQ Computers.
In 38th IEEE/ACM International Conference on Computer-Aided
Design, ICCAD 2019, page 8942132. Institute of Electrical and Electronics
Engineers Inc., 2019.

[7]
Sergey Bravyi, David Gosset, and Robert König.
Quantum Advantage with Shallow Circuits.
Science, 362(6412):308–311, 2018.

[8]
Anastasiia Butko, George Michelogiannakis, Samuel Williams, Costin Iancu, David
Donofrio, John Shalf, Jonathan Carter, and Irfan Siddiqi.
Understanding quantum control processor capabilities and limitations
through circuit characterization.
arXiv preprint arXiv:1909.11719, 2019.

[9]
Fernando A Calderon-Vargas, Timothy Proctor, Kenneth Rudinger, and Mohan
Quantum circuit debugging and sensitivity analysis via local
arXiv preprint arXiv:2204.06056, 2022.

[10]
Andre RR Carvalho, Harrison Ball, Michael J Biercuk, Michael R Hush, and Felix
Error-Robust Quantum Logic Optimization Using a Cloud Quantum
Computer Interface.
Physical Review Applied, 15(6):064054, 2021.

[11]
Davide Castelvecchi.
IBM's Quantum Cloud Computer Goes Commercial.
Nature News, 543(7644):159, 2017.

[12]
J Ignacio Cirac and Peter Zoller.
Goals and Opportunities in Quantum Simulation.
Nature Physics, 8(4):264, 2012.

[13]
Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton.
A New Quantum Ripple-Carry Addition Circuit.
arXiv preprint quant-ph/0410184, 2004.

[14]
Marc G Davis, Ethan Smith, Ana Tudor, Koushik Sen, Irfan Siddiqi, and Costin
Towards Optimal Topology Aware Quantum Circuit Synthesis.
In 2020 IEEE International Conference on Quantum Computing and
Engineering (QCE), pages 223–234. IEEE, 2020.

[15]
Alexander Erhard, Joel J Wallman, Lukas Postler, Michael Meth, Roman Stricker,
Esteban A Martinez, Philipp Schindler, Thomas Monz, Joseph Emerson, and
Rainer Blatt.
Characterizing large-scale quantum computers via cycle benchmarking.
Nature communications, 10(1):1–7, 2019.

[16]
Edward Farhi and Aram W Harrow.
Quantum Supremacy through the Quantum Approximate Optimization
arXiv preprint arXiv:1602.07674, 2016.

[17]
Alexei Gilchrist, Nathan K Langford, and Michael A Nielsen.
Distance Measures to Compare Real and Ideal Quantum Processes.
Physical Review A, 71(6):062310, 2005.

[18]
Andrew Hancock, Austin Garcia, Jacob Shedenhelm, Jordan Cowen, and Calista
Cirq: A Python Framework for Creating, Editing, and Invoking Quantum
URL https://github.com/quantumlib/Cirq, 2019.

[19]
Thomas Häner, Damian S Steiger, Torsten Hoefler, and Matthias Troyer.
Distributed Quantum Computing with QMPI.
In Proceedings of the International Conference for High
Performance Computing, Networking, Storage and Analysis, pages 1–13, 2021.

[20]
Yipeng Huang and Margaret Martonosi.
Statistical Assertions for Validating Patterns and Finding Bugs in
Quantum Programs.
In Proceedings of the 46th International Symposium on Computer
Architecture, pages 541–553. ACM, 2019.

[21]
Eric Jones, Travis Oliphant, Pearu Peterson, et al.
SciPy: Open Source Scientific Tools for Python, 2001, 2016.

[22]
Tyson Jones, Anna Brown, Ian Bush, and Simon C Benjamin.
Quest and High Performance Simulation of Quantum Computers.
Scientific reports, 9(1):1–11, 2019.

[23]
Nader Khammassi, Imran Ashraf, Xiang Fu, Carmen G Almudever, and Koen Bertels.
QX: A High-Performance Quantum Computer Simulation Platform.
In Design, Automation & Test in Europe Conference & Exhibition
(DATE), 2017, pages 464–469. IEEE, 2017.

[24]
David Layden, Sisi Zhou, Paola Cappellaro, and Liang Jiang.
Ancilla-Free Quantum Error Correction Codes for Quantum Metrology.
Physical review letters, 122(4), 2019.

[25]
Gushu Li, Yufei Ding, and Yuan Xie.
SANQ: A Simulation Framework for Architecting Noisy
Intermediate-Scale Quantum Computing System.
arXiv preprint arXiv:1904.11590, 2019.

[26]
Gushu Li, Yufei Ding, and Yuan Xie.
Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices.
In Proceedings of the Twenty-Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
1001–1014. ACM, 2019.

[27]
Gushu Li, Anbang Wu, Yunong Shi, Ali Javadi-Abhari, Yufei Ding, and Yuan Xie.
Paulihedral: A Generalized Block-wise Compiler Optimization
Framework for Quantum Simulation Kernels.
In Proceedings of the 27th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
554–569, 2022.

[28]
Ji Liu, Luciano Bello, and Huiyang Zhou.
Relaxed Peephole Optimization: A Novel Compiler Optimization for
Quantum Circuits.
In 2021 IEEE/ACM International Symposium on Code Generation and
Optimization (CGO), pages 301–314. IEEE, 2021.

[29]
Ji Liu, Gregory T Byrd, and Huiyang Zhou.
Quantum Circuits for Dynamic Runtime Assertions in Quantum
In Proceedings of the Twenty-Fifth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
1017–1030, 2020.

[30]
Ji Liu and Huiyang Zhou.
Reliability Modeling of NISQ-Era Quantum Computers.
In 2020 IEEE International Symposium on Workload
Characterization (IISWC), pages 94–105. IEEE, 2020.

[31]
Ji Liu and Huiyang Zhou.
Systematic Approaches for Precise and Approximate Quantum State
Runtime Assertion.
In 2021 IEEE International Symposium on High-Performance
Computer Architecture (HPCA), pages 179–193. IEEE, 2021.

[32]
Sandeep Mavadia, Virginia Frey, Jarrah Sastrawan, Stephen Dona, and Michael J
Prediction and Real-Time Compensation of Qubit Decoherence via
Machine Learning.
Nature communications, 8, 2017.

[33]
Jarrod R McClean, Jonathan Romero, Ryan Babbush, and Alán Aspuru-Guzik.
The Theory of Variational Hybrid Quantum-Classical Algorithms.
New Journal of Physics, 18(2):023023, 2016.

[34]
Shubhendu S Mukherjee, Christopher Weaver, Joel Emer, Steven K Reinhardt, and
Todd Austin.
A systematic methodology to compute the architectural vulnerability
factors for a high-performance microprocessor.
In Proceedings. 36th Annual IEEE/ACM International Symposium on
Microarchitecture, 2003. MICRO-36., pages 29–40. IEEE, 2003.

[35]
Prakash Murali, Jonathan M Baker, Ali Javadi-Abhari, Frederic T Chong, and
Margaret Martonosi.
Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale
Quantum Computers.
In Proceedings of the Twenty-Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
1015–1029. ACM, 2019.

[36]
Prakash Murali, David C McKay, Margaret Martonosi, and Ali Javadi-Abhari.
Software Mitigation of Crosstalk on Noisy Intermediate-Scale Quantum
In Proceedings of the Twenty-Fifth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
1001–1016, 2020.

[37]
Victor Namias.
The Fractional order Fourier Transform and its Application to
Quantum Mechanics.
IMA Journal of Applied Mathematics, 25(3):241–265, 1980.

[38]
Tirthak Patel, Baolin Li, Rohan Basu Roy, and Devesh Tiwari.
Ureqa: Leveraging operation-aware error rates for effective quantum
circuit mapping on nisq-era quantum computers.
In 2020 USENIX Annual Technical Conference (USENIX ATC 20),
pages 705–711, 2020.

[39]
Tirthak Patel, Abhay Potharaju, Baolin Li, Rohan Roy, and Devesh Tiwari.
Experimental Evaluation of NISQ Quantum Computers: Error
Measurement, Characterization, and Implications.
In 2020 SC20: International Conference for High Performance
Computing, Networking, Storage and Analysis (SC), pages 636–650. IEEE
Computer Society, 2020.

[40]
Tirthak Patel and Devesh Tiwari.
VERITAS: Accurately Estimating the Correct Output on Noisy
Intermediate-Scale Quantum Computers.
In 2020 SC20: International Conference for High Performance
Computing, Networking, Storage and Analysis (SC), pages 188–203. IEEE
Computer Society, 2020.

[41]
Tirthak Patel and Devesh Tiwari.
QRAFT: Reverse your Quantum Circuit and Know the Correct Program
In Proceedings of the 26th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
443–455, 2021.

[42]
Tirthak Patel, Ed Younis, Costin Iancu, Wibe de Jong, and Devesh Tiwari.
QUEST: Systematically Approximating Quantum Circuits for Higher
Output Fidelity.
In Proceedings of the 27th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
514–528, 2022.

[43]
John Preskill.
Quantum Computing in the NISQ Era and Beyond.
Quantum, 2:79, 2018.

[44]
Timothy J Proctor, Arnaud Carignan-Dugas, Kenneth Rudinger, Erik Nielsen, Robin
Blume-Kohout, and Kevin Young.
Direct Randomized Benchmarking for Multiqubit Devices.
Physical review letters, 123(3):030503, 2019.

[45]
Yunong Shi, Nelson Leung, Pranav Gokhale, Zane Rossi, David I Schuster, Henry
Hoffmann, and Frederic T Chong.
Optimized Compilation of Aggregated Instructions for Realistic
Quantum Computers.
In Proceedings of the Twenty-Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
1031–1044. ACM, 2019.

[46]
Kaitlin N Smith and Mitchell A Thornton.
A Quantum Computational Compiler and Design Tool for
Technology-Specific Targets.
In Proceedings of the 46th International Symposium on Computer
Architecture, pages 579–588. ACM, 2019.

[47]
Vilas Sridharan and David R Kaeli.
Eliminating microarchitectural dependency from architectural
In 2009 IEEE 15th International Symposium on High Performance
Computer Architecture, pages 117–128. IEEE, 2009.

[48]
Luyan Sun, Ling Hu, Yuwei Ma, Weizhou Cai, Xianghao Mu, Yuan Xu, Wang Weiting,
Yukai Wu, Haiyan Wang, Yipu Song, et al.
Experimental Quantum Error Correction with Binomial Bosonic Codes.
In APS Meeting Abstracts, 2019.

[49]
Bochen Tan and Jason Cong.
Optimality Study of Existing Quantum Computing Layout Synthesis
arXiv preprint arXiv:2002.09783, 2020.

[50]
Swamit S Tannu and Moinuddin Qureshi.
Ensemble of Diverse Mappings: Improving Reliability of Quantum
Computers by Orchestrating Dissimilar Mistakes.
In Proceedings of the 52nd Annual IEEE/ACM International
Symposium on Microarchitecture, pages 253–265. ACM, 2019.

[51]
Swamit S Tannu and Moinuddin K Qureshi.
Mitigating Measurement Errors in Quantum Computers by Exploiting
State-Dependent Bias.
In Proceedings of the 52nd Annual IEEE/ACM International
Symposium on Microarchitecture, pages 279–290. ACM, 2019.

[52]
Swamit S Tannu and Moinuddin K Qureshi.
Not All Aubits are Created Equal: A Case for Variability-Aware
Policies for NISQ-Era Quantum Computers.
In Proceedings of the Twenty-Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
987–999. ACM, 2019.

[53]
Barbara Terhal, Leonid Pryadko, Daniel Weigand, Yang Wang, Hamed Asasi, and
Christophe Vuillot.
Scalable Quantum Error Correction with the Bosonic GKP Code.
In APS Meeting Abstracts, 2019.

[54]
Lorenza Viola and Seth Lloyd.
Dynamical Suppression of Decoherence in Two-State Quantum Systems.
Phys. Rev. A, 58, Oct 1998.

[55]
Christophe Vuillot, Hamed Asasi, Yang Wang, Leonid P Pryadko, and Barbara M
Quantum Error Correction with the Toric Gottesman-Kitaev-Preskill
Physical Review A, 99(3), 2019.

[56]
Robert Wille, Lukas Burgholzer, and Alwin Zulehner.
Mapping Quantum Circuits to IBM QX Architectures Using the Minimal
Number of SWAP and H Operations.
In Proceedings of the 56th Annual Design Automation Conference
2019, page 142. ACM, 2019.

[57]
Ellis Wilson, Frank Mueller, Lindsay Bassman, and Costin Iancu.
Empirical Evaluation of Circuit Approximations on Noisy Quantum
In Proceedings of the International Conference for High
Performance Computing, Networking, Storage and Analysis, pages 1–15, 2021.

[58]
Ellis Wilson, Sudhakar Singh, and Frank Mueller.
Just-in-time Quantum Circuit Transpilation Reduces Noise.
arXiv preprint arXiv:2005.12820, 2020.

[59]
K Wright, KM Beck, S Debnath, JM Amini, Y Nam, N Grzesiak, J-S Chen,
NC Pisenti, M Chmielewski, C Collins, et al.
Benchmarking an 11-Qubit Quantum Computer.
Nature communications, 10(1):1–6, 2019.

[60]
Lei Xie, Jidong Zhai, ZhenXing Zhang, Jonathan Allcock, Shengyu Zhang, and
Yi-Cong Zheng.
Suppressing ZZ Crosstalk of Quantum Computers Through Pulse and
Scheduling Co-Optimization.
In Proceedings of the 27th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
499–513, 2022.

[61]
Lei Xie, Jidong Zhai, and Weimin Zheng.
Mitigating Crosstalk in Quantum Computers through
Commutativity-Based Instruction Reordering.
In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages
445–450. IEEE, 2021.

[62]
Charles Yuan, Christopher McNally, and Michael Carbin.
Twist: Sound Reasoning for Purity and Entanglement in Quantum
Proceedings of the ACM on Programming Languages, 6(POPL):1–32,

[63]
Chi Zhang, Ari B Hayes, Longfei Qiu, Yuwei Jin, Yanhao Chen, and Eddy Z Zhang.
Time-optimal Qubit Mapping.
In Proceedings of the 26th ACM International Conference on
Architectural Support for Programming Languages and Operating Systems, pages
360–374, 2021.

[64]
Alwin Zulehner, Alexandru Paler, and Robert Wille.
An Efficient Methodology for Mapping Quantum Circuits to the IBM QX
IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems, 2018.

[65]
Alwin Zulehner and Robert Wille.
Compiling SU (4) Quantum Circuits to IBM QX Architectures.
In Proceedings of the 24th Asia and South Pacific Design
Automation Conference, pages 185–190. ACM, 2019.