Preparing for Quantum

 Good piece out of ACM, prepare for the quantum.   Passing this on for review for usefulness.  Thoughts?

Exploring the Promise of Quantum Computing By Leah Hoffmann

Communications of the ACM, December 2021, Vol. 64 No. 12, Pages 120-ff

10.1145/3490319

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. Here, Aaronson talks about his work in quantum complexity.

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.

It's a type of problem that shows up in many different settings in cryptography. How did you come to it?

When I entered the field, in the late 1990s, I got very interested in understanding quantum computers by looking at how many queries they have to make to learn some property of a function. This is a subject called query complexity, and it's actually the source of the majority of what we know about quantum algorithms. Because you're only counting the number of accesses to an input, you're not up against the P vs. NP problem. But you are fighting against a quantum computer, which can make a superposition of queries and give a superposition of answers. And sometimes quantum computers can exploit structure in a function in order to learn something with exponentially fewer queries than any classical algorithm would need.

So, what kind of structure does your problem need before a quantum computer can exploit it to get this exponential speed-up?

That's exactly what we've been working on for the past 30 years. In 1995, Peter Shor showed that quantum computers are incredibly good at extracting the period of a periodic function. Others showed that, if you're just searching for a single input that your function maps to a designated output, then quantum computers give only a modest, square-root improvement. The collision problem was interesting precisely because it seemed poised between these two extremes: it had less structure than the period-finding problem, but more structure than the "needle in a haystack" problem.

When my advisor, Umesh Vazirani, told me that the collision problem was his favorite problem in quantum query complexity, I said, "Okay, well, I'll know not to work on that one, because that one's too large." But it kept coming up in other contexts that I cared about. I spent a summer at Caltech and I decided to try to attack it.

I had a colleague, Andris Ambainis, who had invented this amazing lower bound technique—what's now called the Ambainis adversary method—a couple years prior. I didn't know it at the time, but he had actually invented it to try to solve the collision problem, though he was not able to make it work for that. But he could solve some problems that I couldn't solve using this method that I understood really well, called the polynomial method. I started trying to use Ambainis' method to attack the collision problem. I worked on it probably more intensely than I've worked on anything before or since, and what I finally realized was that the polynomial method would work to prove a lower bound for the problem and show that even a quantum computer needs at least N1/5 queries to solve it, where N is the number of outputs. Shortly afterward, Yaoyun Shi refined the technique and was able to show, first, that you need N1/4 queries, and then that you need N1/3.

You have since gone on to produce groundbreaking results in quantum supremacy.

Around 2008 or 2009, I got interested in just how hard quantum computations can be to simulate classically. Forget whether the quantum computer is doing anything useful; how strong can we make the evidence that a quantum computation is hard to simulate? It turns out—and there were others who came to the same realization around the same time—if that is your goal, you can get enormous leverage by switching attention from problems like factoring, which have a single right answer, to sampling problems, where the goal of your computation is just to output a sample from some probability distribution over strings of N bits.

There are certain probability distributions that a quantum computer can easily sample from.

Not only that, but a pretty rudimentary quantum computer. If a classical computer could efficiently sample the same distribution in polynomial time, then the polynomial hierarchy would collapse to the third level, which we use as a kind of standard yardstick of implausibility.

But if you want to do an experiment to demonstrate quantum supremacy, it's not enough to have a distribution that's hard for a classical computer to sample exactly. Any quantum computer is going to have a huge amount of noise, so the most you could hope for is to sample from some distribution that's close to the ideal one. And how hard is it for a classical computer to approximately sample from the same distribution?

To answer that, we realized you needed a quantum computation where the amplitudes (related to probabilities) for the different possible outputs are what's called "robustly #P-complete," meaning that if you could just approximate most of them, then you could solve any combinatorial counting problem. ..... '