Efficient algorithms for synthesizing T-count and T-depth optimal circuits

CQT Online Talks – Series: Computer Science Seminars

Speaker: Priyanka Mukhopadhyay, Institute for Quantum Computing and Department of Combinatorics and Optimization, University of Waterloo
Abstract: We investigate the problem of synthesizing T-count and T-depth optimal quantum circuits over the Clifford+T gate set. Our results can be summarized as follows.
1. We study the channel representation of exactly synthesizable unitaries. Our observations lead to compact representation of these channel representations and much more efficient algorithms for inverse, multiplication. These also pave the way for our heuristic algorithms.
2. Modifying the meet-in-the-middle (MITM) algorithm of Gosset et al. (2013) we introduce nested MITM technique that leads to provable algorithms for synthesizing T-count optimal circuits. Though we cannot avoid the exponential (in T-count) complexity, we get a space-time trade-off.
3. We apply the nested MITM technique to synthesize T-depth optimal circuits using channel representation of unitaries. We get a provable algorithm that has much less complexity than the provable algorithm of Amy et al.(2013). As a result, a task they take more than 4 days to complete, can be done by us in about 2 secs.
4. We design a polynomial (in T-count) complexity heuristic algorithm for synthesizing T-count optimal circuits. This is a significant improvement over any previous T-count-optimal synthesis algorithm. For example, we can synthesize the T-count optimal circuit for 4-qubit adder in about 7 mins with 1 core, while the parallel algorithm of Di Matteo and Mosca (2016) takes 12.5 hours with 4096 cores.
5. We design a quasi-polynomial complexity heuristic algorithm for synthesizing T-depth optimal circuits. We do not know whether the two conjectures can be derived from each other. With this we can synthesize previously unknown T-depth optimal circuits for many standard 3-qubit unitaries like Fredkin, Peres, Negated Toffoli, Quantum XOR in about 30 mins.

The results in this talk combine the results from two of our papers: (1) A polynomial time and space heuristic algorithm for T-count (arXiv:2006.12440), authored by Michele Mosca and Priyanka Mukhopadhyay, and (2) A quasi-polynomial time heuristic algorithm for synthesizing T-depth optimal circuits (arXiv:2101.03142), authored by Vlad Gheorghiu, Michele Mosca and Priyanka Mukhopadhyay.