論文の概要: A Variational Qubit-Efficient MaxCut Heuristic Algorithm
- arxiv url: http://arxiv.org/abs/2308.10383v2
- Date: Thu, 23 Nov 2023 18:49:54 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-28 03:42:49.565460
- Title: A Variational Qubit-Efficient MaxCut Heuristic Algorithm
- Title（参考訳）: 変分量子ビット効率maxcutヒューリスティックアルゴリズム
- Authors: Yovav Tene-Cohen, Tomer Kelman, Ohad Lev, and Adi Makmal
- Abstract要約: グラフサイズに対して対数的な量子ビット数を必要とする新しい変分Qubit-Efficient MaxCut (QEMC)アルゴリズムを提案する。
実超伝導ハードウェア上では最大32ノード(5キュービット)のグラフインスタンスに対して,ノイズレスシミュレーションを用いて最大2048ノード(11キュービット)のグラフに対して,最先端の性能を示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: MaxCut is a key NP-Hard combinatorial optimization graph problem with
extensive theoretical and industrial applications, including the Ising model
and chip design. While quantum computing offers new solutions for such
combinatorial challenges which are potentially better than classical schemes,
with the Quantum Approximate Optimization Algorithm (QAOA) being a
state-of-the-art example, its performance is currently hindered by hardware
noise and limited qubit number. Here, we present a new variational
Qubit-Efficient MaxCut (QEMC) algorithm that requires a logarithmic number of
qubits with respect to the graph size, an exponential reduction compared to
QAOA. We demonstrate cutting-edge performance for graph instances consisting of
up to 32 nodes (5 qubits) on real superconducting hardware, and for graphs with
up to 2048 nodes (11 qubits) using noiseless simulations, outperforming the
established classical algorithm of Goemans and Williamson (GW). The QEMC
algorithm's innovative encoding scheme empowers it with great noise-resiliency
on the one hand, but also enables its efficient classical simulation on the
other, thus obscuring a distinct quantum advantage. Nevertheless, even in the
absence of quantum advantage, the QEMC algorithm serves as a potential
quantum-inspired algorithm, provides a challenging benchmark for QAOA, and
presents a novel encoding paradigm with potential applications extending to
other quantum and classical algorithms.
- Abstract（参考訳）: MaxCutは、Isingモデルやチップ設計を含む広範な理論および工業的応用を持つNP-Hard組合せ最適化グラフ問題である。
量子コンピューティングは、古典的なスキームよりも優れた組合せ問題に対する新しい解決策を提供する一方で、Quantum Approximate Optimization Algorithm (QAOA)は最先端の例であるが、その性能は現在、ハードウェアノイズと限定量子ビット数によって妨げられている。
本稿では,QAOAと比較して指数的に削減されたグラフサイズに対して,量子ビットの対数を必要とする変分Qubit-Efficient MaxCut (QEMC)アルゴリズムを提案する。
実超伝導ハードウェア上で最大32ノード (5 qubits) のグラフインスタンスに対して,ノイズレスシミュレーションを用いた最大2048ノード(11 qubits) のグラフに対して,Guemans and Williamson (GW) の確立した古典的アルゴリズムよりも優れた最先端性能を示す。
qemcアルゴリズムの革新的なエンコーディング方式は、大きなノイズ耐性を持つ一方で、その効率の良い古典的シミュレーションを可能にするため、量子的な利点を損なう。
にもかかわらず、量子優位性がなくても、QEMCアルゴリズムは量子に着想を得た潜在的なアルゴリズムとして機能し、QAOAの挑戦的なベンチマークを提供し、他の量子および古典的アルゴリズムに拡張する可能性のある新しいエンコーディングパラダイムを提供する。
関連論文リスト
- Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
本研究は、4つの異なる最適化問題にまたがっていくつかの非フォールト耐性量子コンピューティングアルゴリズムを体系的にベンチマークする。
我々のベンチマークには、変分量子固有解法など、ノイズの多い中間スケール量子(NISQ)アルゴリズムが含まれている。
以上の結果から,FTQC以外のアルゴリズムは全ての問題に対して最適に動作しないことが明らかとなり,アルゴリズム戦略の調整の必要性が浮き彫りになった。
論文 参考訳（メタデータ） (2024-10-30T08:41:29Z) - Graph Learning for Parameter Prediction of Quantum Approximate
Optimization Algorithm [14.554010382366302]
量子近似最適化(Quantum Approximate Optimization, QAOA)は、Max-Cutの問題を効率的に解く可能性において際立っている。
我々は,GNNをウォームスタート手法として,グラフニューラルネットワーク(GNN)を用いてQAOAを最適化する。
以上の結果から,量子コンピューティングにおけるGNNのQAOA性能向上の可能性が示唆され,量子古典的ハイブリッドコンピューティングへの新たな道が開かれた。
論文 参考訳（メタデータ） (2024-03-05T20:23:25Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - NISQ-compatible approximate quantum algorithm for unconstrained and
constrained discrete optimization [0.0]
本稿では,振幅符号化を用いたハードウェア効率の高い回路に対する近似勾配型量子アルゴリズムを提案する。
目的関数にペナルティ項を加えることなく, 単純な線形制約を回路に直接組み込むことができることを示す。
論文 参考訳（メタデータ） (2023-05-23T16:17:57Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - A quantum advantage over classical for local max cut [48.02822142773719]
量子最適化近似アルゴリズム(QAOA)は、次数3グラフ上の古典的手法に匹敵する計算上の優位性を持つ。
結果として、最先端の量子ハードウェアに関係している小規模量子計算でさえ、比較可能な単純な古典よりも大きな優位性を持つ可能性が示唆された。
論文 参考訳（メタデータ） (2023-04-17T16:42:05Z) - Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる
本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。
その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
論文 参考訳（メタデータ） (2022-09-01T17:08:41Z) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳（メタデータ） (2021-12-21T12:41:31Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳（メタデータ） (2021-06-24T20:16:02Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Classical variational simulation of the Quantum Approximate Optimization
Algorithm [0.0]
パラメタライズドゲートからなる層状量子回路をシミュレートする手法を提案する。
マルチキュービット波動関数のニューラルネットワークパラメトリゼーションを用いる。
シミュレーションした最大の回路では、4QAOA層で54量子ビットに達する。
論文 参考訳（メタデータ） (2020-09-03T15:55:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。