CLINE: Improving Control Flow Compilation of Quantum Programs with Control Line Encoding

Important applications like quantum search and quantum simulation rely on control flow implemented by oracle circuits, which may account for up to 99% of the total gate count [1] as oracle circuits consist of expensive multi-controlled (MC) quantum operations that formulate the control flow. Existing efforts optimize them by simplifying Boolean expressions associated with MC gates. They merge MC gates, if associated Boolean expressions are adjacent, to reduce the gate cost. Being more aggressive, our work introduces control line encoding (CLE), a technique that even allows merging non-adjacent MC gates by modifying their control (line) polarity. We further develop a plug-in compiler framework that efficiently applies this technique. The framework is grounded in the following observations: 1) Control flows often commute with one another and can be globally reorganized to maximize their merging by CLE; 2) numerous CLE schemes exist to allow gate merge and we can co-design CLE applications to diminish the overhead of CLE itself. Experiments demonstrate that, compared to the baseline, our framework further reduces the CX and T cost, on average by 54.7% and 56.8%, respectively.