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

• Item type: SIG Technical Reports(1)
• 公開日: 2021-06-24
• タイトル: Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
• タイトル / 言語: en
• タイトル: Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: NTT Communication Science Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者名: Seiichiro, Tani
• 著者名(英): Seiichiro, Tani
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function. OBDDs are also known as special cases of oblivious read-once branching programs in the field of complexity theory. 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 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 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. Hence, numerous studies have sought heuristics to find an optimal variable ordering. From practical as well as theoretical points of view, it is also important to seek algorithms that output optimal solutions with lower (exponential) time complexity than trivial brute-force algorithms do. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O*(3n), where n is the number of variables of the function, which is much better than the trivial brute-force bound O*(n!2n). This paper shows that a further speedup is possible with quantum computers by demonstrating the existence of a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O*(2.77286n) time and space with an exponentially small error. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams such as zero-suppressed BDDs, which provide compact representations of sparse sets and are often used in the field of discrete optimization and enumeration.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function. OBDDs are also known as special cases of oblivious read-once branching programs in the field of complexity theory. 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 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 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. Hence, numerous studies have sought heuristics to find an optimal variable ordering. From practical as well as theoretical points of view, it is also important to seek algorithms that output optimal solutions with lower (exponential) time complexity than trivial brute-force algorithms do. Friedman and Supowit provided a clever deterministic algorithm with time/space complexity O*(3n), where n is the number of variables of the function, which is much better than the trivial brute-force bound O*(n!2n). This paper shows that a further speedup is possible with quantum computers by demonstrating the existence of a quantum algorithm that produces a minimum OBDD together with the corresponding variable ordering in O*(2.77286n) time and space with an exponentially small error. Moreover, this algorithm can be adapted to constructing other minimum decision diagrams such as zero-suppressed BDDs, which provide compact representations of sparse sets and are often used in the field of discrete optimization and enumeration.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12894105
• 書誌情報: 量子ソフトウェア（QS）; 巻 2021-QS-3, 号 1, p. 1-6, 発行日 2021-06-24
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2435-6492
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会