Quantum Computation and Cryptography

Overview

Quantum mechanics is one of the most successful and, at the same time, counter-intuitive theories in physics. In the past 30 years, it has been established that quantum mechanics allows us to solve a whole range of problems which are believed to be intractable for regular computers. Moreover, it can allow for cryptographic tasks that achieve an unprecedented level of security. Thus, the fields of quantum computation, quantum cryptography and quantum information theory were born. Recently, it has been shown that the theory of quantum information can even be used to investigate difficult questions about black holes, wormholes, quantum fields, space-time geometry and others.

In terms of computations, using quantum algorithms one can efficiently solve 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. On top of that, quantum algorithms can be used to efficiently simulate complex quantum systems, a task which can take a long time even on the most powerful supercomputers.

While some cryptographic protocols can be easily broken by a quantum computer, we also have a potential 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 fundamental laws of physics.

The workshop (like the one from last year, which you can find here) aims to give a general introduction to these topics. This year's workshop will span 2 weeks and apart from lectures will also include programming labs in Microsoft's Liquid, The Language Integrated Quantum Operations Simulator. Liquid was developed by Microsoft's QuArC (Quantum Architectures and Computation) group, it is quite easy to learn and use and includes a wide range of tools pertaining to quantum computation, simulation and quantum systems in general. It was recently used as part of a competition, called the Quantum Challenge, aimed at getting people more interested in quantum computation through programming. You can read more about Liquid here.

By the end of the workshop you will, hopefully, be familiar with the major ideas and concepts of quantum computation and quantum cryptography, you will know how to write some “quantum code” and you will have had some fun :)

When and Where?

Dates: Aug 15th - Aug 26th (excluding the weekend in between, see outline below).
Times: 7pm-9pm
Location: Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare
Room: EC004

Outline

There will be 6 lecture days and 4 lab days. Lecture days will comprise of 2 lectures of 50 mins each. Lab days will involve 2 sessions of 50 mins each of solving problems and programming in Liquid.

  1. Monday, 15 Aug
    • Introduction: Why are quantum computation and cryptography interesting? What is it that makes them strange but at the same time extremely useful? What is the current state of the art? We'll try to answer these questions in the broad sense in this introductory lecture. Presentation can be found here.
    • The quantum speed-up: Next, we'll try to understand where the power of quantum computers comes from by remembering some high-school physics and looking at a simple model of computation. Presentation can be found here.
  2. Tuesday, 16 Aug
    • Basic quantum mechanics: What exactly is quantum mechanics anyway? We'll look at its postulates and try to understand them from an informational and computational perspective. Presentation can be found here.
    • Measurement, collapse and all that: One of the weirdest features of quantum mechanics is measurement. Armed with our understanding of the QM postulates, we'll investigate what quantum measurement is all about. Presentation can be found here.
  3. Wednesday, 17 Aug
    • Liquid lab: Using what we've learned, we'll try to do some basic quantum operations in Liquid. This will, hopefully, develop your intuition about the concepts and pave the way towards understanding quantum algorithms. The labsheet can be found here and the source file we'll use is here. You might also want to look at this useful sheet containing the basics concepts of QM here. The solutions are here.
  4. Thursday, 18 Aug
    • Quantum algorithms 1: We now have all the tools to start looking at some of the first quantum algorithms and understand why they are more efficient than their classical counterparts. Presentation can be found here.
    • Quantum algorithms 2: We'll discuss some of the more advanced quantum algorithms and see how they can be used to break classical cryptography. Presentation can be found here.
  5. Friday, 19 Aug
    • Liquid lab: Implementing and testing quantum algorithms in Liquid. The labsheet can be found here and the source files we'll use are here and here. We're also going to use a library of black box functions which can be found here here. In part 2 we're going to implement Grover's algorithm, for which you can find a description here. Solutions can be found here and here. Paper on which the bomb detector is based on can be found here.
  6. Monday, 22 Aug
    • Quantum entanglement: One of the most interesting concepts in quantum mechanics, referred to by Einstein as “spooky action at a distance”. We'll try to understand what it's about and why it's so spooky. Presentation can be found here.
    • Quantum cryptography: Having understood entanglement, we now have all the elements to talk about quantum cryptography, what the protocols do and how one can achieve security based on the laws of physics. Presentation can be found here
  7. Tuesday, 23 Aug
    • Liquid lab: Implementing and playing with entanglement-based applications in Liquid (teleportation, super-dense coding, cryptography). Labsheet can be found here and the source file here. Solutions can be found here.
  8. Wednesday, 24 Aug
    • Quantum physics: Things have been a bit abstract, so let's delve into some actual physics and see how all the things discussed so far would be implemented in practice. Presentation can be found here.
    • Where are the quantum computers?: We have, thus far, idealized the real world. What are the practical (physical) challenges in building quantum computers? How can we resolve these challenges? Presentation can be found here.
  9. Thursday, 25 Aug
    • Liquid lab: Doing some simple quantum error correction. Labsheet can be found here and the source file here. Solutions can be found here.
  10. Friday, 26 Aug
    • Hot topics: What are some of the hot topics in the field? We'll briefly go through some of them (Universal Blind Quantum Computation, Topological Quantum Computation, Quantum Communication Complexity etc) and see why they're interesting and how far along we are with them. Presentation can be found here.
    • Fun stuff: Saving the best for last, we'll look at some of the most unexpected (and quite interesting) applications of quantum information and quantum computation to things like black holes, quantum field theory, quantum computation without quantum computers etc. Presentation can be found here.

Prerequisites

It is recommended that you are familiar with the basics of:

  • Complex numbers
  • Vector spaces and linear algebra
  • Probability theory

In particular, no knowledge of quantum mechanics is required :)

What do I mean by “the basics”? Ideally you should be able to answer these questions, or at the very least be familiar with the concepts addressed by the questions. In any case, if you want to gain the most out of this workshop, you should briefly recap these “basics” :)

Additionally, for the labs it would be useful (but not necessary) if you've had some basic programming experience. You should follow the instructions listed here to install and be able to use Liquid. You can also find useful tutorials for Liquid here and here.

Registration

Registration is now closed. If you have any questions, please email me (see below).

Instructor and Organizer

Alexandru Gheorghiu

E-mail: gheorghiuandru@gmail.com

sesiuni/quantum-comp.txt · Last modified: 2016/09/11 10:26 by agheorghiu