Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum algorithms and approximating polynomials for composed functions with shared inputs
89
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be an $m$-bit Boolean function and consider an $n$-bit function $F$ obtained by applying $f$ to conjunctions of possibly overlapping subsets of $n$ variables. If $f$ has quantum query complexity $Q(f)$, we give an algorithm for evaluating $F$ using $tilde{O}(sqrt{Q(f) cdot n})$ quantum queries. This improves on the bound of $O(Q(f) cdot sqrt{n})$ that follows by treating each conjunction independently, and our bound is tight for worst-case choices of $f$. Using completely different techniques, we prove a similar tight composition theorem for the approximate degree of $f$. By recursively applying our composition theorems, we obtain a nearly optimal $tilde{O}(n^{1-2^{-d}})$ upper bound on the quantum query complexity and approximate degree of linear-size depth-$d$ AC$^0$ circuits. As a consequence, such circuits can be PAC learned in subexponential time, even in the challenging agnostic setting. Prior to our work, a subexponential-time algorithm was not known even for linear-size depth-3 AC$^0$ circuits. As an additional consequence, we show that AC$^0 circ oplus$ circuits of depth $d+1$ require size $tilde{Omega}(n^{1/(1- 2^{-d})}) geq omega(n^{1+ 2^{-d}} )$ to compute the Inner Product function even on average. The previous best size lower bound was $Omega(n^{1+4^{-(d+1)}})$ and only held in the worst case (Cheraghchi et al., JCSS 2018).
rate research
Read More
We establish a polynomial-time approximation algorithm for partition functions of quantum spin models at high temperature. Our algorithm is based on the quantum cluster expansion of Netov{c}ny and Redig and the cluster expansion approach to designing algorithms due to Helmuth, Perkins, and Regts. Similar results have previously been obtained by related methods, and our main contribution is a simple and slightly sharper analysis for the case of pairwise interactions on bounded-degree graphs.
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several different possible definitions. Our main results are * For every n-bit Boolean function f there is an n-variate polynomial p of degree O(n) that robustly approximates it, in the sense that p(x) remains close to f(x) if we slightly vary each of the n inputs of the polynomial. * There is an O(n)-query quantum algorithm that robustly recovers n noisy input bits. Hence every n-bit function can be quantum computed with O(n) queries in the presence of noise. This contrasts with the classical model of Feige et al., where functions such as parity need Theta(n*log n) queries. We give several extensions and applications of these results.
We study the close connection between rational functions that approximate a given Boolean function, and quantum algorithms that compute the same function using postselection. We show that the minimal degree of the former equals (up to a factor of 2) the minimal query complexity of the latter. We give optimal (up to constant factors) quantum algorithms with postselection for the Majority function, slightly improving upon an earlier algorithm of Aaronson. Finally we show how Newmans classic theorem about low-degree rational approximation of the absolute-value function follows from these algorithms.
We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo Markov Chain method and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grovers fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.
Matrix scaling and matrix balancing are two basic linear-algebraic problems with a wide variety of applications, such as approximating the permanent, and pre-conditioning linear systems to make them more numerically stable. We study the power and limitations of quantum algorithms for these problems. We provide quantum implementations of two classical (in both senses of the word) methods: Sinkhorns algorithm for matrix scaling and Osbornes algorithm for matrix balancing. Using amplitude estimation as our main tool, our quantum implementations both run in time $tilde O(sqrt{mn}/varepsilon^4)$ for scaling or balancing an $n times n$ matrix (given by an oracle) with $m$ non-zero entries to within $ell_1$-error $varepsilon$. Their classical analogs use time $tilde O(m/varepsilon^2)$, and every classical algorithm for scaling or balancing with small constant $varepsilon$ requires $Omega(m)$ queries to the entries of the input matrix. We thus achieve a polynomial speed-up in terms of $n$, at the expense of a worse polynomial dependence on the obtained $ell_1$-error $varepsilon$. We emphasize that even for constant $varepsilon$ these problems are already non-trivial (and relevant in applications). Along the way, we extend the classical analysis of Sinkhorns and Osbornes algorithm to allow for errors in the computation of marginals. We also adapt an improved analysis of Sinkhorns algorithm for entrywise-positive matrices to the $ell_1$-setting, leading to an $tilde O(n^{1.5}/varepsilon^3)$-time quantum algorithm for $varepsilon$-$ell_1$-scaling in this case. We also prove a lower bound, showing that our quantum algorithm for matrix scaling is essentially optimal for constant $varepsilon$: every quantum algorithm for matrix scaling that achieves a constant $ell_1$-error with respect to uniform marginals needs to make at least $Omega(sqrt{mn})$ queries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
