論文の概要: Simple constructions of linear-depth t-designs and pseudorandom unitaries

• arxiv url: http://arxiv.org/abs/2404.12647v1
• Date: Fri, 19 Apr 2024 06:13:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-22 16:05:28.721879
• Title: Simple constructions of linear-depth t-designs and pseudorandom unitaries
• Title（参考訳）: 線形深度t-設計と擬ランダムユニタリの簡単な構成
• Authors: Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen,
• Abstract要約: 一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。 $t-設計はハール測度の最初の$tモーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)はハール測度と計算的に区別できないランダムユニタリーである。
• 参考スコア（独自算出の注目度）: 40.72668922727092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that "look" sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$-designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$-designs and PRUs. For this, we introduce and analyse the "$PFC$ ensemble", the product of a random computational basis permutation $P$, a random binary phase operator $F$, and a random Clifford unitary $C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the $PFC$ ensemble to show the following: (1) Linear-depth $t$-designs. We give the first construction of a (diamond-error) approximate $t$-design with circuit depth linear in $t$. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $2t$-wise independent counterparts. (2) Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. (3) Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n + \omega(\log n)$ qubits, a small modification of our PRU construction achieves general adaptive security.
• Abstract（参考訳）: 一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。 このことは、ランダムなユニタリに関する長い研究の動機となり、それは十分にハールランダムに見えると同時に、実装も効率的である。 例えば、$t$-designsは、情報理論によってハール測度の最初の$t$モーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)は計算的にハール乱数と区別できないランダムユニタリーである。 本研究では,$t$-designs と PRUs を統一的に構築する。 このために、ランダムな計算基底置換である$P$、ランダムなバイナリ位相演算子$F$、ランダムなCliffordユニタリ$C$の積である「$PFC$アンサンブル」を導入、分析する。 このアンサンブルは、ハール測度の指数的に高いモーメントを再現することを示す。 すると、$PFC$アンサンブルをデランドマイズして、次のことを示せる: (1) Linear-depth $t$-designs。 回路深度線形な(ダイアモンドエラー)近似 $t$-design の最初の構成を$t$で与える。 これは、ランダム位相と置換演算子を2t$-wiseの独立な演算子に置き換えることで、$PFC$アンサンブルから続く。 2)非適応型PRU 我々は、適応的でないセキュリティを持つPRUの最初の構成、すなわちアール乱数から多項式時間区別器と区別できないユニタリを構築し、アービタリー状態においてユニタリを並列にクエリする。 これは、ランダム位相と置換演算子を擬似乱数に置き換えることで$PFC$アンサンブルから続く。 (3)適応的擬似乱数同型 等距離を$n$から$n + \omega(\log n)$ qubitsまで(ユニタリではなく)考えると、我々のPRU構造の小さな修正は一般的な適応セキュリティを実現する。

関連論文リスト

• Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
  普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。 ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
  論文  参考訳（メタデータ） (2024-10-21T19:37:35Z)
• How to Construct Random Unitaries [2.8237889121096034]
  量子セキュアな片方向関数が存在すると仮定して、PRUが存在することを証明する。 本研究では,Haar-randomユニタリに対するクエリを量子コンピュータ上で効率的にシミュレートできることを証明した。
  論文  参考訳（メタデータ） (2024-10-14T03:07:36Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
  論文  参考訳（メタデータ） (2024-04-25T17:08:34Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。 また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T00:50:57Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  Feistelの構築は擬似乱数置換とブロック暗号を構築するための基本的な技術である。 本稿では, アルゴリズム置換攻撃に対しても, 簡単な構成法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-15T04:29:24Z)
• Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
  実数値ユニタリは完全に擬似ランダムとは言えなくても、実数値ユニタリを諦めることなく、いくつかの擬似ランダム特性を得ることができることを示す。 我々の分析は、ランダムな(バイナリ)フェーズとランダムな計算ベイシスの置換を適用すると、さらに単純な構成になることを示している。
  論文  参考訳（メタデータ） (2024-03-25T12:37:50Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。 このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:56:37Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization [96.26317627118912]
  群分散ロバスト最適化(GDRO) オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。 分布依存収束率を導出できる重み付きGDROの新規な定式化。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)

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

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