This morning I was re-reading David Deutsch’s classic paper “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer”, Proc. of the Roy. Soc. London A, 400, 97-117 (1985) This is the paper where he explicitly shows an example of a quantum speedup over what classical computers can do, the first time an explicit example of this effect had been pointed out. Amusingly his algorithm is not the one most people call Deutsch’s algorithm. But what I found funny was that I had forgotten about the last line of the article:
From what I have said, programs exist that would (in order of increasing difficulty) test the Bell inequality, test the linearity of quantum dynamics, and test the Everett interpretation. I leave it to the reader to write them.
I guess we are still waiting on a program for that last problem?