論文の概要: Exponential quantum space advantage for Shannon entropy estimation in data streams

• arxiv url: http://arxiv.org/abs/2604.18014v1
• Date: Mon, 20 Apr 2026 09:37:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 13:09:20.340321
• Title: Exponential quantum space advantage for Shannon entropy estimation in data streams
• Title（参考訳）: データストリームにおけるシャノンエントロピー推定のための指数量子空間の利点
• Authors: Weijun Feng, Yongzhen Xu, Lvzhou Li, Gongde Guo, Song Lin,
• Abstract要約: 量子ビットが制限された短期量子デバイスは、データストリームモデルにおける空間有界量子計算の研究を動機付けている。 シャノンエントロピー推定は、この設定において量子空間と古典空間の複雑さを指数関数的に分離することを示す。
• 参考スコア（独自算出の注目度）: 4.740331063526406
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Near-term quantum devices with limited qubits motivate the study of space-bounded quantum computation in the data stream model. We show that Shannon entropy estimation exhibits an exponential separation between quantum and classical space complexity in this setting. Technically, we develop a two-stage quantum streaming algorithm based on a quantum procedure with an explicitly constructed oracle derived from the streaming input. This algorithm achieves logarithmic space complexity in the accuracy parameter, whereas any classical streaming algorithm requires polynomial space. In sharp contrast, existing results for Shannon entropy estimation in the quantum query model achieve only a quadratic speedup. Our work establishes a natural problem with practical applications in computer networking that admits an exponential quantum space advantage, revealing a fundamental gap between quantum query complexity and streaming space complexity.
• Abstract（参考訳）: 量子ビットが制限された短期量子デバイスは、データストリームモデルにおける空間有界量子計算の研究を動機付けている。 シャノンエントロピー推定は、この設定において量子空間と古典空間の複雑さを指数関数的に分離することを示す。 技術的には、ストリーミング入力から導出されるオラクルを明示的に構築した量子プロシージャに基づく2段階の量子ストリーミングアルゴリズムを開発する。 このアルゴリズムは精度パラメータの対数空間の複雑さを達成するが、古典的なストリーミングアルゴリズムでは多項式空間を必要とする。 対照的に、量子クエリモデルにおけるシャノンエントロピー推定の既存の結果は、二次的なスピードアップしか達成できない。 我々の研究は、指数量子空間の優位性を認め、量子クエリの複雑さとストリーミング空間の複雑さの根本的なギャップを明らかにするコンピュータネットワークの実践的な応用において、自然問題を確立している。

関連論文リスト

• Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits [2.886955168147019]
  本研究では,外部サーバと通信する長寿命キュービットを持つトラップオン量子コンピュータを用いたデータストリーミングモデルを実現する。 量子空間の優位性は、フォールトトレランスのオーバーヘッドにおいても持続することを示す。
  論文  参考訳（メタデータ） (2025-11-05T18:16:21Z)
• Quantum smoothed particle hydrodynamics algorithm inspired by quantum walks [0.0]
  時間依存型滑らかな粒子流体力学(SPH)の量子アルゴリズムを提案する。 このアルゴリズムは離散時間量子ウォークの概念を用いて一次元の対流偏微分方程式を解く。 本研究では,2粒子系の計算を1,2,3段階の時間ステップで行う量子回路を構築した。
  論文  参考訳（メタデータ） (2025-03-07T13:09:33Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  量子学習理論の最近の進歩は、様々な古典的な入力によって生成された測定データから、大きな量子ビット回路の線形特性を効率的に学習できるのか? 我々は、小さな予測誤差を達成するためには、$d$で線形にスケーリングするサンプルの複雑さが必要であることを証明し、それに対応する計算複雑性は、dで指数関数的にスケールする可能性がある。 そこで本研究では,古典的影と三角展開を利用したカーネルベースの手法を提案し,予測精度と計算オーバーヘッドとのトレードオフを制御可能とした。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Digital quantum simulator for the time-dependent Dirac equation using discrete-time quantum walks [0.7036032466145112]
  離散時間量子ウォークを用いて3+1次元の時間依存ディラック方程式をシミュレートする量子アルゴリズムを提案する。 この結果から,相対論的力学は量子コンピュータで実現可能であることが示唆された。
  論文  参考訳（メタデータ） (2023-05-31T05:36:57Z)
• Preparing random states and benchmarking with many-body quantum chaos [48.044162981804526]
  時間に依存しないハミルトン力学の下で自然にランダム状態アンサンブルの出現を予測し、実験的に観察する方法を示す。 観測されたランダムアンサンブルは射影測定から現れ、より大きな量子系のサブシステムの間に構築された普遍的相関に密接に関連している。 我々の研究は、量子力学におけるランダム性を理解するための意味を持ち、より広い文脈でのこの概念の適用を可能にする。
  論文  参考訳（メタデータ） (2021-03-05T08:32:43Z)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。 本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-24T12:48:00Z)
• Information Scrambling in Computationally Complex Quantum Circuits [56.22772134614514]
  53量子ビット量子プロセッサにおける量子スクランブルのダイナミクスを実験的に検討する。 演算子の拡散は効率的な古典的モデルによって捉えられるが、演算子の絡み合いは指数関数的にスケールされた計算資源を必要とする。
  論文  参考訳（メタデータ） (2021-01-21T22:18:49Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。 観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
  論文  参考訳（メタデータ） (2020-05-05T20:11:53Z)

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

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