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

• arxiv url: http://arxiv.org/abs/2605.10666v1
• Date: Mon, 11 May 2026 14:45:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.909527
• Title: Decoded Quantum Interferometry for Weighted Optimization Problems
• Title（参考訳）: 重み付き最適化問題に対する復号量子干渉法
• Abstract要約: 復号化量子干渉法(Decoded Quantum Interferometry, DQI)は、最近導入された復号化量子最適化法である。 元々の定式化において、DQIはすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。 我々は、重み付き最適化問題に対するDQIの理論を開発し、重み付きMax-LINSAT問題に焦点を当てる。
• 参考スコア（独自算出の注目度）: 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 a theory of 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 \emph{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はすべての制約を均一に扱い、興味のあるほとんどの最適化問題に存在する重み構造を利用できない。 本研究では,重み付き最適化問題に対するDQI理論を開発し,素体上の重み付きMax-LINSAT問題に着目した。 制約を異なる重みで$N$ブロックにグルーピングし、有界全次数$N$変数多項式から構築した \emph{multivariate DQI state} を導入し、それらの最適期待値とそれらの濃度挙動の両方に対して閉形式漸近式を導出する。 単一デコーダコールを用いて明示的な準備回路を提供し、解析を不完全なデコーダに拡張する。 また、ある重み付きOPI問題に対して、多変量DQIはPrangeのアルゴリズムの自然な重み付き類似性よりも優れており、これは非重み付き設定で使用される古典的ベンチマークの重み付き類似性として機能することを示す。 最後に、アイデアをハミルトニアン DQI に拡張し、ブロック構造を持つパウリ・ハミルトニアンを通勤するギブス状態を得る。

関連論文リスト

• A nearly linear-time Decoded Quantum Interferometry algorithm for the Optimal Polynomial Intersection problem [0.0]
  最近、JordanらはDecoded Quantum Interferometry (DQI)と呼ばれる新しい量子アルゴリズム技術を導入した。 彼らは、OPI (Optimal Polynomial Intersection) と呼ばれる制約条件問題を提示し、時間内で動作するDQIアルゴリズムが、既知のどの古典的アルゴリズムよりも大きな制約を満足できることを示した。 これらの改善によって,OPI問題に対するほぼ線形時間DQIアルゴリズムがもたらされることを示す。
  論文  参考訳（メタデータ） (2026-01-21T16:48:05Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  チュートリアルは変分量子回路とQUBO問題の概要から始まる。 次に、ハミルトンの定式化、ゲート分解、サンプル応用など、QAOAの詳細を探索する。 このチュートリアルはこれらの概念を高階ハミルトニアンに拡張し、関連する対称性と回路構成について議論する。
  論文  参考訳（メタデータ） (2025-11-23T09:54:20Z)
• A Rigorous Quantum Framework for Inequality-Constrained and Multi-Objective Binary Optimization [0.4753535328327316]
  本稿では、不等式制約を含むことは、多目的最適化の解法と等価であることを示す。 この洞察はMulti-Objective Quantum Approximation (MOQA)フレームワークを動機付け、より小さな$p$-normsで最大値を近似する。
  論文  参考訳（メタデータ） (2025-10-15T18:05:27Z)
• 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)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  我々はQCBOの制約を満たす量子状態の同値重ね合わせを生成する変動的アプローチを開発する。 結果として生じる同値な重ね合わせは、QUBO/QCBOを解く量子アルゴリズムの初期状態として使用できる。
  論文  参考訳（メタデータ） (2025-08-04T16:44:53Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• 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)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  本稿では,量子コンピュータ上での2次線形反復問題を解くために,フランク・ウルフアルゴリズム(Q-FW)に基づく古典量子ハイブリッドフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-03-23T18:00:03Z)
• Predicting parameters for the Quantum Approximate Optimization Algorithm for MAX-CUT from the infinite-size limit [0.05076419064097732]
  推定次数$d$のランダムエルドス・レーニグラフに適用したMAX-CUT上でのQAOAの性能を評価するための明示的なアルゴリズムを提案する。 この解析により、エルドス・レーニグラフ上のMAX-CUTのQAOAパラメータとシェリントン・カークパトリックモデルとの明示的なマッピングが得られる。
  論文  参考訳（メタデータ） (2021-10-20T17:58:53Z)

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

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