論文の概要: Exponential quantum advantages for decoded quantum interferometry in the streaming setting

• arxiv url: http://arxiv.org/abs/2610.01902v1
• Date: Thu, 01 Oct 2026 15:49:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-03 01:19:24.233904
• Title: Exponential quantum advantages for decoded quantum interferometry in the streaming setting
• Title（参考訳）: ストリーミング環境におけるデコード量子干渉計の指数量子優位性
• Abstract要約: Decoded quantum interferometry (DQI) は、元の最適交叉(OPI)問題に対して証明可能な量子優位性を持つことを示す。 DQIアルゴリズムの適応は、満足のいく93%の制約を生成するが、入力ストリームは1つの多対数空間でのみ読み取る。 この結果から,DQI が元の OPI 問題に対して証明可能な量子優位性を持つことを示す。
• 参考スコア（独自算出の注目度）: 0.5844015313757266
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.
• Abstract（参考訳）: デコード量子干渉法(Decoded quantum Interferometry, DQI)は、Jordan et al (Nature 2025)によって導入された多項式時間量子アルゴリズムである。 最適多項式交叉(OPI)と呼ばれる自然な最適化問題に対して、既知のすべての古典的アルゴリズムが指数時間を必要とする状況下で近似を保証する。 大規模な入力の保存と操作は、特に論理キュービットが重大なフォールトトレラントな実装オーバーヘッドを抱えている場合、非常に難しい。 DQIはメモリに量子的優位性をもたらすのか、無条件で証明できるのか? ストリーミング環境では、この質問に対して肯定的な回答を出します。 特に,Hermite補間とHasse微分を用いたOPIの自然な一般化を考える。 具体例として, DQI アルゴリズムの適応は, 制約の 93 % を満足する多項式を生成する。さらに, 入力ストリームのみを1パスで読み出し, 多対数空間を使用し, ストリームエントリ毎に多対数計算時間を有する。 古典的難易度] 制約のわずか76 %$を満たす解を生成する古典的アルゴリズムは, 多項式的に多くのパスで入力ストリームを読み取ることができ, 無制限の時間で使用できる場合にも, 多項式空間を必要とする。 この結果は、チューナブルパラメータに対する完全なトレードオフ曲線を提供し、DQIが元のOPI問題に対して証明可能な量子優位性を持っていることを示唆している。

関連論文リスト

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  浅量子回路では解けない問題を格子ベースの仮定で解くのが困難である。 浅量子回路は、解を効率よく検証できる古典的な難題を解くのに十分な構造を持っていることを証明している。
  論文  参考訳（メタデータ） (2026-09-01T15:54:34Z)
• 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)
• The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions [1.3108652488669732]
  ここでは,QAOAが線形関数を解くのに指数時間を要することを示す。 我々は QAOA が任意の定数 $p$ に対して線型関数の大域的最適化を求めるには指数時間が必要であると推測し、ランタイムが線型であることは$p geq n$ の場合のみである。
  論文  参考訳（メタデータ） (2025-05-09T20:04:10Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (2020-02-27T15:32:08Z)

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

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