Efficient approximate unitary designs from random Pauli rotations
- URL: http://arxiv.org/abs/2402.05239v1
- Date: Wed, 7 Feb 2024 20:34:36 GMT
- Title: Efficient approximate unitary designs from random Pauli rotations
- Authors: Jeongwan Haah, Yunchao Liu, Xinyu Tan
- Abstract summary: We construct random walks on simple Lie groups that quickly converge to the Haar measure for all moments up to order $t$.
Specifically, a step of the walk on the unitary or orthognoal group of dimension $2mathsf n$ is a random Pauli rotation $emathrm i theta P /2$.
Our simple proof uses quadratic Casimir operators of Lie algebras.
- Score: 3.29295880899738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We construct random walks on simple Lie groups that quickly converge to the
Haar measure for all moments up to order $t$. Specifically, a step of the walk
on the unitary or orthognoal group of dimension $2^{\mathsf n}$ is a random
Pauli rotation $e^{\mathrm i \theta P /2}$. The spectral gap of this random
walk is shown to be $\Omega(1/t)$, which coincides with the best previously
known bound for a random walk on the permutation group on $\{0,1\}^{\mathsf
n}$. This implies that the walk gives an $\varepsilon$-approximate unitary
$t$-design in depth $O(\mathsf n t^2 + t \log 1/\varepsilon)d$ where $d=O(\log
\mathsf n)$ is the circuit depth to implement $e^{\mathrm i \theta P /2}$. Our
simple proof uses quadratic Casimir operators of Lie algebras.
Related papers
- Incompressibility and spectral gaps of random circuits [2.359282907257055]
reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively.
We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
arXiv Detail & Related papers (2024-06-11T17:23:16Z) - Efficient Continual Finite-Sum Minimization [52.5238287567572]
We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization.
Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires.
We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
arXiv Detail & Related papers (2024-06-07T08:26:31Z) - Algorithms for mean-field variational inference via polyhedral optimization in the Wasserstein space [10.292118864147097]
We develop a theory of finite-dimensional polyhedral subsets over the Wasserstein space and optimization of functionals over them via first-order methods.
Our main application is to the problem of mean-field variational inference, which seeks to approximate a distribution $pi$ over $mathbbRd$ by a product measure $pistar$.
arXiv Detail & Related papers (2023-12-05T16:02:04Z) - Fitting an ellipsoid to a quadratic number of random points [12.519286388088958]
We consider the problem $(mathrmP)$ of fitting $n$ standard Gaussian random vectors in $mathbbRd$ to the boundary of a centered ellipsoid, as $n, d to infty$.
This problem is conjectured to have a sharp feasibility transition: for any $varepsilon > 0$, if $n leq (1 - varepsilon) d2 / 4$ then $(mathrmP)$ has a solution with high probability.
arXiv Detail & Related papers (2023-07-03T17:46:23Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem.
The goal is to approximate $mathbfA$ as a product of low-rank factors.
Our techniques generalize to other common variants of the BMF problem.
arXiv Detail & Related papers (2023-06-02T18:55:27Z) - On the moments of random quantum circuits and robust quantum complexity [0.0]
We prove new lower bounds on the growth of robust quantum circuit complexity.
We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
arXiv Detail & Related papers (2023-03-29T18:06:03Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - Matrix concentration inequalities and efficiency of random universal
sets of quantum gates [0.0]
For a random set $mathcalS subset U(d)$ of quantum gates we provide bounds on the probability that $mathcalS$ forms a $delta$-approximate $t$-design.
We show that for $mathcalS$ drawn from an exact $t$-design the probability that it forms a $delta$-approximate $t$-design satisfies the inequality $mathbbPleft(delta geq x right)leq 2D_t
arXiv Detail & Related papers (2022-02-10T23:44:09Z) - On Submodular Contextual Bandits [92.45432756301231]
We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function.
We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
arXiv Detail & Related papers (2021-12-03T21:42:33Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals.
Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
arXiv Detail & Related papers (2021-08-19T16:16:48Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
Linear bandit algorithms yield $tildemathcalO(nsqrtT)$ pseudo-regret bounds on compact convex action sets.
Two types of structural assumptions lead to better pseudo-regret bounds.
arXiv Detail & Related papers (2021-03-10T07:33:03Z)
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.