{'fraction_non_alphanumeric': 0.029586404586404585, 'fraction_numerical': 0.0068591318591318595, 'mean_word_length': 4.601108562691132, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
LEQA: Latency Estimation for a Quantum Algorithm Mapped to a Quantum Circuit Fabric

This paper presents LEQA, a fast latency estimation tool for evaluating the performance of a quantum algorithm mapped to a quantum fabric. The actual quantum algorithm latency can be computed by performing detailed scheduling, placement and routing of the quantum instructions and qubits in a quantum operation dependency graph on a quantum circuit fabric. This is, however, a very expensive proposition that requires large amounts of processing time. Instead, LEQA, which is based on computing the neighborhood population counts of qubits, can produce estimates of the circuit latency with good accuracy (i.e., an average of less than 3% error) with up to two orders of magnitude speedup for mid-size benchmarks. This speedup is expected to increase superlinearly as a function of circuit size (operation count).


INTRODUCTION
To accurately calculate the latency (total execution time) of a software program, one needs to simulate or run it on a specific processor. Changing the processor architecture including the size of cache memories or internal buffers can affect the latency dramatically. A number of approaches have been proposed to estimate program latency without performing time consuming simulations [1] [2]. Researchers in the area of quantum computing face the same issue for estimating the latency of a quantum algorithm, programmed in a high-level quantum programming language such as QPL. In this field, the problem is even harder because the size of quantum programs for real-size problems is so huge that the simulation time is much more time consuming than that for classical programs [3]. 1 Devising a new quantum algorithm is a challenging task because of the complex structure of today's quantum computers and the non-intuitive principles (i.e. quantum physics) they are built upon. Currently, quantum algorithms are designed and evaluated by asymptotic runtime analysis, i.e. big notation [4]. Unfortunately, in many cases, the asymptotic analysis is too coarse-grained to be of practical use to 1 By simulation, we only mean tracing the execution of quantum operations. Simulation of a quantum program and calculating the results cannot be performed efficiently on classical computers even for mid-size problems. algorithm developers. Another problem is that quantum computers built using the current technology are only capable of executing toysize programs, so they cannot be used to experimentally determine the latency of a quantum program. Hence devising a fast, yet accurate, method for estimating the latency of a program is necessary. This method would enable quantum algorithm designers to evaluate their new algorithms and learn efficient ways of coding their quantum algorithms by quickly comparing the latency of different software coding techniques. Moreover, this method allows designers of quantum error correction codes (QECC) to investigate the effect of different error correction codes on the latency of quantum programs. Latency is an important factor for QECC designers since quantum computers allow only a limited amount of time for running a quantum program without using error correction. QECC has a high impact on the latency. At the same time, one needs to know the latency of a quantum program to know how much error correction it needs. So there is a complex inter-dependency between the quantum algorithm and its latency on one hand and the QECC used on the other hand. In this paper, we present a procedural method to accurately and quickly estimate the latency of a quantum program. A tool called quantum algorithm latency estimator (LEQA) is developed based on this method. To the best of our knowledge, no research has been conducted on this topic before. The rest of this paper is organized as follows. Section 2 uses the prior art (such as [5] and [6]) to describe a (somewhat novel) design flow for compiling a quantum algorithm and mapping it to primitive quantum structures on a 2-D plane. Section 3 explains the estimation method used for the latency calculation. A procedural method is presented for estimating the average routing latency for the CNOT gates. This section introduces a new parameter called , which is the average routing latency of a qubit in an average-size presence zone when the routing channels are not congested. Estimation of this parameter is explained followed by the detailed description of LEQA (a prototype software implementation of the proposed method). Section 4 presents experimental results while Section 5 concludes the paper.

A QUANTUM DESIGN FLOW
A typical quantum circuit fabric consists of an infinite 2-D array of identical primitive structures (called quantum templates in this paper), each structure containing some sites for generating/initializing qubits, measuring them, performing operations on one or two qubits, and channels for moving qubits or swapping their information. Unfortunately, dealing with this primitive template array is very cumbersome and unwieldy. So in practice another 2-D array of supertemplates (which we call tiles) is built. Each tile comprises a number of primitive templates. Instead of mapping a quantum circuit directly to the quantum fabric, quantum circuit is mapped to this tiled architecture (see below). A quantum logic synthesis tool (surveyed in reference [7]) generates a reversible quantum circuit. Every qubit in the output circuit is called a logical qubit, which is subsequently encoded into several physical qubits to detect and correct potential errors. To prevent the propagation of errors in the quantum circuit, the (reversible) logic gates in the synthesized circuit (which are typically NOT, CNOT, and Toffoli gates [8]) must be converted into Fault-Tolerant (FT) quantum operations. A possible universal (but redundant) set of FT quantum operations includes CNOT, H (Hadamard), T (π/4 rotation), T † (-π/4 rotation), S (phase), X, Y and Z gates. Note that these gates are all one and two-qubit gates. Implementation of these FT quantum operations depend on the picked error correction method. Note that the set {CNOT, H, T} constitutes a universal basis for quantum circuit realization-the other operations are included to enable more logical simplification in the process of converting the logic synthesis output to the FT quantum operation realization. Each quantum fabric is natively capable of performing a universal set of one and two-qubit instructions (also called native quantum instructions). This set differs among various quantum fabrics. Each FT quantum operation can be implemented by using a composition of these native quantum instructions. The transformation from logical gates (results of the quantum logic synthesis) to the FT quantum operations and from the FT quantum operations to the native quantum instructions can be called quantum FT synthesis and quantum fabric synthesis, respectively. Quantum FT and quantum fabric synthesis are outside of the scope of this paper. Each of these FT quantum operations performs a desired function on one or two logical qubits as input producing one or two logical qubits as output; each of the input qubits is encoded with some number of physical qubits. The output qubits will also be coded. Moreover, each of these FT quantum operations requires syndrome extraction circuitry following the quantum gate in order to detect and correct errors (up to a certain limit) that may have been introduced by the quantum operation. Based on the adopted encoding scheme, implementation of each of the aforementioned FT quantum operations may require hundreds to tens of thousands of native quantum instructions in a given quantum fabric. Various works (e.g. [9] and [10]) have suggested using the tiled quantum architecture (TQA), composed of a regular two-dimensional array of Universal Logic Blocks (ULBs) to avoid dealing with this complexity. Notice that each ULB in TQA is capable of performing any FT quantum operations. ULBs are separated by the routing channels, which are needed to move logical qubits (or information about these qubits) from some source ULBs to a target ULB in the TQA. A pictorial representation of the TQA is shown in Figure 1. The quantum structures placed at the junctions of routing channels may be thought out as quantum crossbars (possibly with some qubit purification capability [11]). Routing channels and quantum crossbars are also built from quantum templates.

Figure 1. A 3×3 tiled quantum architecture (TQA)
A ULB is analogous to a Configurable Logic Block (CLB) in an FPGA device, in that it can implement any of a set of target functions. Moreover, the same ULB (as identified by its unique row and column indices in the ULB array) can be configured to perform different FT quantum operations at different times as needed. This is analogous to an on-the-fly-reconfigurable CLB. After appropriate high-level transformations, a quantum algorithm may be represented as a quantum operation dependency graph (QODG), in which nodes represent FT quantum operations and edges capture data dependencies. A one-qubit operation is represented by a node with one edge entering it and one edge leaving it. On the other hand, a two-qubit operation is shown using a node with two edges entering it and two edges leaving it. One edge is called control edge while the other is called target edge. It is assumed that the order of gates does not change after the synthesis step. If two edges in the QODG come from one node and go to another node, the edges are combined in order to keep the graph simple. Also, due to the no-cloning theorem, a fan-out in the circuit is forbidden. A start node is added which connects to the first-level nodes in order to satisfy the initial dependencies. Also an end node is added where all the last-level nodes are connected to it. These two extra nodes simplify the problem formulation. A sample synthesized quantum circuit and the QODG constructed from it is presented in Figure 2. Figure 2. (a) The synthesized ham3 circuit [12] for size 3 Hamming optimal coding. Note that this circuit only contains FT gates. (b) A QODG constructed from the circuit shown in (a). Numbers are added to relate each node to its corresponding operation in the circuit. Based on the target quantum fabric and error threshold, a particular quantum coding is selected, and subsequently, a high-level tool maps the QODG into a TQA, where each ULB (tile) in this architecture can implement any operation in a fault-tolerant way. The latency of the quantum algorithm mapped to the TQA can be calculated as the length of the longest path (critical path) in the mapped QODG, where the length of a path in the QODG is the summation of latencies of operations located on the path plus routing latencies of their qubit operands. Note that the critical path of the mapped QODG may not be the same as the critical path of the original QODG because the latter does not contain routing latencies of logical qubits. These latencies change the scheduling slacks and hence may change the critical path of the entire graph. Mapping a QODG to a TQA comprises of three intertwined steps: scheduling, placement, and routing. These steps depend on each other. For example, the result of placement and routing can increase the routing latency of a logical qubit and hence the qubit may fail to meet the timing requirements of the scheduling. As a result, the operation should be deferred by one or more scheduling steps. The quantum mapping problem, similar to the corresponding problem in the traditional VLSI area, is a hard problem. Hence, several heuristics have been proposed in the literature for solving it near-optimally [9][10] [13] [14]. Unfortunately, these heuristics are still very slow. They produce the mapping solution with the details of every qubit movement on the TQA. Since quantum computers are still not mature enough to handle large-scale problems [15], detailed information that a quantum mapper produces is excessive and not very useful. Hence, we introduce a model to quickly estimate the latency of a quantum algorithm as explained next.

ESTIMATING LATENCY OF A QUANTUM ALGORITHM
The latency of a quantum algorithm may be calculated as follows: where is the set of one-qubit FT operations (such as H, T, S, etc.); and are the number of CNOTs and operations of type (one-qubit FT operations) on the critical path; and determine the delay of CNOT and the operation of type respectively; and capture the average routing latency for CNOT and the operation of type . Note that the equation treats one and two-qubit operations differently. The only two-qubit FT operation is CNOT while there are different one-qubit operations. and can be determined by calculating the critical path of the circuit. As explained earlier, considering the critical path of the original QODG instead of the critical path of the mapped QODG introduces some errors to the estimation model. So the values of and will be added to the operation delays in the QODG in order to determine the critical path more accurately. and depend on the underlying fabric technology, the error correction and the control techniques used. These parameters are the output of a ULB fabric designer tool which has a very low runtime execution (in the order of at most a few minutes) and produces exact results which can be used for any algorithms. Hence, values of these parameters for all types of FT operations are assumed to be given.
can be estimated empirically since routing of a qubit is not too complex. A one-qubit operation can be done in the ULB where the qubit currently resides or in the nearest free ULB if the current location is also occupied by another qubit. Value of is set to 2 × where is a physical parameter which captures the time that a logical qubit needs to move from any ULBs, channels, or quantum crossbars to another ULB, channel or quantum crossbar in its neighborhood. This empirical result shows that on average each qubit needs to move to its nearest ULB for a one-qubit operation. The main challenge is to estimate which is more interesting as it represents the average traveling (routing) time of two logical qubits from their source locations to the target ULB (i.e., the ULB where the two qubits will interact). This value accounts for the traffic congestion in the routing channels. In this paper, a procedural method for estimating is suggested. Knowing this value and estimating the critical path, one can calculate the latency of a quantum program using Equation (1).

Estimating the Average Routing Latency for CNOT
The wire length estimation problem in the traditional VLSI area [16] approximates the average total wire length among all of the connected standard logic cells before performing the time-consuming cell placement and routing steps. Our problem is similar to the aforesaid, but in fact it is more complex. This is mainly because also depends on the scheduling of a QODG. More precisely, mapping of a QODG to a quantum fabric consists of three steps: scheduling, placement and routing. These steps are interrelated, and none can be optimally solved without solving the others. Placement and routing affect the result of scheduling (which in turn affects the timing slacks in the QODG.) Placement cannot be done optimally without considering the effect of routing and channel congestions. Also note that in the placement problem, one should assign both the logical qubits and the logical operations to ULBs. Compared to the VLSI placement, this problem has (dynamically) moveable cells since the qubits move during the execution of a program. Also two or more operations may be assigned to a ULB as long as they are scheduled to be done in different time slots. Moreover, the size of QODG for realsize problems is generally far larger than any standard VLSI gate-level netlists [10]. So, this estimation problem is more complex than the traditional VLSI counterpart. For each logical qubit, a hypothetical presence zone is assumed in which the qubit performs most of its interactions. This zone also shows the area where the other qubits that interact with the qubit in question are located at some point in time. These zones are located in different places of the TQA fabric. They can overlap with each other. An overlap resembles congestion since it is possible that more than one qubit pass the overlapping area at the same time. Figure 3 depicts an illustration of five presence zones placed randomly on a fabric showing the interaction among five qubits. The overlapping area among zones 3, 4, and 5 is the most congested area.

Figure 3 Five presence zones placed randomly on the fabric
Since the result of the placement is not known a priori, the zones are assumed to be placed randomly (uniformly and independently) on the fabric.
can be estimated using Equation (2).
where is the total number of logical qubits; Ε[ ] is the expected surface of the fabric covered by exactly overlapping presence zones; is the average routing latency of a qubit in an average-size presence zone when all the routing channels are occupied by qubits; and is the area of the fabric and it is equal to the total number of ULBs assuming that each ULB is a 1 × 1 square. Equation (3) shows a constraint on Ε[ ]. Note that the summation index in the constraint starts at 0 instead of 1 since some parts of the fabric may not be covered by any presence zones. Since calculating the latency for the unoccupied surface is meaningless, is used in Equation (2) where , is the probability that the ULB at position (x,y) on the fabric is being covered by a qubit's presence zone randomly placed on the fabric; and are width and length of the fabric. (Remember that a fabric is modeled as a grid of × square-shape ULBs and × = .) The coefficient is the number of ways to choose presence zones from the total presence zones (i.e. which equals to the total number of logical qubits). The two summations add the probability that each of the ULBs on the fabric is covered by exactly presence zones. The overall equation calculates the expected surface of the fabric covered by exactly presence zones. Calculating this equation times and using it in Equation (2)    is added between nodes and if these two qubits interact with each other. Weight of this edge, which is denoted by ( ), is equal to the number of two-qubit operations between and . Note that edges are not directed, so and refer to the same edge. Clearly, IIG(V,E) has no self-loops since no edges are added for one-qubit operations. is defined as the number of neighbors of node in the IIG(V,E). It is equal to deg ( ) which is the degree of node in the IIG(V,E). We model the area of the presence zone associated with , which is denoted by , as follows: Addition of one to the term accounts for the qubit itself. (There are + 1 qubits in the presence zone.) Qubit travels inside this zone and interacts with qubits. It visits ∑ ( ) ∀ ∈adj( ) number of ULBs which may not be necessarily unique during the program execution. The average size of presence zones, B, can be calculated by using a weighted average over the size of the presence zone of all logical qubits: sums over the weights of all adjacent edges of the node in IIG(V,E). It increases the weight of the term if the qubit is involved in more two-qubit operations. To calculate , which was used in Equation (2), the following equation is used: where is the capacity of routing channels and is the average routing latency of a qubit for interacting with another qubits in an average-size presence zone when all the routing channels are uncongested. A channel is considered as uncongested if the number of qubits inhibiting the channel is less than or equal to . In this case, qubits can pass through the channel with the minimum delay (i.e. ). If is greater than , the channel is called congested and qubits will form a pipeline for passing through it (hence, they will be delayed depending on their position in the pipeline). We capture this increase in the routing latency by modeling the routing channels as an M/M/1/∞ queue. Figure 5 shows a pictorial view of this model. Green blocks show logical qubits that are currently using the channel. Red blocks show the qubits waiting to get access to the channel. We assume that the arrival rate of qubits has Poisson distribution with parameter since the inter-arrival time of qubits are independent and memory-less. Hence, a Poisson distribution can model it very well. The service rate is assumed to have an exponential distribution with parameter . This assumption is made to simplify the calculations. Experimental results show that this simple model performs well in practice. Knowing that the average routing latency for each qubit under the service is , can be calculated as / . Moreover, the average length of the queue, , is which is the number of qubits in the queue.

Figure 5. An M/M/1/∞ queue model for routing channels
Based on the queuing theory [17], , (i.e., the average length of the queue) can be calculated as in Equation (9). Exploiting this equation and knowing the value of , can be calculated as shown in Equation (10).
Now the values of the arrival rate ( ) and the average queue length ( ) are known. With these values, Little's formula [17] gives the average waiting (service) time in the queue ( ): This is the expression used in Equation (8). Estimation of is not a trivial task and explained in the next section.

Estimating
To estimate , a new parameter called , is defined. This variable represents the average routing latency of the qubit in an average-size presence zone when the routing channels are not congested. A weighted average over all , values, similar to the Equation (7), gives an estimation of : One way to estimate , is to randomly place + 1 qubits in the presence zone of the qubit and calculate the expected length of the shortest Hamiltonian path ( [ ℎ , ]) which goes through these qubits. These qubits can be placed anywhere in the presence zone, even they can be placed at the same location. This captures the fact that two qubit can travel to the same ULB for interaction. The reason for selecting Hamiltonian path is that according to the assumption, in a presence zone, only one qubit interacts with others, so it has to travel to locations (not necessarily unique) and interact with unique qubits. Interactions among other qubits are considered in their own presence zone calculation. A shortcoming of the aforementioned approach is that the problem of calculating the expected shortest Hamiltonian path is NP-hard [18]. Hence, the exact calculation of [ ℎ , ] is infeasible for a quick estimation method. An upper bound and a lower bound for the expected path length of traveling salesman problem (TSP) are presented in reference [19]. It assumes that ( + 1) ≫ 1 points are randomly distributed in a 1 × 1 square. Equation N c q-N c (13) presents a lower bound and equation (14) shows an upper bound for the expected path length of TSP.
lower bound: 0.708� + 1 + 0.551 (13) upper bound: 0.718� + 1 + 0.731 (14) Taking the average of the upper bound and the lower bound gives a good estimation for the expected path length of TSP. In our problem, the square length is � times greater so the result should be multiplied by � . Moreover, since TSP solution is a tour, the result should also be multiplied by ( − 1)/ to give the Hamiltonian path length which has one edge less than the tour. Equation (15) shows the resultant estimation for � ℎ , �.
By knowing the value of [ ℎ , ], , can be calculated as follows: where is a parameter depending on the physical characteristics of the fabric technology mostly the speed of moving a logical qubit through the channels. This parameter also can be used for tuning the LEQA with different quantum mappers.
is presented in the denominator to give the average routing latency for an operation.

LEQA Algorithm and Its Performance
Algorithm 1 shows the implementation of LEQA based on the presented procedural method. Note that QODG is an input of the algorithm. One can easily construct it from a synthesized quantum circuit as shown in Figure 2. Size of the fabric is another input. This value can be changed to find the optimal size for the fabric which results in the minimum delay. The other inputs are physical parameters. The runtime complexity of the algorithm may be summarized as follows: �� QODG � + � QODG � + . . log � More details on the analytical analysis to derive this time complexity are presented in the Supplemental Material section.

Simulation Setup
LEQA is implemented in Java. For the baseline, a quantum scheduling, placement, and routing tool (called QSPR) [20] was used. QSPR was minimally modified to work on the tile-based architecture of Figure 1. Table 1 lists the physical parameters of the TQA used for simulations. QSPR was also used to calculate the delay of performing FT operations on an ion-trap circuit fabric (left table). The [ [7,1,3]] Steane code was used as the encoding and error correction scheme. Hence, delays of the T and T † gates ( and † ) which are non-transversal in this coding, are higher than the others. These numbers can be adjusted based on any underlying technologies and does not limit the functionality of LEQA to a specific quantum realization technique. In the right table, the specifications of a TQA are presented. Benchmarks are taken from reference [12] and synthesized using the fault-tolerant gate library. The simple method presented in reference [4] is used to decompose n-input Toffoli and n-input Fredking gates (n>3) to several 3-input Toffoli and Fredking gates. Note that this method adds ancillary qubits to the circuit. Also no ancillary sharing is performed among the decomposed gates. The resultant 3-input Fredkin gates are replaced by three 3-input Toffoli gates. Finally, 3-input Toffoli gates are decomposed to a set of fault-tolerant gates using the method presented in reference [21] and shown in Figure 2.
LEQA and QSPR share the same parsers for parsing the inputs, the TQA specification, and physical parameters. A PC with Intel Pentium Dual-Core E5500 CPU clocked at 2.80GHz with 4GB RAM running Windows 7 and Java Development Kit (JDK) 7 is used for simulations. Table 2 shows the comparison between the actual delay computed by QSPR and the estimated delay calculated by LEQA. As can be seen, the average estimation error is equal to 2.11% while the maximum error is below 9%. Table 3 lists the information about the benchmarks as well, i.e. the qubit count and operation count. The benchmarks are sorted based on the operation count. Also Table 3 compares the runtime of LEQA and QSPR. Evidently, when the operation count grows, LEQA performs better. In the largest benchmark, which its netlist file size is more than 12MB, LEQA performs more than two orders of magnitude faster than QSPR. This trend shows that as the size of netlist grows, LEQA beats QSPR in terms of speed and still gives accurate results.

Simulation Results
As an interesting case, consider the last two benchmarks, i.e. gf2^128mult and gf2^256mult. The operation count of the latter benchmark is almost 4 times of the former one. By comparing the runtime of LEQA and QSPR for these two benchmarks, it can be seen that runtime of LEQA is increased by a factor of 3 while the runtime of QSPR is increased by a factor of 4.5. This further depicts the scalability of LEQA compared to QSPR. LEQA achieves 114X speedup over QSPR for the largest benchmark, i.e. gf2^256mult. This factor increases for larger benchmarks. Precisely, QSPR runtime scales super linearly with operation count in the circuit (with degree of 1.5) whereas LEQA runtime depends only linearly on this count (see Equation (17)). Reference [10] reports that Shor algorithm for a 1024-bit integer has 1.35×10 15

CONCLUSION
This paper presented LEQA-a fast latency estimation tool for evaluating the latency of a quantum algorithm mapped to a tiled quantum architecture. It uses a procedural method to calculate the latency of an algorithm based on computing the neighborhood population counts of qubits. Simulation results showed that in mid-size circuits, LEQA is two orders of magnitude faster than the modern quantum mapper that performs detailed scheduling, placement and routing of the quantum instructions and qubits in a quantum operation dependency graph to a quantum fabric. This speedup is expected to increase superlinearly as a function of circuit size (operation count). Moreover, LEQA could produce quick estimates of the circuit latency with sufficient accuracy i.e., an average of 2.11% error.

ACKNOWLEDGEMENT
This research was supported by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior National Business Center contract number D11PC20165. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright annotation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the U.S. Government.