Spring school on Quantum Computation

March 19-22, 2018
University of California, San Diego

Location: CSE building (EBU3B), room 1242

Overview: The 3.5-day Spring school will bring TCS researchers up to speed on the current excitement in quantum computing. The past decade had marked tremendous experimental progress, from one or two-qubit devices to dozens of qubits and more. What are the theoretical models for such devices, and what are their prospects? Can they be classically simulated, and if not, can they accomplish algorithmic speed-ups? What are the obstacles to full-blown fault-tolerant quantum computation? And what does all this tell us about complexity theory, cryptography, and quantum information?

Target audience: The school is oriented towards graduate students, postdocs and faculty alike, who want to get to a point where not only they understand the questions at the forefront of quantum complexity nowadays, but also can start thinking about them themselves. We expect participants to have a background in computer science (complexity and algorithms), as well as a working familiarity with linear algebra, but no prior exposure to quantum information is needed.

Schedule: Each day will have ~5 hours of lecture by Dorit Aharonov, David Gosset, and Thomas Vidick, and 1-2 hours of hands-on problem solving sessions in which the participants will solve exercises to integrate the material. We are still working on the detailed schedule, but talks would be roughly 9am-5pm on Monday,Tuesday,Wednesday, and 9am-3pm on Thursday. Problem solving sessions will follow the talks on the first 3 days.

Topics covered: The first day of the school will be devoted to establishing a common language: we’ll review the basics of quantum mechanics, entanglement, the quantum circuit model, the complexity class BQP, the notion of a local Hamiltonian, and the class QMA (the quantum analog of NP). In the rest of the school, we will branch out to several timely topics with interesting interconnections. We will describe restricted models of quantum computation, such as low-depth circuits and adiabatic computation, and ask whether they can be classically efficiently simulated or whether they encompass additional computational power; We will describe the theory of quantum error correcting codes, discuss how multiparticle entanglement is manifested in such codes and how they differ from classical codes; we will discuss quantum interactive proofs with one or more provers and their connection to cryptography (delegating quantum computations) and complexity (the quantum PCP conjecture). Emphasis will be put on interesting open algorithmic and computational complexity questions which are of appeal to theoretical computer scientists.


Dorit Aharonov
Hebrew University
David Gosset
IBM Research
Thomas Vidick
California Institute of Technology


Registration is free. Please register here.


when reserving any of the following hotels, please ask for the UCSD rate unless otherwise specified. UCSD rates are usually accommodated upon request but are not guaranteed; it depends on the hotel's availability (the sooner, the better!).

Questions? please email Shachar Lovett.