Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
Shin Nishio Yulu Pan Takahiko Satoh Hideharu Amano Rodney Van Meter

Improving the Scalability of a Prosumer Cooperative Game with K-Means Clustering

This work was supported in part by the Engineering and 
Physical Sciences Research Council under Grants EP/N03466X/1 and 
EP/S000887/1, and in part by the Oxford Martin Programme on Integrating 
Renewable Energy.
©2019 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. 
Digital Object Identifier 10.1109/PTC.2019.8810558.

    Liyang Han, Thomas Morstyn, Constance Crozier, Malcolm McCulloch
Department of Engineering Science 

University of Oxford

Oxford, United Kingdom 

{Liyang.Han, Thomas.Morstyn, Constance.Crozier, Malcolm.McCulloch}@eng.ox.ac.uk

    December 30, 2023
=============================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

firstpage
plain






  NISQ (Noisy, Intermediate-Scale Quantum) computing requires error
  mitigation to achieve meaningful computation.  Our compilation tool
  development focuses on the fact that the error rates of individual
  qubits are not equal, with a goal of maximizing the success
  probability of real-world subroutines such as an adder circuit.  We
  begin by establishing a metric for choosing among possible paths and
  circuit alternatives for executing gates between variables placed
  far apart within the processor, and test our approach on two IBM
  20-qubit systems named Tokyo and  Poughkeepsie.  We find that a single-number metric
  describing the fidelity of individual gates is a useful but
  imperfect guide.

  Our compiler uses this subsystem and maps complete circuits onto the
  machine using a beam search-based heuristic that will scale as
  processor and program sizes grow.  To evaluate the whole compilation
  process, we compiled and executed adder circuits, then calculated
  the KL-divergence (a measure of the distance between two probability
  distributions).  For a circuit within the capabilities of the
  hardware, our compilation increases estimated success probability
  and reduces KL-divergence relative to an error-oblivious placement.




§ INTRODUCTION


Quantum computers
exist <cit.>,
and once mature, they will surpass classical computers on a range of
important
problems <cit.>.
Experimental progress in recent years has been rapid, with systems of
up to 20 qubits now accessible, and systems ranging from 49 qubits to
128 qubits either undergoing testing in the laboratory or promised for
the near future.  Quantum machines will overtake classical ones
somewhere between 50 and 150 qubits as quantum capability (especially
fidelity of gate operations) and improving classical simulation
techniques <cit.> compete,
first for demonstration problems then inevitably (we believe) for
problems of practical import.  This leaves computer engineers with
challenges in
architecture <cit.>
and programming
tools <cit.>.
In particular, because full realization of quantum error
correction <cit.>
remains out of reach, in the near term, we must create error-aware
compilers for the noisy, intermediate-scale quantum computing
era <cit.>.

Compilation varies significantly depending on whether we are compiling
for fault-tolerant execution on top of error-corrected logical qubits,
or for the “bare metal” machine, and further whether qubits fly
(photons), can be moved modest distances (ions), or stay in place
(solid-state), and what connectivity constraints are
incurred <cit.>.
QEC compilation has been the subject of dramatic advances in recent
years
(e.g., <cit.>),
but in this paper we focus on bare metal machines, which imposes a
different set of goals and constraints.  Machine-level compilation
involves a series of phases: first, decomposition of higher-level
language constructs into a series of one- and two-qubit operations
that can be executed on the target system; second, mapping of the
variables defined by the programmer to locations in the system, in
tandem with generation of appropriate execution of gates between
qubits unfortunately placed far apart; third, generation of low-level
control for the hardware itself.  This paper focuses on the second
phase, as shown in Fig. <ref>.  We test our ideas on a
specific system, the IBM 20-qubit machine named Tokyo [Tokyo
  is only the name of the machine, it actually resides in Yorktown
  Heights.] and Poughkeepsie, but expect that the ideas will hold for a broad range of
solid-state systems.




Tokyo and Poughkeepsie are  transmon-style superconducting systems with limited
connectivity between qubits, as shown in
Fig. <ref> <cit.> and Fig. <ref>.  Each
vertex indicates a qubit, and each edge indicates whether or not a
multi-quantum bit gate is physically executable.  Existing solid-state
quantum processors such as this have limitations on the execution of
multi-qubit gates such as CNOT because effects such as crosstalk make
it undesirable to cross qubit-to-qubit couplers or control wires or to
make all-to-all shared buses.







In existing quantum processors, fidelity degrades due to various
errors, affecting the success probability of calculations.  The
susceptibility to errors of each quantum bit on the quantum processor
can vary dramatically.  For Tokyo, two-qubit errors dominate.  The
error rates reported by the Qiskit tools do not distinguish between
bit flip errors and phase flip errors (the two primary types of
quantum state errors), giving us only a single number to work with.
The edges in Fig. <ref> have reported error rates ranging
from 3% to 12%.  (Newer designs for qubit couplers may push those
errors to 1% or below <cit.>.)  Executing
medium-length programs on such a system is challenging, making it
imperative not only to minimize the total number of gates, but also to
assign program variables to qubits with a careful eye toward which edges will
be most used.  While a number of projects have focused on gate
reduction, we choose to make execution success probability our primary
goal.


