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

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

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.