論文の概要: Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
- arxiv url: http://arxiv.org/abs/2407.07876v1
- Date: Wed, 10 Jul 2024 17:43:23 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-11 15:33:18.736434
- Title: Approximate Unitary $k$-Designs from Shallow, Low-Communication Circuits
- Title（参考訳）: 浅低周波回路からの近似ユニタリ$k$-Designs
- Authors: Nicholas LaRacuente, Felix Leditzky,
- Abstract要約: 近似ユニタリ$k$-デザインは、平均が最初の$k$モーメントまでのハールランダムアンサンブルに近いようなユニタリと測度のアンサンブルである。
我々はサブシステム間の通信がシステムサイズで$O(1)$である乗法誤り近似単位の$k$-designアンサンブルを構築する。
- 参考スコア（独自算出の注目度）: 6.844618776091756
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Random unitaries are useful in quantum information and related fields but hard to generate with limited resources. An approximate unitary $k$-design is an ensemble of unitaries and measure over which the average is close to a Haar (uniformly) random ensemble up to the first $k$ moments. A particularly strong notion of approximation bounds the distance from Haar randomness in relative error: the approximate design can be written as a convex combination involving an exact design and vice versa. We construct multiplicative-error approximate unitary $k$-design ensembles for which communication between subsystems is $O(1)$ in the system size. These constructions use the alternating projection method to analyze overlapping Haar twirls, giving a bound on the convergence speed to the full twirl with respect to the $2$-norm. Using the von Neumann subalgebra indices to replace system dimension, the 2-norm distance converts to relative error without introducing any additional dependence on system size. Via recursion on these constructions, we construct a scheme yielding relative error designs in $O \big ( (k \log k + \log m + \log(1/\epsilon) ) k\, \text{polylog}(k) \big )$ depth, where $m$ is the dimension of the complete system and $\epsilon$ the approximation error. This sublinear depth construction answers one variant of [Harrow and Mehraban 2023, Open Problem 1]. Moreover, entanglement generated by the sublinear depth scheme follows area laws on spatial lattices up to corrections logarithmic in the full system size.
- Abstract（参考訳）: ランダムユニタリは量子情報や関連分野において有用であるが、限られた資源で生成することは困難である。
近似ユニタリ$k$-デザインは、平均が最初の$k$モーメントまでの(一様)ランダムアンサンブルに近いようなユニタリと測度のアンサンブルである。
近似の特に強い概念は相対誤差におけるハールランダムネスからの距離の境界であり、近似設計は正確な設計を含む凸結合として記述できる。
我々はサブシステム間の通信がシステムサイズで$O(1)$である乗法誤り近似単位の$k$-designアンサンブルを構築する。
これらの構造は交互射影法を用いて重なり合うハール・ツワールを解析し、2ドルのノルムに関してフル・ツワールへの収束速度に制限を与える。
フォン・ノイマン部分代数指数を用いて系次元を置換し、2ノルム距離は系の大きさに付加的な依存を加えることなく相対誤差に変換する。
これらの構成を再帰することにより、$O \big ( (k \log k + \log m + \log(1/\epsilon) ) k\, \text{polylog}(k) \big )$ depth, ここで$m$はシステム全体の次元であり、$\epsilon$は近似誤差である。
この線形深度構成は[Harrow and Mehraban 2023, Open Issue 1]の1つの変種に答える。
さらに、下線深度スキームによって生じる絡み合いは、空間格子上の領域法則に従って、全系サイズで対数的な補正を行う。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Optimal Approximation of Zonoids and Uniform Approximation by Shallow
Neural Networks [2.7195102129095003]
以下の2つの問題について検討する。
1つ目は、$mathbbRd+1$の任意のソノイドがハウスドルフ距離で$n$の線分で近似できる誤差を決定することである。
2つ目は、変動空間上の浅いReLU$k$ニューラルネットワークの均一ノルムにおける最適近似率を決定することである。
論文 参考訳（メタデータ） (2023-07-28T03:43:17Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Multiscale regression on unknown manifolds [13.752772802705978]
マルチスケールで$mathcalM$に低次元座標を構築し、ローカルフィッティングによるマルチスケール回帰を行います。
本手法の一般化誤差を,事前のリッチクラス上で高い確率で有限サンプル境界を証明することによって解析する。
私たちのアルゴリズムは、サンプルサイズの準線形複雑性を持ち、定数は$D$で、指数は$d$です。
論文 参考訳（メタデータ） (2021-01-13T15:14:31Z) - Complexity of zigzag sampling algorithm for strongly log-concave
distributions [6.336005544376984]
強いログ凹分布に対するジグザグサンプリングアルゴリズムの計算複雑性について検討する。
ジグザグサンプリングアルゴリズムは, 計算コストが$obiglに匹敵するchi-squareの発散において, $varepsilon$ 誤差を達成することを証明した。
論文 参考訳（メタデータ） (2020-12-21T03:10:21Z) - Convergence of Sparse Variational Inference in Gaussian Processes
Regression [29.636483122130027]
計算コストが$mathcalO(log N)2D(log N)2)$の手法を推論に利用できることを示す。
論文 参考訳（メタデータ） (2020-08-01T19:23:34Z) - 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) - FANOK: Knockoffs in Linear Time [73.5154025911318]
本稿では,ガウスモデル-Xノックオフを効率的に実装し,大規模特徴選択問題における誤発見率を制御するアルゴリズムについて述べる。
当社のメソッドは、最大50,000ドルという問題でテストしています。
論文 参考訳（メタデータ） (2020-06-15T21:55:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。