To understand the system, we began by conducting a form of system
testing known as randomized benchmarking (RB) (described with other
background material in Sec. <ref>).  We omit our RB
results here because we chose to develop our compilation algorithms
using the error rates reported by the Qiskit tools (which are also
RB-derived), since extensive testing of the machine itself before
every application compilation is inherently impractical.

Our first task is to assess our ability to accurately predict
  the success rate of a given circuit using the product of the
individual gate success probabilities as our estimated success
  probability (ESP) (Sec. <ref>).  We find that our exact
numbers are off, but we can correctly choose which of two circuits
will be better on the real machine about two-thirds of the
time.  We use this to choose how to execute long-distance gates across
the chip, selecting from among a group of circuits that are all
theoretically equivalent but in practice demonstrate large
differences.

The second task is to build on this capability and compile and test
complete circuits (Sec. <ref>).  Unfortunately, we know
that the circuit mapping phase, similar to place-and-route in hardware
design, is NP-complete <cit.>.
Therefore, we use a beam search-based heuristic that includes some
stochastic behavior.  We compile an adder
circuit <cit.> for input register sizes of one, two,
and four qubits, consisting of tens to well over a hundred two-qubit
gates.  Compilations are repeated with different random number seeds
to assess the performance.  For the smaller circuits, our compiler
results in executions on the quantum hardware with substantially less
divergence from the expected output distributions than simple random
placement of variables on the chip.  The largest circuits exceed the
current capabilities of the system.

We conclude from this data from a real quantum computer that the
simple ESP can be used to improve the success probability of quantum
computations for a reasonable (classical) compilation cost, and we
expect that this will scale to the largest processors projected to
exist in the next few years.  We suggest that further work on more
nuanced metrics will allow still further improvements
(Sec. <ref>).



§ BACKGROUND



Quantum computing research has been appearing in computer architecture
venues for over fifteen years, so we dispense with a complete
introduction
here <cit.>.
Instead, we wish to focus on the key problems with measuring and
modeling errors to achieve high success rates in execution, and their
relationship to compilation that will lead to using quantum computers
to solve problems that classical systems cannot.



 §.§ Error model


Our model classifies errors in quantum circuits into three groups.
Fig. <ref> shows where such errors occur.  Rather than a formal
quantum mechanical model <cit.>,
here we need only the error probabilities.



  * Single-Qubit Gate errors (G) may be unitary bit flips
  (|0⟩→|1⟩ and |1⟩→|0⟩) or
  phase flips
  ((α|0⟩+β|1⟩)→(α|0⟩-β|1⟩)),
  where {α,β}∈ℂ are the complex amplitudes of
  a qubit's state, or they may be non-unitary errors such as
  relaxation, in which |1⟩ tends to decay to the lower-energy
  state |0⟩;

  * Bi-Qubit gate errors (CNOT error) (B) may also flip the value
  or phase of one or both qubits, and are particularly insidious
  because they propagate errors from one qubit to another; they
  are critical to creating quantum entanglement and appear in
  algorithms in large numbers; and

  * State Preparation And Measurement (SPAM) errors (S) are
  important but can appear only once per qubit in a program execution
  on the IBM machines, and so have less cumulative impact on success.



IBM publishes the value of each of these errors on a per-qubit or
per-coupler basis as a backend property of each machine, retrievable
using a Qiskit call available to IBM Q Network members.  Tokyo is
calibrated once a day, using a procedure called randomized
  benchmarking, below.

Beyond these straightforward errors, various crosstalk and resonances
within the system cause the state of qubits to affect one another.  A
complete characterization of this would require extensive
tomography.



 §.§ Tomography


Quantum tomography comes in two primary forms: state tomography and
process tomography.  This tomography tells us how well we have done at
creating our desired state, or how well a particular process (gate or
set of gates) works, respectively.  It can be used to characterize
errors.  However, a practical problem arises: the number of possible
states naturally grows exponentially with the number of qubits;
moreover, we need to test not just for bit flip errors, but also for
phase flip errors.  Ultimately, we may need to execute the creation of
the state or the gate sequence k3^n times for n qubits, where k
is a constant determined by the precision we require for the
reconstruction and may be thousands.  Although only tomography or a
similarly rigorous (and heavyweight) procedure can tell us about the
state-dependent crosstalk and other factors, it is impractical even at 20 qubits and altogether beyond reach for larger systems.  This need led to the creation of randomized benchmarking.



 §.§ Randomized Benchmarking


