Los Alamos National Laboratory
Lab Home  |  Phone
 
 
Quantum Institute : 2006 Quantum Lunch Seminar Archives

CONTACTS

  • Coordinator
    Diego Dalvit
  • Quantum Lunch Location:
    T-Division Conference Room, TA-3,
    Building 123, Room 121





Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121.
For more information, contact Diego Dalvit.

Please note the location for this meeting is in Santa Fe, New Mexico
Noyce Conference Room, Santa Fe Institute, 1399 Hyde Park Road, Santa FE

May 3 , 2006
Wednesday, 3:30 PM

Contact: Howard N. Barnum
http://www.santafe.edu/events/abstract/416

Joseph M. Traub,
Columbia University

Qubit Complexity of Continuous Problems

Abstract

For the foreseeable future the number of qubits will be a crucial computational resource. 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.


Operated by Los Alamos National Security, LLC for the U.S. Department of Energy's NNSA

Inside | © Copyright 2007-8 Los Alamos National Security, LLC All rights reserved | Disclaimer/Privacy | Web Contact