Reordering Decision Diagrams for Quantum Computing Is Harder Than You Might Think

Stefan Hillmich, Lukas Burgholzer, Florian Stögmüller, Robert Wille

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

2 Scopus citations

Abstract

Decision diagrams have proven to be a useful data structure in both, conventional and quantum computing, to compactly represent exponentially large data in many cases. Several approaches exist to further reduce the size of decision diagrams, i.e., their number of nodes. Reordering is one such approach to shrink decision diagrams by changing the order of variables in the representation. In the conventional world, this approach is established and its availability taken for granted. For quantum computing however, first approaches exist, but could not fully exploit a similar potential yet. In this paper, we investigate the differences between reordering decision diagrams in the conventional and the quantum world and, afterwards, unveil challenges that explain why reordering is much harder in the latter. A case study shows that, also for quantum computing, reordering may lead to improvements of several orders of magnitude in the size of the decision diagrams, but also requires substantially more runtime.

Original languageEnglish
Title of host publicationReversible Computation - 14th International Conference, RC 2022, Proceedings
EditorsClaudio Antares Mezzina, Krzysztof Podlaski
PublisherSpringer Science and Business Media Deutschland GmbH
Pages93-107
Number of pages15
ISBN (Print)9783031090042
DOIs
StatePublished - 2022
Event14th International Conference on Reversible Computation, RC 2022 - Urbino, Italy
Duration: 5 Jul 20226 Jul 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13354 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Reversible Computation, RC 2022
Country/TerritoryItaly
CityUrbino
Period5/07/226/07/22

Fingerprint

Dive into the research topics of 'Reordering Decision Diagrams for Quantum Computing Is Harder Than You Might Think'. Together they form a unique fingerprint.

Cite this