量子科技中心_量科网

该研究团队研究了其泡利谱支持于小子群上的酉通道的过程层析。给定对某个未知酉通道的查询访问，该酉通道的泡利谱支持于大小为2^k的子群上，其目标是输出一个在钻石距离下与未知酉通道ε接近的经典描述。该工作提出了一种算法，使用O(2^k/ε)次查询实现这一目标，并证明了匹配的下界，确立了该算法的查询最优性。当k=2n时，即支持为完整泡利群时，该结果恢复了Haah、Kothari、O'Donnell和Tang在FOCS'23上提出的查询最优O(4^n/ε)查询算法。 该结果有两个重要推论。首先，该研究给出了一个查询最优的O(4^k/ε)查询算法，用于学习量子k-juntas（即仅对n个量子比特中的k个进行非平凡操作的酉通道）以达到钻石距离ε的精度。这相较于先前工作，在查询和时间复杂度上都实现了指数级改进。 其次，该工作为学习深度为O(log log n)电路与近克利福德电路的组合提供了计算高效的算法，其中“近克利福德”指通过最多O(log n)个非克利福德单量子比特门增强的克利福德电路。这统一了先前的工作，先前只能处理常数深度电路或近克利福德电路，但无法处理它们的组合。