論文の概要: Comparing the hardness of MAX 2-SAT problem instances for quantum and
classical algorithms
- arxiv url: http://arxiv.org/abs/2206.06876v2
- Date: Fri, 21 Jul 2023 11:16:11 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-24 16:59:56.214721
- Title: Comparing the hardness of MAX 2-SAT problem instances for quantum and
classical algorithms
- Title（参考訳）: 量子および古典アルゴリズムにおけるMAX 2-SAT問題インスタンスの硬さの比較
- Authors: Puya Mirkarimi, Adam Callison, Lewis Light, Nicholas Chancellor, Viv
Kendon
- Abstract要約: 特定の問題に対するアルゴリズムは、固定された入力サイズであっても、問題のいくつかの例がより簡単であり、解決が困難である可能性がある。
我々は, MAX 2-SAT問題インスタンスの相対的硬度を, 連続時間量子アルゴリズムと同等の古典的アルゴリズムに対して数値解析する。
- 参考スコア（独自算出の注目度）: 1.0499611180329804
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An algorithm for a particular problem may find some instances of the problem
easier and others harder to solve, even for a fixed input size. We numerically
analyse the relative hardness of MAX 2-SAT problem instances for various
continuous-time quantum algorithms and a comparable classical algorithm. This
has two motivations: to investigate whether small-sized problem instances,
which are commonly used in numerical simulations of quantum algorithms for
benchmarking purposes, are a good representation of larger instances in terms
of their hardness to solve, and to determine the applicability of
continuous-time quantum algorithms in a portfolio approach, where we take
advantage of the variation in the hardness of instances between different
algorithms by running them in parallel. We find that, while there are
correlations in instance hardness between all of the algorithms considered,
they appear weak enough that a portfolio approach would likely be desirable in
practice. Our results also show a widening range of hardness of randomly
generated instances as the problem size is increased, which demonstrates both
the difference in the distribution of hardness at small sizes and the value of
a portfolio approach that can reduce the number of extremely hard instances. We
identify specific weaknesses of these quantum algorithms that can be overcome
with a portfolio approach, such their inability to efficiently solve
satisfiable instances (which is easy classically).
- Abstract（参考訳）: 特定の問題に対するアルゴリズムは、固定された入力サイズであっても、問題のいくつかの例がより簡単であり、解決が困難である可能性がある。
我々は, MAX 2-SAT問題インスタンスの相対的硬度を, 連続時間量子アルゴリズムと同等の古典的アルゴリズムに対して数値解析する。
ベンチマークのために量子アルゴリズムの数値シミュレーションで一般的に使用される小型問題インスタンスが、解くのが難しいという観点で大規模インスタンスのよい表現であるかどうかを調べること、ポートフォリオアプローチにおける連続時間量子アルゴリズムの適用性を決定すること、そして、異なるアルゴリズム間のインスタンスの難易度の変化を並列に実行することによって活用すること、の2つの動機がある。
すべてのアルゴリズムが考慮した困難さには相関関係があるが、ポートフォリオアプローチが実際には望ましいと思われるほど弱いように見える。
また,問題の規模が大きくなるにつれて,ランダムに生成されたインスタンスの硬度が広範囲に広がることを示し,小サイズでの硬度分布の違いと,極めて硬度の高いインスタンス数を減らすポートフォリオアプローチの価値を示した。
ポートフォリオアプローチによって克服できるこれらの量子アルゴリズムの特定の弱点を特定し、満足できる(古典的には容易な)インスタンスを効率的に解決できないようにする。
関連論文リスト
- 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) - Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
変分量子アルゴリズム、特に変分量子固有解器の変種は最適化(CO)問題に対処するために提案されている。
ベンチマークとしてMax-Cutを用いてCO問題を解く上で,このスケーリング結果がどのような意味を持つのかを数値的に検討する。
論文 参考訳（メタデータ） (2024-08-06T09:57:34Z) - Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
変分量子アルゴリズムは, 近い将来, 古典的アルゴリズムの代替となる可能性が示唆された。
特に、2つのアルゴリズム、すなわち量子近似最適化アルゴリズム(QAOA)と変分量子固有解器(VQE)の性能を比較した。
シミュレーション実験は、クラウドと2つのエッジノードを含む %CM230124 の単純な問題に対して実施され、VQE アルゴリズムは、検索空間を制限できる適切な回路テクスタイタンサッチを備えている場合に、より良い性能を保証することを示す。
論文 参考訳（メタデータ） (2024-01-25T17:37:40Z) - Quantum Algorithm for Maximum Biclique Problem [11.96554895748371]
頂点の最大数で双斜線を同定することは、多くの応用分野に相当な意味を持つ。
本稿では,時間的複雑性O*(2(n/2))を持つ基底破れアルゴリズムqMBSを提案する。
最大二進問題と最大二進問題に適した2つの変種を詳述する。
論文 参考訳（メタデータ） (2023-09-08T04:43:05Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
グラフ編集距離(GED: Graph Edit Distance)は、2つのグラフ間の(異なる)相似性の度合いを測定する。
本稿では、GED計算における2つの量子アプローチの比較研究について述べる。
論文 参考訳（メタデータ） (2021-11-19T12:35:26Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Entropic barriers as a reason for hardness in both classical and quantum
algorithms [2.062593640149623]
古典的および量子的アルゴリズムを用いて3つの規則ランダムグラフ上の3-XORSATという難解な最適化問題を解く。
大規模なエネルギー障壁を乗り越えることができない新しい準グレーディアルゴリズムを導入することにより、問題硬度は主にエントロピー障壁によるものであることを示す。
論文 参考訳（メタデータ） (2021-01-30T07:58:24Z) - Qualifying quantum approaches for hard industrial optimization problems.
A case study in the field of smart-charging of electric vehicles [0.0]
本稿では,電気自動車のスマートチャージ分野から引き出された2つの産業用NP-Hard問題について事例研究を行う。
量子アルゴリズムは従来の近似アルゴリズムと同じ近似比を示すか、改善する。
次のステップは、より大きなインスタンス上で、実際のデバイス上で、そして対処される問題のより複雑なバージョンに対して、それらを確認することである。
論文 参考訳（メタデータ） (2020-12-29T17:10:31Z) - The limits of min-max optimization algorithms: convergence to spurious
non-critical sets [82.74514886461257]
min-max最適化アルゴリズムは周期サイクルや同様の現象が存在するため、はるかに大きな問題に遭遇する。
問題のどの点も引き付けないアルゴリズムが存在することを示す。
ほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほぼほとんどである。
論文 参考訳（メタデータ） (2020-06-16T10:49:27Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。