量子科技中心_量科网

在该工作中，研究人员建立了目前已知针对QAC⁰电路的最强下界，同时允许其充分利用多项式数量的辅助位和门操作。两个主要成果表明：（1）无论规模如何，深度为3的QAC⁰电路无法计算奇偶校验函数（PARITY），且计算多数函数（MAJORITY）至少需要Ω(exp(√n))数量级的门操作；（2）无论规模如何，深度为2的电路无法以显著优势近似高影响布尔函数（如奇偶校验函数）。该团队提出了在AC⁰中经典模拟特定QAC⁰电路的新技术，从而获得深度3的下界结果。这些研究将量子电路的输出要求放宽至单比特（即不限制输入保持/可逆计算条件），使得获得的深度2近似下界强于Rosenthal（2021年）的最佳先前结果。这也使该工作能与经典AC⁰电路形成自然对比——后者可通过指数规模在深度2精确计算奇偶校验函数。证明技术进一步表明：对于本质经典的决策问题，恒定深度量子电路未必比经典电路更具优势。第三个成果证明无论规模如何，深度2的QAC⁰电路无法精确合成n目标猫态（其合成与奇偶校验计算直接相关），这补充了Rosenthal（2021年）关于近似猫态的深度2指数规模上界结果（该子电路是已知唯一恒定深度奇偶校验上界的组成部分）。