Quantum Computation and Cryptography

Overview

Quantum mechanics is one of the most successful and, at the same time, controversial theories in physics. It has been established that the laws of quantum mechanics enable us to perform efficient computations and achieve cryptographic primitives (as well as many other things) that were otherwise assumed to be impossible.

In terms of computations, using quantum algorithms one can solve efficiently a wide range of problems which were believed to be extremely difficult (factoring, discrete logarithm computation, principal ideal computation etc). These problems are still assumed to be difficult to solve using classical computers. In fact, researchers were so confident in this belief that these problems were used as the basis for most of today's cryptographic protocols (RSA, El Gamal, Eliptic Curve Cryptography etc). This means for example, that an adversary having a quantum computer could, in principle, break most existing encryption schemes.

Fear not, though! While some cryptographic protocols are rendered useless against a quantum computer, quantum mechanics also gives us a solution, namely quantum cryptography. Quantum cryptography provides protocols which are secure not just against quantum computers, but against any kind of adversary (with unlimited computational resources), as their security is based on the laws of physics.

This workshop aims to give an introduction into these topics. By the end you will be, hopefully, familiar with the major ideas and concepts of quantum computation and quantum cryptography. Each lecture will have a set of assignments which you can do in order to improve your understanding.

When and Where?

Aug, 24th - Aug, 29th. The lectures will take place between 6:00pm and 8:00pm.
Location: Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare
Room: EC105

Outline

Each lecture is divided into two parts of 50 mins each.

  1. Monday, 24 Aug
    • Introduction: We start by looking at some very interesting and counter-intuitive features of quantum mechanics and the emergence of quantum computation. Presentation can be found here.
    • The quantum speed-up: We'll then try to understand where the power of quantum computers comes from by looking at a simple model of computation. Presentation can be found here.
  2. Tuesday, 25 Aug
    • Quantum information: The basics of how quantum information is represented and which operations can be performed on it (and which cannot). Presentation can be found here.
    • Quantum algorithms: Using what we've learned, we'll look at some of the first quantum algorithms and understand why they are efficient. We'll also look at some of their applications, such as breaking cryptography protocols. Presentation can be found here. A cheatsheet can be found here.
  3. Wednesday, 26 Aug
    • Quantum entanglement: One of the quintessential features of quantum mechanics/computing is entanglement. We'll see what it is, how it can be used for teleportation and why Einstein called it “spooky action-at-a-distance”. Presentation can be found here.
    • Where's my quantum computer?: After hopefully convincing you why quantum computers are awesome, we'll see why we don't have them yet. To do this we'll look at some of the problems in implementing them and how these are dealt with in practice (we'll also briefly touch upon D-Wave). Presentation can be found here.
  4. Thursday, 27 Aug
    • Cryptography 1: While we don't have quantum computers yet, we do have quantum cryptography. The security of quantum cryptography protocols is based on the laws of physics, rather than computationally hard problems. We'll look into a couple of these protocols to understand how they work and what interesting properties they have (unconditional security and device independence). Presentation can be found here.
    • Cryptography 2: Continuing, we'll also look into quantum authentication, digital signatures and also post-quantum cryptography (cryptography that is secure against quantum computers). Presentation can be found here.
  5. Friday, 28 Aug
    • Measurement-based quantum computing: We'll examine a relatively newer model of quantum computation which has been very fruitful in providing new insight into quantum computing and has widened its applications. Presentation can be found here.
    • Hot topics: The final part is dedicated to the various hot topics in the field, which are currently being researched (Universal Blind Quantum Computation, Topological Quantum Computation, Quantum Communication Complexity etc). Presentation can be found here.
  6. Saturday, 29 Aug - Bonus lecture by Daniel Ciocîrlan (daniel.ciocirlan@gmail.com)
    • Adiabatic quantum computing: We'll look at the following: an overview of the adiabatic theorem; adiabatic quantum computing (idea, constraints, gap condition); complexity in adiabatic quantum computing; how to solve SAT with a theoretical adiabatic quantum computer; D-Wave and blackbox (overview and principles); a few problems (SAT, NAND, WMIS in Python with D-Wave's Blackbox API). Presentation can be found here. The general program for D-Wave's Blackbox, can be found here.

Prerequisites

  • Basic knowledge of vector spaces, matrices and linear algebra in general
  • Basic knowledge of probabilities (what a probability distribution is, conditional probability)

No knowledge of quantum mechanics is required :)

Registration

Registration has closed.
If you have any questions, please email the organizer.

Instructor and Organizer

Alexandru Gheorghiu

E-mail: gheorghiuandru@gmail.com

sesiuni/quantum-comp.txt · Last modified: 2015/08/30 16:05 by andru