| Home | About Me | Courses | Recent Publications | Collaborators | Research Interests | Data | Contact |
School of Computational Sciences
QUANTUM COMPLEXITY THEORY
CSI-789-004, 75815 FALL 2004
Cross Listed with PHYS 780-002, 75816
Description: This course will provide the requisite materials to understand quantum complexity theory and its applications. The emphasis will be to explore the emerging research in quantum complexity theory and related issues of quantum algorithms. Topics that will be covered include classical complexity classes, quantum complexity classes, quantum algorithms, quantum communication complexity, and cryptography. The quantum complexity classes and quantum algorithms will include recent works will cover power and limitations of quantum computers. Applications and case studies will include quantum teleportation, quantum counting, and quantum fingerprinting.
Course objectives: To provide students with an introduction to quantum information science techniques, analysis of quantum algorithms, and the basic fundamental physics involved in this technology. The course will (1) prepare the student to undertake graduate research in quantum computing and related areas, (2) prepare the student to participate in professional activities in this field of study, (3) broaden the student’s background in the general field of novel computer architectures, and (4) prepare the student to explore finding applications of this enabling technology to areas of interest to specific users. It will also introduce related areas such as fault-tolerance and cryptography.
Prerequisites: An undergraduate course on Quantum Computation, or Quantum Physics, or General Physics, or Computer Science, and an Undergraduate Degree in the Physical or Computer Sciences, or Permission of Instructor.
Text:
1. Classical and Quantum Computation by A. Yu. Kitaev, A.H. Shen, M. N. Vyalyi
2. An Introduction to Quantum Complexity Theory – Richard Cleve
http://xxx.lanl.gov/find/quant-ph/1/au:+Cleve_R/0/1/0/all/0/1
Grading: Assigned Project and Oral Presentation – 60%
Mid-Term Take-Home Exam – 30%
Class Participation and Group Discussion – 10%
Instructor: Dr. Richard B. Gomez
Office: George Johnson Center Room 237
Office Hours: 2 – 5 Tuesdays or other hours by appointment
Office Phone: 703-993-3629
E-mail: rgomez@gmu.edu
Class Place, Dates, and Times: Innovation Hall, Room 134, Fridays 4:30 pm to 7:10 pm. First day of class is 3 September 2004 and last day of class is 10 December 2004.
Course Section Topics Number of Weeks
Part I. Review of Classical Computability Theory 1
-Turing Machines
-Boolean Circuits
-Computability Theory
Part II. Review of Classical Complexity Theory 3
-Space and Time Complexity for Turing Machines
-Hierarchy of Classical Complexity Classes
-Classes P, NP, CO-NP, R
-NP Class: Reducibility and Completeness
-BPP: Probabilistic Algorithms
-Proofs: Interactive and Probabilistically Checkable
-Average Case Complexity and Distributed NP
Part III. Quantum Complexity Theory 4
-Concepts, Definition and Notations
-Quantum Circuit and Circuit Complexity
-Quantum Computation: Complexity Perspective
-Quantum Fourier Transform
-Deutsch-Josza Algorithm, Simon’s Algorithm
-Shor’s Quantum Algorithm for integer factorization
-Grover’s Search Algorithm
-BQP Class: Quantum Probability
-BQNP Class: Quantum Analogue of NP
-Quantum Complexity and Measurement
-Quantum Algorithms for Abelian group
Part IV. Quantum Complexity Classes and Open problems 2
-Relations between Classical and Quantum Complexity classes
-Open problems and Quantum Complexity Theory
Part V. Quantum Communication Complexity Theory 1
-Query Complexity of order finding; Lower bound and Upper bound
-Quantum Communication Complexity
-Converting one complexity to another
Part VI. Applications Case Studies and Class Presentations 3
-Quantum Teleportation
-Quantum Counting and Minimum Distance
-Quantum Fingerprinting
-Class Presentations