論文の概要: A provable quantum advantage for approximate optimization via decoded quantum interferometry

• arxiv url: http://arxiv.org/abs/2610.02145v1
• Date: Thu, 01 Oct 2026 17:48:56 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.353378
• Title: A provable quantum advantage for approximate optimization via decoded quantum interferometry
• Title（参考訳）: 復号化量子干渉法による近似最適化のための証明可能な量子優位性
• Abstract要約: Decoded quantum Interferometry (DQI) は、量子コンピュータ上で近似最適化問題に取り組むための新しいパラダイムである。 DQIは、より大規模な古典的アルゴリズムよりも確実に優れていることを示す。
• 参考スコア（独自算出の注目度）: 0.815557531820863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly larger gap on the folded OPI problem, yielding an even stronger quantum separation. As a concrete example, for code rate $0.3$, DQI and the modified algorithm achieve expected scores of approximately $0.85$ and $0.95$, respectively. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.
• Abstract（参考訳）: Decoded quantum Interferometry (DQI) は、量子コンピュータ上で近似最適化問題に取り組むための新しいパラダイムである。 このフレームワークは強力な性能保証を備えており、最適化と符号化理論の双対性をうまく利用している。 しかし、DQIがすべての多項式時間古典アルゴリズムを確実に上回るかどうかが中心的な疑問である。 本研究では,折り畳まれた最適多項式交叉 (folded OPI) と呼ばれる最適化タスクを考える。 多項式時間古典アルゴリズムで得られる近似比とDQIアルゴリズムで達成される近似比との厳密なギャップを確立する。 我々の証明は、近似最適化のためのJordan et alのDQIフレームワークの上に構築され、山川とZhandryの正確な探索オラクル分離に基づく古典的な下界法を拡張して近似する。 Sun, Wootters, Horinaga, Yamakawa, Jo の最近の発展に基づいて、DQI アルゴリズムの修正版が折り畳まれた OPI 問題に対して厳密に大きなギャップを達成し、さらに強い量子分離をもたらすことを示す。 具体的な例として、コードレートが0.3$の場合、DQIと修正されたアルゴリズムはそれぞれ0.85$と0.95$の期待スコアを得る。 対照的に、古典しきい値が0.65$を超える場合、サンプリングされたインスタンスに一定の確率で固定された量を超えると、多くの古典的メンバーシップクエリが必要になる。

関連論文リスト

• Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
  Decoded Quantum Interferometry (DQI) はスーパーポリノミカル量子スピードアップのためのフレームワークを提供する。 DQIをリードソロモン(Reed-Solomon, RS)コードである最適多項式区間(OPI)問題に適用する。 我々は、OPIのDQIが、最適スピードアップによる検証可能な量子優位性の最初の候補であることを示す。
  論文  参考訳（メタデータ） (2025-10-13T03:19:28Z)
• 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)
• 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)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  変分量子アルゴリズム(VQA)は、特定の計算上の利点を得るために、短期量子マシンを利用する可能性がある。 現代のVQAは、巨大なデータを扱うために単独の量子プロセッサを使用するという伝統によって妨げられている、計算上のオーバーヘッドに悩まされている。 ここでは、この問題に対処するため、効率的な分散最適化手法であるQUDIOを考案する。
  論文  参考訳（メタデータ） (2021-06-24T08:18:42Z)

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

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