Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation

Booth, Kyle E C ; Do, Minh ; Beck, J Christopher ; Rieffel, Eleanor ; Venturelli, Davide ; Frank, Jeremy

关键词: COMPUTER PROGRAMMING;    CONSTRAINTS;    QUANTUM COMPUTATION;    ALGORITHMS;    TEMPORAL LOGIC;    CIRCUITS;    OPTIMIZATION;    PROJECT PLANNING;   

RP-ID  :  ARC-E-DAA-TN49896,ARC-E-DAA-TN51643

美国|英语

来源: NASA Technical Reports Server

【 摘 要 】

Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong solution approach for the studied class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of methods from operations research, specifically constraint programming (CP), as an alternative and complementary approach to temporal planning. We also extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. The hybrid method uses solutions found by temporal planning to warm-start CP, leveraging the ability of temporal planning to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. These solutions are then used to seed the CP formulation which significantly benefits from inferred bounds on planning horizon and task counts provided by the warm-start. Our extensive empirical evaluation indicates that while stand-alone CP is not competitive with temporal planning, except for the smallest problems, CP in a hybrid setting is beneficial for all temporal planners in all problem classes.