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

• arxiv url: http://arxiv.org/abs/2312.16025v1
• Date: Tue, 26 Dec 2023 12:27:10 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 15:12:09.050171
• Title: A Note on Output Length of One-Way State Generators
• Title（参考訳）: 一方向状態発生器の出力長に関する一考察
• Authors: Minki Hhan and Tomoyuki Morimae and Takashi Yamakawa
• Abstract要約: 本研究では,一方向状態発生器(OWSG)の出力長とその弱い変種について検討する。 我々は、$(log log lambda)/2+O(1)$-qubit出力を持つ$O(1)$-OWSGは存在しないことを示した。
• 参考スコア（独自算出の注目度）: 10.102718700226914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study output length of one-way state generators (OWSGs) and their weaker variants. - 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. - Constant-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 $\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 injective OWFs with linear expansion. We show that this is tight by proving that there do not exist weak OWSGs with $O(1)$-qubit outputs.
• Abstract（参考訳）: 単方向状態発生器(owsgs)の出力長と,その弱い変種について検討した。 -標準OWSG。 最近、Cavalar et al. (arXiv:2312.08363) は$m$-qubit出力を任意の$m=\omega(\log \lambda)$に対して与え、$\lambda$はセキュリティパラメータであり、$O(\log \log \lambda)$-qubit出力を持つOWSGは存在しないと推測する。 我々は、それらの予想をより強い方法で証明し、$O(\log \lambda)$-qubit 出力を持つ OWSG が存在しないことを示す。 これは、その構成が出力長の点で最適であることを意味する。 -定値アドバンテージOWSG。 例えば、$\epsilon$-OWSGs を OWSG のパラメータ化された変種とし、量子多項式時間反転の利点は最大$\epsilon$である。 任意の定数 $\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 が存在しないことを証明することで、これは厳密であることを示す。

関連論文リスト

• Nearly-Linear Time Seeded Extractors with Short Seeds [9.896415488558036]
  種子長と出力長の大きい種子抽出機の既設構造を時間内に実行した。 本研究では, コンデンサと古典的手法を併用して, 高ミンエントロピー源のシード抽出器を構築することにより, 強い抽出器が得られることを示す。 また、RAMモデルにおいて真に線形時間で評価できるトレビサン抽出器のインスタンス化を行う。
  論文  参考訳（メタデータ） (2024-11-12T01:19:35Z)
• 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)
• 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)

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

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