Fugu-MT 論文翻訳(概要): Complexity Amplification from Compression in Quantum Random Access Optimization

論文の概要: Complexity Amplification from Compression in Quantum Random Access Optimization

arxiv url: http://arxiv.org/abs/2609.07090v1
Date: Mon, 07 Sep 2026 06:28:48 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-12 01:40:37.372472
Title: Complexity Amplification from Compression in Quantum Random Access Optimization
Title（参考訳）: 量子ランダムアクセス最適化における圧縮による複雑性増幅
Abstract要約: 各キュービットの最大3つのバイナリ変数をパウリ$X$,$Y$,および$Z$オブザーバブルに割り当てるパウリ相関符号化フレームワークの特別なケースについて検討する。我々は,NP,StoqMA,QMAで完結した明示的なQRAO最適エネルギー公約問題と,後者の2つの逆多項式の公約ギャップを同定した。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, while their bipartite restrictions lie in StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.
Abstract（参考訳）: 圧縮量子符号化(Compressed quantum encodings)は、ハードウェアの限界を克服し、量子ビットの少ない非可換な観測変数に多くの古典変数をマッピングすることで、大規模に困難な問題に取り組むことを目的としている。古典的には、計算効率のためのMaxCut取引ソリューションの品質の半定プログラム定式化のような緩和である。対照的に、圧縮に基づく量子緩和は、解決される問題の最悪のケースの複雑さを増幅することができる。量子ランダムアクセス最適化(QRAO)は、最大3つのバイナリ変数を各キュービットのPauli $X$, $Y$, $Z$オブザーバブルに割り当て、圧縮されたハミルトニアンを最適化するパブリ相関符号化(PCE)フレームワークの特別な場合である。我々は,NP,StoqMA,QMAで完結した明示的なQRAO最適エネルギー公約問題と,後者の2つの逆多項式の公約ギャップを同定した。我々の問題点は、ガジェットやアンシラを必要とせずに、逆ポリノミカルな約束ギャップを保ちます。任意の所定のパッキングに対して、重み付きMaxCutインスタンスは、既知のシフトと再スケーリングまで圧縮され、パッキングによって許容される任意の非負重対パウリカップリングに変換されることを示す。 QRAOの場合、1つのアライメント軸を用いると、NP完全エネルギー問題が発生する。 2つまたは3つの正のアライメントを持つパウリ軸は一般にQMA完全問題をもたらすが、それらの二部制限はStoqMAにある。この計算硬度は, コンパイルに留まり, 実際に関係があることが示される。特に、この結果は、Qiskit Optimization 0.7.0における現在のQRAOコンパイラの実装に直接適用される。その結果、量子圧縮によって生じる最悪のケースの複雑さの障壁が明らかになりましたが、典型的なケースや、それを使用するアルゴリズムパイプラインのパフォーマンスとトレーニング性については、大きな主張はありません。

関連論文リスト

Multivariate Decoded Quantum Interferometry for Weighted Optimization [6.4675604105664]
量子干渉法 (Quantum Interferometry, DQI) は、特定のMax-LINSAT問題に対して最もよく知られたアナログ時間古典アルゴリズムに比べて、復号化への離散最適化を低減させる。元々の定式化において、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。
論文参考訳（メタデータ） (2026-05-11T14:45:46Z)
Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem [0.0]
制約付き最適化問題は量子コンピューティングでは困難である。 Cop-QAOAは、一周期UCに対する制約付き最適化のためのハードウェア効率のよいアプローチである。この研究は、最大150量子ビットを使用するIBM Quantumハードウェア上でのknapsack問題の最大の成功例を示す。
論文参考訳（メタデータ） (2026-02-27T19:16:28Z)
Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing [0.0]
量子コンピューティングは、古典的コンピュータの到達範囲を超えているNP重み付き(最適化)問題を解く大きな可能性を秘めている。この可能性を活用する方法の1つは、2次非制約バイナリ最適化(QUBO)問題として問題を再構成することである。最大$k$-cut問題の2つの異なるQUBO再構成に対する厳格なペナルティ係数の閉形式的特徴について述べる。
論文参考訳（メタデータ） (2025-11-02T22:49:59Z)
Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
論文参考訳（メタデータ） (2025-04-17T03:09:37Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
本稿では,既存の量子最適化手法を解法に統一して二項解を求める方法を示す。 MAX-CUT問題における数百ノードの標準ベンチマークグラフの実験は、完全に古典的な方法で行われた。
論文参考訳（メタデータ） (2024-03-04T13:48:21Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文参考訳（メタデータ） (2022-12-06T22:01:49Z)
Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
余分なスラック変数を必要としない代替手法を提案する。我々は,旅行セールスマン問題,ビン包装問題,ナプサック問題に対するアプローチを評価した。この新しいアプローチは、リソースの少ない不等式制約の問題を解決するために使用できる。
論文参考訳（メタデータ） (2022-11-25T06:05:18Z)
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)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。 3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文参考訳（メタデータ） (2021-08-03T17:49:09Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文参考訳（メタデータ） (2021-07-08T17:59:55Z)
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)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。