論文の概要: Efficient unitary designs and pseudorandom unitaries from permutations
- arxiv url: http://arxiv.org/abs/2404.16751v1
- Date: Thu, 25 Apr 2024 17:08:34 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-26 13:01:06.725584
- 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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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$の低次有理多項式であることを示すことができる。
関連論文リスト
- Efficient Unitary T-designs from Random Sums [0.6640968473398456]
Unitary $T$-Designsは、量子アルゴリズム、ベンチマーク、トモグラフィ、通信における様々な応用において、量子情報において重要な役割を果たす。
我々は、$tildeO(T2 n2)$量子ゲートを用いたランダム行列理論による$T$-designsの新たな構成を提供する。
論文 参考訳(メタデータ) (2024-02-14T17:32:30Z) - Optimised Baranyai partitioning of the second quantised Hamiltonian [0.0]
第二量子化ハミルトン分割のためのバラナイ群法の実装と最適化について述べる。
この方法では、ハミルトニアンのスパーシリティを自然に処理し、ハミルトニアンを線形にスケーリングする群を$O(1)$で生成する。
また、余分な計算労力を伴わずに8ドルの係数でグループ数を減少させるスピン対称性の明示的な最適化も提示する。
論文 参考訳(メタデータ) (2023-11-20T15:04:05Z) - 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) - A generic quantum Wielandt's inequality [1.0152838128195465]
一般の場合とは対照的に、$k$が次数$Theta(log n)$であることを示す。
我々は、Projected Entangled Pair Stateの長年のオープンな問題に新たな光を当てた。
論文 参考訳(メタデータ) (2023-01-19T18:57:32Z) - 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) - Joint quasiprobability distribution on the measurement outcomes of
MUB-driven operators [2.9005223064604078]
メソッドは、Mutually Unbiased Basesに関連する正規直交可換作用素の完全な集合に基づいている。
準確率分布が非負である状態の集合を幾何学的に特徴づける。
集合は$(n2-1)$-次元凸ポリトープで、純状態は$n+1$、高次元の面は$n+1$、辺は$n3(n+1)/2$である。
論文 参考訳(メタデータ) (2021-01-20T13:10:26Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。