Introduction to quantum computation and simulability

October 15-19, 2018

São Paulo, Brazil




  • Leandro Aolita (IF-UFRJ, Rio de Janeiro & ICTP/SAIFR, São Paulo)
  • Daniel J. Brod (UFF, Niterói)
  • Ernesto F. Galvão (UFF, Niterói)

Place:  Room 3


In this minicourse, we will introduce the essentials of the fascinating field of quantum computation and its (classical) simulability. The scope of the course will be self-contained. We will start from a general overview of the basics of quantum information, but will progress towards more advanced topics requiring a higher level of mathematical abstraction. In particular, we intend to address current research topics, including: approaches to the demonstration of quantum computational supremacy; useful and reliable quantum simulators; verification of quantum computations; connections with machine learning, etc.

The course is aimed at graduate students (or advanced undergrads) of all areas of physics, computer science, and mathematics. Basic knowledge of quantum mechanics is required and will be assumed. Even so, motivated mathematicians and computer scientists with no prior knowledge of quantum mechanics are also welcome, provided they read chapters 1 and 2 of the book “Quantum computer science”, by N. David Mermin (Cambridge University Press), as a preparation for the course.

There is no registration fee and limited funds are available for travel and local expenses.

The program will be online in the first week of October. 



Click here for online application

Registration deadline: August 17, 2018

Preliminary Program

Proposed schedule and contents:

Day 1.

Lecture 1 (Daniel). General overview of the field (I): Super-position principle and quantum parallelism. Doubly-exponentially many quantum states versus exponentially many classical ones (informal argument). Entanglement, super-dense coding, and quantum teleportation.

Lecture 2 (Leandro). General overview of the field (II): Quantum (cryptographic-)key distribution (BB84 and Ekert91 schemes), Bell’s theorem and Bell non-locality. Basic notions of device-independent quantum key distribution.

Lecture 3 (Ernesto). Quantum algorithms and circuits: Example of a simple quantum algorithm (e.g. Deutsch-Joza algorithm), universality and universal set of gates (Solovay-Kitaev theorem). Pauli group, Clifford circuits, IQP circuits, and other simple circuits.

Day 2.

Lecture 4 (Ernesto). Measurement-based quantum computing (MBQC) (I): Graph states and stabilizer formalism. 1-bit teleportation as a MBQC primitive. Universality constructions, adaptiveness.

Lecture 5 (Ernesto). Measurement-based quantum computing (II): Time-ordering, computational depth. How to implement Clifford and IQP circuits in the measurement-based approach. Contextuality and non-locality as resources for MBQC. Applications: blind quantum computation (and other protocols).

Lecture 6 (Leandro). The “physical corner” of Hilbert space (I): Doubly-exponentially many quantum states versus exponentially many classical ones (formal argument). Matrix-product states, projected entangled pairs (PEPS), and tensor-network basics.

Day 3.

Lecture 7 (Leandro). The “physical corner” of Hilbert space (II): Non-local physical state Ansätze. Bosonic and fermionic Gaussian states, and quantum neural-network states (Machine learning).

Lecture 8 (Daniel). Introduction to computational complexity theory (I): Decision problems. P, NP, and the polynomial hierarchy. Computational complexity conjectures. Example of NP-hard problem.

Lecture 9 (Daniel). Introduction to computational complexity theory (II): BQP and post-BQP problems.

Day 4.

Lecture 10 (Ernesto): Non-universal, but hard-to-simulate (intermediate) models of quantum computation. Notions of quantum simulation (weak versus strong simulations), adaptiveness. Revisiting Clifford circuits.

Lecture 11 (Ernesto): Sampling problems. Rejection sampling, other approaches to simulation. IQP circuits, DQC-1 model.

Lecture 12 (Daniel): The race for quantum supremacy (I). Boson-Sampling and random quantum circuits (Google’s approach).

Day 5.

Lecture 13 (Daniel): The race for quantum supremacy (II). Experimental considerations. Linear-optical experiments. Noisy Boson-Samplers and random quantum circuits.

Lecture 14 (Leandro): Verification of quantum computations and simulations (I). Basics of quantum-state tomography, direct fidelity estimation, and fidelity witnesses.

Lecture 15 (Leandro): Verification of quantum computations and simulations (II). Delegated and verifiable quantum computing. Interactive-proof schemes versus measurement-only schemes.


Additional Information