MAT 315: Quantum Computation

14 — 18 March 2005

Old Main 403 Canisius College: 5:00pm — 8:00pm Daily

Instructor:
   Dr. Petrus Potgieter
Associate Professor
Department of Decision Sciences
School of Economic Sciences
University of South Africa (UNISA)

Course Abstract for MAT 315:  The main ideas behind developments in the theory and technology of quantum computation were articulated in the late 1970s and early 1980s by scientists from the United States and the Soviet Union. Some twenty years later the excitement is palpable as physicists and engineers rush to build quantum computing devices large enough to solve practical problems while computer scientists, operations researchers and  mathematicians try to find new algorithms in this paradigm.

For computer science and computer engineering, quantum computation is not an optional topic: with continuing miniaturization, computing devices would sooner or later have to deal with quantum mechanical effects in any case. Mathematics, in turn, has had strong links to mechanical (i.e. non-human) computation since at least 1900—not only (and certainly not initially) with the aim of obtaining numerical results, but rather with the idea of formal computability itself. One need think no further than Hilbert’s 10th problem and his Entscheidungsproblem for an illustration of this observation. Any development in the scientific concept of computation should therefore be carefully examined by mathematicians for its theoretical and for its practical impact.

Since the appearance of Maxwell’s Daemon over a hundred years ago, mathematics, physics and—later—computer science (if you will, algorithmic information theory) have faced some interesting common problems and this interplay is very much alive today. This can be seen in the continuing lively debate around the so-called Information Paradox for black holes, to name just one prominent example related to quantum computation.

The lectures are an expanded and revised version of a similar course given at the Corvinus University in Budapest at the end of 2003, at the invitation of the foundation Pro Renovanda Cultura Hungariae Alapítvány. The primary aim of the course is to give the audience a good basic grasp of the theory behind quantum computation, to enable them to understand quantum algorithms and to bring to their attention the very nice interaction between information science, physics and mathematics in this field.

Prerequisites for MAT 315:  Students taking MAT 315 for credit will preferably have had at least one calculus course, and some exposure to either linear algebra or discrete mathematics. A casual acquaintance with the principles of quantum mechanics and formal computability will be advantageous but not strictly necessary as all these ideas will be reviewed in the course.

Lecture Breakdown for MAT 315:  MAT 315 consists of five lectures of length three hours each, covering the followings topics, in summary.

Lecture 1:

  • Origin of the idea with Feynman and others and why we really need it.
  • Reversible and irreversible computation and thermodynamical issues, or Maxwell’s Daemon II.
  • Classical bits and quantum bits (qubits)—entanglement and measurement.
  • Logic gates and circuits in classical and in quantum computing.
Lecture 2:

  • Brief overview of quantum mechanics — operators on finite-dimensional state spaces.
  • Quantum logic gates consistent with the laws of physics.
  • Finding basis gates for quantum computation.
  • An elementary quantum algorithm.
Lecture 3:

  • The square root of NOT.
  • An overview of quantum algorithms currently known.
  • Grover’s algorithm.
  • A programming language for quantum computing.
  • Quantum computing and cryptology.
Lecture 4:
  • Quantum evolution for a state in finite-dimensional Hilbert space — vis-á-vis SchrÖdinger’s equation.
  • Controlling superposition.
  • Classical error correction.
  • Decoherence and quantum error correction.
Lecture 5:
  • What exactly do we mean by computation?
  • A million dollar question.
  • How does quantum computation fit into computability and complexity theory?
  • Other new and/or unusual models for computing, including Zeno machines and biological models.
  • Prospects for quantum computational theory and technology.
Biographical Sketch of Professor Potgieter:  Born in the South African province of KwaZulu-Natal during the decade of relentless economic optimism, Carnaby Street and Uhuru, Petrus Potgieter waited for things to calm down a bit before finishing his university education in the 1990s with a PhD in mathematics at the University of Pretoria, where he had been an undergraduate student before completing an MA at Kent State University in the USA. His academic interests are chiefly in the foundations of computation and computational complexity and in mathematical finance. Underlying both of these areas is the connection with probability theory and the observation that both deal with the interface between an agent (computing device or investor) and a system (human observers or the economy) by means of well defined signals (input or prices, respectively). He is a regular consultant to the South African financial industry, tireless advocate of Open Source operating systems and software, a regular contributor to the Mathematical Reviews and recently elected to the Executive of the Operations Research Society of South Africa. In the course of his academic career he has visited universities on four continents.

His hobbies include learning and thinking about languages and history, the latter especially from a socio-economic point of view. He is a strong believer in the process of civilization, i.e. the (obvious) idea that knowledge and its application has always been and will remain the engine of human progress.