Experimental implementation of Hogg’s algorithm on a three-quantum-bit NMR quantum computer
Xinhua Peng, Xiwen Zhu, Ximing Fang, Mang Feng, Maili Liu, Kelin Gao · Physical Review A · 2002
Using nuclear magnetic resonance (NMR) techniques with a three-qubit sample, we have experimentally implemented the highly structured algorithm for the satisfiability problem with one variable in each clause proposed by Hogg. A simplified temporal averaging procedure was employed to prepare the three-qubit pseudopure state. The algorithm was completed with only a single evaluation of the structure of the problem and the solutions were found theoretically with probability $100%,$ results that outperform both unstructured quantum and the best classical search algorithms. However, about $90%$ of the corresponding experimental fidelities can be attributed to the imperfections of manipulations.