論文の概要: Quantum communication complexity of linear regression

• arxiv url: http://arxiv.org/abs/2210.01601v1
• Date: Tue, 4 Oct 2022 13:27:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-23 22:02:34.812200
• Title: Quantum communication complexity of linear regression
• Title（参考訳）: 線形回帰の量子通信複雑性
• Authors: Ashley Montanaro and Changpeng Shao
• Abstract要約: 量子コンピュータは、いくつかの基本的な線形代数問題に対する通信複雑性の観点から指数関数的なスピードアップを持つことができることを示す。 本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
• 参考スコア（独自算出の注目度）: 0.05076419064097732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Dequantized algorithms show that quantum computers do not have exponential speedups for many linear algebra problems in terms of time and query complexity. In this work, we show that quantum computers can have exponential speedups in terms of communication complexity for some fundamental linear algebra problems. We mainly focus on solving linear regression and Hamiltonian simulation. In the quantum case, the task is to prepare the quantum state of the result. To allow for a fair comparison, in the classical case the task is to sample from the result. We investigate these two problems in two-party and multiparty models, propose near-optimal quantum protocols and prove quantum/classical lower bounds. In this process, we propose an efficient quantum protocol for quantum singular value transformation, which is a powerful technique for designing quantum algorithms. As a result, for many linear algebra problems where quantum computers lose exponential speedups in terms of time and query complexity, it is possible to have exponential speedups in terms of communication complexity.
• Abstract（参考訳）: 量子化アルゴリズムは、時間とクエリの複雑さの観点から、多くの線形代数問題に対して指数関数的なスピードアップを持たないことを示す。 本研究では,量子コンピュータが基本的な線形代数問題に対して,通信複雑性の観点から指数関数的に高速化できることを示す。 主に線形回帰とハミルトンシミュレーションの解法に焦点をあてる。 量子の場合、タスクは結果の量子状態を準備することである。 公正な比較を可能にするために、古典的な場合、タスクは結果からサンプルを取ることである。 本研究では,これら2つの問題を二元モデルと多元モデルで検討し,準最適量子プロトコルを提案し,量子・古典下界を証明した。 本研究では,量子アルゴリズム設計のための強力な手法である量子特異値変換のための効率的な量子プロトコルを提案する。 結果として、量子コンピュータが時間とクエリの複雑さの点で指数的なスピードアップを失う多くの線形代数問題に対して、通信複雑性の点で指数的なスピードアップが可能である。

関連論文リスト

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか? 我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。 我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
  論文  参考訳（メタデータ） (2024-08-22T08:21:28Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  本稿では,量子コンピュータによって解を加速できる問題のクラスを記述するためのアプローチを検討する。 初期量子状態を所望の状態に変換するユニタリ演算は、1ビットと2ビットのゲートの列に分解可能である必要がある。
  論文  参考訳（メタデータ） (2024-03-25T15:47:35Z)
• Sample-size-reduction of quantum states for the noisy linear problem [0.0]
  本稿では,量子ランダムアクセスメモリ(QRAM)の量子サンプルサイズを線形次数に削減できることを述べる。 ノイズの多い線形問題に対して,より短い実行時間を実現する。
  論文  参考訳（メタデータ） (2023-01-08T05:53:17Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Quantum Computing Quantum Monte Carlo [8.69884453265578]
  量子コンピューティングと量子モンテカルロを統合したハイブリッド量子古典アルゴリズムを提案する。 我々の研究は、中間スケールおよび早期フォールト耐性量子コンピュータで現実的な問題を解決するための道を開いた。
  論文  参考訳（メタデータ） (2022-06-21T14:26:24Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  グラフ上の量子ウォークを量子回路として表現する方法を研究する。 提案手法は,量子ウォークアルゴリズムを量子コンピュータ上で効率的に実装する方法である。
  論文  参考訳（メタデータ） (2020-12-28T18:04:16Z)
• Quantum Assisted Simulator [0.0]
  量子システムの力学をシミュレートする新しいハイブリッド量子古典アルゴリズムを提案する。 既存の変分量子シミュレーションアルゴリズムとは異なり、我々のアルゴリズムは古典量子フィードバックループを必要としない。
  論文  参考訳（メタデータ） (2020-11-12T13:52:44Z)
• Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation to a New Level [10.765480856320018]
  我々は2次元の量子回路シミュレーション(精度と拡張性)を強化する。 実験により,本手法は様々な量子回路の最先端技術よりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-18T01:26:40Z)

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

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