Novel strategy for database searching in spin Liouville space by NMR ensemble computing

Quantum computing by nuclear magnetic resonance using pseudopure spin state s is bound by the maximal speed of quantum computing algorithms operating o n pure states. In contrast to these quantum computing algorithms, a novel a lgorithm for searching an unsorted database is presented here that operates on truly mixed states in spin Liouville space. It provides an exponential speedup over Grover's quantum search algorithm with the sensitivity scaling exponentially with the number of spins, as for pseudopure state implementa tions. The minimal decoherence time required is exponentially shorter than that for Grover's algorithm.