論文の概要: Efficient unitary designs and pseudorandom unitaries from permutations

• arxiv url: http://arxiv.org/abs/2404.16751v2
• Date: Fri, 01 Nov 2024 01:49:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-04 14:32:25.470520
• Title: Efficient unitary designs and pseudorandom unitaries from permutations
• Title（参考訳）: 置換による効率的なユニタリ設計と擬似ランダムユニタリ
• Authors: Chi-Fang Chen, Adam Bouland, Fernando G. S. L. Brandão, Jordan Docter, Patrick Hayden, Michelle Xu,
• Abstract要約: 実測値の最初の2Omega(n)$モーメントと無作為位相によるS(N)$置換の指数和が一致することを示す。 我々の証明の核心は、ランダム行列理論における大次元(大きな=N$)展開と方法の間の概念的接続である。
• 参考スコア（独自算出の注目度）: 35.66857288673615
• License:
• Abstract: In this work we give an efficient construction of unitary $k$-designs using $\tilde{O}(k\cdot poly(n))$ quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over $S(N)$ to random unitaries over $U(N)$ for $N=2^n$. In particular, we show that products of exponentiated sums of $S(N)$ permutations with random phases approximately match the first $2^{\Omega(n)}$ moments of the Haar measure. By substituting either $\tilde{O}(k)$-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-$N$ by interpolating from the much simpler large-$N$ limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-$N$ expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension $N$.
• Abstract（参考訳）: 本研究では、$\tilde{O}(k\cdot poly(n))$量子ゲートを用いたユニタリな$k$-設計の効率的な構成と、並列セキュア擬似ランダムユニタリ(PRU)の効率的な構成を与える。 どちらの結果も、$S(N)$から$U(N)$から$N=2^n$のランダムなユニタリにランダムな置換を持ち上げる効率的な量子アルゴリズムを提供することによって得られる。 特に、ランダム位相の指数和$S(N)$置換の積は、ハール測度の最初の270Omega(n)}$モーメントとほぼ一致することを示す。 ランダムな置換の代わりに$\tilde{O}(k)$-wise independent permutations または Quantum-secure pseudorandom permutations (PRPs) を置換することにより、上記の結果が得られる。 証明の中心は、ランダム行列理論における大次元(大域=N$)展開と多項式法の間の概念的接続であり、より単純な大域=N$極限から補間することにより、有限$N$でのクエリ下界の証明を可能にする。 重要な技術的ステップは、低次大N$展開を持つ分割代数の既約表現の正規直交基底を示すことである。 これにより、判別確率は次元$N$の低次有理多項式であることを示すことができる。

関連論文リスト

• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  可逆回路と量子回路は、交互群 $mathrmAlt (2n)$ とユニタリ群 $mathrmSU (2n)$ のランダムウォークを形成する。 ランダム可逆回路のギャップは、すべての$tgeq 1$に対して$Omega(n-3)$であり、ランダム量子回路のギャップは$Omega(n-3)$ for $t leq Theta(2n/2)$であることを示す。
  論文  参考訳（メタデータ） (2024-06-11T17:23:16Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。 また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T00:50:57Z)
• Simple constructions of linear-depth t-designs and pseudorandom unitaries [40.72668922727092]
  一様ランダムなユニタリ、すなわちハール測度から引き出されたユニタリは、多くの有用な性質を持つが、効率的に実装することはできない。 $t-設計はハール測度の最初の$tモーメントを再現するランダムユニタリーであり、擬ランダムユニタリー(PRU)はハール測度と計算的に区別できないランダムユニタリーである。
  論文  参考訳（メタデータ） (2024-04-19T06:13:02Z)
• Efficient Unitary T-designs from Random Sums [0.6640968473398456]
  Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。 我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
  論文  参考訳（メタデータ） (2024-02-14T17:32:30Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  我々は、ロバスト量子回路の複雑さの増大に新たな低い境界を証明した。 局所ゲートを持つランダム量子回路に対して、$SU(4)$の部分群から引き出された2つの境界を示す。
  論文  参考訳（メタデータ） (2023-03-29T18:06:03Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• 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)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  エントロピー正則化で最適な輸送を解くには、ベクトルに繰り返し適用される$ntimes n$ kernel matrixを計算する必要がある。 代わりに、$c(x,y)=-logdotpvarphi(x)varphi(y)$ ここで$varphi$は、地上空間から正のorthant $RRr_+$への写像であり、$rll n$である。
  論文  参考訳（メタデータ） (2020-06-12T10:21:40Z)

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

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