論文の概要: Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer

• arxiv url: http://arxiv.org/abs/2012.06119v1
• Date: Fri, 11 Dec 2020 04:30:16 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-21 03:35:18.672792
• Title: Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
• Title（参考訳）: 量子アニールにおける不等式制約二項最適化問題の解法
• Authors: Kouki Yonaga, Masamichi J. Miyama and Masayuki Ohzeki
• Abstract要約: 量子アニールを用いた不等式制約下でのバイナリ最適化問題の解法を提案する。 本研究では,乗算器の交互方向法を用いる。 本手法の計算時間は,高密度グラフ上で定義された様々なQKPに取り組み,精度の高い解法よりも高速であることがわかった。
• 参考スコア（独自算出の注目度）: 0.966840768820136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a new method for solving binary optimization problems under inequality constraints using a quantum annealer. To deal with inequality constraints, we often use slack variables, as in previous approaches. When we use slack variables, we usually conduct a binary expansion, which requires numerous physical qubits. Therefore, the problem of the current quantum annealer is limited to a small scale. In this study, we employ the alternating direction method of multipliers. This approach allows us to deal with various types using constraints in the current quantum annealer without slack variables. To test the performance of our algorithm, we use quadratic knapsack problems (QKPs). We compared the accuracy obtained by our method with a simulated annealer and the optimization and sampling mode of a D-Wave machine. As a result of our experiments, we found that the sampling mode shows the best accuracy. We also found that the computational time of our method is faster than that of the exact solver when we tackle various QKPs defined on dense graphs.
• Abstract（参考訳）: 量子アニールを用いた不等式制約下でのバイナリ最適化問題の解法を提案する。 不等式制約に対処するため、従来のアプローチのようにスラック変数を使うことが多い。 slack変数を使用する場合、通常、多くの物理量子ビットを必要とするバイナリ展開を実行する。 したがって、現在の量子アニールの問題は小さなスケールに限られている。 本研究では,乗算器の交互方向法を適用した。 このアプローチにより、スラック変数を使わずに、現在の量子アニールの制約を使って様々な型を扱うことができる。 アルゴリズムの性能をテストするために、二次的なknapsack問題(QKP)を用いる。 本手法の精度をシミュレーションアニーラとd-waveマシンの最適化・サンプリングモードと比較した。 実験の結果,サンプリングモードが最も精度が高いことがわかった。 また,高密度グラフ上で定義された様々なQKPに対処する場合,計算時間は精度の高い解法よりも速いことがわかった。

関連論文リスト

• Effective Embedding of Integer Linear Inequalities for Variational Quantum Algorithms [0.0]
  変分量子アルゴリズムでは、通常、制約はペナルティ項によって問題対象に追加される。 本研究では,これらの欠点を伴わない量子アルゴリズムの線形不等式をモデル化するためのアプローチについて検討する。 我々の主な提案は、スラック量子ビットを完全に省略し、パラメータチューニング中に古典的に不等式を評価することである。
  論文  参考訳（メタデータ） (2024-03-27T09:32:26Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Depth analysis of variational quantum algorithms for heat equation [0.0]
  量子コンピュータ上での熱方程式を解くための3つの方法を考える。 ハミルトン分解におけるパウリ積の指数的な数は、量子速度を達成できない。 アンザッツ・ツリーのアプローチは行列の明示的な形式を利用しており、古典的アルゴリズムよりも有利である。
  論文  参考訳（メタデータ） (2022-12-23T14:46:33Z)
• Quantum Sparse Coding [5.130440339897477]
  我々はスパース符号化のための量子インスピレーション付きアルゴリズムを開発した。 量子コンピュータとイジングマシンの出現は、より正確な推定につながる可能性がある。 我々はLightrの量子インスパイアされたデジタルプラットフォーム上でシミュレーションデータを用いて数値実験を行う。
  論文  参考訳（メタデータ） (2022-09-08T13:00:30Z)
• 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)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。 量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。 提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
  論文  参考訳（メタデータ） (2022-05-24T03:49:10Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  本稿では,2次非制約二項最適化の事例に対する近似解を求める古典的アルゴリズムを提案する。 我々は、チューニング可能な硬さと植え付けソリューションを備えた大規模問題インスタンスに対して、我々のアプローチをベンチマークする。
  論文  参考訳（メタデータ） (2021-08-18T09:26:17Z)
• Mean Field Approximation for solving QUBO problems [0.0]
  平均場焼鈍における統計物理学的アプローチと量子力学的アプローチが同じ結果をもたらすことを示す。 提案手法は連続変数を持つ単純な勾配に基づく最小化からなるため,シミュレーションが容易である。
  論文  参考訳（メタデータ） (2021-06-06T20:35:28Z)
• 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)
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
  線形制約は、量子アニールで表現できる問題のサイズを減らす。 オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。 D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
  論文  参考訳（メタデータ） (2020-12-18T09:48:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。