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


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
Number of pages15
ISBN (Print)9783031090042
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


Conference14th International Conference on Reversible Computation, RC 2022


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