Fugu-MT 論文翻訳(概要): Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA

論文の概要: Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA

arxiv url: http://arxiv.org/abs/2009.01095v3
Date: Mon, 9 Nov 2020 21:35:28 GMT
ステータス: 処理完了
システム内更新日: 2023-05-04 01:03:19.665108
Title: Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
Title（参考訳）: QAOAを用いた量子コンピュータ上の重み付きMAX k-CUTの効率的な符号化
Authors: Franz Georg Fuchs, Herman {\O}ie Kolden, Niels Henrik Aase, and Giorgio Sartor
Abstract要約: 本稿では、ノイズのある中間スケール量子(NISQ)デバイス上で量子近似最適化アルゴリズム(QAOA)を実行するのに適した重み付きMAX k-CUTの定式化について述べる。新しい定式化は、|V|log_2(k) 量子ビットのみを必要とするバイナリエンコーディングを使用する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: The weighted MAX k-CUT problem consists of finding a k-partition of a given weighted undirected graph G(V,E) such that the sum of the weights of the crossing edges is maximized. The problem is of particular interest as it has a multitude of practical applications. We present a formulation of the weighted MAX k-CUT suitable for running the quantum approximate optimization algorithm (QAOA) on noisy intermediate scale quantum (NISQ)-devices to get approximate solutions. The new formulation uses a binary encoding that requires only |V|log_2(k) qubits. The contributions of this paper are as follows: i) A novel decomposition of the phase separation operator based on the binary encoding into basis gates is provided for the MAX k-CUT problem for k >2. ii) Numerical simulations on a suite of test cases comparing different encodings are performed. iii) An analysis of the resources (number of qubits, CX gates) of the different encodings is presented. iv) Formulations and simulations are extended to the case of weighted graphs. For small k and with further improvements when k is not a power of two, our algorithm is a possible candidate to show quantum advantage on NISQ devices.
Abstract（参考訳）: 重み付きMAX k-CUT問題は、与えられた重み付き無向グラフ G(V,E) の k 分割を見つけ、交差エッジの重みの和を最大化する。問題は、多くの実用的な応用があるため、特に興味深い。本稿では、ノイズのある中間スケール量子(NISQ)デバイス上で量子近似最適化アルゴリズム(QAOA)を実行するのに適した重み付きMAX k-CUTの定式化について述べる。新しい定式化は、|V|log_2(k) 量子ビットのみを必要とするバイナリエンコーディングを使用する。本論文の貢献は以下のとおりである。 i) k > 2 の最大 k-カット問題に対して、基底ゲートへのバイナリエンコーディングに基づく位相分離演算子の新規な分解を提供する。二異なる符号化を比較した一組のテストケースの数値シミュレーションを行う。三異なる符号化の資源(キュービット数、cxゲート数)の分析を行う。四定式化及びシミュレーションを重み付きグラフの場合まで拡張する。 k が 2 のパワーでない場合、k が 2 のパワーでない場合、我々のアルゴリズムは NISQ デバイスに量子的優位性を示す候補となる。

関連論文リスト

Encodings of the weighted MAX k-CUT on qubit systems [0.0]
本稿では,重み付きMAX k-CUT問題の量子ビットシステム上での符号化法について検討する。各種符号化方式について検討し,これらの手法の有効性について検討する。重み付きおよび非重み付きグラフインスタンスの数値シミュレーションは、これらの符号化方式の有効性を実証する。
論文参考訳（メタデータ） (2024-11-13T13:21:35Z)
An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-11T04:40:05Z)
Two quantum algorithms for solving the one-dimensional advection-diffusion equation [0.0]
2つの量子アルゴリズムが周期的境界条件を持つ線形一次元対流拡散方程式の数値解に対して提示される。量子ビット数の増加に伴う精度と性能を、ポイントごとに比較する。
論文参考訳（メタデータ） (2023-12-30T21:23:15Z)
Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
猫の量子ビットを用いたQAOAを用いてMaxCut問題の解法を数値シミュレーションする。猫の量子ビットを用いたQAOAの実行は、2レベルシステムに符号化された量子ビットに対して、MaxCutのランダムなインスタンスに対する近似比を増大させることを示す。
論文参考訳（メタデータ） (2023-05-09T15:44:52Z)
End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文参考訳（メタデータ） (2022-11-22T18:54:48Z)
An entanglement perspective on the quantum approximate optimization algorithm [0.0]
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
論文参考訳（メタデータ） (2022-06-14T17:37:44Z)
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)
Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文参考訳（メタデータ） (2021-12-21T12:41:31Z)
Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。量子技術の最近の進歩は、ノイズの多い中間スケール量子(NISQ)デバイスへの道を開く。
論文参考訳（メタデータ） (2021-07-11T10:56:24Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文参考訳（メタデータ） (2021-07-08T17:59:55Z)
Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文参考訳（メタデータ） (2021-06-24T20:16:02Z)

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

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