論文の概要: Finding many Collisions via Reusable Quantum Walks
- arxiv url: http://arxiv.org/abs/2205.14023v1
- Date: Fri, 27 May 2022 14:50:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-11 14:04:32.307386
- Title: Finding many Collisions via Reusable Quantum Walks
- Title（参考訳）: 再利用可能な量子ウォークで多くの衝突を見つける
- Authors: Xavier Bonnetain, Andr\'e Chailloux, Andr\'e Schrottenloher, Yixin
Shen
- Abstract要約: 衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
- 参考スコア（独自算出の注目度）: 1.376408511310322
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Given a random function $f$ with domain $[2^n]$ and codomain $[2^m]$, with $m
\geq n$, a collision of $f$ is a pair of distinct inputs with the same image.
Collision finding is an ubiquitous problem in cryptanalysis, and it has been
well studied using both classical and quantum algorithms. Indeed, the quantum
query complexity of the problem is well known to be $\Theta(2^{m/3})$, and
matching algorithms are known for any value of $m$. The situation becomes
different when one is looking for multiple collision pairs. Here, for $2^k$
collisions, a query lower bound of $\Theta(2^{(2k+m)/3})$ was shown by Liu and
Zhandry (EUROCRYPT~2019). A matching algorithm is known, but only for
relatively small values of $m$, when many collisions exist. In this paper, we
improve the algorithms for this problem and, in particular, extend the range of
admissible parameters where the lower bound is met. Our new method relies on a
chained quantum walk algorithm, which might be of independent interest. It
allows to extract multiple solutions of an MNRS-style quantum walk, without
having to recompute it entirely: after finding and outputting a solution, the
current state is reused as the initial state of another walk. As an
application, we improve the quantum sieving algorithms for the shortest vector
problem (SVP), with a complexity of $2^{0.2563d + o(d)}$ instead of the
previous $2^{0.2570d + o(d)}$.
- Abstract（参考訳）: ランダム関数 $f$ with domain $[2^n]$ と co domain $[2^m]$, with $m \geq n$ が与えられたとき、$f$ の衝突は、同じ画像を持つ異なる入力の対である。
衝突発見は暗号解析においてユビキタスな問題であり、古典アルゴリズムと量子アルゴリズムの両方を用いてよく研究されている。
実際、問題の量子クエリの複雑さは$\Theta(2^{m/3})$であることがよく知られており、マッチングアルゴリズムは$m$の値で知られている。
複数の衝突対を探している場合、状況は異なる。
ここでは、2^k$の衝突に対して、クエリローバウンドの$\Theta(2^{(2k+m)/3})$がLiu and Zhandry (EUROCRYPT~2019)によって示された。
マッチングアルゴリズムは知られているが、衝突が多く存在する場合、比較的小さな$m$の値に限られる。
本稿では,この問題に対するアルゴリズムを改良し,特に下界が満たされる許容パラメータの範囲を広げる。
我々の新しい手法は、独立した関心を持つかもしれない連鎖量子ウォークアルゴリズムに依存している。
mnrsスタイルの量子ウォークの複数の解を全て再計算することなく抽出することができる: 解を見つけて出力した後、現在の状態を別のウォークの初期状態として再利用する。
アプリケーションとして、最短ベクトル問題(svp)に対する量子シービングアルゴリズムを改善し、従来の$^{0.2570d + o(d)}$の代わりに$2^{0.2563d + o(d)}$という複雑さを持つ。
関連論文リスト
- Even-Cycle Detection in the Randomized and Quantum CONGEST Model [1.5566524830295314]
すべての$kgeq 2$に対して、$C_2k$-freenessは、CONGESTモデルで$O(n1-1/k)$ラウンドで決定できることを示す。
また、量子設定において、円複雑度$tilde O(nfrac12-frac12k)$を達成するためのアルゴリズムの量子化方法を示す。
論文 参考訳（メタデータ） (2024-02-19T10:23:37Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - 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) - Optimal exact quantum algorithm for the promised element distinctness
problem [0.2741266294612775]
要素差分問題は、文字列$x=(x_1,ldots,x_N)$の$N$要素が同じ値の2つの要素を含むかどうかを決定することである。
保証問題に対する厳密な量子アルゴリズムを提案するが、これにはO(N2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2022-11-10T09:33:13Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳（メタデータ） (2022-08-14T02:49:26Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。