.png){kind=icon}
.png){kind=icon}
Return
Quantum algorithms and approximating polynomials for composed functions with shared inputs
.png){kind=icon}
OA
AI
DOI：10.22331/q-2021-09-16-543.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (O) over tilde(root Q(f).n) quantum queries. This improves on the bound of O(Q(f).root 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 (O) over tilde (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) circle circle plus circuits of depth d +1 require size (Omega) over tilde (n(1/(1-2-d))) > 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).
Keywords:
LOWER BOUNDS
COMPLEXITY
SIZE
FORMULA