論文の概要: Reducing quantum annealing biases for solving the graph partitioning
problem
- arxiv url: http://arxiv.org/abs/2103.04963v1
- Date: Mon, 8 Mar 2021 18:37:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-08 18:13:17.918815
- Title: Reducing quantum annealing biases for solving the graph partitioning
problem
- Title（参考訳）: グラフ分割問題の解法における量子アニールバイアスの低減
- Authors: Elijah Pelofske, Georg Hahn, Hristo N. Djidjev
- Abstract要約: この研究を重要なNPハード問題であるグラフ分割に適用する。
量子アニーラー上の制約の実装のバイアスを定量化する。
次に,そのようなバイアスを補正するための反復的手法を提案する。
目的を加味した後、量子アニール上のバイアス補正イジング問題を解くことにより、解の精度が向上することを示した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum annealers offer an efficient way to compute high quality solutions of
NP-hard problems when expressed in a QUBO (quadratic unconstrained binary
optimization) or an Ising form. This is done by mapping a problem onto the
physical qubits and couplers of the quantum chip, from which a solution is read
after a process called quantum annealing. However, this process is subject to
multiple sources of biases, including poor calibration, leakage between
adjacent qubits, control biases, etc., which might negatively influence the
quality of the annealing results. In this work, we aim at mitigating the effect
of such biases for solving constrained optimization problems, by offering a
two-step method, and apply it to Graph Partitioning. In the first step, we
measure and reduce any biases that result from implementing the constraints of
the problem. In the second, we add the objective function to the resulting
bias-corrected implementation of the constraints, and send the problem to the
quantum annealer. We apply this concept to Graph Partitioning, an important
NP-hard problem, which asks to find a partition of the vertices of a graph that
is balanced (the constraint) and minimizes the cut size (the objective). We
first quantify the bias of the implementation of the constraint on the quantum
annealer, that is, we require, in an unbiased implementation, that any two
vertices have the same likelihood of being assigned to the same or to different
parts of the partition. We then propose an iterative method to correct any such
biases. We demonstrate that, after adding the objective, solving the resulting
bias-corrected Ising problem on the quantum annealer results in a higher
solution accuracy.
- Abstract（参考訳）: QUBO (quadratic unconstrained binary optimization) あるいは Ising 形式で表現された場合、量子アニールはNP-hard問題の高品質な解を計算する効率的な方法を提供する。
これは問題を量子チップの物理的量子ビットとカプラにマッピングすることで実現され、そこから量子アニーリングと呼ばれるプロセスで解が読み出される。
しかし, このプロセスは, キャリブレーション不良, 隣接量子ビット間の漏れ, 制御バイアスなど, 熱処理結果の品質に悪影響を及ぼす可能性のある複数のバイアスの原因となる。
本研究では,制約付き最適化問題に対するそのようなバイアスの効果を2段階法により軽減し,グラフ分割に適用することを目的とする。
最初のステップでは、問題の制約を実装することによって生じるバイアスを計測し、削減します。
第二に、結果として生じる制約のバイアス補正実装に目的関数を追加し、問題を量子アニーラに送信する。
この概念を重要なNPハード問題であるグラフ分割に適用し、バランスの取れたグラフの頂点の分割(制約)を求め、カットサイズ(目的)を最小化する。
我々はまず、量子アニールの制約の実装のバイアス、すなわち、偏りのない実装において、任意の2つの頂点が同じあるいはパーティションの異なる部分に割り当てられる確率が同じであるようなバイアスを定量化する。
次に,そのようなバイアスを補正するための反復法を提案する。
目的を加味した後、量子アニール上のバイアス補正イジング問題を解くことにより、解の精度が向上することを示した。
関連論文リスト
- 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) - Anti-crossings occurrence as exponentially closing gaps in Quantum
Annealing [0.0]
焼鈍過程における回避レベル交差の発生条件の導出には摂動膨張を用いる。
正規二部グラフに対して指数的に小さなギャップは生じないことを示し、QAがMaxCutを効率的に解けることを示唆する。
論文 参考訳（メタデータ） (2023-04-25T14:42:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Divide-and-conquer embedding for QUBO quantum annealing [0.0]
組込み問題に焦点をあてたアプローチは、桁違いに性能を向上できることを示す。
以上の結果から,組込み問題に焦点をあてたアプローチにより,桁違いの性能向上が期待できることがわかった。
論文 参考訳（メタデータ） (2022-11-03T23:22:06Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。