論文の概要: Quartic quantum speedups for planted inference

• arxiv url: http://arxiv.org/abs/2406.19378v1
• Date: Thu, 27 Jun 2024 17:54:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 13:09:01.976208
• Title: Quartic quantum speedups for planted inference
• Title（参考訳）: 植え込み推論のための量子量子スピードアップ
• Authors: Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush,
• Abstract要約: そこで本研究では,植物ノイズの量子アルゴリズムについて述べる。 我々の研究は、いくつかの構造は超4次量子攻撃の影響を受けやすいことを示唆している。
• 参考スコア（独自算出の注目度）: 44.820711784498
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe a quantum algorithm for the Planted Noisy $k$XOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic ($4$th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings, by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy $k$XOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.
• Abstract（参考訳）: 我々は、最もよく知られた古典的アルゴリズムに対して、対数的に多くの量子ビットのみを使用しながら、ほぼ4分の1 (4$th power) のスピードアップを実現する、プラント・ノイズの$k$XOR問題(スパース・ラーニング・パリティ・ウィズ・ノイズとも呼ばれる)に対する量子アルゴリズムについて述べる。 我々の研究は、テンソル主成分分析(PCA)問題に対する彼の量子アルゴリズムに基づいて、Hastingsの先行研究を一般化し、単純化する。 我々は、菊池法(テンソルPCAのクォートスピードアップを復元する)に基づく一般的なフレームワークを用いて、量子スピードアップを実現し、さらなる植込み推論問題に対して、同様のスピードアップを期待する。 これらのスピードアップは、植え付けられた推論問題がガイド・スパース・ハミルトン問題を自然にインスタンス化するという事実に依存している。 Planted Noisy $k$XORの問題は、特定の暗号構造の構成要素として使われてきたため、我々の研究は、これらのいくつかが超四重項量子攻撃の影響を受けやすいことを示唆している。

関連論文リスト

• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Quantum speedup for combinatorial optimization with flat energy landscapes [0.0]
  我々は,最適化された量子断熱アルゴリズムと古典マルコフ連鎖モンテカルロアルゴリズムの相対的性能を解析するための理論的枠組みを開発する。
  論文  参考訳（メタデータ） (2023-06-22T18:00:00Z)
• Limitations of Noisy Quantum Devices in Computational and Entangling Power [5.178527492542246]
  回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。 また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
  論文  参考訳（メタデータ） (2023-06-05T12:29:55Z)
• 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)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  雑音二元線形問題(NBLP)の量子可解性について完全解析する。 NBLPの解くコストは、指数関数的に増大する論理量子ビットを犠牲にして、問題の規模で解決できることが示される。
  論文  参考訳（メタデータ） (2021-09-23T07:46:20Z)
• Fault-tolerant quantum speedup from constant depth quantum circuits [0.0]
  出力分布に応じて$poly(n)$ timeでサンプリングできる古典的アルゴリズムは存在しないことを示す。 我々は2つの構成を提示し、それぞれ$poly(n)$ physical qubitsを持ち、そのうちのいくつかはノイズの多い魔法の状態で準備される。
  論文  参考訳（メタデータ） (2020-05-23T13:53:27Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。 本稿では,QAOAの回路深度依存性能について実験的に検討する。 この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
  論文  参考訳（メタデータ） (2020-05-11T17:20:51Z)
• Quantum Bandits [10.151012770913622]
  我々は、エム・ベスト・アーム・アイデンティティ(BAI)として知られるバンディット問題の量子バージョンを考える。 まず,学習エージェントと環境の両方が量子であると仮定した,BAI問題の量子モデリングを提案する。 次に,BAIを解くために,量子振幅増幅に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-02-15T15:17:11Z)

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

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