論文の概要: Space Complexity of Streaming Algorithms on Universal Quantum Computers

• arxiv url: http://arxiv.org/abs/2011.00302v1
• Date: Sat, 31 Oct 2020 16:16:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-26 05:38:40.255570
• Title: Space Complexity of Streaming Algorithms on Universal Quantum Computers
• Title（参考訳）: ユニバーサル量子コンピュータにおけるストリーミングアルゴリズムの空間複雑性
• Authors: Yanglin Hu, Darya Melnyk, Yuyi Wang and Roger Wattenhofer
• Abstract要約: PartialMOD や Equality などのデータストリーム問題の空間的複雑さは、普遍量子コンピュータ上で研究されている。 これらの問題の量子アルゴリズムは、古典的なアルゴリズムよりも優れていると考えられている。
• 参考スコア（独自算出の注目度）: 13.941598115553957
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Universal quantum computers are the only general purpose quantum computers known that can be implemented as of today. These computers consist of a classical memory component which controls the quantum memory. In this paper, the space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers. The quantum algorithms for these problems are believed to outperform their classical counterparts. Universal quantum computers, however, need classical bits for controlling quantum gates in addition to qubits. Our analysis shows that the number of classical bits used in quantum algorithms is equal to or even larger than that of classical bits used in corresponding classical algorithms. These results suggest that there is no advantage of implementing certain data stream problems on universal quantum computers instead of classical computers when space complexity is considered.
• Abstract（参考訳）: ユニバーサル量子コンピュータ(Universal quantum computer)は、今日まで実装できる唯一の汎用量子コンピュータである。 これらのコンピュータは、量子メモリを制御する古典的なメモリコンポーネントで構成されている。 本稿では,ユビキタス量子コンピュータにおいて,部分モッドや等式などのデータストリーム問題の空間複雑性について検討する。 これらの問題の量子アルゴリズムは、古典的アルゴリズムよりも優れていると考えられている。 しかし、普遍量子コンピュータは量子ゲートの制御に加えて古典ビットを必要とする。 解析の結果、量子アルゴリズムで使用される古典ビットの数は、対応する古典アルゴリズムで使用される古典ビットと等しいかそれ以上であることがわかった。 これらの結果は、空間複雑性が考慮されるとき、古典的コンピュータではなく、普遍的量子コンピュータにデータストリーム問題を実装する利点がないことを示唆する。

関連論文リスト

• Quantum Frequential Computing: a quadratic run time advantage for all algorithms [0.0]
  量子頻繁計算機と呼ばれる新しい種類のコンピュータを導入する。 彼らは従来の量子コンピュータとは異なる方法で量子特性を利用する。 それらは消費される電力の関数として全てのアルゴリズムに対して二次計算実行時間を生成する。
  論文  参考訳（メタデータ） (2024-03-04T19:00:02Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• A prototype of quantum von Neumann architecture [0.0]
  我々は、フォン・ノイマンアーキテクチャの量子バージョンである普遍量子コンピュータシステムのモデルを提案する。 量子メモリユニットの要素としてebitを使用し、量子制御ユニットと処理ユニットの要素としてqubitを使用する。 本研究は,量子情報の多様体パワーを実証し,量子コンピュータシステム構築の道を開くものである。
  論文  参考訳（メタデータ） (2021-12-17T06:33:31Z)
• A universal qudit quantum processor with trapped ions [1.4675095722281566]
  局所ヒルベルト空間次元最大7のトラップイオンを用いた普遍量子プロセッサを実証する。 このアプローチは、高次元量子システムのネイティブシミュレーションと、より効率的な量子ビットベースのアルゴリズムの実装を可能にする。
  論文  参考訳（メタデータ） (2021-09-14T18:02:25Z)
• Universal quantum computation via quantum controlled classical operations [0.0]
  古典的または量子的な)計算のための普遍的なゲートの集合は、他の任意の操作を近似するために使用できるゲートの集合である。 SWAPゲートのみを実装可能なプリミティブコンピュータであっても、普遍量子コンピューティングに持ち上げることができることを示す。
  論文  参考訳（メタデータ） (2021-04-13T18:00:13Z)
• Quantum Computing without Quantum Computers: Database Search and Data Processing Using Classical Wave Superposition [101.18253437732933]
  スピン波重畳を用いた磁気データベース探索の実験データを示す。 古典的な波動に基づくアプローチは、量子コンピュータと同じ速度でデータベース検索を行う場合もあると我々は論じる。
  論文  参考訳（メタデータ） (2020-12-15T16:21:53Z)
• Quantum Deformed Neural Networks [83.71196337378022]
  我々は,量子コンピュータ上で効率的に動作するように設計された新しい量子ニューラルネットワーク層を開発した。 入力状態の絡み合いに制限された場合、古典的なコンピュータでシミュレートすることができる。
  論文  参考訳（メタデータ） (2020-10-21T09:46:12Z)
• A rigorous and robust quantum speed-up in supervised machine learning [6.402634424631123]
  本稿では,汎用量子学習アルゴリズムを用いて,教師付き分類のための厳密な量子スピードアップを確立する。 我々の量子分類器は、フォールトトレラント量子コンピュータを用いてカーネル関数を推定する従来のサポートベクトルマシンである。
  論文  参考訳（メタデータ） (2020-10-05T17:22:22Z)
• 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)

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

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