Syllabus for the course CS 5353/CS 4390, Fall 2004

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

INSTRUCTOR: Vladik Kreinovich, office COMP 215, email, phone 747-6951.

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.


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:

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:

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:

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:

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