Quantum Complexity Theory

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Lecture Notes; Problem Sets; Projects
MIT OpenCourseWare details
  • As taught in: Fall 2010
  • Department: Electrical Engineering and Computer Science
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Text Based

Specification
Access

Free Access

Academic Level

Graduate

SKU: quantum-complexity-theory Category: Brand:

An introduction to quantum complexity: BQP, quantum algorithms, query lower bounds, QMA, QIP and communication complexity, with project ideas.

At a glance
LevelAll Levels
AccessFree access
FormatText Based
As taught inFall 2010
DepartmentElectrical Engineering and Computer Science
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

What can quantum computers fundamentally do, and what are their limits? This introduction to quantum computational complexity theory aims to bring students to the research frontier, without assuming prior knowledge of quantum mechanics. It covers quantum algorithms, query lower bounds, classes such as BQP, QMA and QIP, quantum advice and communication complexity, and it ends with student projects on current literature.

What You Will Achieve

  • Explain how BQP relates to classical complexity classes
  • Analyze the Deutsch-Jozsa, Simon’s, Shor’s and Grover’s algorithms
  • Prove quantum query complexity lower bounds
  • Survey a topic in quantum complexity from the research literature


Program Overview

Quantum Basics and Algorithms

The first lectures set up the model and its main algorithms.

  • Quantum circuits
  • BQP and classical friends
  • Shor’s algorithm and the hidden subgroup problem
  • Grover’s algorithm and BBBV

Query Lower Bounds

The next group of lectures shows what quantum algorithms cannot do.

  • Quantum query complexity
  • The collision problem

The Zoo of Complexity Classes

Later lectures survey further classes and related questions.

  • QMA and QIP
  • PostBQP and BQP/qpoly
  • Closed timelike curves
  • Quantum communication complexity

Course Completion


Job Outlook

This material prepares students for research in quantum computing, quantum information and theoretical computer science.


Before you start: No prior knowledge of quantum mechanics is assumed. Open to students who have taken a previous course on computational complexity theory (such as 6.045 or 18.404J ), or a previous course on quantum computing and information (such as 18.435 ).

Our take

Good for: Theory students with a prior course in computational complexity or quantum information who want to reach current research in the field.

Keep in mind: The lecture notes were taken by students from a 2008 offering, and the syllabus warns of errors and omissions. There is no official textbook, and no problem set solutions are listed.

Bottom line: A route to the research frontier, from a subject where no single book covers the material.

Frequently Asked Questions

How much quantum mechanics does the class teach?

The first lectures cover quantum basics and quantum circuits, since the syllabus assumes no prior knowledge of quantum mechanics. Its focus after that is complexity, not physics.

What did the course projects involve?

Either a survey of a topic in the literature or original research, with a proposal, a 10-minute presentation and a report of up to five pages. Example topics are listed.

Which books does the syllabus suggest?

There is no official textbook. Helpful books include Nielsen and Chuang, Mermin, Arora and Barak, and Sipser, along with online notes by John Watrous and Quantum Computing Since Democritus.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0