論文の概要: Does quantum lattice sieving require quantum RAM?

• arxiv url: http://arxiv.org/abs/2410.15565v1
• Date: Mon, 21 Oct 2024 01:22:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:19:15.059169
• Title: Does quantum lattice sieving require quantum RAM?
• Title（参考訳）: 量子格子は量子RAMを必要とするか?
• Authors: Beomgeun Cho, Minki Hhan, Taehyun Kim, Jeonghoon Lee, Yixin Shen,
• Abstract要約: 量子格子シービングにおける量子ランダムアクセスメモリ(QRAM)の要件について検討する。 特に、QRAMなしでは量子スピードアップは不可能である。 さらなる改善には、QRAMを使うための新しい方法が必要であることを示す。
• 参考スコア（独自算出の注目度）: 6.159206988529989
• License:
• Abstract: In this paper, we study the requirement for quantum random access memory (QRAM) in quantum lattice sieving, a fundamental algorithm for lattice-based cryptanalysis. First, we obtain a lower bound on the cost of quantum lattice sieving with a bounded size QRAM. We do so in a new query model encompassing a wide range of lattice sieving algorithms similar to those in the classical sieving lower bound by Kirshanova and Laarhoven [CRYPTO 21]. This implies that, under reasonable assumptions, quantum speedups in lattice sieving require the use of QRAM. In particular, no quantum speedup is possible without QRAM. Second, we investigate the trade-off between the size of QRAM and the quantum speedup. We obtain a new interpolation between classical and quantum lattice sieving. Moreover, we show that further improvements require a novel way to use the QRAM by proving the optimality of some subroutines. An important caveat is that this trade-off requires a strong assumption on the efficient replacement of QRAM data, indicating that even speedups with a small QRAM are already challenging. Finally, we provide a circuit for quantum lattice sieving without using QRAM. Our circuit has a better depth complexity than the best classical algorithms but requires an exponential amount of qubits. To the best of our knowledge, this is the first quantum speedup for lattice sieving without QRAM in the standard quantum circuit model. We explain why this circuit does not contradict our lower bound, which considers the query complexity.
• Abstract（参考訳）: 本稿では,格子型暗号解析の基本アルゴリズムである量子格子シービングにおける量子ランダムアクセスメモリ(QRAM)の要件について検討する。 まず,量子格子サイズQRAMを用いて,量子格子のコストの低い値を得る。 我々は,Kirshanova と Laarhoven [CRYPTO 21] による古典的 Sieving lower bound に類似した,広範囲な格子シービングアルゴリズムを含む新しいクエリモデルでそうする。 これは、合理的な仮定の下では、格子シービングにおける量子スピードアップはQRAMを使用する必要があることを意味する。 特に、QRAMなしでは量子スピードアップは不可能である。 第2に、QRAMと量子スピードアップのトレードオフについて検討する。 我々は古典格子と量子格子の新たな補間を得る。 さらに,いくつかのサブルーチンの最適性を証明し,QRAMの新たな利用方法の必要性が示唆された。 重要な注意事項は、このトレードオフがQRAMデータの効率的な置換に強い仮定を必要とすることである。 最後に、QRAMを使わずに量子格子シービングのための回路を提供する。 我々の回路は、最高の古典的アルゴリズムよりも深い複雑さを持つが、指数的な量の量子ビットを必要とする。 我々の知る限りでは、これは標準量子回路モデルにおいてQRAMを使わずに格子シービングを行うための最初の量子スピードアップである。 この回路が,クエリの複雑さを考慮に入れた下位境界に矛盾しない理由を説明する。

関連論文リスト

• Systems Architecture for Quantum Random Access Memory [0.6386668251980657]
  量子ランダムアクセスメモリ(QRAM)は、量子クエリを実現するための有望なアーキテクチャである。 提案するQRAMの固有バイアスノイズレジリエンスを、NISQ(Noisy Intermediate-Scale Quantum)またはFTQC(Fault-Tolerant Quantum Computing)ハードウェア上で実装する方法を示す。
  論文  参考訳（メタデータ） (2023-06-05T20:52:28Z)
• QRAM: A Survey and Critique [1.52292571922932]
  量子ランダムアクセスメモリ(QRAM)は、それ自体が量子状態であるアドレスに基づいてデータにアクセスするメカニズムである。 文献から得られた2つの主要なQRAMカテゴリ(アクティブとパッシブ)を使用します。 結論として、既存の提案では、安価でスケーラブルに受動的なQRAMはありえないと結論付けている。
  論文  参考訳（メタデータ） (2023-05-17T15:48:48Z)
• Quantum Random Access Memory For Dummies [4.608607664709314]
  量子ランダムアクセスメモリ(QRAM)は、量子コンピューティングの領域に革命をもたらす可能性がある。 QRAMは量子コンピューティングの原理を使って量子や古典的なデータを効率的に保存し、修正する。
  論文  参考訳（メタデータ） (2023-05-02T03:24:16Z)
• Approximate Quantum Random Access Memory Architectures [7.509129971169722]
  量子超越性(Quantum supremacy)は、よく知られた量子アルゴリズムを用いた多くのアプリケーションにおいて、量子形式におけるデータの可用性に依存している。 本稿では、アドレス行を入力として取り出し、これらのアドレス行の対応するデータを出力として出力する、近似パラメトリック量子回路(PQC)ベースのQRAMを提案する。 提案するPQCベースのQRAMの2つの応用として、バイナリデータのストレージと機械学習データセットのストレージを分類する。
  論文  参考訳（メタデータ） (2022-10-24T19:53:28Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• A hybrid quantum image edge detector for the NISQ era [62.997667081978825]
  本稿では,量子人工ニューロンのアイデアに基づく量子エッジ検出のハイブリッド手法を提案する。 提案手法は, 量子コンピュータ, 特に現在ノイズの多い中間量子時代において, 実際に実装することができる。
  論文  参考訳（メタデータ） (2022-03-22T22:02:09Z)
• Towards understanding the power of quantum kernels in the NISQ era [79.8341515283403]
  量子カーネルの利点は,大規模データセット,計測回数の少ないもの,システムノイズなどにおいて消失することを示した。 我々の研究は、NISQデバイス上で量子優位性を得るための先進量子カーネルの探索に関する理論的ガイダンスを提供する。
  論文  参考訳（メタデータ） (2021-03-31T02:41:36Z)
• Quantum random access memory via quantum walk [0.0]
  量子ウォークを用いた新しい量子ランダムアクセスメモリ(qRAM)が提供される。 したがって、O(n) ステップのみが量子重ね合わせ状態の形で O(2n) データにアクセスおよび取得するために必要となる。
  論文  参考訳（メタデータ） (2020-08-31T04:54:12Z)
• 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)
• Parallelising the Queries in Bucket Brigade Quantum RAM [69.43216268165402]
  量子アルゴリズムは、しばしばデータベースのような方法で格納された情報にアクセスするために量子RAM(QRAM)を使用する。 本稿では,Clifford+Tゲートの並列性を利用して,効率的なクエリ時間を大幅に短縮する手法を提案する。 理論的には、フォールトトレラントバケットの量子RAMクエリは古典的なRAMの速度とほぼ一致する。
  論文  参考訳（メタデータ） (2020-02-21T14:50:03Z)

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

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