The 20th annual Symposium will be held on Thursday, April 23, 2009.

An Introduction to Quantum Algorithms
Norris 100, 9:15 AM

Tim  Rambo,   '09 4
   Majors: Physics, Computer Science
   Hometown: Charlotte, MI

Sponsor(s): Harold Connamacher
Support:  

Abstract: 
Quantum computation is a paradigm for computing based on principles of quantum mechanics. Since these computers are built upon quantum mechanics, they are capable of some seemingly strange behavior. One example of this behavior is known as superposition, wherein a quantum bit is both “on” and “off” simultaneously. Superposition is a key component in quantum computing, and one source of its potential power. While it has not been proven more powerful than traditional computing, there are a handful of cases in which quantum computing is known to be faster than the best known non-quantum approach. An interesting case of this is quantum search. For a search space of n elements, a traditional computer will , at worst, have to check all n elements of the space (which requires n operations) until it finds the solution to the search problem. A quantum computer on the other hand can, with high probability, find the correct solution in at worst n^1/2 operations, thereby achieving a significant speedup. This talk will begin with an introduction to quantum computing, (covering topics such as qubits, superposition, quantum operations, and quantum circuits,) and conclude with an analysis Grover’s Quantum Search Algorithm.

 4