Advances in Quantum Algorithms & Devices: Exact synthesis for qubit unitaries

The Solovay-Kitaev Theorem shows that any finite subset of SU(2) generating a dense subgroup can be used to epsilon-approximate an arbitrary qubit unitary using a quantum circuit of length O(polylog(1/epsilon)). Recent advances in quantum compiling achieved dramatically improved approximations to arbitrary unitaries with O(log(1/epsilon))-length circuits over special qubit gate sets. A necessary component of such compiling tasks involves solving the “exact synthesis problem” for the given gate set: Given a unitary that can be expressed as a circuit over the elementary gates, the exact synthesis problem is to find the shortest circuit implementing that unitary. In this talk, I will present joint work with Vadym Kliuchnikov, showing how sophisticated mathematical tools from the theory of quaternion orders can be put to work to solve this problem for a very broad class of gate sets including Clifford+T, V-basis and braiding of nonabelian anyons in SU(2) Chern-Simons theory at finite level.