論文の概要: MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
- arxiv url: http://arxiv.org/abs/2505.14461v1
- Date: Tue, 20 May 2025 14:57:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-21 14:49:53.441824
- Title: MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations
- Title（参考訳）: 量子入力サンプリングと擬似定規によるマイクロクリプト推定:構成と分離
- Authors: Mohammed Barhoush, Ryo Nishimaki, Takashi Yamakawa,
- Abstract要約: 量子暗号プリミティブの2つの自然な緩和について検討する。
1つ目は、ランダムに一様にサンプリングされるのではなく、量子アルゴリズムによって入力が生成される量子入力サンプリングである。
2つ目の緩和である $bot$-pseudodeterminism は、入力の逆多項式分数に対して出力を特別な記号 $bot$ にすることで決定論の要求を緩和する。
- 参考スコア（独自算出の注目度）: 9.738636411374223
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate two natural relaxations of quantum cryptographic primitives. The first involves quantum input sampling, where inputs are generated by a quantum algorithm rather than sampled uniformly at random. Applying this to pseudorandom generators ($\textsf{PRG}$s) and pseudorandom states ($\textsf{PRS}$s), leads to the notions denoted as $\textsf{PRG}^{qs}$ and $\textsf{PRS}^{qs}$, respectively. The second relaxation, $\bot$-pseudodeterminism, relaxes the determinism requirement by allowing the output to be a special symbol $\bot$ on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between bounded-query logarithmic-size $\textsf{PRS}^{qs}$, logarithmic-size $\textsf{PRS}^{qs}$, and $\textsf{PRG}^{qs}$. Moreover, we establish that $\textsf{PRG}^{qs}$ can be constructed from $\bot$-$\textsf{PRG}$s, which in turn were built from logarithmic-size $\textsf{PRS}$. Interestingly, these relations remain unknown in the uniform key setting. To further justify these relaxed models, we present black-box separations. Our results suggest that $\bot$-pseudodeterministic primitives may be weaker than their deterministic counterparts, and that primitives based on quantum input sampling may be inherently weaker than those using uniform sampling. Together, these results provide numerous new insights into the structure and hierarchy of primitives within MicroCrypt.
- Abstract（参考訳）: 量子暗号プリミティブの2つの自然な緩和について検討する。
1つ目は、ランダムに一様にサンプリングされるのではなく、量子アルゴリズムによって入力が生成される量子入力サンプリングである。
これを擬似乱数生成($\textsf{PRG}$s)と擬似乱数状態($\textsf{PRS}$s)に適用すると、それぞれ$\textsf{PRG}^{qs}$と$\textsf{PRS}^{qs}$と表記される概念が導かれる。
2つ目の緩和である $\bot$-pseudodeterminism は、入力の逆多項式の分数に対して出力を特別な記号 $\bot$ にすることで決定論の要求を緩和する。
有界クエリ対数サイズ $\textsf{PRS}^{qs}$, logarithmic-size $\textsf{PRS}^{qs}$, $\textsf{PRG}^{qs}$ の同値性を示す。
さらに、$\textsf{PRG}^{qs}$は$\bot$-$\textsf{PRG}$sから構築でき、対数サイズ$\textsf{PRS}$から構築される。
興味深いことに、これらの関係は均一なキー設定で不明である。
これらの緩和モデルをさらに正当化するために,ブラックボックス分離を提案する。
以上の結果から,$\bot$-pseudodeterministic プリミティブは決定論的プリミティブよりも弱い可能性が示唆された。
これらの結果は、MicroCrypt内のプリミティブの構造と階層に関する多くの新しい洞察を提供する。
関連論文リスト
- Lower bounds on entanglement entropy without twin copy [0.0]
我々は、断熱的に準備された基底状態のビットストリングと関連するシャノンエントロピー$S_ABX$を計算する。
広い範囲の格子間隔とデチューニングにおいて、$IX_AB$は通常、$S_AvN$が大きい地域では$S_AvN$より20%低い。
論文 参考訳（メタデータ） (2024-04-15T17:02:17Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。
固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
論文 参考訳（メタデータ） (2023-12-23T15:52:46Z) - Weak Schur sampling with logarithmic quantum memory [0.0]
弱いシュアサンプリングのための新しいアルゴリズムを提案する。
我々のアルゴリズムは、既約表現をインデックスするヤングラベルと対称群の多重度ラベルの両方を効率的に決定する。
論文 参考訳（メタデータ） (2023-09-21T10:02:46Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。
我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。
次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
論文 参考訳（メタデータ） (2020-06-02T16:38:36Z) - Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [8.401078947103475]
Googleの53量子ビット回路のノイズ量子シミュレーションでは、C$は2.24pm0.21)times10-3$の忠実度値を得た。
この結果は,線形XEBテストの不正化が,量子回路の完全なシミュレーションを実現するよりも容易であることを示す証拠とみなすことができる。
論文 参考訳（メタデータ） (2020-05-05T18:01:48Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。