Wednesday, August 12, 2009

Is Quantum the new Random ?

(This blog is an extension of a short conversation I had with Scott A at CCC09.)

Consider the following two statements that nobody would argue with or find controversial:
1. Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers.
2. Even if all you care about are deterministic models of computation you still need to learn probability.
I think that the following is now true:
(Q) Even if all you care about are deterministic models of computation you still need to learn quantum techniques.
There are lower bounds on classical Private Info Ret that use quantum techniques. (See Exponential Lower Bounds for 2-Query Locally Decodable Codes via a Quantum Argument by Kerenidis and de Wolf here.) The papers of Gentry and Peikert used quantum techniques in Crypto. (Disclaimer: Browsing through Peikert's paper I spotted the Quantum, but for Gentry's I didn't see it.) At CCC09 Scott told me a proof that PP is closed under intersection using Quantum techniques.

1. When will statement Q above be as noncontroverial as the two statements (1) and (2)?
2. When will we be teaching Quantum techniques in the standard Grad Complexity Course?
3. When will we be teaching Quantum techniques in the standard Undergrad Complexity Course?

1. "Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers."

I do not agree with this statement at all.
Why does one need to discuss complex numbers in order to talk about real roots of a real polynomial ? Every theorem (that I know of) about real roots of real polynomials can be proved without referring to complex numbers.

2. to anon@1, how do you know that you have exhausted all the real roots?

3. When viable quantum computers exist.

4. The papers of Gentry and Peikert used quantum techniques in Crypto.

This is a bit misleading. Peikert's paper is about *removing* quantumness from an earlier reduction of Oded Regev. Gentry's reduction, though, is quantum much the same way that Regev's reduction is.

5. To Anonymous number 2: What is wrong with using Sturm sequences to determine the number of roots in any interval?

Anyhow, everyone wants to know what the "next big thing" is. What experience has taught us is that we are very bad at this guessing game. I have no idea whether we will care about Quantum Computers in 20 years. I don't even want to guess.

6. To anon #1: I think this is a reference to the explicit formula for the roots of a cubic, which can require calculation with complex numbers even to get real roots.

7. It depends what you want to do with it. I think even your second statement is controversial: you can teach undergraduate algorithms/complexity without mentioning randomization. Would I feel that something was missing from such a course? Yes, but adding one thing means removing something else. The point is that there is plenty to learn without it.

The same goes for quantum, only more so. =)

When will we be teaching Quantum techniques in the standard Grad Complexity Course?

As soon as a good textbook on the subject becomes available. (Or a good chapter in a general complexity textbook -- Arora-Barak may qualify; I haven't checked yet.)

When will we be teaching Quantum techniques in the standard Undergrad Complexity Course?

What standard undergrad complexity course? Or maybe you mean "when will Sipser's book include a section on quantum"? Unfortunately, I have not yet seen an introduction to quantum computing that would work in an undergrad class.

8. Many practical computational problems are problems about simulation (there is even a point of view in which all computations are simulations).

And obviously, a pretty big subset of practical simulations are performed upon state-spaces that are small-dimension encodings of the large-dimension space that nature specifies.

The great advantage of learning quantum techniques comes when we ask questions like "Why does concentration work so well in real-world problems?" "What generic mechanism acts to algorithmically concentrate simulation trajectories?" For quantum systems this question can be phrased in Scott's language as "What physical mechanism accomplishes sure/Shor separations in real-world quantum systems?"

A good reason to learn quantum simulation is that (AFAICT) it is only for quantum systems that a reasonably generic mechanism (and mathematically well-posed) for algorithmic concentration known --- it is the physical mechanism that Zurek calls "einselection".

Now, if we ask, what mathematical aspects of quantum mechanics are necessary for einselection, then the mathematically natural answer is "the compatible triple of symplectic, Riemannian, and complex structure ... and as for the linear structure ... well ... that is merely a 'technical convenience' (according to the point of view of Ashtekar and Schilling)."

The resulting prediction is clear ... furture textbooks on quantum complexity will cover compatible triples first ... then cover linear structure. :)

The advantage of this approach is that complexity students end up speaking pretty much the same symplectic simulation language that biologists use ... and as simulation becomes more central to research at every scale of biology, this mathematical link-up increasingly benefits both disciplines.

9. Oh yeah ... when the above is cast GASARCHian mathematical form it becomes the following advice to students: "Even if all you care about is complex structure, then you still need to know about symplectic and Riemmanian structure."

In fact, an even stronger statement follows: "All you need to know about is symplectic and Riemmanian structure, because then the complex structure comes for free."

10. Will the typical undergrad taking an intro to computation class have the necessary math prerequisites to understand quantum techniques? Or will the math instruction also need to be extended?

11. Kurt asks: Will the typical undergrad taking an intro to computation class have the necessary math prerequisites to understand quantum techniques?