We can assess the fidelity of a set of possible gates (e.g., a
commonly used set of gates known as the Clifford group) under a
broad range of conditions with dense coverage of input states by
using the following randomized benchmarking (RB)
procedure <cit.>.
Fig. <ref> sketches the outline of an RB circuit.



  
  * Randomly select m gates from the Clifford group and arrange
    them in any order.
  
  * Select the Clifford gate (or gates, if performing RB on more
    than one qubit) that will reverse the operation of the entire
    preceding sequence of m Clifford gates,

    C_m+1=(∏_i=1^m C_i)^†;
 
execute this as the m+1th gate.
  
  * Measure the qubit(s). If the output state is not equal to the
    input state, then an error has occurred somewhere in the whole
    circuit.
  
  * Change the number m and perform steps 1 to 3 again.


By performing the above operation for various values of m, the
attenuation of the fidelity as a function of the circuit length can be
fitted. In this way, it is possible to estimate the average value of
errors per gate included in the gate set.  Of course, SPAM (state
preparation and measurement) errors are included in all the quantum
circuits, but this effect can be compensated for by calculating the
attenuation.



The gate error rates reported via Qiskit are derived using a procedure
similar to this, executed daily on Tokyo.  These values are not a
complete description of the behavior of the system under all
circumstances, but they are valuable and derived at reasonable cost.
One of our primary research questions, then, is whether such numbers
are good enough to enable us to extract the maximum success
probability from the machine.



 §.§ Architecture-Aware Compilation


Adapting to the topology of the processor using architecture-aware
circuit design and compilation has been a research topic since the
early proposals for large-scale systems and
applications <cit.>.
Those early studies focused on the impact on execution time.

Recently, researchers have begun paying attention to fidelity
improvements.  For example, in the study by Zulehner et al.,
the cost function is computed by assigning a cost of 10 to a two-qubit
gate, versus a cost of one for a single qubit
gate corresponding roughly to difference in error penalty <cit.>.  However, in that work, no
consideration is given to the qubit-to-qubit variance in error rate.
Tannu et al. and Finigan et al. maximize ESP considering
errors per quantum bit <cit.>.
Finigan's research showed that ESP was improved by verifying the
optimized circuit with IBM's 16-qubit machine.





§ LONG-DISTANCE CNOTS AND MAKING CHOICES


Each G, B, and S error above will have an error rate ε dependent on type and location. Once assigned locations, we can compose our Estimated Success Probability for a sequence of gates to be

    ESP = ∏_i (1 - ε_i).


To evaluate this score function, we conducted the following two experiments.


 §.§ Path selection for remote CNOT


Most quantum algorithms use many CNOT gates.  In an architecture such
as Fig. <ref>, it is not always possible to arrange the
control qubit and the target qubit close to each other. If not,
it is necessary to connect the qubits with the remote CNOT gate, or to
move via SWAP to the vicinity.  We define the following problem and
assess our ability to select the optimal solution using ESP by
experiment on Tokyo.

[l]Problem 1: CNOT Path Selection
The programmer wishes to execute the circuit shown in Fig. <ref>.
When the starting point (control qubit) and the end point (target qubit) for the Bi-Qubit gate (CNOT) are not neighbors, which path is the highest fidelity?

 
We conducted the following experiments.


  * Select the path predicted to complete with the highest fidelity using our proposed score function (ESP). Fig. <ref>, Fig. <ref>, and Fig. <ref> show options for 2, 3, and 4 hops path selection. The corresponding circuits are in Fig. <ref>, Fig. <ref>, and Fig. <ref>.

  * Execute both paths on the actual machine for 1000 shots. For simplicity, |000⟩ is used as the input state.
If the state of the target qubit is not equal to the state of the control qubit(|0⟩), the path can be regarded as including errors.  
As a result, the optimum path (success probability is the highest) is determined.

  * If the optimal path matches the path selected in step 1, path selection can be regarded as successful.

As shown in Fig. <ref>, the maximum eccentricity of each qubit is 4 on the largest processor made available by IBM (as of December 5, 2018). The eccentricity is the distance from a certain vertex to the furthest vertex on the same graph. Since it is sufficient to connect CNOT using routes of the number of hops, experiments were conducted up to 4 hops.





[l]Result 1
ESP was able to select the better of two routes with accuracy of 70% at 2 hops, 66.6% at 3 hops and 62.5% at 4 hops.

Of course, this leaves up to 37.5% of cases in which ESP leads us to the wrong choice. Possible reasons include:


  * The reported error value used to calculate ESP contains both bit-flip and phase-flip errors, but our experiments reveal only bit-flip errors.

  * Long-distance resonances and cross-talk within the system mean that a series of gates doesn't behave the same as an isolated gate. 

  * The actual state of the machine drifts faster than the calibration (Randomized Benchmarking) data is updated, so the gate error rates we use may be out of date.

We don't believe that reason 3 is an important effect. Our future plans include tests that will distinguish the relative importance of reasons 1 and 2.





 §.§ Circuit Selection for Remote CNOT

