Calculable lower bounds on the efficiency of universal sets of quantum gates

Understand

Currently available quantum computers, so called Noisy Intermediate-Scale Quantum (NISQ) devices, are characterized by relatively low number of qubits and moderate gate fidelities.

• In such scenario, the implementation of quantum error correction is impossible and the performance of those devices is quite modest.
• In particular, the depth of circuits implementable with reasonably high fidelity is limited, and the minimization of circuit depth is required.
• Such depths depend on the efficiency of the universal set of gates $\mathcal{S}$ used in computation, and can be bounded using the Solovay-Kitaev theorem.