Single-qubit rotation algorithm with logarithmic Toffoli count and gate depth

Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes <a:math xmlns:a="http://www.w3.org/1998/Math/MathML"><a:mtext>Clifford</a:mtext><a:mo>+</a:mo><a:mtext>Toffoli</a:mtext></a:math> an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only <b:math xmlns:b="http://www.w3.org/1998/Math/MathML"><b:mtext>Clifford</b:mtext><b:mo>+</b:mo><b:mtext>Toffoli</b:mtext></b:math>, which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation <c:math xmlns:c="http://www.w3.org/1998/Math/MathML"><c:msub><c:mi>R</c:mi><c:msup><c:mi>θ</c:mi><c:mo>*</c:mo></c:msup></c:msub></c:math> that is <d:math xmlns:d="http://www.w3.org/1998/Math/MathML"><d:mi>ε</d:mi></d:math>-close to the desired rotation <e:math xmlns:e="http://www.w3.org/1998/Math/MathML"><e:msub><e:mi>R</e:mi><e:mi>θ</e:mi></e:msub></e:math>, with a success probability strictly greater than <f:math xmlns:f="http://www.w3.org/1998/Math/MathML"><f:mrow><f:mn>1</f:mn><f:mo>/</f:mo><f:mn>2</f:mn></f:mrow></f:math>. It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than <g:math xmlns:g="http://www.w3.org/1998/Math/MathML"><g:mrow><g:mn>4</g:mn><g:mo>⌈</g:mo><g:mo form="prefix">log</g:mo><g:mstyle scriptlevel="0" displaystyle="false"><g:mfrac><g:mn>1</g:mn><g:mi>ε</g:mi></g:mfrac></g:mstyle><g:mo>⌉</g:mo></g:mrow></g:math>, an expected gate depth strictly less than <k:math xmlns:k="http://www.w3.org/1998/Math/MathML"><k:mrow><k:mn>4</k:mn><k:mo>⌈</k:mo><k:mo form="prefix">log</k:mo><k:mstyle scriptlevel="0" displaystyle="false"><k:mfrac><k:mn>1</k:mn><k:mi>ε</k:mi></k:mfrac></k:mstyle><k:mo>⌉</k:mo><k:mo>+</k:mo><k:mn>6</k:mn></k:mrow></k:math>, and uses <o:math xmlns:o="http://www.w3.org/1998/Math/MathML"><o:mrow><o:mn>2</o:mn><o:mo>⌈</o:mo><o:mo form="prefix">log</o:mo><o:mstyle scriptlevel="0" displaystyle="false"><o:mfrac><o:mn>1</o:mn><o:mi>ε</o:mi></o:mfrac></o:mstyle><o:mo>⌉</o:mo></o:mrow></o:math> ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas. Published by the American Physical Society 2024