TOPICS IN EMERGING COMPUTING PARADIGMS/QUANTUM COMPUTING
Syllabus for the course CS 5353/CS 4390, Fall 2004

CLASS TIME: Tuesday and Thursday 4:30-5:50 pm, COMP 321.

OFFICE HOURS: Tuesday and Thursday 8:30-9:00 am, 12:00-12:30 pm, 4:00-4:30 pm, 6:00-6:30 pm, or by appointment.

PREREQUISITES:

• for CS 5353: graduate level standing;
• for CS 4390: upper-level standing, preferable either Probability/Statistics (EE 3384 or STAT 3330) or Matrix Algebra (MATH 3323).

MAIN OBJECTIVES: to learn about the computers of the distant future: what will they look like? how to program them?

CONTENTS: No matter how fast modern computers are, there are still problems that take too much computational time and, thus, cannot yet be handled by modern computers. To solve these problems, we must design faster and faster computers.

So far, the speed of the computers has been doubling every 18 months; this is known as Moore's law. Can we keep up with this increase?

According to modern physics, all velocities are bounded by the speed of light; thus, to make computer elements faster, designers try to decrease the size of these elements. At present, the size of the computing elements is in hundreds or dozens of molecules. As the size shrinks to single molecules, we must take into consideration the peculiar properties of physical objects at such small sizes. These properties are described by a special branch of physics called quantum physics.

Originally, in computer design, quantum effects were viewed primarily as a nuisance, e.g., as a source of extra noise. It turns out, however, that quantum effects can also drastically speed up computations. Due to peculiar properties of quantum physics, quantum computers have a potential to do many unexpected things:

• they can do exhaustive search in an unsorted list of n elements (a problem which normally requires n steps) in only square root of n time;
• they can crack most existing codes really fast, and
• they can do many other exciting things.
Due to the extraordinary potential abilities of quantum computations, main computer companies (IBM, AT&T, Microsoft, Intel) are currently trying to make quantum computing real.

Other schemes have been proposed for fast computations, from more practical ones involving genetic computing, chemical computing, etc, to more futuristic ones involving black holes and subtle effects of quantum field theory.

The course will contain:

• a brief popular exposition of modern physical theories (mainly quantum mechanics) that may lead to future computer designs;
• serious description of algorithms which use the corresponding physical phenomena; and finally,
• futuristic speculations about the possible future computers.
PROJECTS: These projects will include mainly theory; you'll have to read, analyze and discuss some theoretical paper, and - for extra credit - come up with some new ideas.

MAIN SOURCE: Michael A. Nielsen and Isaac L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press.

TESTS AND GRADES: There will be two tests and one final exam. Each topic means home assignments (some on the sheets of paper, some on a real computer). Maximum number of points:

• first test: 10
• second test: 25
• home assignments: 10
• final exam: 35
• project: 20

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

• to get an A, you must gain, on all the tests and home assignments, at least 90% of the total possible amount of points (i.e., at least 72 points out of 80), and also at least 90 points overall;
• to get a B, you must gain, on all the tests and home assignments, at least 80% of the total possible amount of points (i.e., at least 64 out of 80), and also at least 80 points overall;
• to get a C, you must gain, on all the tests and home assignments, at least 70% of the total possible amount of points (i.e., at least 56 out of 80), and also at least 70 points overall.

STANDARDS OF CONDUCT: Students are expected to conduct themselves in a professional and courteous manner, as prescribed by UTEP Standards of Conduct. Students may discuss programming exercises in a general way with other students, but the solutions must be done independently. Similarly, groups may discuss project assignments with other groups, but the solutions must be done by the group itself. Graded work should be unmistakably your own. You may not transcribe or copy a solution taken from another person, book, or other source, e.g., a web page). Professors are required to - and will - report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students.

DISABILITIES: If you feel you may have a disability that requires accommodation, contact the Disabled Student Services Office at 747-5148, go to Room 106 E. Union, or e-mail to dss@utep.edu.

SEE Y'ALL IN THE CLASS!