Quantum circuit lower bounds and the role of structure in quantum advantage.

CS/Math Seminar - Joseph Slote, Caltech ONLINE ONLY

An important challenge in quantum computing is to develop quantum circuit lower bound techniques beyond lightcone arguments. Towards this goal, we examine a circuit model formed from a shallow quantum circuit composed with a classical AC0 circuit and ask whether this model can compute parity. We then bridge ideas from Fourier analysis, info-theoretic cryptography, and nonlocal games to settle this question in several cases. We'll also discuss implications for a search-decision dichotomy in unstructured quantum advantage, a phenomenon that was recently understood in the context of query complexity: for unstructured (promise-free) query problems, exponential quantum advantage can exist for search problems but never for decision problems.

Based on https://arxiv.org/abs/2311.13679.

Join Zoom Meeting

https://uwaterloo.zoom.us/j/95891711017?pwd=Y3ROMXlhS1BlNGNTZXJOWkRXdnJOQT09

Meeting ID: 958 9171 1017

Passcode: 490203

Add event to calendar