Optimality, universality and controllability in the theory of quantum computing – Sonata BIS project of National Science Centre, Poland, 2016-2021



Principal Investigator: Adam Sawicki

PhD students: Katarzyna Karnas (finished 2018), Lorenzo Mattioli (current)

MSc students and interns: Oskar Słowik, Sai Krishna Deep (former)


Description of the project

A memory of a classical computer stores bits, where each bit can be either 1 or 0 corresponding to the logical truth or false. On the very basic level, a computer program is a sequence of operations, encoded by Boolean aka switching functions, performed on bits for the completion of a specific task. Boolean functions are realized by logical gates – electronic devices which perform logical operations. A set of gates which allows implementation of any logical function is called a universal set of gates. Universal sets of gates are given for example by {AND, OR, NOT} which realize conjunction, disjunction and negation respectively, or {NAND} which is the negation of conjunction.

One can think of a quantum computer as a machine which operates on qubits – quantum bits. A qubit is the simplest quantum mechanical system with only two basis states which one can think of as states of truth and false. Qubit can be realized physically as polarization of light (vertical or horizontal) or spin (up or down). Quantum mechanics says that the state of a qubit can be any superposition of the state of truth with probability p1 and the state of false with a probability p2, where p1+p2=1. Therefore the set of quantum states for a single qubit is much bigger than for the classical bit. This is actually why quantum computers can perform various tasks much faster than classical ones. All one-qubit quantum gates, that is, operations which send one superposition of truth and false states into another superposition of truth and false states, preserving the sum of probabilities, have a nice mathematical structure: they form a unitary group SU(2). This group contains uncountable number of elements. Producing uncountable number of gates in a laboratory is unrealistic. Typically we have access only to a finite set of gate types which compositions give other gates. This way we can create only countably many SU(2) gates. They can, however, still be dense in SU(2) – that is approximate any gate we want with arbitrary precision. For example the famous set consisting of Hadamard gate H and the so-called phase gate T have this property, and therefore we call it a universal set of gates for one qubit. Of course quantum computer operates on many qubits and one need to add additional gates to form a set which is universal for n-qubit quantum computing. This project focus on various aspects of both one- and many- qudit universality problems – an inevitable part of any sort of quantum computation. The aim is to lay the foundations for the uniform understanding and description of the universality problems and question stemming from them.


Papers published in the project:


  1. K. Karnas, A. Sawicki, When is a product of finite order qubit gates of infinite order?, J. Phys. A: Math. Theor, 51, 7, 075305, (2018) 
  2. A. Sawicki, K. Karnas, Criteria for universality of quantum gates, Phys. Rev. A 95, 062303 (2017)
  3. A. Sawicki, K. Karnas, Universality of single-qudit gates, Ann. Henri Poincaré, 11, vol. 18, 3515–3552, (2017).