  Searching large databases is an important problem with broad applications.
The Grover search algorithm provides a powerful method for quantum computers to
perform searches with a quadratic speedup in the number of required database
queries over classical computers. It is an optimal search algorithm for a
quantum computer, and has further applications as a subroutine for other
quantum algorithms. Searches with two qubits have been demonstrated on a
variety of platforms and proposed for others, but larger search spaces have
only been demonstrated on a non-scalable NMR system. Here, we report results
for a complete three-qubit Grover search algorithm using the scalable quantum
computing technology of trapped atomic ions, with better-than-classical
performance. The algorithm is performed for all 8 possible single-result
oracles and all 28 possible two-result oracles. Two methods of state marking
are used for the oracles: a phase-flip method employed by other experimental
demonstrations, and a Boolean method requiring an ancilla qubit that is
directly equivalent to the state-marking scheme required to perform a classical
search. All quantum solutions are shown to outperform their classical
counterparts. We also report the first implementation of a Toffoli-4 gate,
which is used along with Toffoli-3 gates to construct the algorithms; these
gates have process fidelities of 70.5% and 89.6%, respectively.
