SHF: Small: Tackling Mapping and Scheduling Problems for Quantum Program Compilation

量子计算有可能引发下一次计算革命。它可以在任何可行的时间内快速解决经典计算机无法解决的问题。最近，量子硬件令人印象深刻的进步使量子计算从理论上的好奇变成了技术上的现实。然而，量子算法的理论与算法在物理设备上的实现之间存在着很大的差距。为了弥合这一差距，本提案侧重于提供一个编译器框架，用于将高级算法规范转换为低级硬件兼容代码。它使程序员能够利用量子计算机，而无需在底层硬件细节方面获得重要的领域专业知识。本文重点研究了超导量子计算机编译过程中的映射和调度问题。超导技术作为量子硬件实现的领先技术，有多种类型的限制，阻碍了理论量子算法的全部潜力的实现。映射和调度过程涉及超导量子比特的实际约束，是量子程序转换中最具挑战性的问题。该建议正式解决了映射/调度问题，并将其建模为图论/人工智能问题。它不仅推动了量子程序编译领域的最新技术，而且通过将传统的图论和人工智能领域与量子编译器中的独特挑战联系起来，推动了它们的边界。最终，它会刺激量子程序员的生产力，释放量子计算的巨大计算能力，这将推动社会的技术和经济创新。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Quantum computing has the potential of enabling the next revolution incomputing. It can quickly solve problems that no classical computer could solvein any feasible amount of time. Recently, the impressive advances inquantum hardware have brought quantum computing from theoretical curiosity totechnical reality. However, there is a significant gapbetween the theory of quantum algorithms and the realization of the algorithmson physical devices. To bridge this gap, this proposal focuses on providing acompiler framework for translating high-level algorithm specifications to low-level hardware-compliant code. It enables programmers to take advantage of quantumcomputers without having to obtain significant domain expertise in the low-levelhardware details.In particular, this proposal focuses on the mapping and scheduling problems inthe compilation process for superconducting quantum computers. Superconductingtechnology, as the leading technology for quantum hardware implementation, hasmultiple types of constraints that prevent the realization of the full potential oftheoretical quantum algorithms. The mapping and scheduling process deals withthe practical constraints of superconducting qubits, and are the mostchallenging problems during quantum program translation. Thisproposal formally addresses the mapping/scheduling problems and models them asgraph-theoretic/AI problems. It not only advances the state of the art in thefield of quantum program compilation, but also pushes the boundary of thetraditional graph-theoretic and AI fields by linking them with unique challengesin quantum compilers. Ultimately it spurs the productivity of quantumprogrammers and unleashes the massive computing power of quantum computingthat will fuel the technical and economical innovations in society.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.