论文标题
远见：通过自适应多换词评估减少NISQ程序中的掉期
ForeSight: Reducing SWAPs in NISQ Programs via Adaptive Multi-Candidate Evaluations
论文作者
论文摘要
近期量子计算机嘈杂，量子位之间的连通性有限。需要编译器引入掉期操作，以便在非雅后量子位之间执行两倍的门。掉期增加了门的数量和程序的深度，使它们更容易受到错误的影响。此外，它们重新安置了影响程序中未来门的掉期选择的Qubit。因此，编译器必须选择不仅将当前操作的开销最小化的交换路由，还可以为将来的门提供。现有的编译器倾向于为当前操作选择最少的掉期路径，但没有评估所选互换候选者对未来掉期的搬迁的影响。此外，他们会收敛于当前操作的交换候选人，然后决定将来的大门交换路线，从而严重限制了交换候选搜索空间以进行未来的操作。 我们提出了Foresight，这是一种编译器，该编译器同时评估了未来多项操作的多个互换候选者，延迟了交换选择，以分析其对未来互换决策的影响，并避免早期对亚最佳候选人的融合。此外，如果前瞻性评估当前操作的互换途径稍长，如果它们有可能减少未来大门的掉期，从而减少了该计划在全球范围内的互换。随着汇编的进行，预见会动态地将新的交换候选者添加到解决方案空间中，并消除较弱的候选者。这样一来，远见就可以减少程序级别的互换开销，同时保持编译复杂性可处理。我们在三个设备上使用一百个基准测试的评估表明，与基线相比，预见的掉期平均将掉期开销降低了17％，最佳案例降低了81％。预见需要几分钟，使其可扩展到大型程序。
Near-term quantum computers are noisy and have limited connectivity between qubits. Compilers are required to introduce SWAP operations in order to perform two-qubit gates between non-adjacent qubits. SWAPs increase the number of gates and depth of programs, making them even more vulnerable to errors. Moreover, they relocate qubits which affect SWAP selections for future gates in a program. Thus, compilers must select SWAP routes that not only minimize the overheads for the current operation, but also for future gates. Existing compilers tend to select paths with the fewest SWAPs for the current operations, but do not evaluate the impact of the relocations from the selected SWAP candidate on future SWAPs. Also, they converge on SWAP candidates for the current operation and only then decide SWAP routes for future gates, thus severely restricting the SWAP candidate search space for future operations. We propose ForeSight, a compiler that simultaneously evaluates multiple SWAP candidates for several operations into the future, delays SWAP selections to analyze their impact on future SWAP decisions and avoids early convergence on sub-optimal candidates. Moreover, ForeSight evaluates slightly longer SWAP routes for current operations if they have the potential to reduce SWAPs for future gates, thus reducing SWAPs for the program globally. As compilation proceeds, ForeSight dynamically adds new SWAP candidates to the solution space and eliminates the weaker ones. This allows ForeSight to reduce SWAP overheads at program-level while keeping the compilation complexity tractable. Our evaluations with a hundred benchmarks across three devices show that ForeSight reduces SWAP overheads by 17% on average and 81% in the best-case, compared to the baseline. ForeSight takes minutes, making it scalable to large programs.
