Quantum circuit lower bounds and the role of structure in quantum advantage
Joseph Slote (Caltech)
Monday, May 27th 2024, 2-3pm
Abstract:
Quantum advantage is a subtle thing. Only recently have we understood that for unstructured (read: complete) query complexity problems, quantum advantage is exclusive to search tasks: for decision problems, classical algorithms are only ever polynomially-slower. Is this dichotomy an artifact of the query complexity model, or could it be true for time complexity too? In this talk we consider this question in the world of concrete circuit complexity, where quantum advantage for search problems is well-known. To begin understanding the limitations of shallow circuits for solving decision problems, we consider whether a shallow quantum circuit composed with a classical AC0 circuit can approximate the parity function, and we conjecture this model cannot do much better than random guessing. Ultimately we bridge ideas from Fourier analysis, indistinguishability, and nonlocal games to settle this conjecture in several cases.
Speaker information:
Joseph Slote is a 4th-year PhD candidate at Caltech, advised by Chris Umans. He works on quantum complexity theory and related questions in harmonic analysis.