[Computational Complexity] 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:
- 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?
Posted By GASARCH to Computational Complexity at 8/12/2009 12:52:00 PM