論文の概要: Posiform Planting: Generating QUBO Instances for Benchmarking
- arxiv url: http://arxiv.org/abs/2308.05859v2
- Date: Sun, 29 Oct 2023 02:04:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 20:23:14.815323
- Title: Posiform Planting: Generating QUBO Instances for Benchmarking
- Title（参考訳）: Posiform Planting: ベンチマークのためのQUBOインスタンスの生成
- Authors: Georg Hahn, Elijah Pelofske, Hristo N. Djidjev
- Abstract要約: 本稿では,任意のサイズのランダムQUBOインスタンスを既知の最適解で生成する,posform plantingと呼ばれる新しい手法を提案する。
実験では,最大5,627ドルキュービットの最適化問題の最適植込み解をサンプリングするD-Wave量子アニールの能力を実証した。
- 参考スコア（独自算出の注目度）: 2.7624021966289605
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We are interested in benchmarking both quantum annealing and classical
algorithms for minimizing Quadratic Unconstrained Binary Optimization (QUBO)
problems. Such problems are NP-hard in general, implying that the exact minima
of randomly generated instances are hard to find and thus typically unknown.
While brute forcing smaller instances is possible, such instances are typically
not interesting due to being too easy for both quantum and classical
algorithms. In this contribution, we propose a novel method, called posiform
planting, for generating random QUBO instances of arbitrary size with known
optimal solutions, and use those instances to benchmark the sampling quality of
four D-Wave quantum annealers utilizing different interconnection structures
(Chimera, Pegasus, and Zephyr hardware graphs) as well as the simulated
annealing algorithm. Posiform planting differs from many existing methods in
two key ways. It ensures the uniqueness of the planted optimal solution, thus
avoiding groundstate degeneracy, and it enables the generation of QUBOs that
are tailored to a given hardware connectivity structure, provided that the
connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT
boolean satisfiability combinatorial optimization problems. Our experiments
demonstrate the capability of the D-Wave quantum annealers to sample the
optimal planted solution of combinatorial optimization problems with up to
$5627$ qubits.
- Abstract（参考訳）: 量子アニーリングと古典的アルゴリズムの両方をベンチマークして、量子非制約バイナリ最適化(QUBO)問題を最小化することに興味がある。
このような問題は一般にNPハードであり、ランダムに生成されたインスタンスの正確なミニマは見つけるのが難しく、典型的には未知であることを意味する。
bruteによる小さなインスタンスの強制は可能だが、量子アルゴリズムと古典アルゴリズムの両方が容易すぎるため、そのようなインスタンスは一般的には面白くない。
本研究では,任意の大きさのランダムquboインスタンスを既知の最適解で生成し,異なる相互接続構造(chimera,pegasus,zephyrハードウェアグラフ)とシミュレーションアニーリングアルゴリズムを用いて4つのd波量子アニーラのサンプリング品質をベンチマークする手法であるposiform plantingを提案する。
ポシフォームの植え付けは多くの既存の方法と2つの重要な方法で異なる。
植付された最適解の特異性を保証し、したがって基底状態の縮退を回避し、接続性があまり疎かでないことを前提として、所定のハードウェア接続構造に適合したQUBOの生成を可能にする。
posiform planted qubos は 2-sat boolean satisfiability combinatorial optimization problem の一種である。
実験では,最大5,627ドルキュービットの組合せ最適化問題の最適植込み解をサンプリングするD-Wave量子アニールの能力を実証した。
関連論文リスト
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking [1.6385815610837167]
我々は,多数の小さな離散係数スピングラスイジングモデルを融合させることにより,ポジフォーム植込みQUBOを計算的に困難にすることを検討する。
3つのD-Wave超伝導量子アニーリングプロセッサの性能をベンチマークする。
D-Wave QPUの地中サンプリング成功率は、我々が採用するランダムQUBOのサイズに対して変化しないことがわかった。
論文 参考訳（メタデータ） (2024-11-06T02:46:33Z) - 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) - Quantum Annealing Solutions for the Closest String Problem with D-Wave
Systems [0.0]
クローズストストリング問題(Closest String problem)は、生物情報学や符号化理論でよく見られるNP完全問題である。
2つのQUBOの定式化が提案されており、1つはもう1つに対してわずかに修正されている。
DWaveアナライザは、特定のプラットフォーム固有の関心事に対する最適なガイドラインを提供しながら使われてきた。
論文 参考訳（メタデータ） (2023-10-19T16:03:25Z) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
本研究では,最適化のための量子および古典的手法の可能性を統合する。
線形緩和により問題のサイズを小さくし、最小サイズの量子マシンで問題を処理できるようにした。
実量子ハードウェアの計算結果を多数提示する。
論文 参考訳（メタデータ） (2023-02-10T20:12:53Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
本研究は、キュービット重畳状態に適したQUBO問題に焦点をあてる。
我々は、QUBOをコストオラクルの演算として符号化する回路設計を、標準Grover拡散演算子$U_textrms$と組み合わせると、最適および近似最適解に対応する状態の測定確率が高くなることを示す。
論文 参考訳（メタデータ） (2023-01-31T14:33:40Z) - Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems [1.0878040851638]
我々は3世代にわたるD-Wave量子アニールのベンチマークを報告する。
イジングあるいは等価なQUBOは、これらの問題の定式化は順序の減少のために補助変数を必要としない。
論文 参考訳（メタデータ） (2023-01-08T10:02:56Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。
我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
論文 参考訳（メタデータ） (2021-08-18T09:26:17Z) - Randomized Stochastic Variance-Reduced Methods for Stochastic Bilevel
Optimization [62.87181271021217]
機械学習に多くの応用がある非SBO問題を考察する。
本稿では,非SBO問題に対する高速ランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-05T18:28:42Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。