More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities

• URL: http://arxiv.org/abs/2406.08499v1
• Date: Wed, 8 May 2024 22:38:35 GMT
• Title: More Efficient $k$-wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
• Authors: Lucas Gretta, William He, Angelos Pelecanos,
• Abstract summary: We prove that the permutation computed by a reversible circuit with $tildeO(nkcdot log (1/varepsilon))$ random $3$-bit gates is $varepsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $varepsilon$ is not too small.
• Score: 0.10241134756773229
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the permutation computed by a reversible circuit with $\tilde{O}(nk\cdot \log(1/\varepsilon))$ random $3$-bit gates is $\varepsilon$-approximately $k$-wise independent. Our bound improves on currently known bounds in the regime when the approximation error $\varepsilon$ is not too small. We obtain our results by analyzing the log-Sobolev constants of appropriate Markov chains rather than their spectral gaps.

Related papers

• Quantum state preparation with optimal T-count [2.1386090295255333]
  We show how many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $varepsilon$. We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $varepsilon$.
  arXiv  Detail & Related papers  (2024-11-07T15:29:33Z)
• Robust Sparse Regression with Non-Isotropic Designs [4.964650614497048]
  We develop a technique to design efficiently computable estimators for sparse linear regression in the simultaneous presence of two adversaries. We provide a novel analysis of weighted penalized Huber loss that is suitable for heavy-tailed designs in the presence of two adversaries.
  arXiv  Detail & Related papers  (2024-10-31T13:51:59Z)
• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  We develop and analyze data subsampling techniques for Poisson regression. In particular, we consider the Poisson generalized linear model with ID- and square root-link functions.
  arXiv  Detail & Related papers  (2024-10-30T10:09:05Z)
• Learning junta distributions and quantum junta states, and QAC$^0$ circuits [0.0]
  We consider the problems of learning junta distributions, their quantum counter-part, quantum junta states, and QAC$0$ circuits. We show that they can be learned with error $varepsilon$ in total variation distance. We also prove a lower bound of $Omega(4k+log (n)/varepsilon2)$ copies.
  arXiv  Detail & Related papers  (2024-10-21T09:39:20Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  We propose a piecewise stationary linear bandit (PSLB) model where the quality of an arm is measured by its return averaged over all contexts. PS$varepsilon$BAI$+$ is guaranteed to identify an $varepsilon$-optimal arm with probability $ge 1-delta$ and with a minimal number of samples.
  arXiv  Detail & Related papers  (2024-10-10T06:15:42Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• 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)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)

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.