POPQC: 量子电路的并行优化(扩展版)
量子程序或量子电路优化是量子计算领域的核心问题,至今仍面临重大挑战。当前最先进的量子电路优化器依赖启发式方法,通常需要超线性甚至指数级时间。近期研究(oac2025)提出了一种追求较弱优化形式的新方法——局部优化。该方法以自然数Ω为参数,要求电路的每个Ω片段相对于外部优化器(称为预言机)都达到最优。局部优化仅需线性次数的预言机调用,但除预言机调用外仍会产生二次计算开销。更重要的是,该算法本质上是串行的。 本文提出了一种量子电路局部优化的并行算法。为确保效率,该算法通过维护一组指向电路的“指针”进行操作,并保持以下不变量:仅当Ω深度电路包含指针时才需优化。算法以轮次运行,选择指针集合并并行优化包含指针的片段,随后更新指针集以维持不变量。对于恒定Ω值,该研究团队证明算法需要O(n lg n)的工作量和O(r lg n)的跨度(其中n为电路规模,r为轮次数)。研究还证实算法返回的优化电路具有局部最优性,即电路的任意Ω片段相对于预言机都是最优的。