[l]Problem 2: Circuit Selection
The programmer wishes to execute the circuit shown in Fig. <ref>. When the CNOT gate is executed with remote qubits, there are multiple theoretically equivalent circuits as shown in Fig. <ref>.

However, considering errors, these are not necessarily equivalent. Which circuit has the highest fidelity?



We conducted the following experiments on Tokyo.


  * Select the circuit predicted to have the highest fidelity from B, C, and D in Fig. <ref> using our proposed score function (ESP).

  * Execute all three circuits on IBM Q20 Tokyo for 1000 shots. For simplicity, |000⟩ is used as the input state. 

If the state of the target qubit is not equal to the state of the control qubit (|0⟩), the circuit has incurred an error.

As a result, the optimum path (one with highest success probability) is determined.

  * If the optimal circuit matches the circuit selected in step 1, path selection can be regarded as successful.


[l]Result 2
ESP was able to select the optimal circuit among three candidates with accuracy of 40%. 

ESP selected Circuit B 35% of the time, circuit C 10% of the time,
and circuit D the remaining 55%. Experimentally, the optimal circuit
was B for 50%, C for 15%, and D for 35%. ESP is better than random,
which would select the optimal circuit only 1/3 of the time.


When ESP is used, which circuit is selected based on the magnitude of Bi-Qubit gate error (B) as shown in Fig.<ref>. B_01 is the Bi-Qubit gate error for Q0 and Q1. B_12 is the Bi-Qubit gate error for Q1 and Q2. Intuitively, because C is one fewer two-qubit gate, we would expect it to be the best most of the time.
In our experimental results, circuit C is chosen less often than B and
D. This is because the difference between B_01 and B_12 is
large in the current processor.

If only the number of CNOT gates is used to predict fidelity of the
quantum circuit, this will be the best choice only 15 % of the time.

[l]Problem 2': Circuit Selection  (including SWAP)
  Perform the same circuit as Problem 2 with additional circuit
  options, including permitting the relocation of a qubit,
  using the SWAP gate shown in Fig. <ref>. Which circuit is the
  highest fidelity?

Because Tokyo doesn't implement a SWAP gate natively, we decompose a SWAP into
three CNOT gates. Considering the direction of CNOT gates, we have two possible decompositions.
Circuits shown in Fig. <ref> can be
implemented into circuits shown in Fig. <ref> and
Fig. <ref>. Circuits shown in Fig. <ref> can be
implemented into circuits shown in Fig. <ref> and
Fig. <ref>.  We conducted the experiments in the same way as
problem 2, using circuits B to H.





[l]Result 2'
  ESP was able to select the optimum circuit from among seven candidates 25% of the time.
  Fig.<ref> shows the fidelity of selected circuit
  relative to the other candidate circuits.


The average of the ESP of the circuit selected was 0.8255. On the
other hand, the fidelity obtained by executing the circuit selected by
ESP on Tokyo was 0.8609.  With seven candidates to choose from, ESP's
25% is better than selecting randomly, which will choose the optimal
circuit only 1/7th of the time.  In most cases, we chose an
above-average circuit.

The fidelity of the selected circuit greatly exceeds ESP.  This may be
because we used only the 0 state at the input of this experiment,
whereas the single-qubit gate error used to compute ESP is for a dense
gate set. Alternatively, this may be because our experiments are more
limited than full tomography and do not reveal phase flip errors.

In order to show this, we experimented with |+++⟩ input state in Problem 3'.



[l]Problem 3: Circuit Selection  (on Poughkeepsie)
Perform the same circuit as Problem2’ on  the other 20-qubit processor called Poughkeepsie. Is there any change in the reliability of circuit selection by ESP?

IBM released a quantum processor called Poughkeepsie to IBMQ network members in the winter of 2018.
Table <ref> shows the performance specifications of Poughkeepsie.





[l]Result 3
 ESP was able to select the optimum circuit from among seven candidates 43% of the time. Fig.<ref> shows the fidelity of selected circuit relative to the other candidate circuits.


Among the options, the average of the Fidelity of the circuit with the best result was 0.8492. On the other hand, the average of Fidelity of the execution result of the circuit selected by ESP was 0.8405, and the difference between these was 0.87%. This is extremely small compared to 3.5% in tokyo, and it can be said that the reliability is improved.

The main factor is considered to be the improvement in the reliability of fitting function of the Randomized Benchmarking. That is, there is a possibility that the value of the error is less likely to fluctuate.



[l]Problem 3': Circuit Selection  (|+++⟩)
Perform the same circuit as Problem 3 but with different initial input states on Poughkeepsie. Is there any change in the reliability of circuit selection by ESP?


The same circuit selection is performed by changing the quantum state before CNOT execution to a state other than 000. The  state was used for simplicity. As an alternative to the X-axis measurement, the Z measurement was performed after the H gate was performed after the CNOT. The processor used Poughkeepsie to facilitate comparison with result 3

