Trading T gates for dirty qubits in state preparation and unitary synthesis

Abstract

Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension-<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> pure quantum state specified by a list of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mi>N</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>/</mml:mo></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> clean qubits and a tunable number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mo>&amp;#x223C;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>&amp;#x03BB;</mml:mi><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mrow><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>N</mml:mi></mml:mrow></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi></mml:mfrac><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math> dirty qubits, to reduce the T-gate cost to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi class="MJX-tex-caligraphic" mathvariant="script">O</mml:mi></mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mi>N</mml:mi><mml:mi>&amp;#x03BB;</mml:mi></mml:mfrac><mml:mo>+</mml:mo><mml:mi>&amp;#x03BB;</mml:mi><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mfrac><mml:mi>N</mml:mi><mml:mi>&amp;#x03F5;</mml:mi></mml:mfrac></mml:mrow><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mfrac><mml:mrow><mml:mi>log</mml:mi><mml:mo>&amp;#x2061;</mml:mo><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>N</mml:mi></mml:mrow></mml:mrow><mml:mi>&amp;#x03F5;</mml:mi></mml:mfrac></mml:mrow><mml:mo stretchy="false">)</mml:mo></mml:math>. This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.