License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.36
URN: urn:nbn:de:0030-drops-122832
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12283/
Go to the corresponding LIPIcs Volume Portal

Tani, Seiichiro

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams

pdf-format:
LIPIcs-SWAT-2020-36.pdf (0.9 MB)

Abstract

An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function. Since OBDDs have many nice properties as data structures, they have been extensively studied for decades in both theoretical and practical fields, such as VLSI (Very Large Scale Integration) design, formal verification, machine learning, and combinatorial problems. Arguably, the most crucial problem in using OBDDs is that they may vary exponentially in size depending on their variable ordering (i.e., the order in which the variables are to be read) when they represent the same function. Indeed, it is NP hard to find an optimal variable ordering that minimizes an OBDD for a given function. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O^∗(3ⁿ), where n is the number of variables of the function, which is much better than the trivial brute-force bound O^∗(n!2ⁿ). This paper shows that a further speedup is possible with quantum computers by presenting a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O^∗(2.77286ⁿ) time and space with an exponentially small error probability. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams such as zero-suppressed BDDs.

BibTeX - Entry

@InProceedings{tani:LIPIcs:2020:12283,
  author =	{Seiichiro Tani},
  title =	{{Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Susanne Albers},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12283},
  URN =		{urn:nbn:de:0030-drops-122832},
  doi =		{10.4230/LIPIcs.SWAT.2020.36},
  annote =	{Keywords: Binary Decision Diagram, Variable Ordering, Quantum Algorithm}
}

Keywords: Binary Decision Diagram, Variable Ordering, Quantum Algorithm
Collection: 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI