Towards provable quantum computational advantage in bosonic and fermionic systems

In my talk I will explain how bosonic and fermionic systems can be used to prove quantum computational speedup under generalized P ≠ NP conjectures. I will outline the recent developments in this area, focusing especially on two proposals: Fermion Sampling (PRX Quantum 3 (2), 020328 (2022)) and Boson Sampling in the regime in which number of photons scales linearly with the number of modes (arXiv:2312.00286). I will conclude with some speculations regarding the relevance of these complexity-theoretic results to problems of practical relevance.