論文の概要: Threshold-Based Quantum Optimization
- arxiv url: http://arxiv.org/abs/2106.13860v2
- Date: Mon, 23 Aug 2021 18:44:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-25 13:39:16.868962
- Title: Threshold-Based Quantum Optimization
- Title（参考訳）: 閾値に基づく量子最適化
- Authors: John Golden, Andreas B\"artschi, Daniel O'Malley, Stephan Eidenbenz
- Abstract要約: Th-QAOA(Threshold QAOA)は、量子交互演算子Ansatz(QAOA)の変種である。
GM-Th-QAOAをGroverの量子探索アルゴリズムの一般化と見なすことができる。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the
Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase
separator operator, which encodes the objective function, with a threshold
function that returns a value $1$ for solutions with an objective value above
the threshold and a $0$ otherwise. We vary the threshold value to arrive at a
quantum optimization algorithm. We focus on a combination with the Grover Mixer
operator; the resulting GM-Th-QAOA can be viewed as a generalization of
Grover's quantum search algorithm and its minimum/maximum finding cousin to
approximate optimization. Our main findings include: (i) we provide intuitive
arguments and show empirically that the optimum parameter values of GM-Th-QAOA
(angles and threshold value) can be found with $O(\log(p) \times \log M)$
iterations of the classical outer loop, where $p$ is the number of QAOA rounds
and $M$ is an upper bound on the solution value (often the number of vertices
or edges in an input graph), thus eliminating the notorious outer-loop
parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be
simulated classically with little effort up to 100 qubits through a set of
tricks that cut down memory requirements; (iii) somewhat surprisingly,
GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios
achieved. This third result holds across a range of optimization problems
(MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various
experimental design parameters, such as different input edge densities and
constraint sizes.
- Abstract（参考訳）: 本稿では,Threshold QAOA (Threshold QAOA) と呼ばれる量子交互演算子 Ansatz (QAOA) の変種について検討し,対象関数を符号化した標準位相分離演算子をしきい値関数で置き換える。
量子最適化アルゴリズムに到達するためにしきい値を変更する。
得られたGM-Th-QAOAは、Groverの量子探索アルゴリズムの一般化と、近似最適化の最小値と最大値を求める従兄弟を求めることができる。
私たちの主な発見は
2 GM-Th-QAOA(角としきい値)の最適パラメータ値が古典的外ループの反復($O(\log(p) \times \log M)$$$$$$p$はQAOAラウンドの数であり、$M$はソリューション値上の上限(しばしば入力グラフの頂点数やエッジ数)であり、他のQAOAアルゴリズムの悪名高い外ループパラメータ発見問題を排除することを実証的に示す。
(ii)GM-Th-QAOAは、メモリ要求を削減した一連のトリックによって、100キュービットまでの労力で古典的にシミュレートできる。
3) GM-Th-QAOAは近似比で非閾値のGM-QAOAを上回っている。
この第三の結果は、最適化問題(MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection)と、異なる入力エッジ密度や制約サイズなど、様々な実験的設計パラメータにまたがる。
関連論文リスト
- Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
QAOA(Quantum Alternating Operator Ansatz)は最適化問題を解くための量子アルゴリズムの一分野である。
特定の変種であるGrover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA)は、等価な目的値を共有する状態間で均一な振幅を保証する。
GM-QAOAはサンプリング確率を2次的に向上させ,一貫した性能を維持するために,問題サイズと指数関数的にスケールする回路深度を必要とすることを示す。
論文 参考訳（メタデータ） (2024-05-06T05:47:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くために用いられるハイブリッド量子古典アルゴリズムである。
QAOAはNISQデバイスに実装できるが、物理的制限は回路深さを制限し、性能を低下させる。
この研究は、より古典的なパラメータをアンサッツに割り当て、低深さでの性能を改善するeXpressive QAOA (XQAOA)を導入している。
論文 参考訳（メタデータ） (2023-02-09T07:47:06Z) - A Parameter Setting Heuristic for the Quantum Alternating Operator
Ansatz [0.0]
本稿では,問題の大きさに応じて異なるコスト値の数が増加する場合に適したパラメータ設定戦略を提案する。
我々は、完全均一性が正確に保持され、状態と期待値の両方を記述する情報が得られるQAOAの古典的同次プロキシを定義する。
最大3ドルのQAOAレベルでは、これまでのグローバルに最適化されたアプローチによって返される近似比にマッチするパラメータを容易に見つけることができます。
論文 参考訳（メタデータ） (2022-11-17T00:18:06Z) - 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) - Predicting parameters for the Quantum Approximate Optimization Algorithm
for MAX-CUT from the infinite-size limit [0.05076419064097732]
推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。
この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
論文 参考訳（メタデータ） (2021-10-20T17:58:53Z) - Parameters Fixing Strategy for Quantum Approximate Optimization
Algorithm [0.0]
そこで本稿では,QAOAをパラメータとして初期化することで,回路深度が大きければ平均で高い近似比を与える手法を提案する。
我々は3つの正則グラフやエルド・オス=ルネニグラフのようなグラフのある種のクラスにおけるマックスカット問題に対する我々の戦略をテストする。
論文 参考訳（メタデータ） (2021-08-11T15:44:16Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。
任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
論文 参考訳（メタデータ） (2020-11-26T18:22:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。