Quantum Computers and How Does Nature Compute?
University at Buffalo
May 21, 2015
room TBD
Lunch will be served at noon.


The quest for practical quantum computers is one of the great engineering challenges of our time. It is motivated by theory and experiments — some being currently debated — showing that quantum computation and communication can achieve results that are inaccessible to conventional computers and communication channels. At the heart is Peter Shor's algorithm for factoring d-digit numbers in roughly d^3 quantum operations, as opposed to exponential in the cube root of d for today's computers. Certainly our current mathematical notation for these operations is exponential in size. Insofar as computation is symbolic, this suggests Nature has "linguistics" that our classical computer programming and thought patterns cannot emulate. Either:

  1. Nature computes in ways that are ineffable to our notation; or
  2. Our classical modes can catch up to Nature — in which case we already have the power to factor numbers and hence break "RSA" and related cryptosystems on which the bulk of Internet commerce relies for security.

(Part of the last work is joint with Dr. Amlan Chakrabarti, University of Calcutta. It was covered in a post "Grilling Quantum Circuits" on the "Gödel's Lost Letter and P=NP" blog, and was incorporated into Chapter 16 of my text with Richard Lipton, Quantum Algorithms Via Linear Algebra.)

Kenneth Regan is Associate Professor at the University at Buffalo.

Please email Kristina Striegnitz (striegnk@union.edu) if you have any questions concerning the seminar series or if you would like to receive the seminar announcements by email.