Quantum and Tensor Computing

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

**Instructor:** Vladik Kreinovich, office COMP 215, email vladik@utep.edu,
phone 747-6951.

**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.

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.

**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.