Scott Aaronson will describe two new results that both involve quantum oracles and low-degree rational approximations of the sign function. First, he will show that every black-box amplification protocol for the class QMA must have completeness error at least 1/exp(exp(n)). This implies that a striking recent protocol by Stacey Jeffery and Freek Witteveen (arXiv:2506.15551) is exactly optimal. Second, he will show that PQP=PostBQP, relative to any quantum oracle that's closed under either inverses or complex conjugation. Along with recent work by Ewin Tang and John Wright (arXiv:2507.23787) among others, this underscores the importance of closure properties when dealing with quantum oracles.
Based on upcoming joint works with Freek Witteveen, Adam Bouland, and Jordan Docter.
Join the colloquium:
Zoom link
Meeting ID: 981 5330 2250
Passcode: 640788