Efficient synthesis of universal Repeat-Until-Success circuits
Efficient synthesis of universal Repeat-Until-Success circuits
复制标题
通用重复直至成功电路的高效合成
DOI：
--
复制
发表时间：
2014
影响因子：
8.6
通讯作者：
K. Svore
中科院分区：
文献类型：
--
作者：
Alex Bocharov;M. Rötteler;K. Svore
最近有研究表明，在量子计算机上实现么正运算所需的资源可以通过使用被称为重复直到成功(RUS)电路的概率量子电路来减少。然而，以前最著名的用于综合给定目标么正的RUS电路的算法需要指数经典运行时间。我们提出了一种概率多项式时间算法来综合RUS电路，以在Clifford+T基上逼近任何给定的单量子比特单位到精度的ϵ。令人惊讶的是，合成的RUS电路的T计数超过了理论下限3 _{2}(1/ϵ)，该下界适用于纯酉单量子比特电路分解。通过利用测量和Ancilla量子比特，RUS电路实现了单量子比特z旋转的预期T计数为1.15log_{2}(1/ )。我们的方法利用了这样一个事实，即可由RUS协议实现的单位集在所有单位的空间中具有比纯单位实现的密度更高的密度。
Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.