Broken Glass Everywhere. If it Ain't About Quantum Money, I Just Don't Care

Note the new location (updated 9/28/09)

The Optimizer is coming to town, which is always fun:

TIME: 1:30-2:30 pm, Tuesday, September 29, 2009

PLACE: CSE 305

SPEAKER: Scott Aaronson (MIT)

TITLE: Quantum Money

ABSTRACT:
Ever since there's been money, there have been people trying to counterfeit it, and governments trying to stop them. In a remarkable 1969 manuscript, Stephen Wiesner raised the possibility of money whose authenticity would be guaranteed by the laws of quantum physics. However, Wiesner's money can only be verified by the bank that printed
it -- and the natural question of whether one can have secure quantum money that *anyone* can check has remained open for forty years. In this talk, I'll tell you about progress on the question over the last year.

- I'll show that no "public-key" quantum money scheme can have security based on quantum physics alone: like in most cryptography, one needs a computational hardness assumption.

- I'll show that one can have quantum money that remains hard to counterfeit, even if a counterfeiter gains black-box access to a device for checking the money.

- I'll describe a candidate quantum money scheme I proposed last spring, and how that scheme was broken a few weeks ago by myself, Farhi, Gosset, Hassidim, Kelner, Lutomirski, and Shor.

- I'll describe a new quantum money scheme we propose in the same work. Our new scheme has the strange property that not even the bank can prepare the same bill twice.

Reference for the first two results: S. Aaronson, "Quantum copy-protection and quantum money," in Proceedings of CCC'2009, http://www.scottaaronson.com/papers/noclone-ccc.pdf. The "AFGHKLS" paper should be posted to the arXiv soon.

The last line makes me ask: has anyone every written a paper with all of the letters of the alphabet for last names (and no duplicate uses!)

More like this

For those local to Seattle, I'm talking tomorrow in the Paul Allen center:TIME: 1:30 -- 2:30 pm, Tuesday, Feb 24, 2009 PLACE: CSE 503 SPEAKER: Dave Bacon, University of Washington TITLE: Symmetry in Quantum Algorithms ABSTRACT: Quantum computers can outperform their classical brethren at a variety…
An interesting paper on the arXiv's today, arXiv:0908.2782, "Adiabatic quantum optimization fails for random instances of NP-complete problems" by Boris Altshuler, Hari Krovi, and Jeremie Roland. Trouble for D-wave? Adiabatic quantum algorithms are a set of techniques for designing quantum…
Registration for QIP 2009 is now open:QIP 2009 -- 12th WORKSHOP ON QUANTUM INFORMATION PROCESSING - Santa Fe, New Mexico USA. January 12-16, 2009. REGISTRATION IS NOW OPEN at http://qipworkshop.org/ Deadline for special conference hotel rates: December 1st. Quantum Information Processing is the…
A half day at QIP. The reason I'm having a hard time keeping away this morning: Avinatan Hassidim, "Multi-prover interactive proofs with communicating provers" Paper arXiv:0806.3982. Avinatan described work he performed with Michael Ben-Or and Haran Pilpel on multiprover interactive proofs in…

The Alpher, Bethe, Gammow paper is pretty well known.