Michele Mosca

University of Waterloo
Project Title: A parallel algorithm for quantum circuit synthesis
Industry Partner: evolutionQ
Platform: Blue Gene/Q


Quantum circuit synthesis is an important step in the process of quantum compilation. Given an arbitrary unitary operation, quantum circuit synthesis is the process that constructs a quantum circuit using only gates from a universal gate set which is either exactly, or approximatelyequivalent to the original operation. The currently known algorithms for multi-qubit circuit synthesis run in exponential time and rely on the generation of databases many GBs in size to complete the search; synthesis of circuits of more than 3 qubits up to a certain length is infeasible using current methods due to this exponential scaling. We have developed a framework and accompanying software that uses time/memory tradeoffs and parallel collision finding techniques to synthesize circuits. A simple implementation using 16 OpenMP threads found that this approach can increase the speed of synthesis over previous algorithms, as well as synthesize larger circuits. In order to fully reap the benefits offered by this algorithm, we are developing a hybrid OpenMP/MPI algorithm, with the hopes of scaling up this method to thousands of cores or more.