論文の概要: Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem
- arxiv url: http://arxiv.org/abs/2504.12896v1
- Date: Thu, 17 Apr 2025 12:38:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-18 14:36:18.724987
- Title: Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem
- Title（参考訳）: 最大カット問題に対する光円錐変分量子アルゴリズムの性能保証
- Authors: Xiaoyang Wang, Yuexin Su, Tongyang Li,
- Abstract要約: 変分量子アルゴリズム(VQA)は、古典的計算よりも短期的な量子コンピューティングの利点を実証することを約束している。
本稿では,標準VQAの最適ゲート列を選択することで,光円錐VQAを提案する。
1ラウンドの光円錐VQAがMaxCut問題に対して0.7926の近似比を達成することを証明した。
- 参考スコア（独自算出の注目度）: 12.148326652334598
- License:
- Abstract: Variational quantum algorithms (VQAs) are promising to demonstrate the advantage of near-term quantum computing over classical computing in practical applications, such as the maximum cut (MaxCut) problem. However, current VQAs such as the quantum approximate optimization algorithm (QAOA) have lower performance guarantees compared to the best-known classical algorithm, and suffer from hard optimization processes due to the barren plateau problem. We propose a light-cone VQA by choosing an optimal gate sequence of the standard VQAs, which enables a significant improvement in solution accuracy while avoiding the barren plateau problem. Specifically, we prove that the light-cone VQA with one round achieves an approximation ratio of 0.7926 for the MaxCut problem in the worst case of $3$-regular graphs, which is higher than that of the 3-round QAOA, and can be further improved to 0.8333 by an angle-relaxation procedure. Finally, these performance guarantees are verified by numerical simulations and hardware demonstrations on IBM quantum devices. In a 72-qubit demonstration, the single-round light-cone VQA achieves the exact MaxCut solution whereas the $p$-round QAOA with $p=1,2,3$ only obtains approximate solutions. Furthermore, the single-round light-cone VQA derives solutions surpassing the hardness threshold in a 148-qubit demonstration while QAOA with $p=1,2,3$ does not. Our work highlights a promising route towards solving practical and classically hard problems on near-term quantum devices.
- Abstract（参考訳）: 変分量子アルゴリズム(VQA)は、最大カット(MaxCut)問題など、古典的な計算よりも短期的な量子コンピューティングの利点を実証することを約束している。
しかし、量子近似最適化アルゴリズム(QAOA)のような現在のVQAは、よく知られた古典的アルゴリズムに比べて性能保証が低く、不規則なプラトー問題によるハードな最適化プロセスに悩まされている。
本稿では,標準VQAの最適ゲート列を選択することで,バレンプラトー問題を回避しつつ,解の精度を大幅に向上できる光円錐VQAを提案する。
具体的には、1ラウンドの光円VQAが3ラウンドのQAOAよりも高い3ドル正則グラフの最悪の場合、MaxCut問題に対して0.7926の近似比を達成することを証明し、角緩和法によりさらに0.8333に改善することができる。
最後に、これらの性能保証はIBM量子デバイス上での数値シミュレーションとハードウェア実証によって検証される。
72量子ビットのデモでは、シングルラウンドの光円VQAは正確なMaxCut解を達成するが、$p=1,2,3$のQAOAは近似解しか得られない。
さらに、シングルラウンドの光錐VQAは、128キュービットのデモでは硬度閾値を超える解を導出するが、QAOAは1,2,3$の値では得られない。
我々の研究は、短期量子デバイスにおける実用的で古典的な問題の解決に向けた有望な道のりを強調している。
関連論文リスト
- Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
量子近似最適化アルゴリズムの最適化問題に対する量子優位性を実現する能力はまだ不明である。
ランダムなMax-$k$XOR上でのQAOAの性能を$k$の関数と節対変数比として解析する。
満足度の高いレベルに達するには、非常に大きな$p$が必要であり、変動コンテキストと短期デバイスの両方において、かなり難しいとみなす必要がある。
論文 参考訳（メタデータ） (2024-11-28T21:39:58Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on
NISQ Computers [0.0]
QAOA(Quantum Alternating Operator Ansatz)は、最適化問題の最適解を目的とした量子アルゴリズムである。
我々は、D-Waveハードウェア上のQAとIBMQハードウェア上のQAOAの厳密な比較を実装した。
QAがすべての問題インスタンスでQAOAを上回っていることが分かりました。
論文 参考訳（メタデータ） (2023-01-02T04:19:46Z) - Solving boolean satisfiability problems with the quantum approximate
optimization algorithm [0.05076419064097732]
量子コンピューティング問題とは対照的に,QAOAがハード制約満足度問題を解く能力について検討する。
我々は,QAOAの平均成功確率を,満足度しきい値のランダムな式上で解析的に評価する。
約14のアンザッツ層に対して、QAOAは高性能な古典解法のスケーリング性能と一致することがわかった。
論文 参考訳（メタデータ） (2022-08-14T20:39:48Z) - 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) - Sampling Frequency Thresholds for Quantum Advantage of Quantum
Approximate Optimization Algorithm [0.7046417074932257]
量子近似最適化アルゴリズム(QAOA)の性能を最先端の古典解法と比較する。
古典的解法は線形時間複雑性において高品質な近似解を生成することができる。
異なるグラフ、重み付けされたMaxCut、最大独立集合、および3-SATといった他の問題は、短期量子デバイスにおける量子優位性を達成するのに適しているかもしれない。
論文 参考訳（メタデータ） (2022-06-07T20:59:19Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
我々は、様々なレベルの接続性を持つハードウェアアーキテクチャのための最適化回路により、期待されるリソース要求のスケーリングを定量化する。
問題の大きさと問題グラフの次数で指数関数的に増大する。
これらの問題は、ハードウェア接続性の向上や、より少ない回路層で高い性能を達成するQAOAの変更によって緩和される可能性がある。
論文 参考訳（メタデータ） (2022-01-06T21:02:30Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。
本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。
Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
論文 参考訳（メタデータ） (2021-05-06T17:59:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。