Journal
QUANTUM
Volume 5, Issue -, Pages -Publisher
VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
DOI: 10.22331/q-2021-09-16-543
Keywords
-
Ask authors/readers for more resources
New quantum algorithms have been proposed for evaluating composed functions, and tight composition theorems for linear-size depth-d AC(0) circuits have been proven. Additionally, it has been shown that AC(0) circuits of depth d+1 require a larger size to compute the Inner Product function, even on average.
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).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available