🚀 go-pugleaf

SPECIAL PROGRAM:

 The Ph.D. Program in Computer Science at Harvard
 ------------------------------------------------

 Professor Leslie Valiant will be pleased to meet any
 undergraduates interested in finding out more about
 the Ph.D. program in Computer Science at Harvard. He
 will be available...

    THURSDAY, 16 November 2000
    12:00 noon
    Newell-Simon Hall 3001 (right across from the Perlis Atrium)

    Bring a lunch.

 General information about the program can be found at:

    www.deas.harvard.edu/graduate/computer_science/index.html


NOTE:

  Dr. Valiant will be presenting the November 16 SCS Distinguished
  Lecture at 4:00 pm in Wean Hall 7500. He will discuss:


     Quantum Computations that Can be Simulated
     Classically in Polynomial Time

 ABSTRACT
 The universality of our computational models depends on physical
 suppositions, most notably on the polynomial time version of the
 Turing Hypothesis. Little systematic study of these suppositions
 has been attempted until relatively recently.  However, the quantum
 computational model does now offer an avenue to these foundational
 questions.  In this talk we shall describe some recent results
 that show that significant subclasses of quantum circuits can be
 simulated with only polynomial slowdown by classical computation.
 In particular, a broad class of circuits, each composed of unitary
 gates that generate and process highly entangled states, is
 insufficient in giving more than polynomial speedups over classical
 computers. The result says, in brief, that physics magic does not
 necessarily imply computational magic. We shall also discuss the
 broader context for such results, and some new problems that are raised.