Tuesday, September 11, 2012

Some quantum Stuff

Two quantum announcements (emailed to me by Umesh Vazirani, and producedhere almost exactly) and then some thoughts of mine quantum computing.

Announcement one: The NSF has a new initiative to try to address the lack of tenured faculty (particularly in computer science departments) involved in quantum computation research.  CISE-MPS Interdisciplinary Faculty Program in Quantum Information

The initiative provides a paid sabbatical year to interested tenured faculty to visit a strong quantum computing group, so that can reposition their research interests. The rationale behind the solicitation is to increase the number of tenured researchers in quantum computation, but also to break through the "quantum skepticism" in faculty hiring decisions in those departments where there are no faculty actively involved in quantum computing research.

Announcement two: In support of this program, Carl Williams (a physicist working in Quantum Information who put together the US Vision for Quantum Information Science for the Office of the President) and Umesh have put together a workshop where interested individuals can learn about the initiative, the field and make contacts with people from the major quantum computing centers: see here.

The initiative comes at a particularly opportune moment for researchers in complexity theory, given the increasing relevance of quantum techniques in complexity theory --- the 2-4 norm paper of Barak, et al (SDPs, Lasserre), exponential lower bounds for TSP polytope via quantum communication complexity arguments (See Drucker and de Wolf  paper Quantum proofs for classical theorems for several apps of Q to Complexity, and see
here for the TSP polytope result)
quantum Hamiltonian complexity as a generalization of CSPs, lattice-based cryptography whose security is based on quantum arguments, etc.

MY COMMENTS: Umesh gives as a reason quantum is important its uses in other parts of complexity theory. While that is certainly good there are other intellectual reasons why Quantum is worth studying.
  1. Factoring is in Quantum P! There are MANY problems (maybe 10) where Quantum seemsto be faster than classical.  I wouldn't really want to push this point sincequantum computer aren't build yet. More generally, if one claims a field is validfor real practical value, those arguments may become less believable over time.
  2. Quantum computing can be used to simulate quantum systems- I think this was one of the original motivations.
  3. Quantum computing is valuable for a better understanding of Physics.
    This was first told to be my Fred Green (A Physics PhD who went into computer science)and I made it the subject ofthis blog entry.
    I like his quote so much that I will quote it here

    Learning quantum computing helped me understand quantum mechanicsbetter. As a physicist I never thought about measurement theoryor entanglement, which were foundational issues, irrelevantto what was doing. In quantum computing, we reason about thesethings all the time.

    Over the years others have told me similar things.

  • Side note: The word Quantum is mostly misused in popular culture. Quantum Leap meant a big leapwhen actually quantum means small. The James Bond movie Quantum of Solace used it correctlybut was an awful movie. Oh well.


    1. Re. side note: According to dictionary.com 'quantum' means mostly just _some_ amount (which is the origin of the word) and in general usage seems to mean 'big' more so than 'small.'

      1. quantity or amount
      2. a particular amount.
      3. a share or portion.
      4. a large quantity; bulk.
      5. Physics. a. the smallest quantity of radiant energy, equal to Planck's constant times the frequency of the associated radiation. b. the fundamental unit of a quantized physical magnitude, as angular momentum.
      6. sudden and significant: a quantum increase in productivity.

      1610–20; noun use of neuter of Latin 'quantus' how much

    2. "Learning quantum computing helped me understand quantum mechanics
      better. As a physicist I never thought about measurement theory
      or entanglement, which were foundational issues, irrelevant
      to what was doing. In quantum computing, we reason about these
      things all the time."

      Of course, what this argument really says is that physicists should study the foundations of quantum theory if they want to understand quantum theory better. In most subject areas, the analogous statement would be regarded as a tautology, but physics somehow managed to get itself into the situation where it was taboo to think deeply about one of its most successful theories. It is great that quantum computing has raised the profile of quantum foundations within physics departments, but it is also a damning indictment of the prevailing attitudes in physics that it had to come about that way.

    3. The citation to the article by Ronald de Wolf et al. on exponential lower bounds for the TSP polytope is incorrect. It's: "Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds", arxiv/1111.0837, and it looks great.

      1. Druker and de Wolf et al --> Drucker and de Wolf

      2. It's not just the redundant `et al.': also Drucker is spelled with `ck' instead of `k'.
        And while you're at it, the messed-up layout of the 2nd half of the post could use some editing :)

      3. I have made all corrections above PLUS I now put the pointer
        to the TSP Polytope paper in the post directly.

    4. Quantum refers to discretization into units. For example, a particle in a potential well can live in any of a discrete set of energy levels (or a superposition of them). There is not a continuum. From a computer scientist's perspective, the inherent discretization in quantum mechanics is awesome!

    5. The link for the TSP polytope results (Fiorini, Massar, Pokutta, Tiwary, and myself, STOC'12) is http://arxiv.org/abs/1111.0837

      The paper "Quantum proofs for classical theorems" by Andy Drucker and myself that the post links to, surveys earlier examples of classical results that are obtained in some way or other through quantum ideas; it doesn't contain the recent TSP result.

    6. Much of what I know about careful writing/editing I learned from collaborating with Ronald. Today we see his skills in action :)

    7. "Factoring is in Quantum P!"

      P factorial doesn't seem like a good runtime.

    8. What is the largest qubit machine actually built so far?

    9. The Dutch Genootschap Voor Meetkunde En Kwantumtheorie (Fellowship of Geometry and Quantum Theory, GQT) presents (for me) an outstandingly successful example of creative interdisciplinary research program in quantum dynamics.

      A quantum research niche adjacent to GQT's niche — that presently is largely vacant and/or diffusely focused — would focus upon thermodynamical aspects of quantum information, localization, and transport … these topics being regarded as mutually dual (similar to the mutual duality of fluctuation, dissipation, and concentration in classical thermodynamics).

      Such a quantum thermodynamical program could thematically emphasize the broad span of emerging 21st century strategic enterprises that are enabled by quantum thermodynamics, and the broad objective of the program thus would be to thematically recapitulate the immensely successful 20th century enterprises that were catalyzed by the practical research of dynamical luminaries like Dirac, Feynman, and Onsager.

      Demonstrating the feasibility (or not) of practical quantum computers would of course be a visionary long-range objective of such a quantum thermodynamical program … and yet a well-conceived program would pursue abundance of shorter-range practical objectives, so as to create opportunities for entrepreneurs and investors, create near-term employment for young people, and provide stimulus to the economy as a whole.

      These things would be good! :)

    10. Why is the NSF trying to manipulate the amount of tenured professors in some area? That seems like "science from the top down". In the long run all it's going to result in is a lot of profs with nothing really new to add, churning out boring incremental papers to secure lucrative NSF funding. No breakthrough in science was ever produced in this way; Isaac Newton didn't have a special fellowship to increase academic attention to slopes of tangent lines...

      Question: would you support the NSF if they ran a program to increase the amount of tenured faculty doing research in Intelligent Design Theory?

    11. About your side note; One should be careful before pronouncing the whole world wrong. The popular use of quantum in quantum leap seems perfectly in order. As Thamas noted it has nothing to do with the size of the leap. To quote:

      6. sudden and significant: a quantum increase in productivity.

      The idea is that while normal progress is slowly incremental a quantum leap is a jump ahead from the current state (that's the leap part). Outside of clearly measurable phenomena such as physics is concerned with, size is the only thing that distinguishes such an occurrence - hence the use of this term only for large changes. That's perfectly in line with the original meaning whereby intervening values are skipped over.

    12. The recent James Bond movie "Quantum of Solace" was certainly not very good. However, Ian Fleming's original short story is an excellent read. Recommended!