  Today ion traps are among the most promising physical systems for
constructing a quantum device harnessing the computing power inherent in the
laws of quantum physics. The standard circuit model of quantum computing
requires a universal set of quantum logic gates for the implementation of
arbitrary quantum operations. As in classical models of computation, quantum
error correction techniques enable rectification of small imperfections in gate
operations, thus allowing for perfect computation in the presence of noise. For
fault-tolerant computation, it is commonly believed that error thresholds
ranging between 10^-4 and 10^-2 will be required depending on the noise model
and the computational overhead for realizing the quantum gates. Up to now, all
experimental implementations have fallen short of these requirements. Here, we
report on a Molmer-Sorensen type gate operation entangling ions with a fidelity
of 99.3(1)% which together with single-qubit operations forms a universal set
of quantum gates. The gate operation is performed on a pair of qubits encoded
in two trapped calcium ions using a single amplitude-modulated laser beam
interacting with both ions at the same time. A robust gate operation, mapping
separable states onto maximally entangled states is achieved by adiabatically
switching the laser-ion coupling on and off. We analyse the performance of a
single gate and concatenations of up to 21 gate operations. The gate mechanism
holds great promise not only for two-qubit but also for multi-qubit operations.