[l]Result 3'
 ESP was able to select the optimum circuit from among seven candidates 36% of the time. Fig.<ref>  shows the fidelity of selected circuit relative to the other candidate circuits.




Among the options, the average of the Fidelity of the circuit with the best result was 0.8077. On the other hand, the average of Fidelity of the execution result of the circuit selected by ESP was 0.7966, and the difference between these was 1.10%. 

A significant improvement in accuracy is seen over result 2 ', but a little less accurate than result 3. Also, the overall fidelity itself is low.

Since the number of gates is increasing, it is estimated that the prediction accuracy has fallen.


§ COMPILING COMPLETE PROGRAMS



In the previous section, we discuss several possible realizations of a single CNOT
gate on IBM's QX architecture and compare estimates and observational results of their probability of success.  A general purpose compiler,
however, is required to combine such realizations
in order to deal with much more complex quantum circuits with many CNOT gates.
Since there are several possible combinations of realizing the circuit,
the compiler must be able to distinguish more reliable realizations from the others.
To give a metric of several realizations, we extend the definition of Eq. <ref>'s
Estimated Success Probability; we define the Estimated Success Probability of a
circuit C as the product of ESPs of its components:

    ESP(C) = ∏_g ∈ C ESP(g) = ∏_g ∈ C (1 - ε_g).


In this model, we assumed that

    
  * each gate and measurement in a circuit either succeeds completely or fails to execute and stops the whole execution; and
    
  * the probabilities of such failures are independent of each other and depend only on the physical qubits on which the operations act


With this formalization, the compiler's task is defined to be the maximization of
ESP(C), and we apply a combinatorial optimization method described in the
following subsections to this end.

Although Equation <ref> is simple and easy to
calculate for the optimization process, we cannot use it when evaluating
optimized circuits on real NISQ computers.  The problem is that, in general, the output of a
quantum circuit is not a single value but a probability distribution.
Imagine a quantum circuit with Hadamard gates and measurements for each qubit.
Since this circuit produces a uniform distribution over
all of the possible measurements, we cannot figure out whether a single-shot measurement of
the circuit on a quantum device is a successful execution or not.  Instead, we
have to sample multiple shots from the circuit and compare the resulting empirical
distribution against the ideal distribution a noiseless quantum
computer would produce.  We propose using the KL divergence between the empirical and
ideal distributions as a distribution-based measure of a compiled circuit
and studied the relationship between ESP and KL divergence on IBM Q20 Tokyo
machine.



 §.§ Search Space

In this section, we scrutinize the search space of the ESP maximization problem.


Each state we visit in the optimization process is parameterized by two parts: the
execution state of gates and the qubit mapping.  A gate execution state
describes which gates have already been executed and which have not.  Let N be the
number of gates, then the number of execution states is 2^N.  Moreover, for
each gate execution state, there exists
_QP_V = Q× (Q-1) ×…× (Q-V+1) arrangements of quantum
variables onto the physical qubits <cit.>.


The search space of this problem can be visualized as a collection of hypercubes.
Each hypercube consists of a complete
set of execution states, and there is one corresponding hypercube for each
qubit mapping.  There are two types of transitions between the states: gate
execution and swap insertion.

Execution of a gate sets an execution flag of the gate execution state, moving
the state upward from the 000… 0 vertex toward 111… 1 in the same hypercube.  On the other hand, insertion of SWAP
gates does not change the execution state while it changes the qubit mapping.  Thus
SWAP insertion moves the state laterally, making a jump to another hypercube.
Under this setting, each path from a state at the bottom to
a state at the top constitutes a possible compiled circuit, and the compiler's task can be
interpreted as finding the best path from the bottom to the top.

As discussed in the prior sections, CNOT gates can be executed if and only if
the control qubit and the target qubit are adjacent to each other in the
physical topology.  This adjacency constraint invalidates some edges.
Moreover, to preserve the logical function of the given quantum circuit during
the compilation, some gates must be executed before other gates.  We call this
constraint of order a gate dependency.  Gate dependencies forbid some
transition edges in hypercubes. 

A naive brute-force algorithm will traverse 2^N ×_QP_V states in the
worst case, which is infeasible. Additionally,
 <cit.> shows that finding the optimal path is an
NP-hard problem when the optimization target is the number of inserted SWAP
gates.  Thus, finding the optimal solution would be intractable in practice.



 §.§ The Optimization Algorithm



Therefore, we propose a beam-search based heuristic optimization algorithm.
Beam search is a modified version of breadth-first search where at each depth,
instead of adopting all candidates as breadth-first search does,
only a fixed number of promising states are searched. The number of candidates kept is called the beam
width B. As the beam width grows, the number of states that the algorithm visits
increases and better solutions will be found, at the cost of higher time and
space complexity. Specifically, if B = 1, beam search is
identical to greedy search, and to breadth-first search if B →∞.

