論文の概要: Exponential quantum space advantage in random data streams

• arxiv url: http://arxiv.org/abs/2610.03645v1
• Date: Fri, 02 Oct 2026 17:31:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.519124
• Title: Exponential quantum space advantage in random data streams
• Title（参考訳）: ランダムデータストリームにおける指数量子空間の利点
• Abstract要約: ランダム順序ストリーミングモデルでは、2つの非条件量子空間の利点を示す。 まず, 入力がランダムな順序でストリーミングされる場合, ストリーミングモデルにおいて指数的量子優位を許容する山川-Zhandry Code Intersection問題を示す。 第二に、我々は、Decoded Quantum Interferometryアルゴリズムのストリーミングバージョンを介して、特定の状態における最適多項式区間(OPI)問題に対する量子空間の利点を示すために、我々のフレームワークを使用している。
• 参考スコア（独自算出の注目度）: 1.5169198425950672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show two unconditional quantum space advantages in the random-order streaming model. First, we show the Yamakawa--Zhandry Code Intersection problem admits exponential quantum advantage in the streaming model when its inputs are streamed in random order. This means quantum computers exhibit exponential space advantage even when simply receiving $(x,f(x))$ pairs for a uniformly random function $f$ in a uniformly random order. Our lower bound is shown using density-restoring partitions as in the work of Göös, Gur, Jain, and Li (STOC 2025) combined with a convex potential, similar to the work of Raz (J.ACM 2018) on parity learning and its generalization by Garg, Raz, and Tal (STOC 2018). Second, we use our framework to show quantum space advantage for the Optimal Polynomial Intersection (OPI) problem in certain regimes via a streaming version of the Decoded Quantum Interferometry algorithm (Nature 2025; arXiv:2510.10967). In particular, we show that for degree $d$ and $n$ evaluation points, attaining $1/2 + Ω(\sqrt{d/n})$ fraction of satisfied OPI constraints via streaming requires $Ω(n)$ classical bits of memory but only $O(d\log n)$ qubits. This yields provable quantum advantage in a "low-rate" regime when the number of evaluation points is much larger than the degree, with a space advantage that can be as large as exponential in certain parameter settings.
• Abstract（参考訳）: ランダム順序ストリーミングモデルでは、2つの非条件量子空間の利点を示す。 まず, 入力がランダムな順序でストリーミングされる場合, ストリーミングモデルにおいて指数的量子優位を許容する山川-Zhandry Code Intersection問題を示す。 これは、量子コンピュータが一様ランダムな関数$f$に対して単に$(x,f(x))$ペアを受け取るときでさえ指数空間優位性を示すことを意味する。 我々の下界は、Gööös, Gur, Jain, Li (STOC 2025) の作業と凸ポテンシャルを組み合わせた密度復元分割(STOC 2025)を用いて示されており、これはパリティ学習に関する Raz (J.ACM 2018) の作業と、Garg, Raz, Tal (STOC 2018) の一般化に類似している。 第二に、我々は、Decoded Quantum Interferometryアルゴリズムのストリーミングバージョン(Nature 2025; arXiv:2510.10967)を介して、特定の状態における最適多項式区間(OPI)問題に対する量子空間の利点を示す。 特に、次数$d$と$n$の評価点について、1/2 + Ω(\sqrt{d/n})$ストリーミングによる満たされたOPI制約の分数には、$Ω(n)$古典的なメモリビットが必要であるが、$O(d\log n)$qubitsしか必要でないことを示す。 これは「低レート」な状態において、評価点の数が次数よりもはるかに大きいときに証明可能な量子的優位性をもたらすが、空間的優位性は特定のパラメータ設定で指数関数的に大きい。

関連論文リスト

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  重み付き確率変数に対する新しい量子平均推定器を開発した。 尾指数>4/3$のより強い下界を導出し、次元への非自明な依存が避けられないことを示す。 凸目的関数に対して,量子射影勾配降下法を提案する。
  論文  参考訳（メタデータ） (2026-07-28T09:29:37Z)
• Linear gate bounds against natural functions for position-verification [0.0]
  量子位置検証スキームは、証明者の空間的位置を検証しようとする。 我々は、$f$-routing(英語版)と$f$-BB84(英語版)として知られる2つのよく研究された位置検証スキームを考える。
  論文  参考訳（メタデータ） (2024-02-28T19:00:10Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model [0.24554686192257422]
  自然ストリーミング問題に対して指数量子空間の優位性を示す。 これはまた、離散最適化問題を近似する最初の無条件指数量子資源の利点でもある。 我々の結果は、最近の$widetildetextO(sqrtn)$ space classical streaming approachに基づいています。
  論文  参考訳（メタデータ） (2023-11-23T17:38:16Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions [0.0]
  我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。 2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
  論文  参考訳（メタデータ） (2020-12-09T19:00:50Z)
• Quantum advantage for computations with limited space [6.327095331866255]
  我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。 我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
  論文  参考訳（メタデータ） (2020-08-14T17:31:12Z)

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

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