{'fraction_non_alphanumeric': 0.03546787006302913, 'fraction_numerical': 0.009249244769328311, 'mean_word_length': 4.969278717720392, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Construction of Functional Representations for Quantum Algorithms

Due to the significant progress made in the implementation of quantum hardware, efficient methods and tools to design corresponding algorithms become increasingly important. Many of these tools rely on functional representations of certain building blocks or even entire quantum algorithms which, however, inherently exhibit an exponential complexity. Although several alternative representations have been proposed to cope with this complexity, the construction of those representations remains a bottleneck. In this work, we propose solutions for efficiently constructing representations of quantum functionality based on the idea of conducting as many operations as possible on as small as possible intermediate representations -- using Decision Diagrams as a representative functional description. Experimental evaluations show that applying these solutions allows to construct the desired representations several factors faster than with state-of-the-art methods. Moreover, if repeating structures (which frequently occur in quantum algorithms) are explicitly exploited, exponential improvements are possible -- allowing to construct the functionality of certain algorithms within seconds, whereas the state of the art fails to construct it in an entire day.


Introduction
Quantum computing promises to outperform classical computers in certain applications. While the theoretical background was already developed in the previous century, it is today that actual physical devices are evolving to a point where first experiments are performed that are suggested not to be easy on a classical computer. However, having hardware without efficient tools to design corresponding algorithms on it certainly presents an unsatisfactory situation. Accordingly, researchers and engineers started to develop methods and tools for important tasks such as synthesis/compilation [1]- [5], (classical) simulation [6]- [8], and verification [9]- [12]-leading to elaborate design flows and tool chains as realized, e.g., by IBM's Qiskit [13], Google's Cirq [14], and Microsoft's QDK [15].
These tools and the corresponding design tasks, however, frequently rely on representations of certain building blocks' functionality or even the functionality of an entire quantum algorithm. This poses a severe challenge since quantum functionality is most generally described by matrices of exponential dimension with respect to the size of the quantum system, i.e., 2 n × 2 n for a system consisting of n qubits (the quantum analogue to bits). To date, industrial tool chains like IBM's Qiskit hardly offer efficient and scaleable solutions for constructing and representing quantum functionality (as witnessed by the evaluations later in Section 5).
Fortunately, different approaches have been proposed that try to deal with this complexity, e.g., based on arrays [16]- [19], tensor networks [20]- [23], and Decision Diagrams [24]- [26]. Although we may be able to represent (i.e., store) the overall functionality of certain building blocks or an entire quantum algorithm using these techniques, we may not be able to construct this representation in feasible time-which constitutes a severe bottleneck for many applications in the domain of quantum computing. This is caused by the fact that, even though individual quantum operations typically emit a sparse, tensor product structure, their composition requires subsequent matrix-matrix multiplications-leading to a potential decrease in sparsity and/or exploitable structure. Hence, many computations on potentially large intermediate representations have to be conducted in order to construct the overall functional representation.
In this paper, we propose two solutions to overcome this bottleneck-using Decision Diagrams (DDs) as a representative functional description. First, a general solution is presented which can be applied to arbitrary functionality and is based on the idea to conduct as many operations as possible on as small as possible intermediate representations. Besides that, another solution is proposed which explicitly exploits the fact that many quantum algorithms contain repeating structures (e.g., Grover iterations, random walks, etc.). In both cases, the complexity of constructing quantum functionality representations is substantially reduced-in case of the second solution even an exponential improvement is achieved.
Experimental evaluations eventually confirm the resulting benefits. They show that the proposed solutions allow to construct the desired representations several factors faster than with the current state of the art. If additionally repeating structures are exploited, representations for quantum algorithms and building blocks can be constructed in a matter of seconds which, using the current state of the art, could not be constructed in an entire day. The resulting implementation is available as open source at https://github.com/iic-jku/qfr. The rest of this paper is structured as follows: Section 2 reviews the necessary basics on quantum computing and introduces the Quantum Fourier Transform, which will be used as a running example in this paper. In Section 3, we show the importance of the considered problem and review the state of the artillustrating the current bottleneck. Then, Section 4 introduces and describes the proposed solution which, afterwards, is evaluated in Section 5. Finally, Section 6 concludes the paper.

Background
In this section, we briefly review the key concepts of quantum computing as well as a typical building block for quantum algorithms which will serve as an example over the course of this paper. While the respective reviews are kept brief, we refer the interested reader to [27] for a more thorough treatment on quantum computing.
In classical computing, bits are used as the smallest computation unitattaining values from the discrete set B = {0, 1}. In the field of quantum computing, these discrete values, denoted |0 and |1 using Dirac notation, are chosen as basis elements spanning a two-dimensional complex Hilbert space H. Consequently, the state |q of a qubit (the quantum analogue to the bit) is described by an element of this space, i.e., by a superposition of the basis states |0 and |1 . More specifically, |q = α 0 |0 + α 1 |1 with α i ∈ C such that |α| 2 = |α 0 | 2 + |α 1 | 2 = 1.
A quantum system then consists of n qubits q 0 , . . . , q n−1 described by the 2 ndimensional Hilbert space H ⊗ · · · ⊗ H. The state |q n of such a system is again described by amplitudes α i ∈ C, where |q n = i∈{0,1} n α i |i with |α| 2 = 1. However, the amplitudes α i of a quantum system are not directly observable. Instead, performing a measurement probabilistically collapses the qubits' state to one of the basis states |i (each with probability |α i | 2 ).
The state of a quantum system is manipulated through unitary linear transformations U : H ⊗ · · · ⊗ H → H ⊗ · · · ⊗ H, which are predominantly described by their unitary 2 n × 2 n matrix representations 5 in the computational basis {|0 , . . . , |2 n − 1 }. Usually, these quantum operations act only on a small subset of a system's qubits. Hence, their matrix representations have a sparse, tensor product structure, where the tensor product of smaller "operation matrices" with identity matrices is formed. A quantum algorithm is described as a sequence of quantum operations applied to a quantum system, i.e., G = g 0 , . . . , g m−1 denotes a quantum algorithm consisting of m operations where each g i is described by a unitary matrix U i . Since the composition of unitary transformations is again unitary, the functionality of a quantum algorithm may be interpreted as one unitary transformation itself. Consequently, the functionality is described by a unitary matrix U which arises from the matrix-matrix multiplication of the individual operation matrices U i , i.e., U = U m−1 · · · U 0 . Quantum algorithms are usually visualized as quantum circuit diagrams where wires indicate the individual qubits and operations (also called gates) are placed as boxes on these lines with corresponding identifiers. Time is assumed to progress from left to right. In the following, quantum algorithms and quantum circuit diagrams will be illustrated by means of the Quantum Fourier Transform (QFT) [27]-a wellknown building block in many important quantum algorithms. Its most prominent use probably is for period finding in Shor's algorithm for integer factorization [28] and many other group-theoretic problems (see Chapter 5 of [27]), at which exponential speed-ups over the best classical methods are demonstrated. QFT is also used in quantum approximate counting [29], which provides proven polynomial speed-ups over the best classical methods, i.e., Monte-Carlo-type estimators [30]. Such quantum Monte-Carlo algorithms are now popular candidates to achieve quantum advantage with near-term quantum devices [31].
Example 2. Consider a 3-qubit system as already discussed in Example 1. Then, Fig. 1d shows the quantum circuit for the 3-qubit Quantum Fourier Transform consisting of m = 6 gates in total. This circuit will be used as a running example for the further discussions throughout this work.

Representations for Quantum Algorithms
Working in the domain of quantum computing requires representations of certain building blocks or even entire quantum algorithms. This is evident, e.g., for typical tasks such as: [5], where an entire quantum algorithm is realized in terms of elementary quantum operations supported by the addressed quantum architecture. Without a proper representation of the algorithm's functionality, no synthesis/compilation approach can work. [8], where a given quantum algorithm is "tested" on a classical machine prior to actual execution on a quantum computer. While this can be done using consecutive matrix-vector multiplication on the elementary gates, approaches based on emulation [32], [33], which utilize functional representations of entire building blocks, have been shown to be much more efficient-provided the emulated functionality can be constructed efficiently.
q0 q0 -Verification [9]- [12], where, e.g., for two quantum circuits G and G it should be checked whether they realize the same function-also referred to as equivalence checking. This obviously requires the construction of a functional representation for both functionalities in order to compare them.
In all these cases, having a representation of the considered functionality is essential. The first challenge resulting from that is that quantum functionality in general is described in terms of matrices with exponential size, i.e., for a functionality over n qubits, a matrix U of size 2 n × 2 n results. In previous work, researchers already started to address this challenge, which led to different approaches exploiting certain structural elements of the considered functionality in order to reduce the exponential space complexity of its representation: -Array-based approaches (such as proposed in [16]- [19]) heavily rely on the sparsity of the involved matrices and try to distribute the workload over several cores of supercomputers, which can often be done efficiently since the matrix-multiplication itself is inherently parallelizable. -Tensor Networks (such as proposed in [20]- [23]) capitalize on the tensor product structure inherent to quantum operations-allowing to decompose the whole matrix into many smaller parts. Their performance typically scales with the degree of entanglement of the considered functionality. -Decision Diagrams (DDs, such as proposed in [24]- [26]) recursively split the considered functionality into equally sized sub-matrices until only complex numbers remain. By identifying redundancies in these sub-parts and extracting common factors, equal sub-functionality can be shared-frequently leading to a compact representation in terms of directed acyclic graphs with edge-weights.
In the following, we will illustrate those endeavours using Decision Diagrams as a representative. However, the observations and findings discussed in this work apply to the other representations as well.
Example 3. Consider again the quantum operations shown in Fig. 1. Their functionalities can be represented efficiently in terms of Decision Diagrams as shown in Fig. 2. As can be seen, they allow for a rather compact representation (3-5 nodes vs. 8-16 non-zero matrix entries).
q0 q0 q0 q0 Size: Fig. 3: State-of-the-art DD composition sequence for 3-qubit QFT (see Fig. 1d) Unfortunately, constructing those representations for certain building blocks or even entire quantum algorithms can often not be conducted efficiently-even if it is conceptionally simple 6 . In fact, as reviewed in Section 2, the functionality of a quantum algorithm (given by a quantum circuit G = g 0 , . . . , g m−1 ) is described by the matrix U = U m−1 · · · U 0 , with U i being the matrix corresponding to gate g i (for 0 ≤ i < m). Hence, since the individual matrices U i can usually be represented rather efficiently with either of the approaches reviewed above (arrays, tensor networks, DDs), simply conducting multiplications on those representations should allow for an efficient construction of the entire functional representation. But the more quantum operations are multiplied together, the more complex representations result-reducing the sparsity, increasing the degree of entanglement, or eliminating existing redundancies-and, hence, significantly slowing down the construction. Thus, while the multiplication operation itself is realized rather efficiently in general (utilizing, e.g., specialized techniques for sparse chain multiplication), the bottleneck arises from the consequences of consecutive multiplication.
until only operations on complex numbers remain. That results in a complexity which scales with the product of the number of nodes in the Decision Diagrams to be multiplied. Carrying out all multiplications results in the evolution of representations as shown in Fig. 3 7 . While, as already shown by means of Fig. 2, the functionality of single operations can be represented compactly, the multiplication needed to construct the overall functionality quickly increases the complexity. In fact, after two multiplications, further computations have to be conducted on a representation as large as the final result.
Evaluations on larger examples than the one above confirm that, in many cases, we may be able to represent (i.e., store) the overall functionality of certain building blocks or an entire quantum algorithm (and use it for tasks such as synthesis/compilation, simulation, or verification), but we may not be able to construct this representation in feasible time. This constitutes a severe bottleneck for many applications in the domain of quantum computing.

Proposed Approaches
In order to overcome the bottleneck discussed in the previous section, we propose to approach the construction of functional representations for building blocks or entire quantum algorithms with different strategies. We distinguish thereby two use cases: First, a general construction scheme is presented which can be applied for arbitrary functionality. Afterwards, we present a second scheme which is dedicated to repeating structures as they frequently occur in quantum algorithms (e.g., by means of Grover iterations or quantum walks). The resulting schemes allow to speed up the construction of the desired functional representation considerably and even manage to complete the construction where existing methods time out.

General Scheme
The observations from Section 3 show that the bottleneck emerges as a result of a large number of matrix-matrix multiplications on rather large representations. Hence, in order to avoid this, we propose to conduct as many of those multiplications on as small as possible representations, e.g., on the original gate representations. Here, the fact that matrix multiplication is associative comes in handy as it allows to conduct those multiplications in a different order.
More precisely, assume, for sake of simplicity, that the number m of operations of a given building block or quantum algorithm is a power of two, i.e., m = 2 k (for some k ∈ N). Then, grouping the set of m operations into m/2 consecutive pairs, i.e., and performing the pairwise multiplications (U i+1 · U i ) = U i+1,i , leaves m/2 = 2 k−1 factors to be multiplied, i.e., Recursively applying this idea eventually results in the construction of the full functional representation U ≡ U m−1,...,0 -requiring a total of k levels of pairwise grouping and multiplication. In case m is not a power of two, in some levels a pair may "degenerate" to a single operation. In general, employing the proposed scheme creates a tree-like hierarchy of matrix compositions. In each level l ∈ {0, . . . , k}, at most 2 l operations contribute to a specific group of compositions. As a consequence, the intermediate functionalities during the construction can frequently be represented in a much more compact fashion (since these remain rather compact and/or sparse in many cases)-leading to fewer multiplications involving large representations.
Clearly, associativity of matrix multiplication allows for partitioning schemes beyond pairwise grouping. Determining an optimal partitioning scheme can be related to finding an optimal contraction order of a tensor network (itself an NP-hard problem [34]). In this sense, the proposed scheme can be viewed as one possible heuristic of tackling the contraction problem for quantum circuits.
At a first glance, the proposed scheme merely trades runtime for space: many operations can be conducted on rather small intermediate representations. But, this requires to store a lot more intermediate results when compared to sequential approaches-specifically in the first level of the multiplication hierarchy, where m/2 Decision Diagrams have to be stored. However, as those "early" intermediate results correspond to circuits with very low depth, their representations are rather compact and frequently contain redundant subparts that can be shared 8 . Moreover, the proposed approach can be realized using a stack for the intermediate results containing at most O(log m) elements at any given time by proceeding in a depth-first fashion.

Exploiting Repeating Structures
Besides the general scheme proposed above, the made observations and findings can further be tailored to repeating structures in quantum algorithms-allowing for even more improvements in the construction of functional representations. This is described in the following section. To this end, recall that many quantum algorithms rely on repeated building blocks realizing a certain kind of iteration, e.g., Grover's search algorithm [35], Quantum Random Walks [36], Amplitude Estimation [29], or Phase Estimation [37]. Usually this type of algorithms consists of an initialization phase and an iteration phase comprised of multiple (identical) iteration steps. Inspired by emulation techniques [32], [33], the current state of the art accelerates the construction of the corresponding functional representation by constructing a single initialization matrix U init followed by multiple multiplications with an iteration matrix U iter (which has to be constructed only once), i.e., (U iter · . . . · U iter )U init = U . This procedure can be drastically improved further by, first, efficiently constructing the individual representations for U init and U iter using the general scheme proposed in Section 4.1 and, then, employing a binary exponentiation scheme for the sequence of multiplications involving U iter . Assume, for sake of simplicity, that the number of iterations N is a power of two, i.e., N = 2 k for some k ∈ N. Then, More precisely, once the iteration matrix U iter has been efficiently constructed, it is sufficient to carry out only one multiplication U 2 l iter · U 2 l iter = U 2 l+1 iter (squar-  As a last step, the initialization matrix U init is multiplied to U N iter -yielding the desired representation U . Hence, only k = log 2 (N ) + 1 (instead of N ) building block multiplications are required to construct the representation-an exponential reduction. In case N is not a power of two, at most one additional multiplication per level is necessary. Thus, even in this case O(log N ) building block multiplications are sufficient for the construction. As a matter of fact, this does not just reduce the number of multiplications exponentially, it also avoids many computations on potentially large representations.
Example 6. In order to illustrate the idea we consider an application of Grover's algorithm [35]. The algorithm can be used to search for a specific item in an unstructured set of N items by only querying a given (problem-specific) oracle O( √ N ) times-a quadratic speed-up over classical methods. To this end, it uses log(N ) + 1 qubits and consists of (1) a small initialization phase which puts all qubits into an equal superposition (to be represented by U init ) and (2) multiple Grover iterations (to be represented by U iter ). A single Grover iteration consists of querying a given oracle and, afterwards, applying the diffusion operatoreffectively increasing the probabilities of states matching the search criterion encoded in the oracle. Now, consider for example the case N = 16. This entails log(N )+1 = 5 qubits and approximately √ 16 = 4 Grover iterations. By first constructing the matrices U init and U iter (using the scheme described in Section 4.1) and, then, applying the approach proposed above, an evolution of representations as shown in Fig. 5 results. Here, it can be seen that, at each level, only a single multiplication has to be carried out (while the other multiplications are functionally equivalent and, hence, can be cached/reused). Thus, only three building block multiplications are required in total, while any sequential approach would need four multiplications. Again, this might look negligible for this small example, but has substantial effect once larger instances are considered.

Experimental Evaluations
In order to experimentally evaluate the proposed approaches, we implemented them on top of the publicly-available JKQ-framework [38] which includes the decision diagram package described in [26] and the state-of-the-art construction approach from [24] as reviewed in Section 3 and illustrated in Example 4. The resulting implementation has been integrated into the framework and is available at https://github.com/iic-jku/qfr. Afterwards, we used the resulting implementation to construct representations for the functionality of the Quantum Fourier Transform, as a representative for a common building block in quantum algorithms such as Shor's algorithm for integer factorization [28], -Grover's search algorithm [35], as a representative of an algorithm containing repeated building blocks.
All computations have been performed on a machine with an Intel i7-6700K processor and 16 GiB RAM running macOS 11.2. The obtained results have been split into two parts and are shown in Table 1. In all tables, n and m denote the number of qubits and the number of gates, respectively. Furthermore, the runtime (in CPU seconds) as well as the total memory allocation (in GiB) needed to construct the respective representation is listed for the current state-of-the-art approach [24], the respective proposed techniques, i.e., the general scheme from Section 4.1 in Table 1a and the dedicated scheme for repeated structures from Section 4.2 in Table 1b.
The results for the QFT, which was used as a running example throughout this paper, clearly show that, compared to the current state of the art, the proposed method manages to construct the algorithm's functionality 3.0× faster on average (and up to 4.2× faster). On the one hand this shows that conducting as many operations as possible on as small as possible intermediate representations indeed pays off. On the other hand, it confirms the discussion from Section 4.1 that although the proposed technique requires to store more representations at the same time, possible redundancies/sharing can explicitly be exploited. Drastic improvements can be achieved for quantum algorithms containing repeated structures for which the dedicated approach from Section 4.2 can be used. This is confirmed by the numbers provided in Table 1b: Here, the state-of-the-art method required 6 min to construct a representation for the Grover functionality for n = 22 and failed to construct the functionality at all within 24 h for larger instances. In contrast, the proposed approach managed to construct the functionality in all these cases within fractions of a second.
In a final series of evaluations, we aimed to compare the proposed techniques to IBM's toolchain Qiskit [13], specifically the CPU backend of the Qiskit Aer UnitarySimulator in version 0.7.1 which uses a multi-threaded array-based technique for constructing the functionality of a given circuit. The results for both the QFT as well as the Grover benchmarks are shown in Table 2. Even for moderately sized instances, we observed runtimes more than two orders of magnitude longer when compared to the technique from [24] or the techniques proposed in this paper. In addition, IBM's approach requires exponential amount of memory-leading to memory outs when considering more than 15 qubits while the proposed techniques easily allow to construct the functionality of circuits with more than 20 qubits.

Conclusion
In this work, we addressed the issue of constructing the functional representation of certain building blocks or even entire quantum circuits. Existing approaches for solving this task are severely limited by the rapidly growing size of intermediate representations during the construction. By conducting as many operations as possible on as small as possible intermediate representations, the solutions proposed in this paper manage to consistently outperform existing approachesallowing to construct the desired representations several factors faster than with the state of the art. Moreover, in case repeating structures are explicitly exploited, the construction of the representation for certain prominent quantum algorithms can be completed within seconds, whereas state-of-the-art approaches fail to construct it within an entire day. The comparison with IBM's Qiskit has shown that industrial tools for quantum computing are still in their infancy and would greatly benefit from the integration of existing techniques for efficiently constructing functional representations of quantum circuits-and even more so the techniques proposed in this work.