論文の概要: Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
- arxiv url: http://arxiv.org/abs/1909.12658v3
- Date: Fri, 16 May 2025 06:01:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-19 14:36:10.672276
- Title: Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
- Title（参考訳）: 2値決定ダイアグラムの最適可変順序を求める量子アルゴリズム
- Authors: Seiichiro Tani,
- Abstract要約: 順序付き二項決定図(OBDD)は、ブール関数を表す有向非巡回グラフである。
本稿では,最小のOBDDを生成する量子アルゴリズムの存在を実証することにより,量子コンピュータのさらなる高速化が可能であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: 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 variable 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^\ast(3^n)$, where $n$ is the number of variables of the function, which is much better than the trivial brute-force bound $O^\ast(n!2^n)$. 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^\ast(2.77286^n)$ 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.
- Abstract（参考訳）: 順序付き二項決定図(OBDD)は、ブール関数を表す有向非巡回グラフである。
OBDDは、複雑性理論の分野における不可避な読み取りオンス分岐プログラムの特別なケースとしても知られている。
OBDDはデータ構造として多くの優れた性質を持っているため、VLSI設計、形式検証、機械学習、組合せ問題といった理論的および実践的な分野において、数十年にわたって広く研究されてきた。
間違いなく、OBDDを使用する際の最も重要な問題は、それらが同じ関数を表すときに、変数の順序(つまり、変数が読み込まれる順序)に応じて指数関数的にサイズが変化することである。
実際、与えられた関数に対する OBDD を最小化する最適な変数順序を見つけることは、NP では困難である。
したがって、多くの研究が最適な変数順序付けを見つけるためのヒューリスティックを求めている。
実用的および理論的観点からは、自明なブルートフォースアルゴリズムよりも低い(指数的な)時間複雑性の最適解を出力するアルゴリズムを求めることも重要である。
FriedmanとSupowitは、時間/空間の複雑さを持つ巧妙な決定論的アルゴリズム($O^\ast(3^n)$)を提供し、$n$は関数の変数の数である。
本稿では,O^\ast(2.77286^n)$時間と空間を指数的に小さな誤差で順序付けすることで,最小のOBDDを生成する量子アルゴリズムの存在を実証することにより,量子コンピュータのさらなる高速化が可能であることを示す。
さらに、このアルゴリズムは、スパース集合のコンパクトな表現を提供し、離散最適化や列挙の分野でよく使われるゼロ抑圧BDDのような、他の最小限の決定図を構築することに適応することができる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。
本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。
我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
論文 参考訳（メタデータ） (2024-08-11T10:28:49Z) - Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Submodular Maximization subject to a Knapsack Constraint: Combinatorial
Algorithms with Near-optimal Adaptive Complexity [13.416309759182635]
我々は、ほぼ最適の$O(log n)$適応複雑性を持つ非単調部分モジュラーアルゴリズムに対する最初の定数近似を得る。
我々のアルゴリズムは$tildeO(n2)$の値クエリを要求するが、代わりに$tildeO(n)$で実行するように修正できる。
これはまた、この問題に対して線形適応的な複雑性を持つ最初のアプローチであり、濃度制約や単調な目的の特別な場合であっても、最先端の手法に匹敵する。
論文 参考訳（メタデータ） (2021-02-16T18:15:51Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。