論文の概要: Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm
- arxiv url: http://arxiv.org/abs/2012.10135v3
- Date: Fri, 28 May 2021 06:33:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 06:24:30.133131
- Title: Larger Sparse Quadratic Assignment Problem Optimization Using Quantum
Annealing and a Bit-Flip Heuristic Algorithm
- Title（参考訳）: 量子アニーリングとビットフリップヒューリスティックアルゴリズムを用いたより広いスパース2次割当問題最適化
- Authors: Michiya Kuramata, Ryota Katsuki, Kazuhide Nakata
- Abstract要約: 線形制約は、量子アニールで表現できる問題のサイズを減らす。
オーゼキ法により得られた解に対して,後処理ビットフリップアルゴリズムを適用し,スパースQAPの解法を提案する。
D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
- 参考スコア（独自算出の注目度）: 0.4125187280299248
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum annealing and D-Wave quantum annealer attracted considerable
attention for their ability to solve combinatorial optimization problems. In
order to solve other type of optimization problems, it is necessary to apply
certain kinds of mathematical transformations. However, linear constraints
reduce the size of problems that can be represented in quantum annealers, owing
to the sparseness of connections between qubits. For example, the quadratic
assignment problem (QAP) with linear equality constraints can be solved only up
to size 12 in the quantum annealer D-Wave Advantage, which has 5640 qubits. To
overcome this obstacle, Ohzeki developed a method for relaxing the linear
equality constraints and numerically verified the effectiveness of this method
with some target problems, but others remain unsolvable. In particular, it is
difficult to obtain feasible solutions to problems with hard constraints, such
as the QAP. We therefore propose a method for solving the QAP with quantum
annealing by applying a post-processing bit-flip heuristic algorithm to
solutions obtained by the Ohzeki method. In a numerical experiment, we solved a
sparse QAP by the proposed method. This sparse QAP has been used in areas such
as item listing on an E-commerce website. We successfully solved a QAP of size
19 with high accuracy for the first time using D-Wave Advantage. We also
confirmed that the bit-flip heuristic algorithm moves infeasible solutions to
nearby feasible solutions in terms of Hamming distance with good computational
efficiency.
- Abstract（参考訳）: 量子アニールとD波量子アニールは組合せ最適化問題を解く能力にかなりの注目を集めた。
他のタイプの最適化問題を解くためには、ある種の数学的変換を適用する必要がある。
しかし、線形制約は、量子異方体で表現できる問題のサイズを減少させる。
例えば、線形等式制約を持つ二次代入問題(qap)は、5640キュービットの量子アニーラー d-wave advantage において最大12サイズまで解くことができる。
この障害を克服するため、大関は線形等式制約を緩和する手法を開発し、この手法の有効性をいくつかの問題で数値的に検証した。
特に、QAPのような厳しい制約のある問題に対する実現可能な解を得るのは難しい。
そこで本研究では,オオゼキ法により得られた解に対して,後処理のビットフリップヒューリスティックアルゴリズムを適用し,量子アニールによるQAPの解法を提案する。
数値実験では,提案手法を用いてスパースQAPを解いた。
この粗末なQAPは、Eコマースウェブサイトのアイテムリストのような分野で使われてきた。
D-Wave Advantage を用いて,D-Wave Advantage を用いた QAP の高精度化に成功した。
また, ビットフリップヒューリスティックアルゴリズムは, 計算効率のよいハミング距離の観点から, 実現不可能な解を近くの実現可能解へ移動させることを確認した。
関連論文リスト
- A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
本稿では,量子安定化器符号の最小距離を準拘束的二項最適化問題として再定式化することで計算する手法を提案する。
D-Wave Advantage 4.1quantum annealerと比較することにより,本手法の実用性を示す。
論文 参考訳（メタデータ） (2024-04-26T21:29:42Z) - Hybrid classical-quantum branch-and-bound algorithm for solving integer
linear problems [0.0]
量子アニールは、QUBOの定式化で表されるいくつかのロジスティック最適化問題を解くのに適している。
量子異方体が提案する解法は一般に最適ではなく、熱ノイズやその他の乱雑な効果は計算に関わる量子ビットの数が大きすぎるときに生じる。
本稿では,従来の分枝分枝分枝法を用いて,より少ない量子ビット数で表されるサブプロブレムに分割する手法を提案する。
論文 参考訳（メタデータ） (2023-11-16T09:19:01Z) - Quantum-based Distributed Algorithms for Edge Node Placement and
Workload Allocation [8.937905773981702]
最適なエッジサーバ配置とワークロード割り当てのための混合整数線形プログラミング(MILP)モデルを提案する。
既存の量子解法は制約のないバイナリプログラミング問題の解法に限られる。
数値実験により,エッジコンピューティングの複雑な最適化問題を解くために量子超越性を活用できることが実証された。
論文 参考訳（メタデータ） (2023-06-01T21:33:08Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
波長割当問題を解くための量子インスピレーションアルゴリズムを提案し,開発する。
本研究は,電気通信における現実的な問題に対する量子インスパイアされたアルゴリズムの活用の道筋をたどるものである。
論文 参考訳（メタデータ） (2022-11-01T07:52:47Z) - 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) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳（メタデータ） (2021-10-15T11:19:48Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - 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) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。