论文标题
T计数的多项式时间和空间启发式算法
A polynomial time and space heuristic algorithm for T-count
论文作者
论文摘要
这项工作着重于减少使用最先进的易于故障的量子误差纠正代码的量子算法的物理成本，尤其是那些实现T门的物理成本要比门集中的其他门所消耗的资源要多得多。更具体地说，我们认为可以通过由clifford+t门集组成的量子电路（一个通用门集）来精确实现的一单位。我们的主要权益是使用最少可能的T门数（称为U $ U $的T-Count）来计算给定的$ n $ qubit单一$ U $的电路。我们考虑了问题count-t，其优化版本旨在找到$ u $的T计数。在其决策版本中，目标是确定T-Count是否最多是一些积极的整数$ M $。给定了Count-T的Oracle，我们可以在$ U $的T计数和尺寸中计算一个时间多项式的T计数最佳电路。我们给出了一种可证明的经典算法，该算法在时间$ o \ left（n^{2（c-1）\ lceil \ frac {m} {m} {c} {c} \ rceil} \ text {poly}（poly}（m，m，n）\ right）$和空间$和空间$ o \ left（n^{2 \ lceil \ frac {m} {c} \ rceil} \ text {poly}（m，n）\ right）$，其中$ n = 2^n $和$ c \ geq 2 $。这给了一个时空权衡，以通过各种中间技术来解决此问题。我们还引入了一种渐近的乘法方法，该方法将$ n^{0.7457} $降低整体复杂性。最后，除了我们对严格算法的改进之外，我们还提供了一种启发式算法，该算法在某些假设下，可以输出T计数优势的电路，并具有空间和时间复杂性$ \ text {poly}（m，n）$。虽然我们的启发式方法仍会随量子数的数量而成倍地缩放（尽管指数较低，但通过从指数缩放到$ m $的多项式缩放，可以取得很大的改进。
This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set. Our primary interest is to compute a circuit for a given $n$-qubit unitary $U$, using the minimum possible number of T gates (called the T-count of unitary $U$). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of $U$. In its decision version the goal is to decide if the T-count is at most some positive integer $m$. Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of $U$. We give a provable classical algorithm that solves COUNT-T (decision) in time $O\left(N^{2(c-1)\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$ and space $O\left(N^{2\lceil\frac{m}{c}\rceil}\text{poly}(m,N)\right)$, where $N=2^n$ and $c\geq 2$. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of $N^{0.7457}$ off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal circuit and has space and time complexity $\text{poly}(m,N)$, under some assumptions. While our heuristic method still scales exponentially with the number of qubits (though with a lower exponent, there is a large improvement by going from exponential to polynomial scaling with $m$.
