Breaking the cubic barrier in the Solovay-Kitaev algorithm

• URL: http://arxiv.org/abs/2306.13158v1
• Date: Thu, 22 Jun 2023 18:35:06 GMT
• Title: Breaking the cubic barrier in the Solovay-Kitaev algorithm
• Authors: Greg Kuperberg (UC Davis)
• Abstract summary: We improve the Solovay-Kitaev theorem and algorithm for a general finite, inverse-closed generating set acting on a qudit. 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 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.

Related papers

• 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)
• 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)
• 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)
• 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)
• 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.