I went to the QIS workshop on quantum computing which was on the College Park Campus. I went Thursday (reception- free food!) and Friday (free lunch!) but had to miss the Friday free dinner and the Saturday session.
- Going to a conference that is ON your campus usually makes it FURTHER away for you. If I was from out of town I would have gotten a Hotel Room in the same hotel as the conference. As it was I walked from my office- a 45 minute walk It would have been shorter but it was a quantum random walk.
- Scott Aaronson was there. We were talking about teaching class while being taped. He said that being taped changes what he does. I cleverly pointed out that the act of measuring Scott, changes Scott. He cleverly replied that the search for a NEW and FUNNY quantum joke has not ended yet.
- Frank Gaitan gave a talk on using quantum annealing to find Ramsey Numbers. FINALLY a real application for Quantum Computing! (The downside- I was going to use Quantum Computers Find Ramsey Numbers! for an April Fools Day post.)
- Umesh Vazarni's talk on CLASSICAL results proven using QUANTUM techniques was great. This notion seems to be for real. Its looking more and more like even if you don't like quantum you will have to learn it. A particular example of this is this paper
Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Fiorini, Massar, Pokutta, Tiwaray, de Wolf.
- Yi-Kai Liu gave a talk on Quantum Information in Machine Learning and Cryptography. We discuss a small part of his talk, a result by Oded Regev. (Daniel Apon gave a full talk on this small part at the UMCP Complexity Seminar, his slides are here.) GAPSVP(γ) is the following problem: Given an n-dim lattice and a number d output YES if the shortest vector in L is ≤ d, and output NO if the shortest vector in L is > γ d (if it's neither we don't care what you output). This is NP-hard to solve exactly or within O(1) approx (though to be hard for evern poly approx) and it's a good problem for crypto to use. LWE is the Learning with Errors Problem. There is a quantum-reduction that shows that GAPSVP ≤ LWE, so if GAPSVP is hard then LWE is hard. So there are now three scenarios:
- Quantum computers are not built. Factoring is still hard classically. Crypto goes on as it is now (maybe not- there is a classical reduction from GapSVP to LWE, but for weaker parameters- so maybe you can base crypto on LWE).
- Quantum computers are not built. Factoring is easy classically. GAPSVP is hard. Do Crypto based on GAPSVP.
- Quantum computers are built. Factoring is now easy. GAPSVP is hard. Do Crypto based on LWE. THIS is what the result allows us to do!
- Quantum computers are built. Factoring is now easy. GAPSVP is easy. Now you are in trouble.
- Quantum computers are not built. Factoring is still hard classically. Crypto goes on as it is now (maybe not- there is a classical reduction from GapSVP to LWE, but for weaker parameters- so maybe you can base crypto on LWE).
- New word: Stoquastic. Not sure what it means.
- Issac Chuang spoke about the difficulty of teaching quantum computing since the students have different backgrounds. He has devised (or helped devise) Online Tutoring systems for it that seem to be working very well. I didn't know that quantum computing was at the level to worry about how-to-teach-it. Then again, any course has these concerns, so it's good to see that he did something about it. (Even so, I doubt I'll invest a lot of time and effort into an online tutoring system for my Ramsey Theory course next spring.)
- There were some talks on or touching on Quantum-Prog Languages, Quantum-CAD, Quantum-architecture. I suspect that if quantum computers are ever built we will find that some of the assumptions of this work were wrong; however, I also suspect that having people who have thought about these issues will be valuable.
Stoquastic refers to a Hamiltonian that has real and nonpositive off-diagonal elements in the computational basis. It also refers to the corresponding ground states and Gibbs states, the latter having the property that all the elements of the density matrix are positive. Natural problems for states and Hamiltonians in this class, such as finding the ground state energy, are thought to be intermediate in complexity between their quantum and classical probabilistic counterparts, hence the name.
ReplyDeleteI believe that resolving some complexity questions about stoquastic Hamiltonians is thought to be a key step in proving a quantum analog of the PCP theorem, although I might be confused about this since IANACS. All I know for sure is that a lot of people have become excited about proving complexity results for stoquastic Hamiltonians in the past few years. I believe the term was introduced in this paper http://arxiv.org/abs/quant-ph/0606140
The concept has existed for a long time (40 years, maybe? I don't know) under the name of "no sign problem", or rather, no sign problem for certain quantum Monte Carlo schemes.
ReplyDeleteWas there any QIS Workshop discussion of the recent work by Harvard's Alán Aspuru-Guzik, in collaboration with D-WAVE, that is described in the recent articles "Solving quantum ground-state problems with nuclear magnetic resonance" (2011) and "Finding low-energy conformations of lattice protein models by quantum annealing" (2012)?
ReplyDeleteThese articles introduce to QC/QIT/FTQC an ensemble of dynamical elements and mathematical idioms that, in recent decades, have proved to be spectacularly successful (both theoretically and experimentally) in improving our understanding of (classical) molecular dynamics and (quantum) chemistry … and so it is surprising to see (apparently) no talks relating to this fast-developing frontier in the QIS Workshop's program.
We all know that Prof. Mulmuley's seminal works on using GCT to deduce some relations on the P-NP conjecture( specifically to prove P not equal to NP in characteristic zero) from the perspective of non-standard Riemann hypothesis is having a profound effect on both the fields of pure mathematics and theoretical computer science.
ReplyDeleteBut, does there exist any deep analysis to relate a hypothetical quantum version of the PCP theorem with both Church-Turing thesis and quantum computation,so that the two fields may have some powerful yet subtle connections?