标题： 用于状态制备和酉合成中的脏量子比特的T门交换 显示英文标题

标题： Trading T-gates for dirty qubits in state preparation and unitary synthesis

摘要： 从通用的容错门集，例如 Clifford+T 中高效合成任意量子态和酉操作是量子计算中的关键子程序。由于大型量子算法中包含许多编码相干量子信息但计算部分处于空闲状态的量子比特，如果能减少整体门数，特别是昂贵的 T 门数，这些量子比特应被利用。我们提出了一种量子算法，用于准备由一组$N$个经典数指定的维度为$N$的纯量子态，该算法在空间和 T 门之间实现了权衡。我们的方案使用$\mathcal{O}(\log{(N/\epsilon)})$个干净量子比特和可调数量的$\sim(\lambda\log{(\frac{\log{N}}{\epsilon})})$个脏量子比特，将 T 门成本降低到$\mathcal{O}(\frac{N}{\lambda}+\lambda\log^2{\frac{N}{\epsilon}})$。这种权衡在对数因子范围内是最优的，通过无条件的门计数下限证明，并且在最佳情况下，相对于之前无辅助的方案，在 T 计数上实现了二次改进。我们通过归约到状态制备，证明了关于酉合成的类似结论。 显示英文摘要

摘要： 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-$N$ pure quantum state specified by a list of $N$ classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses $\mathcal{O}(\log{(N/\epsilon)})$ clean qubits and a tunable number of $\sim(\lambda\log{(\frac{\log{N}}{\epsilon})})$ dirty qubits, to reduce the T-gate cost to $\mathcal{O}(\frac{N}{\lambda}+\lambda\log^2{\frac{N}{\epsilon}})$. 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.