Southwest Quantum Information and Technology

Efficient Synthesis of Universal Probabilistic Quantum Circuits

Krysta Svore, Microsoft Research

view abstract +

Techniques to efficiently compile high-level quantum algorithms into lower-level fault-tolerant circuits are crucial for the implementation of a scalable quantum computer. Several universal gate sets can be used for compilation, including Clifford+T, T = [1 0; 0 e^{i \pi/4}], Clifford+K, K = [1 0; 0 e^{i \pi/6}], and Clifford+V, V=\1/\sqrt{5} (Id+2iZ). While in principle the Solovay-Kitaev algorithm can solve the synthesis problem for any universal gate set, the synthesized circuits have a large upper bound on the circuit depth of O(log^{3.97} (1/e), where e is the precision, and a classical compilation time that is almost cubic in \log(1/e). Fortunately, for each of the above-mentioned bases (using separate algorithms), elementary number theory can be leveraged to obtain an optimal or near-optimal depth circuit. For Clifford+T, for example, the number of T gates (and compilation time) is close to 3 log_2(1/\e) for single-qubit Z rotations. In this talk, we show that this constant can be further reduced; this comes as a surprise as there is an information-theoretic lower bound that establishes that there are Z-rotations that require 3 log_2(1/e) many T gates to reach an approximation precision e. By (1) allowing measurements and adaptive decisions on earlier results and (2) allowing to operate on more than one qubit through the use of an ancilla, we show that this bound can be surpassed using so-called ``Repeat-Until-Success" (RUS) circuits. We show that with a single framework we can synthesize RUS circuits over the above three bases and achieve an expected gate count of log_b(1/e)+O(log(log(1/e))), where b is related to an expansion property of the underlying basis; b is defined so that for a given depth t the number of unique circuits scales as Theta(b^t). Specifically, b=2 for Clifford+T, b=4 for Clifford+K, and b=5 for Clifford+V. Based on arxiv:1404.5320 and arxiv:1409.3552.