Boolean satisfiability in quantum compilation

Mathias Soeken, Giulia Meuli, Bruno Schmitt, Fereshte Mozafari, Heinz Riener, Giovanni De Micheli

Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · 2019 · 16 citations · 37 references

DOIFull text

Open access

Concepts

TL;DR

Quantum compilation translates high‑level quantum programs into technology‑dependent instruction flows through a multi‑stage abstraction hierarchy, yet many of its constituent tasks are NP‑hard. The article aims to describe a quantum compilation flow and propose Boolean satisfiability–based algorithms to address its computationally complex tasks. The authors propose using Boolean satisfiability techniques to model and solve the multi‑stage quantum compilation flow. This article is part of the theme issue “Harmonizing energy‑autonomous computing and intelligence.”.

Abstract

Quantum compilation is the task of translating a quantum algorithm implemented in a high-level quantum programming language into a technology-dependent instructions flow for a physical quantum computer. To tackle the large gap between the quantum program and the low-level instructions, quantum compilation is split into a multi-stage flow consisting of several layers of abstraction. Several different individual tasks have been proposed for the layers in the flow, many of them are NP-hard. In this article, we will describe the flow and we will propose algorithms based on Boolean satisfiability, which is a good match to tackle such computationally complex problems. This article is part of the theme issue ‘Harmonizing energy-autonomous computing and intelligence’.

References

37