Quantum Algorithms
Wednesday, June 15, 2005
42 Quantum Questions
I started this blog mainly to explore a variety of questions about quantum computer algorithms and related topics. This, I hoped, would foster some dialog in language that curious non-experts could mostly understand, while not offending the sensibilities of professional researchers. The contents of the blog have diverged pretty substantially from that, but I thought I'd list the types of questions I had in mind anyway (along with some I picked up along the way). Note there is lots of overlap, and the answers to some questions may conditionally make other questions moot. David Hilbert, I am not. (QC = quantum computer/computing)

  1. Will QCs ever exist, and if so, how common will they become?
  2. Where does the QC hype end, and reality begin?
  3. Will writing QC software be fundamentally different to classical programming? What classical knowledge will carry over?
  4. Will future programmers need to become well versed in quantum mechanics to understand and program QC's?
  5. Will "Quantum Processors", if they come to exist, always be secondary to classical CPU's?
  6. How many physical and logical qubits will be needed for "useful" quantum computation?
  7. What is "useful" quantum computation?
  8. How easy/hard is it to understand useful quantum algorithms, and the workings of QC hardware?
  9. Are quantum computing pessimists on to something, or are they short-sighted? Or confused?
  10. What computational problems are QC's poised to handle well?
  11. What computational problems will QC's never be able to handle?
  12. How do the computer science theory and physics communities regard quantum computing, i.e. As the inevitable future? A passing fad? An interesting but non-vital supplement to mainstream research?
  13. Can quantum computers get us closer to proving P != NP?
  14. How does one go about proving lower/upper bounds of QC algorithms? What implications does this have for classical algorithms?
  15. If QC's never come to exist, will it be because something fundamental about physics makes them impossible? Or because they'll be too expensive to build? Or because there aren't enough potential applications to justify the effort?
  16. How are the various QC architectures advancing? What is the frontrunner?
  17. When a clear favorite jumps ahead, will the other architecture programs disappear?
  18. What is the trajectory of experimental quantum computing (i.e. how many qubits by 2010, 2015)? Is it too early to say?
  19. What is the quantum analog to Moore'e Law?
  20. Will quantum error correction work as advertised?
  21. How important/useful are Grover's/Shor's algorithms really?
  22. Were Grover's/Shor's algorithms low-hanging fruit, or the product of extreme insight and imagination?
  23. Are there any recent advances on par with Grover's/Shor's algorithms?
  24. Do the papers that generalize aspects of Grover's and Shor's algorithms represent important powerful and practical extensions, or do they amount to trivial tweaking?
  25. Is designing quantum algorithms difficult simply because it requires deep knowledge of several disciplines? Or is there something more to it?
  26. What quantum physics experiments, specifically, could be simulated on a QC?
  27. What will QC's mean for AI? Specifically: neural nets? Genetic algorithms? Something entirely different?
  28. Will quantum computing have any impact on: Operating systems? Databases? The Internet? Games?
  29. What classical models are most similar to quantum computer programming? i.e. parallel programming? Randomized algorithms? Nothing?
  30. If a quantum algorithm produces only a sub-exponential speed gain over its classical counterpart, is it of any value?
  31. Are there any efficient quantum algorithms that also run efficiently on classical computers, but are much easier to reason about in quantum terms than classical terms?
  32. What can the idea of a quantum computer tell us about the universe?
  33. What can quantum computing teach us about quantum mechanics (does it shed any light on entanglement? The measurement paradox? Teleportation?)?
  34. What can quantum computing teach us about classical computing?
  35. What can quantum computing teach us about the brain?
  36. Is the universe a big quantum computer, and if so, how do we tap into its vast processing power?
  37. Are there abstractions that will make programming QC's intuitive? Or is that fundamentally equivalent to making quantum mechanics intuitive, and therefore impossible?
  38. What's the most efficient way to learn about quantum computing, for someone with: A computer science background? A physics background? A non-technical background?
  39. Is understanding continuous quantum mechanics necessary for fully understanding quantum computing?
  40. Is it possible to follow all the important quantum computing developments if one does not have access to all the notable expensive academic journals?
  41. Quantum information theory placeholder (lots more questions here, but I've probably already gone overboard).
  42. Does this line of questioning miss the point? What else should I/we be asking?

This blog has done a pretty terrible job of even discussing these questions. This is mainly because it's taken me a lot longer to really understand quantum computing than I expected, which will probably be the subject for a future post, if I can find the right way to put it.
I think most of your questions are excellent. I wish you would post more often. You could consider the questions in your list, one at a time, asking important players to write answer for posting on your blog.
> You could consider the questions
> in your list, one at a time,
> asking important players to write
> answer for posting on your blog.

Thanks for the encouragment and the idea...I am mulling the possibility of trying to really address these questions here. I might not even need to ask the relevant players directly, because in many cases there are already papers on these topics. The task at hand is to collect the papers and understand the topics well enough to summarize the current thinking. An "Ask the Experts" kind of thing would improve it all dramatically, I agree.

If I tackle just one per week, then I have nearly a year's worth of posts right there...very tempting.
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
This comment has been removed by a blog administrator.
Post a Comment

<< Home

Powered by Blogger