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

Question

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"?

Answer 1

That fingerprinting argues for an exponential sized state is dubious, but not for quite the reason you outline.

First off, the orthogonality test. While you are correct that you can't with certainty tell whether two states are orthogonal, you can gain some information by performing the well known "swap test" on the states. If you have many copies of the states, and do the test on each pair, then you can get a pretty good idea whether they are orthogonal. Having many copies is feasible because you can just take 100 of your fingerprints and call that a large fingerprint. Since we only care about whether they are polynomial or exponential size, it doesn't matter that you are carting around 100 of them at once.

So, given that you can in fact tell whether two fingerprints are identical or nearly orthogonal, does this say something about whether the states are exponential size? Not so much in this case and in my opinion, because you can do something very similar with classical probability distributions. Given a document, you can just compute a hash function and use that as a fingerprint. Of course, hash functions have collisions, so sometimes two documents will have the exact same fingerprint. You get around this by choosing a hash function at random. Your fingerprint then consists of the hash of the document along with a description of which hash was chosen. Now, since the hash was chosen at random, the same document will have a different fingerprint every time you create a fingerprint. However, consider the fingerprint as a probability distribution, with uniform weights among each of the hash functions that could have been chosen. If you are comparing quantum vs. classical, then you should always allow the option that the classical object can be a probability distribution. Then, equal documents will have equal fingerprints (the same probability distributions), and different documents will have fingerprints that are with very high probability distinguishable.

That being said, there is at least one case where the quantum fingerprint wins out over the classical one (even with probability distributions). That is the case where you need to compare two fingerprints for equality, without having access to the original document. This is discussed in Section V of Buhrman, Cleve, Massar, de Wolf. They also outline the random fingerprints and the swap test that I mentioned above.

A much more compelling argument for a exponential sized state comes from various communication problems where quantum communication is exponentially better than classical. Many examples are in the Buhrman paper linked to above. Of course none of this really proves the state is exponentially large, and people will probably argue about it for a long time.