Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR18-156 | 7th October 2021 19:03

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revision #2
Authors: Mark Bun, Robin Kothari, Justin Thaler
Accepted on: 7th October 2021 19:03
Keywords:

Abstract:

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a 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 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. We also show that any substantially faster learning algorithm will require fundamentally new techniques.

As an additional consequence, we show that AC0 circuits of depth $d+1$ require size $\tilde{\Omega}(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).

Changes to previous version:

Minor changes. This version appears in Quantum.

Revision #1 to TR18-156 | 30th March 2020 00:41

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

Revision #1
Authors: Mark Bun, Robin Kothari, Justin Thaler
Accepted on: 30th March 2020 00:41
Keywords:

Abstract:

We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a 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 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).

Changes to previous version:

Added circuit lower bound for AC$^0 \circ \oplus$ circuits as a corollary of the quantum algorithm for circuit evaluation.

### Paper:

TR18-156 | 8th September 2018 20:41

#### Quantum algorithms and approximating polynomials for composed functions with shared inputs

TR18-156
Authors: Mark Bun, Robin Kothari, Justin Thaler
Publication: 9th September 2018 16:58
We give new quantum algorithms for evaluating composed functions whose inputs may be shared between bottom-level gates. Let $f$ be a Boolean function and consider a 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 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. We also show that any substantially faster learning algorithm will require fundamentally new techniques.