## 2 Motivation for Unitary Decomposition  
Unitary decomposition is useful in several contexts. The first is the broad class of algorithms that generate arbitrary unitary gates that need to be translated into a quantum circuit, but it is also used to enable the more modular design of quantum algorithms or as an aggressive optimization method. We will use two quantum algorithms that we have developed in the context of genome sequencing as an example of a possible application for unitary decomposition. With genome sequencing, a genome sequence is first read as many short pieces which then need to be combined to get the full DNA sequence. This is currently done using many different algorithms, which are executed using (classical) high-performance computing systems [7]. For genome sequencing using quantum accelerators, the DNA sequences can be stored in superposition. The two algorithms that will be discussed both use a unitary matrix in the process of finding the position of a short read (sequence of a small piece of DNA) on a reference genome. That matrix needs to be decomposed before the algorithm can be run on a quantum accelerator or simulator [8]. The first quantum genome sequencing algorithm we will use is Quantum Indexed Bidirectional Associative Memory (QiBAM) [8]. QiBAM uses a unitary oracle \(U(2^{n})=I(2^{n})-2\ket{b_{p}}\bra{b_{p}}\) assembled from a binomial distribution as \(\ket{b_{p}^{x}}=\sqrt{\gamma^{h(p,x)}(1-\gamma)^{n-h(p,x)}}\). Here, \(\gamma\) is a factor that influences the width of the distribution, \(h(p,x)\) is the Hamming distance between the query pattern \(p\) and all memory states \(x\), and \(n\) is the number of qubits required to store the memory states. \(n\) is also the size of the vector and resulting matrix. \[\hat{S}^{S_{p}p}=CR_{y}(2 sin^{-1}(-1/\sqrt{p})= \begin{bmatrix}1&0&0&0\\ 0&1&0&0\\ 0&0&\sqrt{\frac{p-1}{p}}&\frac{-s}{\sqrt{p}}\\ 0&0&\frac{s}{\sqrt{p}}&\sqrt{\frac{p-1}{p}}\end{bmatrix}  \tag{1}\]  
The second genome sequencing algorithm is Quantum Associative Memory (QAM). This uses a Hadamard-like transformation to store the patterns, assembled using Equation (1) [9]. In order to apply either gate from these two algorithms to qubits, they need to be translated into some combination of (elementary) quantum gates that can be executed on a quantum accelerator, and the same is true for other such algorithms. Besides that, unitary decomposition also facilitates short-cuts in the design of new algorithms. With unitary decomposition, a developer can keep part of an algorithm as a unitary gate/matrix while working on some other part and test this. Otherwise, the algorithm can only be executed in full when all of it is made out of known quantum gates. Unitary decomposition allows the full algorithm to be tested and checked much earlier in the development process on the target quantum chip or simulator. Furthermore, unitary decomposition can be used as an aggressive optimization method, because the maximum number of gates resulting from a decomposition can be calculated easily beforehand. The maximum length of the circuit resulting from the decomposition is only dependent on the number of qubits affected by the gate. For circuits longer than this maximum, and thus consisting of more gates, the assembly of all gates into a unitary matrix and then decomposing that matrix will always result in a shorter circuit. Someone programming in OpenQL might, for example, specify a circuit with three qubits with 180 gates--this might be because of application semantics, code-readability or because they did not consider the optimal way to program their quantum algorithm. The total of 180 gates is more than the number of gates that would result from decomposing an arbitrary three-qubit gate. Thus, if the circuit is combined into a single unitary matrix and then that matrix is decomposed using Shannon Decomposition, for example, then the length of the circuit will be reduced from 180 gates to only 120 (84 rotation gates and 36 CNOT gates).