  We analyze and demonstrate the feasibility and superiority of linear optical
single-qubit fingerprinting over its classical counterpart. For one-qubit
fingerprinting of two-bit messages, we prepare `tetrahedral' qubit states
experimentally and show that they meet the requirements for quantum
fingerprinting to exceed the classical capability. We prove that shared
entanglement permits 100% reliable quantum fingerprinting, which will
outperform classical fingerprinting even with arbitrary amounts of shared
randomness.
