論文の概要: Breaking the cubic barrier in the Solovay-Kitaev algorithm

• arxiv url: http://arxiv.org/abs/2306.13158v1
• Date: Thu, 22 Jun 2023 18:35:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-26 14:25:03.376891
• Title: Breaking the cubic barrier in the Solovay-Kitaev algorithm
• Title（参考訳）: Solovay-Kitaevアルゴリズムの立方体障壁を破る
• Authors: Greg Kuperberg (UC Davis)
• Abstract要約: 我々は、一般有限で逆閉生成集合がクーディットに作用するようなソロヴィ・キタエフの定理とアルゴリズムを改善する。 我々の結果はより一般的に、連結半単純実リー群を密に生成する任意の有限集合に対して成り立つ。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve the Solovay-Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. Prior versions of the algorithm can efficiently find a word of length $O((\log 1/\epsilon)^{3+\delta})$ to approximate an arbitrary target gate to within $\epsilon$. Using two new ideas, each of which reduces the exponent separately, our new bound on the world length is $O((\log 1/\epsilon)^{1.44042\ldots+\delta})$. Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group, with an extra length term in the non-compact case to reach group elements far away from the identity.
• Abstract（参考訳）: 我々は、quditに作用する一般有限逆閉生成集合に対するsolovay-kitaevの定理とアルゴリズムを改善する。 アルゴリズムの前のバージョンでは、$O((\log 1/\epsilon)^{3+\delta})$の単語を効率的に見つけることができ、任意のターゲットゲートを$\epsilon$に近似することができる。 それぞれが指数を別々に減らす2つの新しいアイデアを用いて、世界の長さの新たな境界は$o((\log 1/\epsilon)^{1.44042\ldots+\delta})$である。 この結果はより一般に、連結で半単純な任意の実リー群を密に生成し、非コンパクトの場合の余長項が単位元から遠く離れた群の元に到達するような有限集合に対して成立する。

関連論文リスト

• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  サブセット Sum 問題にモジュラー算術的アプローチを導入する。 本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
  論文  参考訳（メタデータ） (2024-08-28T19:32:14Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。 クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。 我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
  論文  参考訳（メタデータ） (2024-02-09T19:01:48Z)
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes [1.8416014644193066]
  共次元$k$ over $mathbbZ_Pd$, ここでは$P$は素数である。 共次元の$$は、プロジェクションのパッキング特性である mod $P$ を1つの双対符号ワードに初期セットの非格子ベクトルに利用することで解決される。 そこで本研究では,反復数,すなわち全長拡大係数を最小化して,短い格子ベクトルが得られることを示す。
  論文  参考訳（メタデータ） (2024-01-22T22:17:41Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm [0.8594140167290096]
  Solovay-Kitaevアルゴリズムは量子計算の基本的な結果である。 普遍ゲート集合を用いて任意のユニタリを効率的にコンパイルするアルゴリズムを提供する。 普遍性を超えたゲートセット内の構造を仮定しない最初の逆フリーなソロワ・キタエフアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-12-03T17:39:41Z)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  非常に滑らかな凸関数を最適化する複雑性について検討する。 正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。 我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
  論文  参考訳（メタデータ） (2021-12-02T10:51:43Z)
• 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)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。 同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
  論文  参考訳（メタデータ） (2020-02-09T03:39:46Z)

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

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