Ten semi-grand challenges for quantum computing theory
Here’s Scott Aaronson’s list. The problems are certainly all very good ones. Here’s a quick list of five questions I like, off the top of my head:
- How can we build a quantum computer?
- How quickly can we simulate a desired physical operation on a quantum computer? An exact formula would be nice, or at least good bounds, preferably completely general, and both upper and lower bounds. I’d guess most computer scientists think this is a hopelessly optimistic goal; I’m nothing if not optimistic.
- What makes quantum computers powerful?
- How powerful are they, relative to classical computer?
- What physical resources are necessary and sufficient to do quantum computation? This is interesting in both the noise-free and noisy cases. Even in the noise-free case we currently know very little, for example, about when measurement-based quantum computation is possible. The problem is much harder in the noisy case (and includes determining the threshold).
Update: After posting that, I’ve decided I have fairly serious reservations about how I express the second hope. Can we really hope for a formula for the number of quantum gates required to synthesize a quantum operation? Although I haven’t thought it through in detail, it seems highly unlikely that there is any reasonably general computable formula for the time complexity of some specifed (but arbitrary) family of operations. However, this doesn’t mean that we can’t obtain a lot more general insight into this question than we currently have.