## 1 Introduction  
Quantum computing is promising to provide the next phase of performance improvement for large-scale computing. To this end, many different algorithms have been developed in the theoretical domain, such as [PERSON]'s algorithm for prime factorization in polynomial time [1], or [PERSON]'s algorithm for finding a specific input corresponding to some output in \(\sqrt{N}\) time [2].  
Recent years have seen some great strides in the field of physical implementations of quantum computers as well. However, these still have some big limitations on the number of qubits, the error rates and the length of the circuits that can be executed on them. Although quantum computers with as many as 128 qubits already exist [3], error rates are of the order \(10^{-2}\)-\(10^{-3}\) per gate [4]. Therefore, executing a circuit on a physical quantum chip requires significant error correction, as well as mapping, scheduling and other such measures [5].  
These algorithms are executed on simulators, which come with their own set of restrictions. Some simulators require the use of specific qubit topology and limit possible qubit states or the number of qubits, and all of them are bound by the classical resources of the system the simulation is run on. The main resource limit is the memory necessary to store the quantum circuit and the total qubit state, which is dependent on the length of the circuit, the number of qubits and the degree of superposition. These also influence the processing time necessary to simulate the full circuit, which is generally done by some form of matrix multiplications of the qubit state and each gate in the circuit.  
Unitary decomposition is the process of translating an arbitrary _unitary_ gate (a unitary matrix \(U\) is a square, complex matrix, of which the inverse (\(U^{-1}\)) and the conjugate transpose (\(U^{\dagger}\)) are the same; i.e., \(U^{\dagger}=U^{-1}\) and \(UU^{\dagger}=I\)[6]) into a specific (universal) set of single and two-qubit gates. Unitary decomposition is necessary because it is not otherwise possible to execute an arbitrary quantum gate on either a simulator or quantum accelerator. This makes it a required feature for algorithms that use any type of gate that is not supported by the target platform or just produce an arbitrary unitary gate that will need to be translated. In this paper, only exact decomposition algorithms will be considered for application on gate-based quantum computing.  
This paper proposes a highly-efficient method to implement unitary decomposition for quantum algorithms using Quantum Shannon Decomposition. The paper shows that our approach is up to \(10\times\) more efficient in terms of the number of gates generated for a given unitary matrix size and requires up to 100 times less wall-clock execution time than other implementations. The contributions of this paper are as follows:  
* Implementation of Quantum Shannon Decomposition for the unitary decomposition of quantum algorithms;
* Decomposition optimizations that take advantage of the underlying matrix structure;
* The integration and evaluation of our method in the OpenQL quantum programming framework;
* The optimization of the implementation of a quantum genome analysis use-case using our method  
This paper is structured as follows. In Section 2, applications for unitary decomposition are discussed. Then, in Section 3, some background is given on qubits, gate-based computation and the special qubit gates that are used. The specific decomposition method for multi-controlled gates is given in Section 4. In Section 5, several decomposition algorithms are compared based on their resulting CNOT-count. The implementation of the selected algorithm, Quantum Shannon Decomposition, is outlined in Section 6. Optimizations to this implementation can be found in Section 7. Experimental results are shown in Section 8 and compared to other implementations in Section 10. Finally, the conclusion and future work can be found in Section 11.