論文の概要: On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem

• arxiv url: http://arxiv.org/abs/2605.09957v1
• Date: Mon, 11 May 2026 04:07:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.510747
• Title: On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
• Title（参考訳）: スケーラブルな擬似単元と単元合成問題について
• Authors: Zvika Brakerski, Henry Yuen,
• Abstract要約: ランダムオラクルモデル(ROM)における統計的に安全なPRUであるROM-PRUの概念を定式化する。 我々は、ROM-PRU、近似ユニタリ設計、ユニタリ群上のエプシロンネット、およびユニタリ合成問題の間の新しい接続性を証明する。
• 参考スコア（独自算出の注目度）: 4.35722906481608
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the task of constructing pseudorandom unitaries (PRUs) with scalable security, i.e. families in which the security parameter may vary independently of the dimension (or input bit-length). It is not known whether scalable PRUs can be constructed. In this work we show that if scalable PRUs can be constructed via the prevailing paradigm for analyzing PRUs, then there would be a positive solution to the Aaronson-Kuperberg unitary synthesis problem, a longstanding question in quantum complexity theory about whether implementing arbitrary unitaries can be efficiently reduced to computing a Boolean function. Specifically, we formalize the notion of ROM-PRUs, which are statistically secure PRUs in the random oracle model (ROM). All prior known constructions of cryptographically secure PRUs are based on a ROM-PRU construction. We prove novel connections between ROM-PRUs, approximate unitary designs, epsilon-nets over the unitary group, and the unitary synthesis problem. In particular, we prove that any unitary synthesis algorithm (and thus any ROM-PRU) must use a classical oracle with input length (2 - o(1)) log d bits, where d is the dimension of the unitary to be implemented. This bound rules out all existing candidates for scalable PRUs in the literature. Together, these connections indicate that ROM-PRUs provide a fruitful idealized model for studying pseudorandom unitaries.
• Abstract（参考訳）: 我々は,セキュリティパラメータが次元(または入力ビット長)と独立に異なる場合のファミリーとして,スケーラブルなセキュリティを備えた擬似乱数ユニタリ(PRU)を構築することを考える。 スケーラブルなPRUを構築できるかどうかは不明である。 この研究で、スケーラブルなPRUが、PRUを解析するための一般的なパラダイムによって構築できるなら、Aaronson-Kuperbergユニタリ合成問題に対する正の解が存在し、任意のユニタリの実装がブール関数の計算に効率的に還元できるかどうかという量子複雑性理論における長年の疑問が存在する。 具体的には、ランダムオラクルモデル(ROM)における統計的に安全なPRUであるROM-PRUの概念を定式化する。 暗号的にセキュアなPRUの既知構成はすべてROM-PRU構造に基づいている。 我々は、ROM-PRU、近似ユニタリ設計、ユニタリ群上のエプシロンネット、およびユニタリ合成問題の間の新しい接続性を証明する。 特に、任意のユニタリ合成アルゴリズム(したがって、ROM-PRU)は入力長(2 - o(1))の対数dビットを持つ古典的なオラクルを使用しなければならない。 この境界は、文学におけるスケーラブルなPRUの既存の候補を全て除外する。 これらの関係は、ROM-PRUが擬似ランダムユニタリを研究するための実りある理想化されたモデルを提供することを示している。

関連論文リスト

• On Limits on the Provable Consequences of Quantum Pseudorandomness [2.683233968306505]
  量子擬似ランダム性が他のものから構築される可能性は低いことを示すいくつかの証拠を示す。 我々は、1つの量子擬似ランダム性が存在するが、別の擬似ランダム性が存在しない新しい神託世界を研究する。
  論文  参考訳（メタデータ） (2025-10-06T21:38:04Z)
• How to Construct Random Unitaries [2.8237889121096034]
  量子セキュアな片方向関数が存在すると仮定して、PRUが存在することを証明する。 本研究では,Haar-randomユニタリに対するクエリを量子コンピュータ上で効率的にシミュレートできることを証明した。
  論文  参考訳（メタデータ） (2024-10-14T03:07:36Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Pseudorandom unitaries with non-adaptive security [43.15464425520681]
  本稿では、ランダムなクリフォードユニタリ、擬似乱数二相演算子、擬似乱数置換演算子の結合であるPRU構成を提案する。 このPRU構造は、量子セキュア片方向関数の存在を前提として、非適応微分器に対して安全であることを示す。
  論文  参考訳（メタデータ） (2024-02-22T18:56:37Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。 我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
  論文  参考訳（メタデータ） (2023-05-22T17:43:34Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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