# Does quantum fingerprinting really argue for the exponential size of wavefunctions?

Does quantum fingerprinting really argue for the exponential size of wavefunctions? Quantum fingerprinting is the idea that an exponentially long classical string can be encoded in a linear number of entangled qubits using quantum fingerprints. To an exponential degree of accuracy, but not exactly, the fingerprints of two different exponentially long classical strings will be nearly orthogonal.

However, the whole idea of quantum fingerprinting rests upon the ability to tell if two different pure quantum states are identical or orthogonal. Can such a comparator exist? Let's work with comparing qubits first. Our hypothetical comparator has the property that if two pure qubits are identical, it always outputs YES. If they are orthogonal, it always outputs NO. For other cases, it may output either. Then, it would definitely output NO for $|0\rangle|1\rangle$ and $| 1\rangle|0\rangle$. By the superposition principle, it would also have to definitely output NO for the linear superposition ${1\over\sqrt{2}} \left[ |0\rangle|1\rangle +|1\rangle|0\rangle\right]$. It would also have to output YES for both ${1\over 2}\left(|0\rangle + |1\rangle\right)\left(|0\rangle + |1\rangle\right)$ and ${1\over 2}\left(|0\rangle - |1\rangle\right)\left(|0\rangle - |1\rangle\right)$, and hence, also YES for their linear combination ${1\over\sqrt{2}} \left[ |0\rangle|1\rangle +|1\rangle|0\rangle\right]$. Contradiction.

If we can't compare whether or not two quantum fingerprints are identical or nearly orthogonal, how then are they supposed to work? Is their apparent exponentiality "fake"?

-