論文の概要: A Quantum Advantage for a Natural Streaming Problem
- arxiv url: http://arxiv.org/abs/2106.04633v2
- Date: Fri, 12 Nov 2021 23:25:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 06:28:14.810170
- Title: A Quantum Advantage for a Natural Streaming Problem
- Title（参考訳）: 自然ストリーミング問題に対する量子アドバンテージ
- Authors: John Kallaugher
- Abstract要約: 古典グラフカウントにおける最も研究の進んだ問題の1つとして,1パスの量子ストリーミングアルゴリズムを提案する。
ほぼ28個のパラメタライズされた上境界と下限は、ストリーミングで知られている。
- 参考スコア（独自算出の注目度）: 0.07614628596146598
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Data streaming, in which a large dataset is received as a "stream" of
updates, is an important model in the study of space-bounded computation.
Starting with the work of Le Gall [SPAA `06], it has been known that quantum
streaming algorithms can use asymptotically less space than their classical
counterparts for certain problems. However, so far, all known examples of
quantum advantages in streaming are for problems that are either specially
constructed for that purpose, or require many streaming passes over the input.
We give a one-pass quantum streaming algorithm for one of the best studied
problems in classical graph streaming - the triangle counting problem.
Almost-tight parametrized upper and lower bounds are known for this problem in
the classical setting; our algorithm uses polynomially less space in certain
regions of the parameter space, resolving a question posed by Jain and Nayak in
2014 on achieving quantum advantages for natural streaming problems.
- Abstract（参考訳）: 大規模なデータセットを更新の"ストリーム"として受信するデータストリーミングは、空間境界計算の研究において重要なモデルである。
Le Gall [SPAA `06]の研究から、量子ストリーミングアルゴリズムは特定の問題に対して古典的なアルゴリズムよりも漸近的に少ない空間を使うことができることが知られている。
しかし、これまでのストリーミングにおける量子上の利点の例は、その目的のために特別に構築されているか、入力に多くのストリーミングパスを必要とする問題である。
古典的なグラフストリーミングにおいて最もよく研究されている問題である三角形カウント問題に対する1パス量子ストリーミングアルゴリズムを提案する。
本アルゴリズムは、パラメータ空間の特定の領域における多項式的に少ない空間を用いており、2014年にjainとnayakが自然ストリーミング問題に対する量子的優位性を達成するために提起した疑問を解決する。
関連論文リスト
- 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) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。
また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
論文 参考訳（メタデータ） (2023-06-05T12:29:55Z) - Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NPハード問題は、一般時間アルゴリズムで正確に解けるとは考えられていない。
本稿では,問題のサイズに応じて対数的にスケールする独自手法を構築した。
これらのアルゴリズムは、100以上のノードのグラフサイズを持つ量子シミュレータと、256のグラフサイズまでの実際の量子コンピュータでテストされる。
論文 参考訳（メタデータ） (2023-01-17T16:03:33Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Distributed quantum algorithm for Simon's problem [2.26741603346646]
我々は分散シナリオにおけるSimonの問題を研究し、この問題を解決するために分散量子アルゴリズムを設計する。
分散量子コンピューティングの新しい計算アーキテクチャは、量子回路のノイズと深さを減らすことが期待されている。
論文 参考訳（メタデータ） (2022-04-25T01:22:22Z) - Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
三角形の数と4サイクルを推定するための,データ駆動型ワンパスストリーミングアルゴリズムを提案する。
従来の"古典的"アルゴリズムを改善するために、ストリーム要素の特定の特性を予測できるトレーニングされたオラクルを使用します。
提案手法は,従来のマルチパスおよびランダム順序ストリーミングアルゴリズムを特殊なケースとみなすことができるため,従来の"古典的"ストリーミングアルゴリズムの取り組みを拡大する。
論文 参考訳（メタデータ） (2022-03-17T19:26:00Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - One-shot inner bounds for sending private classical information over a
quantum MAC [0.0]
量子多重アクセスチャネル上でプライベートな古典情報を送信するための、最初の内部境界を提供する。
我々は、レート分割、複数のアクセスチャネルに対する量子同時復号化、古典的な量子チャネルに対する新しいスムーズな分散被覆補題の3つの強力な情報理論技術を用いて実現している。
論文 参考訳（メタデータ） (2021-05-13T06:31:27Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。