Fugu-MT 論文翻訳(概要): QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem

論文の概要: QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem

arxiv url: http://arxiv.org/abs/2307.15260v1
Date: Fri, 28 Jul 2023 02:06:42 GMT
ステータス: 処理完了
システム内更新日: 2023-07-31 14:05:11.068587
Title: QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem
Title（参考訳）: 量子ビットが少ないQAOA:大規模Max-Cut問題を解決する結合フレームワーク
Authors: Yiren Lu, Guojing Tian, Xiaoming Sun
Abstract要約: より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
参考スコア（独自算出の注目度）: 6.783232060611114
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various $24$-vertex Erd\H{o}s-R\'enyi graphs. Our framework only consumes $18$ qubits and achieves $0.9950$ approximation ratio on average, which outperforms the previous methods showing $0.9778$ (quantum algorithm using the same number of qubits) and $0.9643$ (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices.
Abstract（参考訳）: 最大カット(Max-Cut)問題は実生活における様々な応用のために最も重要な組合せ最適化問題の1つであり、最近では量子近似最適化アルゴリズム(QAOA)が広く用いられている。しかし、問題のサイズが大きくなるにつれて、必要な量子ビットの数が増加する。そこで本研究では,QAOA回路を設計し,より大規模なMax-Cut問題を解くための結合フレームワークを提案する。このフレームワークは、Max-Cutの変種を近似的に解く古典的アルゴリズムに依存し、古典的アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。さらに、フレームワークに適合するヒューリスティックなアプローチを設計し、十分な数値実験を行い、24$-vertex erd\h{o}s-r\'enyiグラフの最大カットを解く。我々のフレームワークは18ドルキュービットしか消費せず、平均で0.950ドル近似比を達成しており、従来の手法では0.9778ドル(同じ数のキュービットを用いた量子アルゴリズム)と0.9643ドル(古典的なアルゴリズム)を上回ります。実験結果から, 量子古典結合フレームワークは, 量子ビットコストを低減しつつ, 良好な近似比を与え, nisqデバイスの計算能力の向上に寄与することが示唆された。

関連論文リスト

A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
提案手法では,Groverをベースとした進化的枠組みと分割・分散原理を用いた量子遺伝的アルゴリズム(QGA)を提案する。完全グラフ上では、提案手法は真に最適なMaxCut値を一貫して達成し、セミデフィニティプログラミング(SDP)アプローチより優れている。 ErdHos-R'enyiランダムグラフでは、QGAは競合性能を示し、SDP結果の92-96%で中央値の解が得られる。
論文参考訳（メタデータ） (2025-01-02T05:06:16Z)
A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
既存の量子処理ユニット(QPU)がマルチレベル戦略においてサブソルバとしてどのように機能するかを実験的に検証する。完全連結な 82$-qubit Sherrington-Kirkpatrick グラフに対して 10$ の近似解を求める。量子最適化の結果は古典学と比較して解の質に関して競争力がある。
論文参考訳（メタデータ） (2024-08-14T20:06:32Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文参考訳（メタデータ） (2024-01-17T18:59:38Z)
Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
論文参考訳（メタデータ） (2023-07-11T22:02:01Z)
Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文参考訳（メタデータ） (2022-06-30T03:15:23Z)
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)
Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文参考訳（メタデータ） (2022-03-01T19:47:16Z)
A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization [0.0]
評価フィードバックコヒーレントIsing Machine(MFB-CIM)、離散断熱量子計算(DAQC)、量子最小探索(DH-QMF)のためのD"urr-Hoyerアルゴリズムの3つの量子アルゴリズムの性能スケーリングについて検討する。各アルゴリズムに対して、ランダムに生成されたエッジ重みを持つ重み付きグラフインスタンスを1ドルで1ドルから1ドルで、ランダムに生成されたSherrington-Kirkpatrick(SK)スピングラスインスタンスをランダムに生成する。
論文参考訳（メタデータ） (2021-05-07T22:35:02Z)
Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
グラフ最大カット問題(MaxCut)の課題に対処するため,Divide-and-Conquer QAOA(DC-QAOA)を提案する。 DC-QAOAは97.14%の近似比(20.32%)を達成するまた、従来のQAOAの時間的複雑さを指数関数から二次的に減少させる。
論文参考訳（メタデータ） (2021-02-26T03:10:30Z)

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

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