Tight Quantum Time-Space Tradeoffs for Function Inversion

Explore a 26-minute IEEE conference talk on quantum computing that delves into tight quantum time-space tradeoffs for function inversion. Learn about classical time-space tradeoffs, circuit complexity, and a generic framework for approaching these problems. Discover the direct product problem, multi-instance gain, and upper and lower bounds. Gain insights into the overall product, multi-instance game, and open questions in the field. Presented by researchers from Academia Sinica, New York University Shanghai, Princeton University, NTT Research, and Boston University, this talk offers a comprehensive overview of cutting-edge research in quantum computing and function inversion.

Introduction
Classical TimeSpace Tradeoffs
Circuit Complexity
Background
Generic Framework
Open Questions
Proof Overview
Direct Product Problem
Multiinstance Gain
Upper Bound
Lower Bound
lemma informally
Overall product
Multiinstance game
Conclusion
Open Question