論文の概要: Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem

• arxiv url: http://arxiv.org/abs/2011.11918v1
• Date: Tue, 24 Nov 2020 06:36:11 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-23 06:48:57.431798
• Title: Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• Title（参考訳）: グラフマッチング問題に対する量子交互演算子Ansatzの適用
• Authors: Sagnik Chatterjee and Debajyoti Bera
• Abstract要約: グラフの最大マッチングに関するいくつかの問題に対処するための導出手法を設計する。 入力として空の状態が与えられたとき、可能なすべてのマッチングに対する重ね合わせと、入力としてW-状態が与えられたとき、すべての最大マッチングに対する重ね合わせを得る。 本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。
• 参考スコア（独自算出の注目度）: 0.5584060970507505
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The Quantum Alternating Operator Ansatz (QAOA+) framework has recently gained attention due to its ability to solve discrete optimization problems on noisy intermediate-scale quantum (NISQ) devices in a manner that is amenable to derivation of worst-case guarantees. We design a technique in this framework to tackle a few problems over maximal matchings in graphs. Even though maximum matching is polynomial-time solvable, most counting and sampling versions are #P-hard. We design a few algorithms that generates superpositions over matchings allowing us to sample from them. In particular, we get a superposition over all possible matchings when given the empty state as input and a superposition over all maximal matchings when given the W -states as input. Our main result is that the expected size of the matchings corresponding to the output states of our QAOA+ algorithm when ran on a 2-regular graph is greater than the expected matching size obtained from a uniform distribution over all matchings. This algorithm uses a W -state as input and we prove that this input state is better compared to using the empty matching as the input state.
• Abstract（参考訳）: Quantum Alternating Operator Ansatz (QAOA+) フレームワークは,ノイズの多い中間スケール量子(NISQ)デバイスにおける離散的な最適化問題を,最悪のケース保証の導出に相応しい方法で解決できることから,近年注目されている。 グラフの最大マッチングに関するいくつかの問題に対処する手法をこのフレームワークで設計する。 最大マッチングは多項式時間可解であるが、ほとんどのカウントとサンプリングは#pハードである。 マッチングの上に重ね合わせを生成するアルゴリズムを設計し、それらからサンプルを抽出する。 特に、空状態が入力として与えられ、w-状態が入力として与えられるとき、すべての最大マッチングに対する重ね合わせが得られる。 本研究の主な成果は,QAOA+アルゴリズムの2正規グラフ上での実行時の出力状態に対応するマッチングの期待サイズが,全てのマッチングの均一分布から得られるマッチングサイズよりも大きいことである。 このアルゴリズムはW状態を入力として使用し、この入力状態が空のマッチングを入力状態として使用するよりも優れていることを示す。

関連論文リスト

• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。 不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。 無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
  論文  参考訳（メタデータ） (2023-12-18T18:29:01Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models [15.857373057387669]
  無限大極限におけるランダム最適化問題のアンサンブル上での任意の一定レベル(層数)における濃度特性を証明した。 我々の分析は、サドル点近似の和対パス積分によって理解することができる。 一定レベルにおけるQAOAの性能は、$qge 4$のときの純$q$-spinモデルの最適性から外れ、偶数であることを示す。
  論文  参考訳（メタデータ） (2022-04-21T17:40:39Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  従来の計算手法は、半定値の標準的なプログラミング技術に基づいていた。 確率分布が均一な量子ビットアンサンブルの量子推定処理を計算すれば、よりクワッドラティックなスピードアップがもたらされることを示す。 例として、正則および準正則なクォービット状態集合の推理を計算する。
  論文  参考訳（メタデータ） (2021-12-03T01:24:57Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。 具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。 ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-06-22T11:07:38Z)
• Generating Target Graph Couplings for QAOA from Native Quantum Hardware Couplings [3.2622301272834524]
  本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。 本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。 Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
  論文  参考訳（メタデータ） (2020-11-16T18:43:09Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  組合せ最適化は、短期的およびフォールトトレラントな量子コンピュータに想定される主な応用の1つである。 量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm, QAOA)は3つの正則グラフ上のMaxCut問題に適用される。 理論上界と下界を導いており、満たされた辺の分数の一定(小さい)増加が実際に達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-10T22:17:50Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case [6.810856082577402]
  量子回路は、グラフの局所性を尊重するユニタリ作用素の p 個の応用を持つ。 我々は、d と n を大きく保った dn/2 エッジを持つランダムグラフにおいて、大きな独立集合を見つけることに集中する。
  論文  参考訳（メタデータ） (2020-04-20T00:48:02Z)

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

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