論文の概要: A Note on Output Length of One-Way State Generators and EFIs

• arxiv url: http://arxiv.org/abs/2312.16025v4
• Date: Sat, 28 Sep 2024 16:12:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-01 22:00:06.683341
• Title: A Note on Output Length of One-Way State Generators and EFIs
• Title（参考訳）: ワンウェイ状態発電機とEFIの出力長に関する一考察
• Authors: Minki Hhan, Tomoyuki Morimae, Takashi Yamakawa,
• Abstract要約: 本研究では,一方向状態発生器(OWSG)の出力長,より弱い変種,EFIの出力長について検討する。 我々は、$O(log lambda)$-qubit出力を持つOWSGは存在しないことを示した。 また、$O(log lambda)$-qubit EFIが存在しないことも証明します。
• 参考スコア（独自算出の注目度）: 8.988985347178424
• License:
• Abstract: We study the output length of one-way state generators (OWSGs), their weaker variants, and EFIs. - Standard OWSGs. Recently, Cavalar et al. (arXiv:2312.08363) give OWSGs with $m$-qubit outputs for any $m=\omega(\log \lambda)$, where $\lambda$ is the security parameter, and conjecture that there do not exist OWSGs with $O(\log \log \lambda)$-qubit outputs. We prove their conjecture in a stronger manner by showing that there do not exist OWSGs with $O(\log \lambda)$-qubit outputs. This means that their construction is optimal in terms of output length. - Inverse-polynomial-advantage OWSGs. Let $\epsilon$-OWSGs be a parameterized variant of OWSGs where a quantum polynomial-time adversary's advantage is at most $\epsilon$. For any constant $c\in \mathbb{N}$, we construct $\lambda^{-c}$-OWSGs with $((c+1)\log \lambda+O(1))$-qubit outputs assuming the existence of OWFs. We show that this is almost tight by proving that there do not exist $\lambda^{-c}$-OWSGs with at most $(c\log \lambda-2)$-qubit outputs. - Constant-advantage OWSGs. For any constant $\epsilon>0$, we construct $\epsilon$-OWSGs with $O(\log \log \lambda)$-qubit outputs assuming the existence of subexponentially secure OWFs. We show that this is almost tight by proving that there do not exist $O(1)$-OWSGs with $((\log \log \lambda)/2+O(1))$-qubit outputs. - Weak OWSGs. We refer to $(1-1/\mathsf{poly}(\lambda))$-OWSGs as weak OWSGs. We construct weak OWSGs with $m$-qubit outputs for any $m=\omega(1)$ assuming the existence of exponentially secure OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with $O(1)$-qubit outputs. - EFIs. We show that there do not exist $O(\log \lambda)$-qubit EFIs. We show that this is tight by proving that there exist $\omega(\log \lambda)$-qubit EFIs assuming the existence of exponentially secure PRGs.
• Abstract（参考訳）: 本研究では,一方向状態発生器(OWSG)の出力長,より弱い変種,EFIの出力長について検討する。 -標準OWSG。 最近、Cavalar et al (arXiv:2312.08363) は、$m =omega(\log \lambda)$に対して$m$-qubit出力を持つ OWSG を与え、$\lambda$ はセキュリティパラメータであり、$O(\log \log \lambda)$-qubit出力を持つ OWSG が存在しないことを予想している。 我々は、それらの予想をより強い方法で証明し、$O(\log \lambda)$-qubit 出力を持つ OWSG が存在しないことを示す。 これは、それらの構成が出力長の点で最適であることを意味する。 -逆多項式アドバンテージOWSG。 例えば、$\epsilon$-OWSGs を OWSG のパラメータ化された変種とし、量子多項式時間反転の利点は最大$\epsilon$ である。 任意の定数 $c\in \mathbb{N}$ に対して、OWF の存在を仮定した $((c+1)\log \lambda+O(1))$-qubit 出力で $\lambda^{-c}$-OWSGs を構成する。 これは、少なくとも$(c\log \lambda-2)$-qubit出力を持つ$\lambda^{-c}$-OWSGが存在しないことを証明することで、ほぼ厳密であることを示す。 -定値アドバンテージOWSG。 任意の定数 $\epsilon>0$ に対して、サブ指数的にセキュアな OWF の存在を前提として $O(\log \log \lambda)$-qubit 出力で $\epsilon$-OWSGs を構築する。 これは、$(((\log \log \lambda)/2+O(1))$-qubit出力を持つ$O(1)$-OWSGが存在しないことを証明することで、ほぼ厳密であることを示す。 -OWSGを弱める。 1-1/\mathsf{poly}(\lambda))$-OWSG を弱い OWSG と呼ぶ。 線形展開を伴う指数的に安全な OWF の存在を前提として、弱 OWSG を$m$-qubit 出力で任意の $m=\omega(1)$ に対して構成する。 我々は、$O(1)$-qubit 出力を持つ弱い OWSG が存在しないことを証明することで、これは厳密であることを示す。 -EFI。 O(\log \lambda)$-qubit EFIは存在しない。 指数的にセキュアなPRGの存在を前提とした$\omega(\log \lambda)$-qubit EFIが存在することを証明することによって、これは厳密であることを示す。

関連論文リスト

• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。 私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
  論文  参考訳（メタデータ） (2023-06-03T04:00:47Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。 PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。 UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
  論文  参考訳（メタデータ） (2023-03-10T00:11:18Z)
• 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)
• Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
  N]:=1,cdots,N$の整数列は、センサから受信される。 目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。 経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
  論文  参考訳（メタデータ） (2022-03-06T17:07:56Z)
• Private Convex Optimization via Exponential Mechanism [16.867534746193833]
  我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。 また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
  論文  参考訳（メタデータ） (2022-03-01T06:51:03Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• On polynomially many queries to NP or QMA oracles [0.0]
  本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。 まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。 次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
  論文  参考訳（メタデータ） (2021-11-03T15:29:01Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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