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.
One word, my son: SOFTWARE
(notice that I didn’t say “complexity theory”; that would be 2 words —not good enough.)
Hi Mike. It’s easy to give a formula for the minimum number of gates needed to synthesize a quantum circuit C:
min_{Circuits C’ equivalent to C} (Number of gates in C’)
🙂
Or were you looking for a *polynomial-time algorithm* that, given a quantum circuit, returns the size of a minimum equivalent circuit? That’s certainly NP-hard, probably QMA-hard, and most likely even harder. In particular, it’s at least as hard as the problem of deciding whether a given circuit is “trivial” (has all eigenvalues close to +1) or “nontrivial” (has an eigenvalue close to -1), promised that one of these is the case.
M.
The links to the EEEL papers I put up in earlier posts might be handy here. In particular the quirks of Ion Trap standards and the links to the MVL logics papers.
Best