Aproximación constructiva en Computación Cuántica

Abstract

[ES] Este documento presenta la prueba del teorema de Solovay- Kitaev en la forma de un algoritmo clásico eficiente para compilar una puerta arbitraria de un solo qbit en una secuencia de puertas de un conjunto fijo y finito. El algoritmo se puede usar, por ejemplo, para compilar el algoritmo de Shor (que usa rotaciones de ́ángulo π/2k) de una forma eficiente y con tolerancia a errores empleando exclusivamente las puertas Hadamard, las puertas NOT-controladas y la puerta π/8. Dada una precisión fijada ε > 0, el algoritmo aproxima a una puerta dada en un tiempo de ejecución O (log2,71(1/ε)), y produce como salida una secuencia de puertas cuánticas de longitud O (log3,97(1/ε)). También explicamos cómo se puede generalizar el algoritmo para aplicarlo a puertas de varios qbit y a matrices de SU(Cd).

[EN] This paper presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm to compile an arbitrary single-qubit gate into a sequence of gates of a fixed and finite set. The algorithm can be used, for example, to compile Shor’s algorithm (which uses π/2k rotations) in an efficient error-tolerant way using only the textit Hadamard gates, textit the NOT controlled gates and textit the gate π/8. The algorithm executes in time O (log2,71(1/ε)), and outputs a sequence of quantum gates O (log3,97(1/ε)) which is guaranteed to approximate the desired quantum gate with a precision less than ε > 0. We also explain how the algorithm can be generalized to apply to multi-qubit gates and SU(Cd) matrices.