Quantum Algorithms for Composed Functions With Shared Inputs

on YouTube ↗29m

" summary

Shows that composing any outer Boolean F with shared-input OR gates has quantum query complexity ~O(polylog(n) sqrt(n Q(F))) so the bound is the geometric mean bound between n and Q(F) and saves a factor sqrt(Q(F)) over the naive Q(F)sqrt(n) whenever Q(F) is sublinear. Proof uses repeated Grover searches to find input bits that kill high-fan-in ORs, then evaluates the simplified circuit; an approximate degree analogue is proven by different techniques and the bounds are tight up to polylog factors*.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 1:25Why query complexity?
3. 4:07Query Complexity of Block-Composed Functions
4. 5:51Query Complexity of Shared-Input Compositions
5. 10:14Idea of the Quantum Algorithm for h
6. 16:22Quantum Query Algorithms for Linear-Size ACO • Recursively applying our Main Theorem shows that any linear size, depth-d
7. 19:21Implications for Circuit Lower Bounds • An important frontier problem in circuit complexity is to show that IP2 cannot
8. 23:58The Lower Bound Argument of CKK 2012 • FactBeame and Machmouchi 2012, Sherstov 2015: There is a quadratic size AC
9. 25:48Generalizing Our Composition Theorem?
10. 26:41More Classical Implications of Quantum Query Upper Bounds? • A sublinear upper bound on the quantum query complexity or approximate degree of a circuit class establishes very strong limitations on that class
11. 27:21Non-Trivial Query or Communication Upper Bounds for Stronger Circuit Classes? . Can we show sublinear quantum query or approximate degree upper bounds