論文の概要: Multivariate Decoded Quantum Interferometry for Weighted Optimization

• arxiv url: http://arxiv.org/abs/2605.10666v2
• Date: Sat, 16 May 2026 15:46:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-19 23:51:08.255758
• Title: Multivariate Decoded Quantum Interferometry for Weighted Optimization
• Title（参考訳）: 重み付け最適化のための多変量復号量子干渉計
• Authors: Kaifeng Bu, Weichen Gu, Xiang Li,
• Abstract要約: 量子干渉法 (Quantum Interferometry, DQI) は、特定のMax-LINSAT問題に対して最もよく知られたアナログ時間古典アルゴリズムに比べて、復号化への離散最適化を低減させる。 元々の定式化において、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。
• 参考スコア（独自算出の注目度）: 6.4675604105664
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decoded Quantum Interferometry (DQI) is a recently introduced quantum algorithm that reduces discrete optimization to decoding with potential advantages over the best-known polynomial-time classical algorithms for certain Max-LINSAT problems. In its original formulation, however, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest. In this work, we develop multivariate Decoded Quantum Interferometry (multivariate DQI) for weighted optimization problems, focusing on the weighted Max-LINSAT problem over a prime field. Grouping constraints into $N$ blocks by distinct weights, we introduce multivariate DQI states built from $N$-variable polynomials of bounded total degree, and derive a closed-form asymptotic expression for both their optimal expectation value and their concentration behavior. We give an explicit preparation circuit using a single decoder call, and extend the analysis to imperfect decoding. We also show that, for certain weighted OPI problems, multivariate DQI outperforms a natural weighted analogue of Prange's algorithm, which serves as the weighted counterpart of the classical benchmark used in the unweighted setting. Finally, we extend the ideas to Hamiltonian DQI, obtaining approximate Gibbs states for commuting Pauli Hamiltonians with block structure.
• Abstract（参考訳）: Decoded Quantum Interferometry (DQI) は、特定のMax-LINSAT問題に対して最もよく知られた多項式時間古典アルゴリズムに対して、復号化のための離散最適化を減らし、潜在的な利点を持つ量子アルゴリズムである。 しかし、元々の定式化では、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。 本研究では、重み付き最適化問題に対する多変量復号量子干渉法(multivariate DQI)を開発し、素体上の重み付きMax-LINSAT問題に着目した。 制約を異なる重みで$N$ブロックにグループ化することで、有界全次数$N$変数多項式から構築された多変量DQI状態を導入し、それらの最適期待値とそれらの濃度挙動の両方に対して閉形式漸近式を導出する。 単一デコーダコールを用いて明示的な準備回路を提供し、解析を不完全なデコーダに拡張する。 また、ある重み付きOPI問題に対して、多変量DQIはPrangeのアルゴリズムの自然な重み付き類似性よりも優れており、これは非重み付き設定で使用される古典的ベンチマークの重み付き類似性として機能することを示す。 最後に、アイデアをハミルトニアン DQI に拡張し、ブロック構造を持つパウリ・ハミルトニアンを通勤するギブス状態を得る。

関連論文リスト

• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• Optimization of Quadratic Constraints by Decoded Quantum Interferometry [0.0]
  Decoded Quantum Interferometry (DQI) を2次制約を含む最適化問題に拡張する。 我々は、最大QDSATに対してDQI状態を作成するための効率的なアルゴリズムを提供する。 2次OPIがmax-QUADSATのインスタンスであることを示し、アルゴリズムを用いて最適化する。
  論文  参考訳（メタデータ） (2025-10-09T10:49:17Z)
• No Quantum Advantage in Decoded Quantum Interferometry for MaxCut [0.08122270502556375]
  Decoded Quantum Interferometry (DQI)は、特別な種類の離散最適化問題を近似するためのフレームワークである。 DQI が非自明な保証を得た MaxCut のインスタンスは、古典的な時間で正確に解決可能であることを示す。
  論文  参考訳（メタデータ） (2025-09-24T10:21:31Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  Decoded Quantum Interferometry (DQI) は、量子フーリエ変換を用いて、復号化問題に対する最適化問題を削減する量子アルゴリズムである。 有限体上の最適適合を近似するために、DQIは既知の古典的アルゴリズムよりも超多項式的なスピードアップを達成する。
  論文  参考訳（メタデータ） (2024-08-15T17:47:42Z)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。 超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。 数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
  論文  参考訳（メタデータ） (2022-09-27T17:56:15Z)
• 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)

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

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