Fugu-MT 論文翻訳(概要): Extending relax-and-round combinatorial optimization solvers with quantum correlations

論文の概要: Extending relax-and-round combinatorial optimization solvers with quantum correlations

arxiv url: http://arxiv.org/abs/2307.05821v2
Date: Wed, 24 Jan 2024 17:20:57 GMT
ステータス: 処理完了
システム内更新日: 2024-01-25 17:41:30.399018
Title: Extending relax-and-round combinatorial optimization solvers with quantum correlations
Title（参考訳）: 量子相関を用いた緩く丸い組合せ最適化解法の拡張
Authors: Maxime Dupont, Bhuvanesh Sundar
Abstract要約: 量子近似最適化アルゴリズム (QAOA) を$pgeq 1$ の層に埋め込む。 Sherrington-Kirk メガネを含む多くの問題に対して、$p=1$とすると、その古典的な問題と同じくらい正確であることを示す。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\geq 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.
Abstract（参考訳）: 量子近似最適化アルゴリズム (QAOA) を$p\geq 1$ の層に埋め込む。シェリントン・カークパトリックスピングラス(英語版)を含む多くの問題に対して、$p=1$は古典的手法と同程度正確であることを示し、QAOAの絶対的な性能保証を維持している。異なる丸めスキームを用いて、あるグラフ上の最大カット問題に対するゴーマンス・ウィリアムソンアルゴリズムの性能を共有することを証明した。古典的アルゴリズムに匹敵するパフォーマンスで、量子リラクゼーションとラウンドを網羅するフレームワークの道を開いた。

関連論文リスト

Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
本稿では,量子オンライン準ニュートン法を提案する。提案手法は, 量子推定不正確な勾配によりヘシアンを近似する。このような後悔は、最適古典アルゴリズムを$T2/3$の係数で改善する。
論文参考訳（メタデータ） (2024-10-25T16:58:44Z)
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)
The role of quantum and classical correlations in shrinking algorithms for optimization [0.0]
最適化問題(COP)における縮小アルゴリズムの性能について検討する。量子近似最適化アルゴリズム (QAOA) と古典線形計画法 (LP) と半定値計画法 (SDP) の相関によるアルゴリズムの性能の比較を行った。その結果、LPは低密度のインスタンスに対して他の全てのアプローチよりも優れており、SDPは高密度の問題に対して優れていた。
論文参考訳（メタデータ） (2024-04-26T08:29:04Z)
Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文参考訳（メタデータ） (2023-12-13T11:08:25Z)
QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
より大規模なMax-Cut問題を解決するためにQAOA回路を設計するためのフレームワークを提案する。古典アルゴリズムとQAOAの近似比を仮定して理論的に近似を保証する。われわれのフレームワークは平均で18ドルと0.950ドルしか消費しない。
論文参考訳（メタデータ） (2023-07-28T02:06:42Z)
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)
Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文参考訳（メタデータ） (2022-03-01T19:47:16Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
Warm-starting quantum optimization [6.832341432995627]
最適化問題の緩和解に対応する初期状態を用いて量子最適化を温める方法について論じる。これにより、量子アルゴリズムは古典的なアルゴリズムの性能保証を継承することができる。同じ考えを他のランダム化ラウンドスキームや最適化問題に適用するのは簡単である。
論文参考訳（メタデータ） (2020-09-21T18:00:09Z)
Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文参考訳（メタデータ） (2020-06-11T17:43:19Z)
Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
論文参考訳（メタデータ） (2020-03-11T13:52:41Z)

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