标题： 高效资源的稀疏量子态合成 显示英文标题

标题： Resource-Efficient Synthesis of Sparse Quantum States

摘要： 准备一个实现给定稀疏态的量子电路是许多不同量子算法所必需的重要构建模块。 在容错量子计算的背景下，所谓的非 Clifford 门比 Clifford 门执行起来要昂贵得多。 因此，我们提供了一个算法，用于合成稀疏量子态，并特别关注量子资源。 该算法生成的电路的电路深度、辅助比特数量以及关键的非 Clifford 数量都与稀疏性成线性关系。 我们猜想非 Clifford 数量的复杂度是紧致的，并展示了这一声明的一个弱化版本。 该算法的第一个关键组件是广义 W 态的合成。 我们提供了一种基于树的电路构造方法，并阐述了树的结构与电路复杂度之间的关系。 第二个关键组件是一个实现排列的经典可逆电路，该排列将 W 态的基态映射到稀疏量子态的基态。 我们使用一组特定的基本矩阵运算，这些运算对应于经典可逆门，将这个问题归约到二进制矩阵的对角化。 然后，我们使用一种新的高斯-约旦消去法来解决这个问题，该方法通过并行消去步骤来最小化包括电路深度在内的电路复杂度。 显示英文摘要

摘要： Preparing a quantum circuit that implements a given sparse state is an important building block that is necessary for many different quantum algorithms. In the context of fault-tolerant quantum computing, the so-called non-Clifford gates are much more expensive to perform than the Clifford ones. We hence provide an algorithm for synthesizing sparse quantum states with a special care for quantum resources. The circuit depth, ancilla count, and crucially non-Clifford count of the circuit produced by the algorithm are all linear in the sparsity. We conjecture that the non-Clifford count complexity is tight, and show a weakened version of this claim. The first key component of the algorithm is the synthesis of a generalized W-state. We provide a tree-based circuit construction approach, and the relationship between the tree's structure and the circuit's complexity. The second key component is a classical reversible circuit implementing a permutation that maps the basis states of the W-state to those of the sparse quantum state. We reduce this problem to the diagonalization of a binary matrix, using a specific set of elementary matrix operations corresponding to the classical reversible gates. We then solve this problem using a new version of Gauss-Jordan elimination, that minimizes the circuit complexities including circuit depth using parallel elimination steps.