論文の概要: Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs

• arxiv url: http://arxiv.org/abs/2002.08944v5
• Date: Thu, 16 Mar 2023 22:26:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-25 04:15:11.596290
• Title: Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs
• Title（参考訳）: 複数の衝突対を見つけるための量子時間空間トレードオフ
• Authors: Yassine Hamoudi and Fr\'ed\'eric Magniez
• Abstract要約: ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。 利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of finding $K$ collision pairs in a random function $f : [N] \rightarrow [N]$ by using a quantum computer. We prove that the number of queries to the function in the quantum random oracle model must increase significantly when the size of the available memory is limited. Namely, we demonstrate that any algorithm using $S$ qubits of memory must perform a number $T$ of queries that satisfies the tradeoff $T^3 S \geq \Omega(K^3 N)$. Classically, the same question has only been settled recently by Dinur [Eurocrypt'20], who showed that the Parallel Collision Search algorithm of van Oorschot and Wiener achieves the optimal time-space tradeoff of $T^2 S = \Theta(K^2 N)$. Our result limits the extent to which quantum computing may decrease this tradeoff. Our method is based on a novel application of Zhandry's recording query technique [Crypto'19] for proving lower bounds in the exponentially small success probability regime. As a second application, we give a simpler proof of the time-space tradeoff $T^2 S \geq \Omega(N^3)$ for sorting $N$ numbers on a quantum computer, which was first obtained by Klauck, \v{S}palek and de Wolf [K\v{S}W07].
• Abstract（参考訳）: 量子コンピュータを用いてランダム関数 $f : [n] \rightarrow [n]$ において、k$衝突対を見つける問題を調べる。 我々は、利用可能なメモリのサイズが限られている場合、量子ランダムオラクルモデルの関数へのクエリ数が著しく増加することを証明します。 すなわち、$s$ qubitsのメモリを使用するアルゴリズムは、$t^3 s \geq \omega(k^3 n)$を満たす数$t$のクエリを実行しなければならない。 古典的には、Dinur [Eurocrypt'20] は、ファン・オースコートとウィーナーの並列衝突探索アルゴリズムが、T^2 S = \Theta(K^2 N)$の最適時間空間トレードオフを達成することを示した。 我々の結果は、量子コンピューティングがこのトレードオフを減らしうる範囲を制限する。 本手法は,Zhandry's recording query technique [Crypto'19] を用いて,指数的に小さな成功確率系における下界の証明を行う。 第2の応用として、Klauck, \v{S}palek と de Wolf [K\v{S}W07] によって最初に得られた量子コンピュータ上の$N$数値をソートするための時間空間トレードオフ $T^2 S \geq \Omega(N^3)$ のより単純な証明を与える。

関連論文リスト

• Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
  古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。 この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
  論文  参考訳（メタデータ） (2024-11-04T19:40:01Z)
• Quantum Speedups for Bayesian Network Structure Learning [0.0]
  ノードが$n$のネットワークの場合、最も高速な既知のアルゴリズムは、最悪の場合は$O(cn)$で実行され、20年で改善はない。 近年の量子コンピューティングの発展に触発されて、BNSLが量子スピードアップを認めているかどうかを問う。 我々は、$c leq 1.817$と$c leq 1.982$の2つのアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-05-31T09:15:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Solving the sampling problem of the Sycamore quantum circuits [6.0604034858265345]
  本研究では,GoogleのSycamore量子回路の出力分布から,目的の忠実度を持つ独立サンプルを生成する問題について検討する。 本稿では,対応するテンソルネットワークを1回だけ契約することで,この問題を古典的に解決する手法を提案する。 530ドルキュービットと20ドルサイクルのSycamore量子超越回路では、無相関なビットストリングが100万個発生しました。
  論文  参考訳（メタデータ） (2021-11-04T17:13:09Z)
• Unstructured Search by Random and Quantum Walk [0.0]
  ソートされていない$N$要素のリストのエントリを探すと、古典的なコンピュータのオラクルに$O(N)$クエリーを取るのが有名である。 離散的かつ連続的なランダムウォークと量子ウォークがこの問題をいかに解決するかを導出する。
  論文  参考訳（メタデータ） (2020-11-30T04:00:31Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。 最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
  論文  参考訳（メタデータ） (2020-07-23T10:50:42Z)
• Tight Quantum Time-Space Tradeoffs for Function Inversion [7.895232155155041]
  量子アドバイスであっても、アルゴリズムがランダム関数を反転させるためには、$ST + T2 = tildeOmega(N)$が必要である。 また、Yaoのボックス問題とソルト暗号に対する量子時間空間の低いバウンダリを証明した。
  論文  参考訳（メタデータ） (2020-06-10T04:23:26Z)
• 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)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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