Trading t-gates for qubits in arbitrary state 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 goal in quantum computation. As physical quantum computers are fixed in size, all available qubits should be used if it minimizes overall gate counts, especially that of the expensive T-gates. In this application, a quantum algorithm is described for preparing any dimension-N quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Example embodiments exploit(λ) ancilla qubits, to reduce the T-gate cost to Notably, this it proven to be optimal up to logarithmic factors for any λ=o(√{square root over (N)}) through an unconditional gate counting argument. Though(N) Clifford gates are always required, only(√{square root over (N)}) T-gates are needed in the best case, which is a quadratic improvement over prior art. Similar statements are provien for unitary synthesis by reduction to state preparation.