Kurt, your question is excellent, and it holds with redoubled force if we replace "quantum" with "classical".

The problem arises because incoming graduate students whose understanding of dynamical state-spaces (whether classical or quantum) is fundamentally Euclidian (whether Newtonian or Hilbert) have an immense amount of mathematics still to learn before they can be entrusted with even the simplest simulation codes.

The point is that even when the state-space of nature is Euclidian/Hilbert (to a very good approximation) it still generically happens that working simulation state-apaces are nonlinear prima facie ... yet dynamical conservation laws and informatic/thermodynamic principles must be strictly respected ... and undergraduate curricula leave many (most?) entering graduate students mathematically unprepared to deal with this.

How many undergraduates have acquired the ever-elusive mathematical maturity needed to learn classical mathematics from (say) Arnol'd?

At last month's FOMMS Conference this problem was widely acknowledged as being so severe, that it had its own short-hand name: "The Education Problem."

12. Sorry if I'm off in left field here, but my impression was that most undergrads will have little to no use for most of complexity theory, seeing as how most of them will be taking jobs in industry. The major points that seem to require communicating are the halting problem and a clear understanding of P vs. NP, that is the notions that problems may be provably hard or insoluble.

It seems to me that widely used linear to cubic time algorithms, ample applications of those algorithms, and techniques and principles for devising novel algorithms and applications are much more important for most students. Probability tends to show up as a pragmatic technique (e.g. quicksort pivots) in the undergraduate curriculum, not as a complexity theoretic topic or technique. I don't imagine quantum techniques will ever find their way into the undergraduate curriculum unless they can (a) be applied to real programs and (b) there is no way to explain the resulting application without appealing to a quantum explanation.

13. Welcome to the UW Gilbert! If you walk across the street from the CSE building, you'll be in the ME Building, and you are very welcome to visit our UW Quantum Systems Engineering (QSE) laboratory.

Our QSE Group's interest in complexity theory resides mainly in model order reduction of quantum system dynamics, and our main tools for achieving this are KĂ¤hlerian concentration theorems that derive from drift-and-diffusion descriptions of measurement-and-control processes.

So we try to keep one foot in both worlds ... we prove theorems *and* we cut metal ... and yes, we most definitely use a *lot* of quantum mechanical analysis.

14. Counting generously, there are now about a dozen examples of applications of quantum computing techniques to non-quantum TCS/math. For those interested in the topic, Andy Drucker and I are writing a survey paper, which should be out in a month or two.

-- Ronald de Wolf

15. Quantum is much more compelling for its own sake than for its classical applications. However, given that quantum computers can be built in principle, it would seem to be the correct model to study for lower bounds.

16. This term I took a course at Waterloo on "Quantum Applications of Classical Complexity".

I found that Scott's PostBQP-based proof that PP is closed under intersection was very neat and good motivation to understand the basic formulation of quantum computing. My course project was to write this up, see http://en.wikipedia.org/wiki/PostBQP

On the other hand, my own feeling was that this was sort of a unique example -- the other topics in the course felt to me like quantum topics with quantum results. (Just an opinion, I don't mean to debate it, and certainly I am interested to see the upcoming survey paper.)

17. Thanks John. I may just have to take you up on that offer.

18. Give me a call, Gilbert, once you're in Seattle -- we have twice-a-week QSE Group meetings at which everyone is welcome ... and these Kavli tutorial notes summarize our QSE Group's geometric framework for QIT/QIS analysis and simulation.

19. I find it amusing that noone has mentioned the Dasgupta-Papadimitriou-Vazirani (undergraduate) textbook. It has a chapter on quantum algorithms, including a sketch of Shor's.

So quantum techniques have been taught to undergraduates for a couple of years, at many places, without the need for special extra Math courses (see also Scott's version of intro quantum computation as negative probabilities, and Lance's paper on characterizing quantum complexity classes as complex number versions of "correct" counting classes.)

As for when will we teach it in a Complexity course, the answer is "when we think it is more useful than some other topic currently being taught"--I guess, a very personal decision of what techniques are likely to lead to good new results.

20. The Dasgupta-Papadimitriou-Vazirani textbook has a chapter on quantum, but that doesn't mean anyone teaches it. Do you know of which schools teach quantum in their undergrad algorithms course? What kinds of questions would you expect students to answer on an exam?

21. What kinds of [quantum] questions would you expect [undergraduate] students to answer on an exam?

The same questions that undergraduate [engineering] students would be expected to answer about classical systems---and that they could find jobs for knowing how to answer.

"What varieties of quantum system can be optimally designed and efficiently simulated? Give practical examples."

22. Drucker and de Wolf's survey "Quantum Proofs for Classical Theorems" has appeared on the arXiv.
http://xxx.lanl.gov/abs/0910.3376