Contact: E. Rodney Canfield, erc at cs dot uga dot edu
Pre-req: at least one of CSCI 2670, or a 3000-level MATH class, or a 3000-level PHYS class. You may contact Dr. Canfield if you feel that you are prepared to take this class despite lacking the prerequisite.
In recent years, computer scientists and physicists have begun to discuss the possibility of a computer whose hardware utilizes quantum phenomena. There has developed a notion of a quantum algorithm, and examples are known of computational problems whose solution can be carried out in significantly less time by a quantum algorithm than by the currently best known traditional algorithm. Foremost among these is the recovery of two primes, p and q, given their product pq. This particular algorithm, known as Shor's algorithm, will be the focal point of the course. Our objective will be to develop the basics of the subject, including quantum gates, circuits, and Turing machines, in sufficient detail to understand this algorithm. To fully understand the algorithm, it is necessary to cover some prerequisite number theory. To fully appreciate the significance of the algorithm, we will cover briefly also several of the standard complexity classes in theoretical computer science. There will also be some background in quantum mechanics, enough to motivate the definition of quantum algorithm, and to let the student have some understanding of the extent to which the goal of building a quantum computer is being realized.