Loading ...
Sorry, an error occurred while loading the content.
 

[Computational Complexity] Is Quantum the new Random ?

Expand Messages
  • GASARCH
    (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
    Message 1 of 1 , Aug 12, 2009
      (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?


      --
      Posted By GASARCH to Computational Complexity at 8/12/2009 12:52:00 PM
    Your message has been successfully submitted and would be delivered to recipients shortly.