論文の概要: An entanglement perspective on the quantum approximate optimization
algorithm
- arxiv url: http://arxiv.org/abs/2206.07024v2
- Date: Mon, 22 Aug 2022 16:14:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 09:45:48.782051
- Title: An entanglement perspective on the quantum approximate optimization
algorithm
- Title(参考訳): 量子近似最適化アルゴリズムにおける絡み合いの視点
- Authors: Maxime Dupont, Nicolas Didier, Mark J. Hodson, Joel E. Moore, Matthew
J. Reagor
- Abstract要約: ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討する。
また、ランダム行列理論に関連する絡み合いスペクトルについても検討する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many quantum algorithms seek to output a specific bitstring solving the
problem of interest--or a few if the solution is degenerate. It is the case for
the quantum approximate optimization algorithm (QAOA) in the limit of large
circuit depth, which aims to solve quadratic unconstrained binary optimization
problems. Hence, the expected final state for these algorithms is either a
product state or a low-entangled superposition involving a few bitstrings. What
happens in between the initial $N$-qubit product state $\vert 0\rangle^{\otimes
N}$ and the final one regarding entanglement? Here, we consider the QAOA
algorithm for solving the paradigmatic Max-Cut problem on different types of
graphs. We study the entanglement growth and spread resulting from randomized
and optimized QAOA circuits and find that there is a volume-law entanglement
barrier between the initial and final states. We also investigate the
entanglement spectrum in connection with random matrix theory. In addition, we
compare the entanglement production with a quantum annealing protocol aiming to
solve the same Max-Cut problems. Finally, we discuss the implications of our
results for the simulation of QAOA circuits with tensor network-based methods
relying on low-entanglement for efficiency, such as matrix product states.
- Abstract(参考訳): 多くの量子アルゴリズムは、解が縮退している場合、興味のある問題を解く特定のビット文字列を出力しようとする。
量子近似最適化アルゴリズム(QAOA)は,2次非制約二元最適化問題を解くことを目的とした,大きな回路深さの限界におけるアルゴリズムである。
したがって、これらのアルゴリズムの最終状態は積の状態か、数ビット文字列を含む低エンタングル重ね合わせである。
最初の$N$-qubit の積状態 $\vert 0\rangle^{\otimes N}$ と、絡み合いに関する最後のものの間に何が起こるのか?
本稿では,様々なグラフ上のパラダイム的最大カット問題を解くためのqaoaアルゴリズムについて考察する。
ランダム化および最適化されたQAOA回路による絡み合いの増大と広がりについて検討し、初期状態と最終状態の間には体積法的な絡み合い障壁があることを見出した。
また,乱数行列理論と絡み合いスペクトルについても検討した。
さらに, エンタングルメント生成と量子アニーリングプロトコルを比較して, 同じMax-Cut問題の解法を提案する。
最後に,行列積状態のような低エンタングルメントに依存するテンソルネットワークに基づく手法を用いて,qaoa回路のシミュレーションにおける結果の意義について考察する。
関連論文リスト
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
我々は、QUBO問題として表されるグラフ上の最大傾きを見つける量子D波アンナーの能力を解析する。
本稿では, 相補的な最大独立集合問題に対する分解アルゴリズムと, ノード数, 傾き数, 密度, 接続率, 解サイズの他のノード数に対する比を制御するグラフ生成アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-06-11T04:40:05Z) - Depth scaling of unstructured search via quantum approximate optimization [0.0]
変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。
そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。
我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
論文 参考訳(メタデータ) (2024-03-22T18:00:03Z) - A Universal Quantum Algorithm for Weighted Maximum Cut and Ising
Problems [0.0]
本稿では,二項問題の近似解を計算するためのハイブリッド量子古典アルゴリズムを提案する。
我々は、重み付き最大カットまたはイジング・ハミルトン演算子をブロック符号化するユニタリおよびエルミート演算子を実装するために浅深さ量子回路を用いる。
この作用素の変動量子状態への期待を測定すると、量子系の変動エネルギーが得られる。
論文 参考訳(メタデータ) (2023-06-10T23:28:13Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
問題入力から問題出力までの完全な量子回路レベルのアルゴリズム記述を提供する。
アルゴリズムの実行に必要な論理量子ビットの数と非クリフォードTゲートの量/深さを報告する。
論文 参考訳(メタデータ) (2022-11-22T18:54:48Z) - The Quantum Approximate Optimization Algorithm performance with low
entanglement and high circuit depth [0.0]
変分量子アルゴリズムは、現在の雑音量子コンピュータを使用する最も広範な方法の1つである。
最適化問題の解法における絡み合いの役割について検討する。
ここでは, 絡み合いが MaxCut と Exact Cover 3 問題において軽微な役割を担っていると結論づける。
論文 参考訳(メタデータ) (2022-07-07T16:21:36Z) - 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) - How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
ADAPT-QAOA施行時に発生する絡みについて検討した。
この柔軟性を漸進的に制限することにより、初期におけるより多くの絡み合いエントロピーが、後段におけるより速い収束と一致していることが分かる。
論文 参考訳(メタデータ) (2022-05-24T18:00:02Z) - 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) - Efficient Classical Computation of Quantum Mean Values for Shallow QAOA
Circuits [15.279642278652654]
浅いQAOA回路の量子ビット数と線形にスケールするグラフ分解に基づく古典的アルゴリズムを提案する。
我々の結果は、QAOAによる量子アドバンテージの探索だけでなく、NISQプロセッサのベンチマークにも有用である。
論文 参考訳(メタデータ) (2021-12-21T12:41:31Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
有名な最小二乗モンテカルロ (LSM) アルゴリズムは、線形最小二乗回帰とモンテカルロシミュレーションを組み合わせることで、最適停止理論の問題を解決する。
プロセスへの量子アクセス、最適な停止時間を計算するための量子回路、モンテカルロの量子技術に基づく量子LSMを提案する。
論文 参考訳(メタデータ) (2021-11-30T12:21:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。