What kind of program was Deutsch envisioning to test for the linearity of quantum mechanics?

Question

I've recently been studying Deutsch's 1985 paper "Quantum theory, the Church-Turing principle and the universal quantum computer" (pdf here). In this he endorses the position that a naïve statement of the Church-Turing thesis is in tension with quantum mechanics. He augments the Church-Turing thesis to consider universal quantum Turing machines (QTM), in lieu of or in addition to the (classical) Turing machines, and suggests a number of ways to use such quantum Turing machines to test various predictions of quantum mechanics.

Deutsch finds it instructive to program his QTM with a high-level programming language. For example, he contends that the following ALGOL-68 code "is a performance of the Einstein-Podolsky-Rosen experiment" (emphasis in original):

BEGIN
   INT n=8*random;                %pick one of eight random rotation matrices%
   BOOL x, y;                     %prepare two qubits%
   x:=y:=FALSE;                   %initialize the qubits to |0>%
   V(8,y);                        %apply a Hadamard matrix to the second qubit%
   x eorab y;                     %perform a CNOT (exclusive OR) operation%
   IF V(n,y)≠                     %perform the random rotation on qubit y%
      V(n,x)                      %do the same on qubit x%
      THEN print(("Quantum theory refuted."))
      ELSE print(("Quantum theory corroborated."))
   FI
END

Deutsch ends his paper rather cheekily with a couple of challenges:

Quantum computers raise interesting problems for the design of programming languages, which I shall not go into here. 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. (Emphasis added).

In addition to the ALGOL pseudocode for the EPR experiment above, of the three other challenges proposed by Deutsch we regularly program quantum computers to run Bell experiments now, for example with CHSH games. While, Deutsch's grand vision of combining AI with quantum computers to place a conscious AI in superposition so as to test the Everettian many-worlds hypothesis is manifestly difficult and perhaps reliant on questionable or at least controversial assumptions.

But, what kind of program could test for the (non)linearity of quantum dynamics?

For example, would a failure of quantum phase estimation falsify linearity? Are there old ideas of, say, Wigner or others, that could be put to the test with a quantum computer succinctly described with a snippet of code or a quantum circuit?

---

^{As far as I can see, this is the first explicitly written program to perform a purely quantum task. For example as Deutsch notes, Feynman's earlier 1982 talk/paper proposed something that we would now call a quantum simulator but only briefly described how such a device could be "programmed" with ladder operators, while Feynman's 1985 proposal of a quantum mechanical computer offered reversible circuits for the (classical) half- and full-adder.}

Answer 1

The obvious test is to tomograph a state evolution that you suspect of being nonlinear. Let $f$ be the evolution such that (up to normalization) $$f(|\psi\rangle + |\phi\rangle) \neq f(|\psi\rangle) + f(|\phi\rangle).$$Then you do quantum state tomography on $f(|\psi\rangle),f(|\phi\rangle)$, and $f(|\psi\rangle + |\phi\rangle)$. If they don't respect the equation, bingo, you have falsified the linearity of quantum mechanics, and your Nobel Prize will arrive soon by mail. One possible such $f$ is the cloning function, which cannot exist because of linearity.

Merely failing quantum phase estimation or some other task is not enough, as there are several different ways to cause such a failure while respecting linearity. For example, due to decoherence.