Fugu-MT 論文翻訳(概要): Breaking the cubic barrier in the Solovay-Kitaev algorithm

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

arxiv url: http://arxiv.org/abs/2306.13158v2
Date: Wed, 08 Oct 2025 04:56:43 GMT
ステータス: 翻訳完了
システム内更新日: 2025-10-09 19:00:13.060164
Title: Breaking the cubic barrier in the Solovay-Kitaev algorithm
Title（参考訳）: Solovay-Kitaevアルゴリズムの立方体障壁を破る
Authors: Greg Kuperberg,
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 efficiently find a word of length $O(n^{3+\delta})$ to approximate an arbitrary target gate to $n$ bits of precision. Using two new ideas, each of which reduces the exponent separately, our new bound on the word length is $O(n^{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 noncompact case to reach group elements far away from the identity.
Abstract（参考訳）: 我々は、一般有限で逆閉生成集合がクーディットに作用するようなソロヴィ-キタエフの定理とアルゴリズムを改善する。アルゴリズムの以前のバージョンでは、任意のターゲットゲートを$n$bitsの精度で近似するために、長さ$O(n^{3+\delta})$の単語を効率よく見つける。 2つの新しいアイデアを使い、それぞれが指数を別々に減らし、単語長の新たな境界は$O(n^{1.44042\ldots+\delta})$である。我々の結果はより一般的に、連結半単純実リー群を密に生成する任意の有限集合に対して成り立つ。

関連論文リスト

Fixed Point Computation: Beating Brute Force with Smoothed Analysis [28.978340288565118]
本稿では,$varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself。アルゴリズムのランタイムは、スムーズな分析フレームワークの下で、$eO(n)/varepsilon$でバウンドされる。
論文参考訳（メタデータ） (2025-01-18T21:32:26Z)
Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
サブセット Sum 問題にモジュラー算術的アプローチを導入する。本研究では,LLL削減基底ベクトルの長さを解析することにより,密度保証を向上できることを示す。
論文参考訳（メタデータ） (2024-08-28T19:32:14Z)
Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
論文参考訳（メタデータ） (2024-06-04T15:23:29Z)
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)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
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)

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