QUBIT COMPLEXITY OF CONTINUOUS PROBLEMS

Date: 
Monday, March 6, 2006 - 9:09am

Joseph F. Traub
Computer Science Department, Columbia University
Date: Monday, March 6, 2006
Time: 3:00pm-4:00pm
Location: Engineering I, Room 2114

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.

Biography:
currently unavailable

Host: Wim van Dam