Number-theoretic methods in quantum computing

Réalisation : 28 avril 2016 Mise en ligne : 28 avril 2016
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

An important problem in quantum computing is the so-called approximate synthesis problem: to find a quantum circuit, preferably as short as possible, that approximates a given unitary operator up to given epsilon. Moreover, the solution should be computed by an efficient algorithm. For nearly two decades, the standard solution to this problem was the Solovay-Kitaev algorithm, which is based on geometric ideas. This algorithm produces circuits of size O(log^c(1/epsilon)), where c is approximately 3.97.

It was a long-standing open problem whether this exponent c could be reduced to 1. In this talk, I will report on a number-theoretic algorithm that achieves circuit size O(log(1/epsilon)) in the case of the so-called Clifford+T gate set, thereby answering the above question positively.

In case the operator to be approximated is diagonal, the algorithm satisfies an even stronger property: it computes the optimal solution to the given approximation problem. The algorithm also generalizes to certain other gate sets arising from number-theoretic unitary groups. This is joint work with Neil J. Ross.

Langue :
CNRS - Centre National de la Recherche Scientifique (Publication), INRIA (Institut national de recherche en informatique et automatique) (Production), INRIA (Institut national de recherche en informatique et automatique) (Publication), Région PACA (Production), UNS (Publication), Peter Selinger (Intervenant)
Conditions d'utilisation
Droit commun de la propriété intellectuelle
Citer cette ressource :
Peter Selinger. Inria. (2016, 28 avril). Number-theoretic methods in quantum computing. [Vidéo]. Canal-U. (Consultée le 30 janvier 2023)