論文の概要: Adiabatic Quantum Graph Matching with Permutation Matrix Constraints

• arxiv url: http://arxiv.org/abs/2107.04032v1
• Date: Thu, 8 Jul 2021 17:59:55 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-09 13:32:01.695387
• Title: Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
• Title（参考訳）: 置換行列制約を伴う断熱量子グラフマッチング
• Authors: Marcel Seelbach Benkner and Vladislav Golyanik and Christian Theobalt and Michael Moeller
• Abstract要約: 3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
• 参考スコア（独自算出の注目度）: 75.88678895180189
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Matching problems on 3D shapes and images are challenging as they are frequently formulated as combinatorial quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. In this work, we address such problems with emerging quantum computing technology and propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. We investigate several ways to inject permutation matrix constraints in a quadratic unconstrained binary optimization problem which can be mapped to quantum hardware. We focus on obtaining a sufficient spectral gap, which further increases the probability to measure optimal solutions and valid permutation matrices in a single run. We perform our experiments on the quantum computer D-Wave 2000Q (2^11 qubits, adiabatic). Despite the observed discrepancy between simulated adiabatic quantum computing and execution on real quantum hardware, our reformulation of permutation matrix constraints increases the robustness of the numerical computations over other penalty approaches in our experiments. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures, which opens up multiple new directions for solving matching problems in 3D computer vision and graphics.
• Abstract（参考訳）: 3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ組合せ二次代入問題(QAP)としてしばしば定式化されるため、困難である。 本研究では,量子コンピューティング技術の進歩に伴う問題に対処し,量子ハードウェア上での効率的な実行に適した制約のない問題として,QAPのいくつかの改革を提案する。 量子ハードウェアにマッピング可能な2次非制約二元最適化問題において、置換行列制約を注入する方法をいくつか検討する。 本研究は,最適解と変分行列を単一ランで測定する確率をさらに高める十分なスペクトルギャップを得ることに焦点を当てる。 量子コンピュータD-Wave 2000Q (2^11 qubits, adiabatic) で実験を行った。 シミュレーションされたアディバティック量子コンピューティングと実際の量子ハードウェア上での実行の相違にもかかわらず、置換行列制約の再構成は、実験における他のペナルティアプローチよりも数値計算の堅牢性を高める。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャの高次元にスケールできる可能性があり、3次元コンピュータビジョンとグラフィックスのマッチング問題を解決するために、複数の新しい方向を開く。

関連論文リスト

• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。 どの場の量子スピードアップが達成できるかという新たな課題が生じる。 量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
  論文  参考訳（メタデータ） (2024-02-26T09:32:07Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation Scheduling [0.0]
  本稿では、量子コンピューティング、機械学習、分散最適化による生成スケジューリングのための2ループ量子解アルゴリズムを提案する。 この目的は、実用的な電力系統の問題を解決するために、限られた量子ビット数を持つ短期量子機械の雑音を緩和することである。
  論文  参考訳（メタデータ） (2023-03-28T21:31:39Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer [13.528362112761805]
  本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。 我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。 本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
  論文  参考訳（メタデータ） (2022-06-13T16:21:04Z)
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer [0.0]
  グラフ上の組合せ最適化問題は、科学と工学に幅広い応用がある。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は、変分回路の複数ラウンドを適用して量子コンピュータ上でこれらの問題を解く方法である。 本稿では,いくつかの任意のグラフ上の複数の問題に対するラウンド数によってQAOAが向上するトラップイオン量子コンピュータを実演する。
  論文  参考訳（メタデータ） (2022-01-28T18:57:14Z)
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing [1.7077661158850292]
  データ集約的な問題領域において重要なNPハード問題である多重クエリ最適化問題(MQO)に取り組む。 ゲート型量子コンピュータ上でMQOを解くために,新しい古典量子アルゴリズムを提案する。 提案アルゴリズムでは, クビット効率が99%に近づき, ほぼ2倍に向上した。
  論文  参考訳（メタデータ） (2021-07-22T08:12:49Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• 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)
• Quantum-Assisted Graph Clustering and Quadratic Unconstrained D-ary Optimisation [1.4653008985229616]
  本稿では、量子アルゴリズムやより正確には量子支援アルゴリズムによる教師なしグラフクラスタリングについて検討する。 量子近似最適化アルゴリズムによる最大カットを解くためのキュート回路を構築する。
  論文  参考訳（メタデータ） (2020-04-03T09:10:24Z)

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

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