論文の概要: Symmetries and Dimension Reduction in Quantum Approximate Optimization
Algorithm
- arxiv url: http://arxiv.org/abs/2309.13787v2
- Date: Mon, 22 Jan 2024 00:55:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-23 20:37:44.520906
- Title: Symmetries and Dimension Reduction in Quantum Approximate Optimization
Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムの対称性と次元縮小
- Authors: Boris Tsvelikhovskiy, Ilya Safro, Yuri Alexeev
- Abstract要約: 我々は、$n-要素$d$-ary文字列の集合上で定義される最適化問題の一般化された定式化に焦点を当てる。
我々の主な貢献は、当初提案されたQAOAの次元を含む。
アルゴリズムをより小さな次元の空間に制限することは、回路の量子シミュレーションと古典シミュレーションの両方を著しく加速させる可能性がある。
- 参考スコア（独自算出の注目度）: 1.3469999282609788
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper, the Quantum Approximate Optimization Algorithm (QAOA) is
analyzed by leveraging symmetries inherent in problem Hamiltonians. We focus on
the generalized formulation of optimization problems defined on the sets of
$n$-element $d$-ary strings. Our main contribution encompasses dimension
reductions for the originally proposed QAOA. These reductions retain the same
problem Hamiltonian as the original QAOA but differ in terms of their mixer
Hamiltonian, and initial state. The vast QAOA space has a daunting dimension of
exponential scaling in $n$, where certain reduced QAOA spaces exhibit
dimensions governed by polynomial functions. This phenomenon is illustrated in
this paper, by providing partitions corresponding to polynomial dimensions of
the corresponding subspaces. As a result, each reduced QAOA partition
encapsulates unique classical solutions absent in others, allowing us to
establish a lower bound on the number of solutions to the initial optimization
problem. Our novel approach opens promising practical advantages in
accelerating the algorithm. Restricting the algorithm to Hilbert spaces of
smaller dimension may lead to significant acceleration of both quantum and
classical simulation of circuits and serve as a tool to cope with barren
plateaus problem.
- Abstract（参考訳）: 本稿では,問題ハミルトニアンに内在する対称性を利用して量子近似最適化アルゴリズム(qaoa)の解析を行う。
我々は、$n$-element $d$-ary stringsの集合上で定義される最適化問題の一般化された定式化に焦点を当てる。
本研究の主な貢献は,当初提案されたQAOAの次元削減である。
これらの還元は元々の QAOA と同じ問題を保っているが、ミキサーの Hamiltonian と初期状態の点で異なる。
広大な QAOA 空間は $n$ の指数スケーリングの余計な次元を持ち、ある減少 QAOA 空間は多項式函数によって支配される次元を示す。
この現象は、対応する部分空間の多項式次元に対応する分割を提供することによって示される。
その結果、削減されたQAOAパーティションは、他のものにはないユニークな古典解をカプセル化し、初期最適化問題の解数に対する低い境界を確立することができる。
提案手法はアルゴリズムの高速化に有望な実用的利点を開く。
アルゴリズムをより小さい次元のヒルベルト空間に制限すると、回路の量子シミュレーションと古典シミュレーションの両方が大幅に加速し、バレン高原問題に対処するツールとなる。
関連論文リスト
- Ising Hamiltonians for Constrained Combinatorial Optimization Problems
and the Metropolis-Hastings Warm-Starting Algorithm [0.0]
量子近似最適化アルゴリズム(QAOA)は最適化問題に対する有望な変分量子アルゴリズムである。
QAOAのMetropolis-Hasstingウォームスタートアルゴリズムは、大域的最適解に確実に収束することができる。
論文 参考訳（メタデータ） (2023-07-18T05:28:45Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
制約付き最適化問題を解くためのフェルミオン量子近似最適化アルゴリズム(FQAOA)を提案する。
FQAOAは、フェルミオン粒子数保存を用いて、QAOAを通して本質的にそれらを強制する制約問題に対処する。
制約付きハミルトニアン問題に対して、運転者ハミルトニアンを設計するための体系的なガイドラインを提供する。
論文 参考訳（メタデータ） (2023-01-25T18:36:58Z) - Expanding the reach of quantum optimization with fermionic embeddings [2.378735224874938]
本研究では、このクラス LNCG 問題の自然な埋め込みをフェルミオンハミルトニアンに確立する。
量子表現は、線形数の量子ビットしか必要としないことを示す。
この丸みを帯びた量子緩和が高品質な近似を生み出す証拠を提供する。
論文 参考訳（メタデータ） (2023-01-04T19:00:01Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳（メタデータ） (2022-11-22T18:54:48Z) - Problem-Size Independent Angles for a Grover-Driven Quantum Approximate
Optimization Algorithm [0.0]
本稿では,Grover-driven,QAOA-prepared状態下でのハミルトニアンの期待値の計算をシステムサイズとは無関係に行うことができることを示す。
このような計算は、大きな問題の大きさの限界において、QAOAにおける角度のパフォーマンスと予測可能性に関する洞察を与えるのに役立つ。
論文 参考訳（メタデータ） (2022-08-22T17:18:25Z) - Characterization of variational quantum algorithms using free fermions [0.0]
我々はこれらの対称性と対象状態の局所性の間の相互作用を数値的に研究する。
解に収束するイテレーションの数は、システムサイズと線形にスケールする。
論文 参考訳（メタデータ） (2022-06-13T18:11:16Z) - General Hamiltonian Representation of ML Detection Relying on the
Quantum Approximate Optimization Algorithm [74.6114458993128]
最適化問題を解くために考案された量子近似最適化アルゴリズム(QAOA)は、既存のノイズのある中間スケール量子(NISQ)デバイス上で実行することができる。
我々は、QAOAを適切に適応させることにより、一般星座の最大可能性(ML)検出問題を解く。
特に、M-ary Gray-mapped Quarature amplitude modulation (MQAM) 星座では、同相成分をコードする特定の量子ビットと二次成分をコードする量子ビットが、興味のある量子系において独立であることを示す。
論文 参考訳（メタデータ） (2022-04-11T14:11:24Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z) - Conditional gradient methods for stochastically constrained convex
minimization [54.53786593679331]
構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。
私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。
提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
論文 参考訳（メタデータ） (2020-07-07T21:26:35Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。