Breaking the cubic barrier in the Solovay-Kitaev algorithm

• URL: http://arxiv.org/abs/2306.13158v2
• Date: Wed, 08 Oct 2025 04:56:43 GMT
• Title: Breaking the cubic barrier in the Solovay-Kitaev algorithm
• Authors: Greg Kuperberg,
• Abstract summary: We improve the Solovay--Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit.<n>Our result holds more generally for any finite set that densely generates any connected, semisimple real Lie group.
• Score: 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.

Related papers

• Unitary synthesis with fewer T gates [1.3512504563343783]
  We present a simple algorithm that implements an arbitrary $n$-qubit unitary operator using a Clifford+T circuit with T-count $O(24n/3 n2/3)$.<n>This improves upon the previous best known upper bound of $O(23n/2 n)$, while the best known lower bound remains $Omega (2n)$.
  arXiv  Detail & Related papers  (2025-09-30T03:01:34Z)
• Fixed Point Computation: Beating Brute Force with Smoothed Analysis [28.978340288565118]
  We propose a new algorithm that finds an $varepsilon$-approximate fixed point of a smooth function from the $n$-dimensional $ell$ unit ball to itself. The algorithm's runtime is bounded by $eO(n)/varepsilon$, under the smoothed-analysis framework.
  arXiv  Detail & Related papers  (2025-01-18T21:32:26Z)
• Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach [3.0079490585515343]
  We introduce a modular arithmetic approach to the Subset Sum problem. We show that density guarantees can be improved by analysing the lengths of the LLL reduced basis vectors.
  arXiv  Detail & Related papers  (2024-08-28T19:32:14Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation $Gx = 0$. Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms. numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-06-04T15:23:29Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• A New Class of Algorithms for Finding Short Vectors in Lattices Lifted from Co-dimension $k$ Codes [1.8416014644193066]
  We introduce a new class of algorithms for finding a short vector in lattices defined by codes of co-dimension $k$ over $mathbbZ_Pd$, where $P$ is prime. The co-dimension $1$ case is solved by exploiting the packing properties of the projections mod $P$ of an initial set of non-lattice vectors onto a single dual codeword. We show that it is possible to minimize the number of iterations, and thus the overall length expansion factor, to obtain a short lattice vector.
  arXiv  Detail & Related papers  (2024-01-22T22:17:41Z)
• Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
  This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley's $O (N3|GR|)$, which is unworkable for the large grammars that arise in natural language processing. We treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes.
  arXiv  Detail & Related papers  (2023-07-06T13:33:59Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  General tools for designing efficient private estimation algorithms. First efficient $(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery.
  arXiv  Detail & Related papers  (2023-01-11T09:12:28Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm [0.8594140167290096]
  Solovay-Kitaev algorithm is a fundamental result in quantum computation. It gives an algorithm for efficiently compiling arbitrary unitaries using universal gate sets. We provide the first inverse-free Solovay-Kitaev algorithm, which makes no assumption on the structure within a gate set beyond universality.
  arXiv  Detail & Related papers  (2021-12-03T17:39:41Z)
• Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness [26.71898403195793]
  We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an $epsilon$-approximate minimum of a convex function $f$. We prove a new lower bound that matches this bound (up to log factors), and holds not only for randomized algorithms, but also for quantum algorithms.
  arXiv  Detail & Related papers  (2021-12-02T10:51:43Z)
• Well Separated Pair Decomposition and power weighted shortest path metric algorithm fusion [0.0]
  We consider an algorithm that computes all $s$-well separated pairs in certain point sets in $mathbbRn$, $n$ $>$ $1$. We also consider an algorithm that is a permutation of Dijkstra's algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $mathbbRn$, $n$ $>$ $1$.
  arXiv  Detail & Related papers  (2021-03-20T17:38:13Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
  arXiv  Detail & Related papers  (2020-04-16T16:12:10Z)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  We prove tight lower bounds for the following variant of the counting problem considered by Aaronson, Kothari, Kretschmer, and Thaler ( 2020) The task is to distinguish whether an input set $xsubseteq [n]$ has size either $k$ or $k'=(1+varepsilon)k$.
  arXiv  Detail & Related papers  (2020-02-17T10:53:50Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.