Consider the following two statements that nobody would argue with or find controversial:
- Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers.
- Even if all you care about are deterministic models of computation you still need to learn probability.
(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.
- When will statement Q above be as noncontroverial as the two statements (1) and (2)?
- When will we be teaching Quantum techniques in the standard Grad Complexity Course?
- When will we be teaching Quantum techniques in the standard Undergrad Complexity Course?
"Even if all you care about is finding real roots of polynomials over the reals then you still need to know about complex numbers."
ReplyDeleteI 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.
to anon@1, how do you know that you have exhausted all the real roots?
ReplyDeleteWhen viable quantum computers exist.
ReplyDeleteThe papers of Gentry and Peikert used quantum techniques in Crypto.
ReplyDeleteThis 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.
To Anonymous number 2: What is wrong with using Sturm sequences to determine the number of roots in any interval?
ReplyDeleteAnyhow, 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.
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.
ReplyDeleteIt 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.
ReplyDeleteThe 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.
Many practical computational problems are problems about simulation (there is even a point of view in which all computations are simulations).
ReplyDeleteAnd 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.