Decomposing Quantum Unitaries into Circuits with Program Synthesis

Superposition principle and entanglement are quantum effects that make quantum computing powerful. However, the development of quantum algorithms that exploit these properties is hard and requires considerable expertise. We want to investigate if one can employ machine learning techniques to facilitate the discovery of new algorithms. In particular, by mapping quantum algorithms to graphs of operations ("programs"), one could use program synthesis to find interpretable solutions to given tasks. As a proof-of-concept, we consider quantum unitary matrices of a fixed number of qubits and try to automatically decompose them in sequences of gates. We show how program synthesis algorithms allow to start from an elementary set of gates, gradually build circuits, understand which combinations of gates make useful composed gates and use them to decompose harder and harder matrices.