論文の概要: Random-Oracle Unitary Synthesis is Impossible

• arxiv url: http://arxiv.org/abs/2610.06700v1
• Date: Mon, 05 Oct 2026 16:59:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 23:32:47.76219
• Title: Random-Oracle Unitary Synthesis is Impossible
• Title（参考訳）: ランダムOracleユニタリ合成は不可能である
• Abstract要約: 本稿では,Haarランダムなユニタリを効率的に実装できるかどうかを問う,平均ケースのユニタリ合成問題を提案する。 次に、スーパーポリノミカルなクエリの低いバウンダリを示し、このモデルにおけるユニタリ合成は不可能であることを示す。 特に、ROM-PRUモデルでは、$n$ qubits上の$(N1+)$ユニタリ設計は行わない。
• 参考スコア（独自算出の注目度）: 0.9969485010222057
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case'' unitary synthesis problem, which asks whether it is possible to efficiently implement a Haar random unitary given access to a random Boolean function. We then demonstrate a superpolynomial query lower bound, establishing that unitary synthesis in this model is impossible. Along with our main result, we settle in the negative a question Brakerski and Yuen pose, of whether scalable pseudorandom unitaries (PRUs) can be implemented in the ROM-PRU model. In particular, we show that in the ROM-PRU model, no $Ω(N^{1+γ})$ unitary design on $n$ qubits, where $N=2^n$, can be efficiently achieved for any $γ> 0$. On the other hand, we construct an $O(N)$-design in $\text{poly}(n)$ queries in the same model, surpassing the previously best known results which constructed $O(\sqrt{N})$-designs.
• Abstract（参考訳）: 量子複雑性における主要なオープン問題はユニタリ合成の問題であり、すなわち、重ね合わせにおける古典的関数を評価する能力を考えると、任意のユニタリを効率的に実装することは可能か? 近年の Brakerski と Yuen (CRYPTO 2026) の業績に触発され,ランダムブール関数へのアクセスを与えられたハールランダムユニタリを効率的に実装できるかどうかを問う,'平均ケース' のユニタリ合成問題を提案する。 次に、スーパーポリノミカルなクエリの低いバウンダリを示し、このモデルにおけるユニタリ合成は不可能であることを示す。 ROM-PRUモデルにおいて,拡張性のある擬似乱数ユニタリ(PRU)を実装できるかどうかについて,Blakerski と Yuen の負の疑問を考察する。 特に、ROM-PRUモデルでは、$n$ qubits 上の$Ω(N^{1+γ})$ユニタリ設計は行わない。 一方、同じモデルで$O(N)$-designを$\text{poly}(n)$クエリで構築し、$O(\sqrt{N})$-designsを構成する最もよく知られた結果を上回る。

関連論文リスト

• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
  論文  参考訳（メタデータ） (2024-04-25T17:08:34Z)
• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。 本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
  論文  参考訳（メタデータ） (2023-10-13T05:39:42Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• 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)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。 また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:05:09Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Towards Optimal Separations between Quantum and Randomized Query Complexities [0.30458514384586394]
  入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。 任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
  論文  参考訳（メタデータ） (2019-12-29T01:42:31Z)

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

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