Title: Exponential Improvements in Qubit Complexity

Speaker: Joseph F. Traub, Columbia University & Santa Fe Institute

Date/Time: Monday, December 7, 2009, 10:30 – 11:30 am        

Location: CSRI Building, Room 90 (Sandia NM)

Brief Abstract: There is a general belief that Moore's Law will end within some ten year using current silicon technology. Quantum computation is one candidate for a future technology.

For the foreseeable future the number of qubits will be a crucial computational resource on a quantum computer.  We show how to lower bound the qubit complexity using the classical query complexity.

We use this result to present a simple problem which cannot be solved on a quantum computer in the standard quantum setting with deterministic queries but can be solved on a classical computer using randomized queries (Monte Carlo).  This suggests introducing a quantum setting with randomized queries.

We apply this setting to high dimensional integration and to path integration.  In particular, there is an exponential improvement in the qubit complexity of path integration using the quantum setting with randomized queries.

We end by discussing future directions and where to learn more.

CSRI POC: Danny Rintoul, (505) 844-9592