TOPICS IN EMERGING COMPUTING PARADIGMS/TOPICS IN SOFT COMPUTING
Quantum and Tensor Computing
Syllabus for course CS 5353/CS 4365, Fall 2009

Class time: Tuesday and Thursday 1:30-2:50 pm, COMP 321.

Office hours: Tuesday and Thursday 10:00-10:30 am, 12:00-12:30 pm, 1:00-1:30 pm, 3:00-3:30 pm, or by appointment.

Prerequisites:

• for CS 5353: graduate level standing;
• for CS 4365: upper-level standing; ideally, either Probability/Statistics or Matrix Algebra (MATH 3323).

General course description: Introduction to emerging, revolutionary computing paradigms. Topics may include quantum, chemical, and biological computing. May be repeated for credit when topic varies.

Main objectives of this particular course: 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.

In quantum computing, a special role is played by tensors, a natural generalization of vectors and matrices that have been used to describe interactions between quantum bits. In this class, we will also show how tensors can be used to speed up computations beyond quantum computing: e.g., in traditional (non-quantum) high performance computing.

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.

General learning outcomes for CS 5353

1. Knowledge and Comprehension

a. Understand the need for emerging, revolutionary computing paradigms - e.g., NP-hardness of many practical problems

b. Understand the main physical and engineering ideas behind a specific paradigm (such as quantum, chemical, and biological computing)

c. Know and understand the mathematics behind the new paradigm: e.g., for quantum computing, complex numbers, Hilbert space, operators, projection, tensor product, etc.

d. Know the main algorithms developed within the studied paradigm: e.g., for quantum computing, fast search, integer factorization, and quantum cryptography; understand the problems solved by these algorithms and the practical need to solve these problems fast

e. Know the best existing algorithms (within the standard computing paradigm) for solving the problems that the new paradigms solves; understand the advantages of the new paradigm in solving these problems

f. Understand the main ideas behind other algorithms developed within the paradigm, and the problems solved by these algorithms

g. Understand the current state of practical implementation of the studied paradigm

h. Understand the engineering and computational limitations of the studied paradigm

i. Have a general understanding of other emerging computing paradigms.

2. Application and Analysis

a. Use the mathematics behind the new paradigm, on simple examples

b. Trace the best existing algorithms (within the standard computing paradigm) for solving the problems that the new paradigms solves

c. Trace the main algorithms developed within a studied paradigm on simple examples

3. Synthesis and Evaluation

a. Within the studied paradigm, design new algorithms for solving problems which are similar to the ones studied in the class

b. Understand and present a published research paper related to the class topic - with a minor help from a professor

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 you all in the class!