論文の概要: 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のボックス問題とソルト暗号に対する量子時空間下界の証明によって,我々のフレームワークのパワーを実証する。
関連論文リスト
- Quantum One-Wayness of the Single-Round Sponge with Invertible
Permutations [55.2480439325792]
スポンジハッシュ(Spnge hashing)は、現在の国際ハッシュ関数標準SHA-3の基盤となる暗号ハッシュアルゴリズムの新たなクラスである。
ウンルーが提唱した「二重側ゼロ探索」予想を証明する。
また、ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要であることも示している。
論文 参考訳(メタデータ) (2024-03-07T18:46:58Z) - 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) - Random quantum circuits are approximate unitary $t$-designs in depth
$O\left(nt^{5+o(1)}\right)$ [0.0]
ランダム量子回路は深さ$O(nt5+o(1))$で近似単位の$t$-designsを生成する。
我々の手法は、ガオの量子団結境界とクリフォード群の理にかなわない有効性を含んでいる。
論文 参考訳(メタデータ) (2022-03-30T18:02:08Z) - Optimal (controlled) quantum state preparation and improved unitary
synthesis by quantum circuits with any number of ancillary qubits [20.270300647783003]
制御量子状態準備(CQSP)は、与えられた$n$-qubit状態に対するすべての$iin 0,1k$に対して、$|irangle |0nrangleから |irangle |psi_irangle $への変換を提供することを目的としている。
我々は、深さ$Oleft(n+k+frac2n+kn+k+mright)$とサイズ$Oleft(2n+kright)$のCQSPを実装するための量子回路を構築する。
論文 参考訳(メタデータ) (2022-02-23T04:19:57Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Improved spectral gaps for random quantum circuits: large local
dimensions and all-to-all interactions [0.0]
我々は、$D$のランダム量子回路がスペクトルギャップスケーリングを$Omega(n-1)$とすることを示し、$t$が局所次元と比較して小さいことを仮定する:$t2leq O(q)$。
2つ目の結果は、全ての相互作用を持つランダム量子回路に対して、以下に$Omega(n-1log-1(n) t-alpha(q))$で有界な非条件スペクトルギャップである。
論文 参考訳(メタデータ) (2020-12-09T19:00:50Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。