論文の概要: A Variational Qubit-Efficient MaxCut Heuristic Algorithm
- arxiv url: http://arxiv.org/abs/2308.10383v1
- Date: Sun, 20 Aug 2023 23:06:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-22 15:51:29.454766
- 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)アルゴリズムは、MaxCut問題の解を見つけるために特別に設計されている。
最大2048ノード(11量子ビット)の正則グラフ上でのノイズレスQEMCシミュレーションを提案する。
最大32ノード(5threshold qubits)のグラフの最先端の結果を達成した実際の量子デバイス上でのQEMCの実行
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The resolution of hard combinatorial problems is essential in a wide range of
industrial applications and theoretical fields. Quantum computers offer a
unique platform for addressing such problems, with the Quantum Approximate
Optimization Algorithm (QAOA) being a state-of-the-art example. However, due to
high levels of noise and limited numbers of qubits in current quantum devices,
only very small problem instances can be addressed on actual quantum hardware.
Here we present a new variational Qubit-Efficient MaxCut (QEMC) algorithm that
is specifically designed to find heuristic solutions for the MaxCut problem, a
well-studied NP-hard combinatorial problem. The QEMC method introduces a unique
information encoding scheme that requires $\log{N}$ qubits to address graphs
with $N$ nodes, an exponential reduction in comparison to QAOA. Each node of
the graph is assigned to a unique computational quantum state, and its logical
state is depicted by the measurement probability of the corresponding state,
using a probability-threshold encoding scheme. Consequently, each partition of
the graph is associated with a volume of states, rather than with just a single
state. We present noiseless QEMC simulations on regular graphs with up to 2048
nodes (11 qubits). These simulations achieved cut solutions that outperform
those obtained by the best-known classical approximation algorithm of Goemans
and Williamson (GW), by several percent. Moreover, executing the QEMC algorithm
on actual IBM quantum devices achieved leading-edge results for graphs with up
to 32 nodes (5 qubits), providing a challenging benchmark for the QAOA
algorithm. We analyze the computational complexity of the QEMC algorithm and
show that it can be simulated efficiently using classical methods, thereby
constituting a new quantum-inspired classical MaxCut heuristic.
- Abstract（参考訳）: ハードコンビネーション問題の解決は、幅広い産業応用や理論分野において不可欠である。
量子コンピュータはそのような問題に対処するためのユニークなプラットフォームを提供しており、Quantum Approximate Optimization Algorithm (QAOA) は最先端の例である。
しかし、現在の量子デバイスではノイズのレベルが高く、量子ビット数が限られているため、実際の量子ハードウェア上では、非常に小さな問題しか対処できない。
ここでは、NP-ハード組合せ問題であるMaxCut問題に対するヒューリスティックな解を見つけるために特別に設計された変分Qubit-Efficient MaxCut (QEMC)アルゴリズムを提案する。
QEMC法は、QAOAと比較して指数関数的な削減である$N$ノードを持つグラフを扱うために$\log{N}$ qubitsを必要とするユニークな情報符号化方式を導入する。
グラフの各ノードは一意な計算量子状態に割り当てられ、その論理状態は確率安定符号化方式を用いて対応する状態の測定確率によって描写される。
その結果、グラフの各分割は単一の状態ではなく、状態の体積に関連付けられている。
我々は,最大2048ノード (11 qubits) の正規グラフ上で雑音のないqemcシミュレーションを行う。
これらのシミュレーションは、ゴマンズとウィリアムソン(gw)の最もよく知られた古典近似アルゴリズムによって得られた解を数パーセント上回るカット解を実現した。
さらに、実際のIBM量子デバイス上でのQEMCアルゴリズムの実行は、32ノード (5 qubits) のグラフの最先端結果を実現し、QAOAアルゴリズムの挑戦的なベンチマークを提供する。
我々はQEMCアルゴリズムの計算複雑性を解析し、古典的手法で効率的にシミュレートできることを示し、量子に着想を得た古典的なMaxCutヒューリスティックを構成する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。