論文の概要: Tight Quantum Time-Space Tradeoffs for Function Inversion
- arxiv url: http://arxiv.org/abs/2006.05650v2
- Date: Sun, 22 Nov 2020 19:44:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-16 03:00:00.819097
- Title: Tight Quantum Time-Space Tradeoffs for Function Inversion
- Title（参考訳）: 関数反転のための高量子時間空間トレードオフ
- Authors: Kai-Min Chung, Siyao Guo, Qipeng Liu, Luowen Qian
- Abstract要約: 量子アドバイスであっても、アルゴリズムがランダム関数を反転させるためには、$ST + T2 = tildeOmega(N)$が必要である。
また、Yaoのボックス問題とソルト暗号に対する量子時間空間の低いバウンダリを証明した。
- 参考スコア（独自算出の注目度）: 7.895232155155041
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In function inversion, we are given a function $f: [N] \mapsto [N]$, and want
to prepare some advice of size $S$, such that we can efficiently invert any
image in time $T$. This is a well studied problem with profound connections to
cryptography, data structures, communication complexity, and circuit lower
bounds. Investigation of this problem in the quantum setting was initiated by
Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of
$ST^2 = \tilde\Omega(N)$ for random permutations against classical advice,
leaving open an intriguing possibility that Grover's search can be sped up to
time $\tilde O(\sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019),
and Chung, Liao, and Qian (2019) extended the argument for random functions and
quantum advice, but the lower bound remains $ST^2 = \tilde\Omega(N)$.
In this work, we prove that even with quantum advice, $ST + T^2 =
\tilde\Omega(N)$ is required for an algorithm to invert random functions. This
demonstrates that Grover's search is optimal for $S = \tilde O(\sqrt{N})$,
ruling out any substantial speed-up for Grover's search even with quantum
advice. Further improvements to our bounds would imply new classical circuit
lower bounds, as shown by Corrigan-Gibbs and Kogan (2019).
To prove this result, we develop a general framework for establishing quantum
time-space lower bounds. We further demonstrate the power of our framework by
proving quantum time-space lower bounds for Yao's box problem and salted
cryptography.
- Abstract（参考訳）: 関数逆転では、関数 $f: [N] \mapsto [N]$ が与えられます。
これは、暗号、データ構造、通信複雑性、回路下限と深いつながりを持つ、よく研究された問題である。
量子環境におけるこの問題の調査は、Nayebi, Aaronson, Belovs, Trevisan (2015) によって始められ、古典的アドバイスに対するランダムな置換に対して$ST^2 = \tilde\Omega(N)$の低い境界を証明した。
Hhan, Xgawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) による最近の研究はランダム関数と量子アドバイスの議論を拡張したが、下限は $ST^2 = \tilde\Omega(N)$ のままである。
この研究では、量子アドバイスでさえも、ランダム関数を逆転させるアルゴリズムには$ST + T^2 = \tilde\Omega(N)$が必要であることを証明している。
これはグロバーの探索が$S = \tilde O(\sqrt{N})$に対して最適であることを示し、量子アドバイスでさえグロバーの探索に対する実質的なスピードアップを除外する。
我々の境界に対するさらなる改良は、コリガン・ギブスとkogan (2019) が示したように、新しい古典回路の下限を意味する。
この結果を証明するために,量子時空間下界を確立するための汎用フレームワークを開発した。
さらに,Yaoのボックス問題とソルト暗号に対する量子時空間下界の証明によって,我々のフレームワークのパワーを実証する。
関連論文リスト
- Testing classical properties from quantum data [0.0]
古典的テスタをサンプルに制限する場合のスピードアップは,量子データを使用するテスタによって回復可能であることを示す。
単調性テストでは、古典的に必要とされる2Omega(sqrtn)$サンプルと比較して、$tildemathcalO(n2)$関数状態コピーを使用する量子アルゴリズムを提供する。
Omega(n1/4)$ および $Omega(n)$ の古典的下限と比較し,対称性と三角形自由度に関する $mathcalO(1)$-copy テスタも提示する。
論文 参考訳（メタデータ） (2024-11-19T18:52:55Z) - Achieving quantum advantage in a search for a minimal Goldbach partition with driven atoms in tailored potentials [15.236546465767026]
ゴールドバッハ予想は、自然数 $N$ が 2 より大きいときでも、$p$ と $p'$ の和として書けると述べている。
偶数$N$が与えられたとき、最小のゴールドバッハ分割$N=p+p'$の存在を検出するための量子アナログプロトコルを提案する。
論文 参考訳（メタデータ） (2024-03-31T01:29:16Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Time-Efficient Quantum Entropy Estimator via Samplizer [7.319050391449301]
量子状態のエントロピーを推定することは、量子情報の基本的な問題である。
我々は、フォン・ノイマンエントロピー $S(rho)$ と R'enyi entropy $S_alpha(rho)$ を$N$次元量子状態 $rho として推定するための時間効率のよい量子アプローチを導入する。
論文 参考訳（メタデータ） (2024-01-18T12:50:20Z) - 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) - Matching Triangles and Triangle Collection: Hardness based on a Weak
Quantum Conjecture [0.8924669503280332]
これら2つのグラフ問題のいずれかに対する$n1.5-epsilon$の時間量子アルゴリズムは、k-SAT, 3SUM, APSPの量子アルゴリズムを高速化することを示す。
また、データ構造とアムバイニスの変動時間探索を慎重に利用する必要がある量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-07-22T13:16:50Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
ランダム関数 $f : [N] rightarrow [N]$ の衝突対を量子コンピュータを用いて探索する。
利用可能なメモリのサイズが制限された場合、関数に対するクエリの数は大幅に増加しなければなりません。
論文 参考訳（メタデータ） (2020-02-20T18:48:51Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。