In addition, the choice of initial qubit mappings is crucial because it corresponds to
the initial states of the beam search.  One possible way to generate initial
mappings is to assign quantum variables to physical qubits randomly.  Besides
that, several papers <cit.> have proposed heuristic methods to generate
proper mappings in order to get shorter or more shallow circuits.  Our approach
combines these methods.  In other words, we start the search with an initial
qubit mapping computed by a heuristic method in addition to random initial mappings.
This approach enjoys the performance of heuristics while also exploring the
possibility of nicer configurations through chance.  We denote
the number of random initial mappings as M.

We show the compilation algorithm in Algorithm <ref>.  In this
algorithm, the number of executed gates inside all the states in the next state
set (S_i+1) is incremented by one from those of the previous state set (S_i).
Therefore, after N iterations of the outermost loop, S_N contains
states with all gates executed.

Inside the loop, we iterate the state set S_i and update it by the new set
S_i+1.  Since the innermost loop only checks N gates, the inside of the loop runs
N|S_i| times for each i.  Inside the loop, the dependency check
(line 7) can be done in constant time with auxiliary information
encoded in state. Moreover, the BEST_SWAP function call (line 9) is also a
constant time operation with caching.  Therefore, the most compute-intensive
part of the algorithm is calculating the score of the state at line 12.
Since UPDATE_SCORE takes O(N) time (described in Section
<ref>), the complexity of the update is O(N^2|S_i|) for each
i.  On the first iteration, |S_0| = M because S_0 is filled with initial states and
when i > 0, |S_i| ≤ B holds because beam search prunes the states.
Therefore, the total complexity of this algorithm is O(N^2 M + N^3 B), where
the first term corresponds to the first iteration and the second term
to the rest.

We can ignore the complexity of pruning (line 17) as pruning takes
O(|S_i+1|) = O(N|S_i|) time with the Floyd-Rivest algorithm
 <cit.>, which has lower complexity than
computing the score of each new state.





 §.§ Subroutines for Compilation Algorithm

In the following sections, we describe the three subroutines which appear in the
compilation algorithm.



  §.§.§ Scoring States


The function UPDATE_SCORE computes the score of states. Pruning removes
states with lower scores calculated by this function.

The simplest score function is just using the ESP of executed gates.
Incorporating information of future gates can further improve the
selection of states.  In this compiler, we multiply current ESP with the
imaginary ESPs of each gate to be executed.  The imaginary ESP is the
Estimated Success Probability of SWAP gates to satisfy the adjacency constraint
under the current mapping times the success probability of the
gate. Imaginary ESP can differ from actual ESP because the current mapping
can differ from
mappings at the time of gate execution due to the insertions of SWAP gates
required for the execution of former gates.

We show this computation in Algorithm <ref>.  This algorithm
enumerates unexecuted gates, so the complexity of computing the score is
O(N).





  §.§.§ Heuristic Initial Mapping: Greatest Connecting Edge Mapping

As mentioned above, our compiler adopts random and heuristic initial mappings as
the starting points of search.  The core idea of our initial heuristic
mapping is to map more significant edges between the quantum variables to
less noisy edges in the physical topology.  This idea comes from the fact
that error rates of CNOT gates are a magnitude higher than those of
single qubit gates on the IBM QX architecture <cit.>.

This heuristic starts with counting the number of CNOT gates executed over for
each pair of quantum variables.  These numbers constitute a guest graph,
a graph whose vertices correspond to each quantum variable and edges to the
number of CNOT gates over them.

Next, we scan the edges of the guest graph in a similar manner to Prim's algorithm <cit.>. However, instead
of scanning from the lowest to greatest, this algorithm scans from the greatest
to lowest, constructing a maximum spanning tree over the guest graph.

During the first scan, both endpoints of the chosen edge are not mapped yet.
Thus, we pick the least noisy edge from the physical topology and map those two variables
to this edge.

In the following scans, one endpoint of the chosen edge is already
mapped, and the other is not, so the chosen edge is the greatest edge
connecting the set of mapped variables and that of unmapped variables.  The
name of the heuristics comes from this.  Since one of the variables is already
mapped, it would be a good idea to map the other to the adjacent qubit in the
physical topology.  So we search for the free qubit adjacent to the qubit the endpoint
is mapped to and adopt the qubit with the lowest CNOT error rate between the
qubits.  We show pseudo-code in Algorithm <ref>.
During the scan, a mapped qubit may not have free qubits adjacent to
itself.  In that case, this algorithm skips that edge and maps unmapped
variables to the remaining qubits randomly at the end.





  §.§.§ Finding Best Swap Sequence

In our compiler, we consider only the realizations of CNOT gates via the
insertion of a sequence of SWAP gates.  The compiler needs to know how to
insert a SWAP sequence to change the mapping such that the adjacency constraint is
satisfied in the new mapping.  BEST_SWAP function computes such SWAP sequences
for each physical qubit in the topology.

