Title: Trading T gates for dirty qubits in state preparation and unitary synthesis Show Chinese title

Title: 在状态制备和酉合成中用T门交换脏量子比特

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-$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{\frac{N}{\epsilon}}\log{\frac{\log{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. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data. Show Chinese abstract

Abstract: 从通用容错门集，例如 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{\frac{N}{\epsilon}}\log{\frac{\log{N}}{\epsilon}})$。这种权衡在对数因子范围内是最优的，通过无条件门计数下界证明，并且在最佳情况下，相比之前无需辅助量子比特的方法，T 计数有二次改进。我们通过归约到状态准备，证明了关于酉合成的类似结论。我们构造的基础是一种针对任意经典数据的 T 高效电路实现的量子预言机。