論文の概要: Pseudorandom unitaries with non-adaptive security
- arxiv url: http://arxiv.org/abs/2402.14803v1
- Date: Thu, 22 Feb 2024 18:56:37 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-23 13:52:38.255864
- Title: Pseudorandom unitaries with non-adaptive security
- Title(参考訳): 非適応的セキュリティを持つ疑似ランダムユニタリ
- Authors: Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen
- Abstract要約: 本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。
このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
- 参考スコア(独自算出の注目度): 43.15464425520681
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable
unitary operators that cannot be distinguished from Haar random unitaries by
any quantum polynomial-time algorithm with query access to the unitary. We
present a simple PRU construction that is a concatenation of a random Clifford
unitary, a pseudorandom binary phase operator, and a pseudorandom permutation
operator. We prove that this PRU construction is secure against non-adaptive
distinguishers assuming the existence of quantum-secure one-way functions. This
means that no efficient quantum query algorithm that is allowed a single
application of $U^{\otimes \mathrm{poly}(n)}$ can distinguish whether an
$n$-qubit unitary $U$ was drawn from the Haar measure or our PRU ensemble. We
conjecture that our PRU construction remains secure against adaptive
distinguishers, i.e. secure against distinguishers that can query the unitary
polynomially many times in sequence, not just in parallel.
- Abstract(参考訳): Pseudorandom Unitary (PRU) は、Haarランダムユニタリと区別できない効率的な実装可能なユニタリ演算子の集合である。
本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合である単純なPRU構成を提案する。
このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
つまり、$u^{\otimes \mathrm{poly}(n)}$の単一の応用を許される効率的な量子クエリアルゴリズムは、n$-qubitユニタリ$u$がハール測度または我々のpruアンサンブルから引き出されたかどうかを区別できない。
我々は、pru構成が適応的識別器に対して安全であり続けると仮定する。すなわち、単項多項式を並列ではなく列で何度もクエリできる識別器に対して安全である。
関連論文リスト
- 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) - Pseudorandom unitaries are neither real nor sparse nor noise-robust [0.0]
Pseudorandom quantum state (PRSs) と pseudorandom unitary (PRUs) は、任意の効率的な量子アルゴリズムに完全にランダムに現れながら効率的に構成可能であるという双対の性質を持っている。
PRSとPRUは、エラーが発生する確率が無視可能である場合にのみ存在し、ノイズの多い中間スケールおよび早期フォールトトレラント量子コンピュータでそれらの生成を除外する。
論文 参考訳(メタデータ) (2023-06-20T16:54:27Z) - Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
量子世界と古典世界における擬似ランダム性の概念の関連について研究する。
量子擬似乱数発生器(QPRGs)と呼ばれる擬似乱数発生器の自然変種は対数出力長PSRGsの存在に基づいていることを示す。
また、擬似乱数関数のような状態生成器と擬似乱数関数の関係についても検討する。
論文 参考訳(メタデータ) (2023-06-09T01:16:58Z) - Sampled Transformer for Point Sets [80.66097006145999]
スパース変換器は、連続列列列関数の普遍近似器でありながら、自己アテンション層の計算複雑性を$O(n)$に下げることができる。
我々は、追加の帰納バイアスを伴わずに点集合要素を直接処理できる$O(n)$複雑性サンプリング変換器を提案する。
論文 参考訳(メタデータ) (2023-02-28T06:38:05Z) - Pseudorandom (Function-Like) Quantum State Generators: New Definitions
and Applications [7.2051162210119495]
擬似ランダム状態の新しい定義、新しい性質、応用について検討する。
Pseudorandom quantum state (PRS) は、計算的にハールランドムと区別できない効率的な構成可能な状態である。
対数的な出力長を持つPSSジェネレータは、古典的な通信によるコミットメントと暗号化スキームを暗示している。
論文 参考訳(メタデータ) (2022-11-02T19:24:55Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
おもちゃの光ファイバーをベースとしたセットアップを用いてバイナリシリーズを生成し、そのランダム度をVilleの原理に従って評価する。
標準統計指標の電池、ハースト、コルモゴロフ複雑性、最小エントロピー、埋め込みのTakensarity次元、および拡張ディッキー・フラーとクワイアトコフスキー・フィリップス・シュミット・シン(英語版)でテストされ、ステーション指数をチェックする。
Toeplitz 抽出器を不規則級数に適用することにより得られる系列のランダム性のレベルは、非還元原料のレベルと区別できない。
論文 参考訳(メタデータ) (2022-08-31T17:39:29Z) - On the Connection Between Quantum Pseudorandomness and Quantum Hardware
Assumptions [1.4174475093445233]
本稿では,量子擬似ランダム性と量子ハードウェアの仮定との関係について述べる。
我々は、効率的な擬似ランダム量子状態(PRS)は、普遍的に鍛えられないqPUFの挑戦セットを構築するのに十分であることを示す。
その結果,既存のqPUFベースのクライアントサーバ識別プロトコルの効率性は,セキュリティ要件を損なうことなく向上できることを示した。
論文 参考訳(メタデータ) (2021-10-22T11:55:06Z) - Coherent randomized benchmarking [68.8204255655161]
独立サンプルではなく,異なるランダム配列の重ね合わせを用いることを示す。
これは、ベンチマーク可能なゲートに対して大きなアドバンテージを持つ、均一でシンプルなプロトコルにつながることを示す。
論文 参考訳(メタデータ) (2020-10-26T18:00:34Z) - Best Arm Identification for Cascading Bandits in the Fixed Confidence
Setting [81.70513857417106]
CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。
CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。
その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
論文 参考訳(メタデータ) (2020-01-23T16:47:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。