Exploring the Promise of Quantum Computing

We have not yet have realized--or, perhaps, even fully understood--the full promise of quantum computing. However, we have gotten a much clearer view of the technology's potential, thanks to the work of ACM Computing Prize recipient Scott Aaronson, who has helped establish many of the theoretical foundations of quantum supremacy and illuminated what quantum computers eventually will be able to do. Let's start with your first significant result in quantum computing: your work on the collision problem, which you completed in graduate school. The collision problem is where you have a many-to-one function, and your task is just to find any collision pair, meaning any two inputs that map to the same output. I proved that even a quantum computer needs to access the function many times to solve this problem.