論文の概要: Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds

• arxiv url: http://arxiv.org/abs/2610.06727v1
• Date: Mon, 05 Oct 2026 17:15:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 23:20:02.654393
• Title: Random Order in Quantum Streaming: Replenishment and Robust Lower Bounds
• Title（参考訳）: 量子ストリーミングにおけるランダム順序:補充とロバストな下界
• Abstract要約: ランダム順序がストリーミングにおける量子メモリの役割をどのように変えるかを示す。 Block Hidden XOR の量子通信下界は、十分に大きなサイクルに対してランダムなエッジオーダーで$(n)$スペース下界を得る。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: How can random order change the role of quantum memory in streaming? Later classical input can restore the usefulness of a quantum state consumed by earlier queries. We call this replenishment. We construct an artificial problem based on Hidden Matching, with repeated coordinate data and online matching requests. It admits a one-pass quantum algorithm using polylogarithmic space in uniformly random order, but unconditionally requires polynomial space both classically in random order and quantumly when all updates precede the requests. To prove the quantum lower bound, we strengthen the consumability bounds of Gilboa, Jain, and McClean for Multiple Hidden Matching. Without prior entanglement, any quantum encoding supporting $r$ independent matching requests requires $Ω(r)$ qubits for $r\le N^{1/2-δ}$ and every fixed $δ\in(0,1/2)$, even with simultaneous revelation and arbitrary joint decoding. For sequential requests, the linear bound extends through $r=Θ(\sqrt N)$. We also adapt Kallaugher's triangle-counting algorithm to uniformly random streams in which every edge is repeated equally often. Rebuilding the quantum sketch and resampling the classical estimator improve its expected-space bound in suitable parameter regimes. Finally, we extend the robust Noisy Gap Cycle framework of Assadi and Sundaresan to quantum streaming. A quantum communication lower bound for Block Hidden XOR yields an $Ω(n)$ space lower bound in random edge order for large enough cycles, with consequences for several graph problems. Thus random order can enable replenishment of small quantum representations, while substantial space requirements persist for other tasks.
• Abstract（参考訳）: ストリーミングにおける量子メモリの役割をどのようにランダムに変化させるか? その後の古典的な入力は、以前のクエリで消費された量子状態の有用性を回復することができる。 私たちはこれを補充と呼ぶ。 我々は,協調データとオンラインマッチング要求を繰り返すことで,隠れマッチングに基づく人工的な問題を構築する。 均一にランダムな順序で多対数空間を用いるワンパス量子アルゴリズムを認めるが、全ての更新が要求に先行する場合は、古典的にランダムな順序で多項式空間を必要とする。 量子下界を証明するために、多重隠れマッチングに対するジルボア、ジャイン、マクリーンの可消費境界を強化する。 事前の絡み合いがなければ、$r$独立マッチング要求をサポートする任意の量子符号化は$r\le N^{1/2-δ}$とすべての固定された$δ\in(0,1/2)$に対して$Ω(r)$ qubitsを必要とする。 シーケンシャルな要求に対して、線形境界は$r= > (\sqrt N)$ で拡張される。 また、各エッジが同じ頻度で繰り返される一様ランダムストリームにカライヤーの三角形計数アルゴリズムを適用する。 量子スケッチを再構築し、古典的推定器を再サンプリングすることで、適切なパラメータの条件下での期待空間のバウンドを改善する。 最後に、AssadiとSundaresanの堅牢なNoisy Gap Cycleフレームワークを量子ストリーミングに拡張する。 Block Hidden XOR の量子通信下界は、いくつかのグラフ問題に対する帰結として、ランダムなエッジオーダーで$Ω(n)$スペース下界を得る。 したがって、ランダム順序は小さな量子表現の補充を可能にするが、他のタスクにはかなりの空間要求が持続する。

関連論文リスト

• Exponential quantum space advantage in random data streams [1.5169198425950672]
  ランダム順序ストリーミングモデルでは、2つの非条件量子空間の利点を示す。 まず, 入力がランダムな順序でストリーミングされる場合, ストリーミングモデルにおいて指数的量子優位を許容する山川-Zhandry Code Intersection問題を示す。 第二に、我々は、Decoded Quantum Interferometryアルゴリズムのストリーミングバージョンを介して、特定の状態における最適多項式区間(OPI)問題に対する量子空間の利点を示すために、我々のフレームワークを使用している。
  論文  参考訳（メタデータ） (2026-10-02T17:31:43Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  格子ベースの暗号は、量子後暗号の主要な候補の1つである。 量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
  論文  参考訳（メタデータ） (2024-10-17T16:54:41Z)
• Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits [15.89518426969296]
  非同一分散サンプルに対するクエリアクセスの平均推定のための量子アルゴリズムと低境界について検討する。 一方、有界または準ガウス確率変数の2次量子スピードアップを持つ量子平均推定器を与える。 一方、一般に、量子アルゴリズムが古典的なサンプルの数に対して二次的なスピードアップを達成することは不可能であることを示す。
  論文  参考訳（メタデータ） (2024-05-21T14:42:39Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Efficient Pauli channel estimation with logarithmic quantum memory [17.16536262746742]
  a protocol can estimated the eigen values of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla and $tildeO(n2/epsilon2)$ measured。 我々の知識によれば、量子メモリの対数的に多くの量子ビットが指数統計上の優位性のために十分である最初の量子学習タスクである。
  論文  参考訳（メタデータ） (2023-09-25T17:53:12Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  本稿では,第1量子化における量子力学の実行のための変分量子アルゴリズムを提案する。 シミュレーションでは,従来観測されていた変動時間伝播手法の数値不安定性を示す。
  論文  参考訳（メタデータ） (2022-03-04T19:00:45Z)
• 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)
• Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
  ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。 利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
  論文  参考訳（メタデータ） (2020-02-20T18:48:51Z)

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

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