  We report the realization, using nuclear magnetic resonance techniques, of
the first quantum computer that reliably executes an algorithm in the presence
of strong decoherence. The computer is based on a quantum error avoidance code
that protects against a class of multiple-qubit errors. The code stores two
decoherence-free logical qubits in four noisy physical qubits. The computer
successfully executes Grover's search algorithm in the presence of arbitrarily
strong engineered decoherence. A control computer with no decoherence
protection consistently fails under the same conditions.
