Thursday, March 4, Volen 101, 2:10-3:10 pm. (Refreshments at 2:00pm)
A central feature of quantum mechanics is the notion of superposed state of a physical system, in which mutually exclusive states, in the classical sense, coexist as a complex linear combination of all of them. The state of the computing system can be prepared as the uniform superposition of all possible states representable with $n$ bits (qu-bits). A computational process applied to the system makes each basic state evolve independently, exposing a parallelism exponential in the size of the representation. It is therefore tempting to expect exponential speed-ups of hard problems, such as factoring or members of the NP-complete class. The major difficulty, however, is the extraction of the output, or, "reading the wave function". This is achievable by making the basic states collectively interfere. A clever interference technique due to Grover allows quadratic speed-up for the search problem (and this is optimal). By contrast, the special number-theoretic nature of factoring promises an exponential speed-up for this problem.
Host: Harry Mairson