論文の概要: Quantum Annealing for the Set Splitting Problem
- arxiv url: http://arxiv.org/abs/2508.06410v1
- Date: Fri, 08 Aug 2025 15:55:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-11 20:39:06.290828
- Title: Quantum Annealing for the Set Splitting Problem
- Title（参考訳）: 集合分割問題に対する量子アニーリング
- Authors: Sean Borneman,
- Abstract要約: 本稿では,QUBO問題定式化を用いたセット分割問題の解法として,新しい量子アニール法を提案する。
この研究の貢献は、QUBOハミルトニアンの基底状態が入力部分集合を分割する有効な解に対応することを保証するペナルティ関数を定式化することにある。
提案した解の実証実験は, 繰り返し試行よりも高い精度で, 全球最適解への収束を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: I present a novel use of quantum annealing to solve the Set Splitting Problem using (QUBO) problem formulation. The contribution of the work is in formulating penalty functions that ensure the ground state of the QUBO Hamiltonian corresponds to valid solutions that split the input subsets. This approach scales linearly in terms of the number of logical qubits relative to problem size. Empirical tests of the proposed solution show convergence to globally optimal solutions, with high accuracy rates over repeated trials. Hardware limitations of current quantum annealers lead to an exponential rise in required physical qubits, versus the theoretical linear increase, although this can improve with future developments. Further work is needed to enhance formulation robustness, reduce qubit requirements for embedded problems, and to conduct more extensive bench-marking. Quantum solutions to the Set-Splitting problem lead to reduced time complexity versus classical solutions, and may accelerate research in biology, cybersecurity, and other domains.
- Abstract（参考訳）: 本稿では,QUBO問題定式化を用いたセット分割問題の解法として,新しい量子アニール法を提案する。
この研究の貢献は、QUBOハミルトニアンの基底状態が入力部分集合を分割する有効な解に対応することを保証するペナルティ関数を定式化することにある。
このアプローチは、問題サイズに対する論理量子ビットの数の観点から線形にスケールする。
提案した解の実証実験は, 繰り返し試行よりも高い精度で, 全球最適解への収束を示す。
現在の量子アニールのハードウェア上の制限は、理論的な線形増加よりも要求される物理量子ビットの指数的な増加につながるが、これは将来の発展によって改善される。
フォーミュレーションの堅牢性を高め、組込み問題に対するキュービット要求を減らし、より広範なベンチマーキングを行うためには、さらなる作業が必要である。
Set-Splitting問題に対する量子解は、古典的な解に比べて時間の複雑さを減らし、生物学、サイバーセキュリティ、その他の領域の研究を加速させる可能性がある。
関連論文リスト
- Quantum-Classical Hybrid Quantized Neural Network [7.759760132559044]
本稿では、任意のアクティベーションと損失関数の使用を可能にする、量子化されたニューラルネットワークトレーニングのための新しい擬似バイナリ最適化(QBO)モデルを提案する。
我々はQCBO問題を直接解くために量子コンピューティングを利用するQCGD(Quantum Gradient Conditional Descent)アルゴリズムを用いる。
コヒーレントイジングマシン(CIM)を用いた実験結果は、Fashion MNIST分類タスクにおいて94.95%の精度を示し、1.1ビットの精度しか示さない。
論文 参考訳（メタデータ） (2025-06-23T02:12:36Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-11T04:40:05Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳（メタデータ） (2023-11-16T09:19:01Z) - Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno
Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。
これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
論文 参考訳（メタデータ） (2023-05-14T03:49:10Z) - Efficient MILP Decomposition in Quantum Computing for ReLU Network
Robustness [2.854196251981274]
本研究では,MILP(Mixed-Integer Linear Programming)の2つの分解法について検討した。
我々は、元の問題をより小さなサブプロブレムに分割することに集中し、量子古典的ハードウェアのアプローチを組み合わせて反復的に解決する。
実験の結果,従来の量子アニール法やゲートベース量子コンピュータと比較して最大90%の量子ビットを削減できることがわかった。
論文 参考訳（メタデータ） (2023-04-30T13:10:56Z) - Multiobjective variational quantum optimization for constrained
problems: an application to Cash Management [45.82374977939355]
本稿では,変分量子アルゴリズムを用いた制約付き最適化問題の解法を提案する。
我々は、キャッシュマネジメント問題という、金融の極めて関連性の高い現実世界の問題について、我々の提案を検証した。
実験の結果, 実現したソリューションのコスト, 特に局所最小値の回避に関して, 大幅な改善が見られた。
論文 参考訳（メタデータ） (2023-02-08T17:09:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。