Boolean satisfiability in quantum compilation. (23rd December 2019)

• Record Type: Journal Article
• Authors: Soeken, Mathias; Meuli, Giulia; Schmitt, Bruno; Mozafari, Fereshte; Riener, Heinz; De Micheli, Giovanni
• Is Part Of: Philosophical transactions. Volume 378:Number 2164(2020)
• Publication Date: 2019-12-23
• Subjects: quantum computing -- quantum programming languages -- quantum compilation -- Boolean satisfiability -- logic synthesis; Physical sciences -- Periodicals; Engineering -- Periodicals; Mathematics -- Periodicals; 500
• DOI: 10.1098/rsta.2019.0161
• Languages: English
• ISSNs: 1364-503X

Abstract

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'.