Limiting the Search Space in Optimal Quantum Circuit Mapping

Lukas Burgholzer, Sarah Schneider, Robert Wille

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

Executing quantum circuits on currently available quantum computers requires compiling them to a representation that conforms to all restrictions imposed by the targeted architecture. Due to the limited connectivity of the devices' physical qubits, an important step in the compilation process is to map the circuit in such a way that all its gates are executable on the hardware. Existing solutions delivering optimal solutions to this task are severely challenged by the exponential complexity of the problem. In this paper, we show that the search space of the mapping problem can be limited drastically while still preserving optimality. The proposed strategies are generic, architecture-independent, and can be adapted to various mapping methodologies. The findings are backed by both, theoretical considerations and experimental evaluations. Results confirm that, by limiting the search space, optimal solutions can be determined for instances that timeouted before or speed-ups of up to three orders of magnitude can be achieved.

Original languageEnglish
Title of host publicationASP-DAC 2022 - 27th Asia and South Pacific Design Automation Conference, Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages466-471
Number of pages6
ISBN (Electronic)9781665421355
DOIs
StatePublished - 2022
Externally publishedYes
Event27th Asia and South Pacific Design Automation Conference, ASP-DAC 2022 - Virtual, Online, Taiwan, Province of China
Duration: 17 Jan 202220 Jan 2022

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume2022-January

Conference

Conference27th Asia and South Pacific Design Automation Conference, ASP-DAC 2022
Country/TerritoryTaiwan, Province of China
CityVirtual, Online
Period17/01/2220/01/22

Fingerprint

Dive into the research topics of 'Limiting the Search Space in Optimal Quantum Circuit Mapping'. Together they form a unique fingerprint.

Cite this