The algorithm is shown in Algorithm <ref>.  The main idea of this
algorithm is to find the best “meeting edge” for the given pair of qubits.
Each qubit will be moved to the endpoints of the meeting edge, and finally, we
execute the CNOT gate over the edge.  The ESP of this movement plus the CNOT
gate can be calculated as the product of ESP of the SWAP sequences and ESP
of the CNOT gate over the meeting edge.  We can run the shortest path algorithm
over the physical topology to find the SWAP sequence with optimal ESP.

In Algorithm <ref>, we run the shortest path algorithm in the
loop; in the implementation, however, we ran the Warshall-Floyd algorithm <cit.> at the
beginning of the compilation to compute the optimal path for all pairs of
qubits, and we fetch the result.  Moreover, the results of calls to BEST_SWAP
themselves can be cached.  Therefore, we compute BEST_SWAP for all possible
combinations of qubits before Algorithm <ref> and we use the cached
sequence in the main loop.





 §.§ Experimental Evaluation of Compilation




  §.§.§ Probability Distribution Based Evaluation


In this section, we explain the experimental evaluation of the compilation on
IBM's Q20 Tokyo machine.  As described in Equation <ref>, our
compiler uses a simple multiplicative error model to optimize the ESP of
quantum circuits.  However, ESP has difficulty as an metric of the quality
of the compiled circuits when it comes to the evaluation of real quantum
hardware.

The difficulty is that the experimental result of a quantum circuit cannot be
judged either successful or unsuccessful in general.  Imagine a quantum circuit
with a Hadamard gate and measurement for each qubit.  This circuit will produce
a uniform distribution over the all possible measurements.  Therefore, we
cannot decide whether the circuit succeeded or failed from one shot of measurement.
Instead, we have to focus on how close the empirical probability distribution
sampled by running the compiled circuit on a NISQ machine multiple times and the
ideal distribution an imaginary noiseless quantum computer will produce are.

To deal with this difficulty, we propose a probability distribution based
measure of compiled circuits.  For each quantum circuit C, let P_ideal be
the ideal distribution of circuit C and P_empirical be the empirical
distribution we observed by running compiled circuit on a machine.  Then, we
define KL divergence D_KL(P_ideal || P_empirical) between those two
probability distributions as follows:

    D_KL(P_ideal || P_empirical) = ∑_x P_ideal(x) logP_ideal(x)/P_empirical(x)

where x runs over the possible measurement results. It's known that
P_ideal = P_empirical a.e. ⇔ D_KL(P_ideal || P_empirical) = 0
so the lower D_KL is, the better the quality of the compiled circuit is.

Boixo et al. proposed the cross entropy, which is equal to KL divergence plus a certain
offset, as a benchmark for verifying Quantum Supremacy <cit.> in NISQ
devices <cit.>, however, no papers yet use such
measures for compiling quantum circuits as far as we know.



  §.§.§ Experiment and Result






























To test our compiler, we compiled Cucarro's ripple-carry adder
circuit <cit.>. Fig. <ref>
shows the schematic. In the test bench, we first applied Hadamard gates for each
qubit to initialize the states, and then passed the qubits to the adder.
Finally, we measured the addition result and the carry-out in the computational
basis. We adopted the adder circuit because:

    
  * the computation is simple to understand, and the ideal distribution is easy to compute; but
    
  * the addition circuit is made of a complex combination of CNOT gates, and
    
  * addition is a key component of many quantum algorithms, so its performance is inherently important.


In this experiment, we compared the following two compilation algorithms:

    
  * The beam search compiler.
    We used B = 10000 and M = 1000 as the parameters.
    
  * A random selection compiler.
    Instead of ranking states via the score function, this compiler randomly picks a
    state s from S_i and set S_i+1 as a singleton {s} in Algorithm
    <ref>. Also, we randomly selected one initial mapping as the
    starting point.

Since the initial execution state is a superposition state where all values appear with
equal probability, the output of this circuit is identical to the distribution
of the sum of two rolls of dice.  Fig. <ref> shows the ideal
distribution and observed distributions of two compilers.

We tested the adder circuits for input register sizes of one, two, and four qubits on IBM Q20 Tokyo
machine.  Table <ref> shows the number of gates and the time required to compile.

Figures <ref>–<ref> show the
results.  The horizontal axis is the ESP of the compiled circuits.
Note that the horizontal axis is a logarithmic scale.  The vertical axis shows
the KL divergence between the observed distribution and the ideal distribution.
We sampled 5000 shots to compute one KL divergence for each experiment.
Moreover, to consider the variation of noises during the experiments, we ran
the same circuit several times.  Each point in the plot corresponds to the
median of KL divergence and the error bar shows the maximum and the minimum for
each compiled circuit. We have also included the KL divergence between the
ideal distribution and the uniform distribution as a guide.

