RUS  ENG
Full version
SEMINARS

Quantum computation
March 27, 2024 13:10, Steklov Mathematical Institute, Room 430 (8 Gubkina) + Zoom


Lecture 8. Universality in approximate sense

V. I. Yashin


https://youtu.be/KLuOetTCCYA

Abstract: In this Lecture we discussed whether it is possible to perform quantum computation efficiently if we have only a finite set of quantum operations available. In such a case, arbitrary quantum operations can only be expressed with some precision $\varepsilon>0$. The accuracy drops linearly as the number of operations increases. Owing to the Solovey-Kitaev theorem, we can rewrite any quantum circuit of size $\mathrm{SIZE}$ as a quantum circuit with a finite universal dictionary of gates, with size $\mathrm{SIZE}' = \mathrm{SIZE}\cdot \mathrm{polylog}\frac{\mathrm{SIZE}}{\varepsilon}$. The proof of the theorem relies on properties of the group $\mathrm{SU}(2)$. This theorem can be interpreted as guaranteeing the possibility, as in the classical case, to digitise continuous quantities. Also, this property turns out to be important for achieving fault-tolerance of quantum computations.


© Steklov Math. Inst. of RAS, 2024