First, we can see the points of beam search tend to concentrate in the right
half in all plots.  This shows beam search can indeed choose
realizations of gates such that ESP of the whole circuit improves dramatically.  Since the
horizontal axis is a logarithmic scale, our technique often results in one
magnitude higher ESP.

Next, Fig. <ref> shows that most of the 1-qubit adder
experiments results in better output distributions than a uniform
distribution.  As the number of qubits increases and the circuit gets more
complicated, however, the KL divergence gets worse.  For a 2-qubit adder, only
half of the experiments performed better than a uniform distribution, and for a
4-qubit adder, no experiments did.  This tendency can be observed regardless of
the compilation algorithm.

Finally, we analyzed how KL divergence differs as the ESP of the compiled
circuit changes.  We draw the linear regression of KL and ESP as a dashed line
to each plot.  For the 1-qubit adder experiments shown in Figure
<ref>, there is a clear negative correlation between ESP and KL
divergence. Its correlation coefficient was -0.475.  Since lower KL
divergence means the output of the compiled circuit is closer to the ideal, the
negative trend implies that our approach of compiling a quantum circuit with
higher ESP actually improves the reliability of compiled circuits for the
1-qubit adder circuit.

When it comes to 2-qubit adder experiments (Fig. <ref>),
the correlation coefficient of ESP and KL is -0.0279, which means there is
almost no correlation between ESP and KL.

Although there is also negative correlation between ESP and KL for the
4-qubit adder experiments, the absolute values of KL divergence are much worse
than that of even the uniform distribution.  So we can see the improvement of
KL divergence here, but the improvement is too small to make the computation
reliable.



§ FUTURE WORK AND CONCLUSION




In this paper, we proposed two reliability metrics for quantum
gates and circuits: Estimated Success Probability for use during
compilation and KL divergence for assessing results.  Estimated
Success Probability is a composable measure of the quality of quantum
operations. The ESPs of qubit initialization, single qubit gates, CNOT
gates, and measurements are the error rates given by randomized
benchmarking.  We defined the ESP of a composite circuit as the
product of the ESPs of its components.  Due to its composability,
compilers can calculate ESP easily, so we adopted full-circuit ESP as
the optimization target of our compiler.


Since we cannot experimentally observe the ESP of circuits that end
with a superposition state just before measurement, including
important building blocks for other algorithms such as adders and the
Quantum Fourier Transform, we use KL divergence for comparing the
output distributions of experiments across compilation algorithms.

In lieu of full tomography, KL divergence is a useful intermediate
tool.

Experiments on path selection and circuit selection showed that using
ESP gives lower (better) KL divergence than random choice among
shortest-path candidates.  However, even in the relatively simple case
of selecting a two-hop path, our best success rate is only 70%.


Despite the difficulty of path selection, our experiments showed that
our beam search-based compiler improves the ESP of a quantum
circuit. Our experiments with 1-qubit adders showed that the
improvement of ESP led to lower KL divergence, which means our
approach of optimizing ESP experimental can mitigate errors in NISQ
devices, at least for smaller circuits. However, as the circuit
becomes complex, the relationship between ESP and KL divergence
vanished, or KL got much worse than even the uniform
distribution. This behavior demonstrates the limit of current NISQ
computation, while highlighting the importance of compilation
aggressively focused on errors.


Although ESP is better than random selection, in some cases we can
make the optimal choice out of seven candidates 43% of the
time. This is due to the fact that ESP and the physical reality are
divergent.

One shortcoming of our current approach is that it does not take into
account memory errors.  Due to the complexity of gate scheduling
within Qiskit, augmenting ESP via a gate-by-gate, qubit-by-qubit
insertion of Identity (“Wait”) gates complete with T_1 (energy
relaxation time) and T_2 (dephasing time) decoherence is a difficult
challenge.  We are considering methods to incorporate the execution
time and apply a blanket decoherence term.


We plan to test other circuits such as QFT for more
comprehensive benchmarking of the compiler. However, our evaluation
will not work for circuits which appear in the context of quantum
supremacy because our KL divergence based evaluation requires deriving
the ideal distribution with a classical computer
beforehand. Therefore, we need a method for estimating KL divergence
to better generalize our approach.  Additionally, we need a method for
extrapolating from KL divergence to the prospects of seeing the
expected quantum interference patterns that drive quantum algorithms;
this will involve assessing sign errors as well as bit flip errors.


Finally, now that we have shown the value of error-aware compilation,
we hope to influence the design of the Qiskit compiler (and compilers
for other languages and systems) or have our code incorporated
directly into the standard release.  As our ability to correctly
predict success improves, the tools can also be used as part of an
evaluation of architectural tradeoffs between different types of
system couplers and qubit layouts, influencing the design of future
generations of quantum computers.



§ ACKNOWLEDGEMENT

The results presented in this paper were obtained in part using an IBM Q quantum computing system as part of the IBM Q Network.
The views expressed are those of the authors and do not reflect the official policy or position of IBM or the IBM Q team.




ieeetr



