$\ell_p$-norm preserving Turing machines Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine.

For people working in complexity theory going to quantum complexity a great introductory text is Fortnow's paper which link was posted by Joshua Grochow here. In that paper, the quantum Turing machine is presented as a generalized probabilistic Turing machine. Basically, the probabilistic machine have a state $s$ normalized under the $\ell_1$-norm, i.e. $\parallel s\parallel_1=1$. The time evolution of the machine is given by the application of a stochastic matrix $P$ such that $\parallel Ps\parallel_1=1$, i.e. $P$ preserves the $\ell_1$-norm. So the state at time $t$ is $P^ts$ (the notation may not be precise because the left or right multiplication of $P$ depends on if $s$ is a row or column vector or the rows or columns of $P$ are the subspaces preserving the norm). So in this sense the probabilistic Turing machine is a $\ell_1$-norm preserving machine denoted $M^{\ell_1}$.

Then a quantum Turing machine can be seen as having a state $s$ with $\parallel s\parallel_2=1$ and unitary matrix $P$ (that preserves $\ell_2$-norms) such that $P^ts$ is the state at time $t$ where $\parallel P^ts\parallel_2=1$. This is a $\ell_2$-norm preserving machine denoted $M^{\ell_2}$.

Let in general a $\ell_p$-norm preserving machine be denoted by $M^{\ell_p}$.

So my questions are:

(1) What's the power of $\ell_p$-norm preserving machines for finite $p$? More formally, can we prove that for any given $p$ and $q$, if $q&gt;p$ then there exists a language $L$ and machine $M^{\ell_q}$ such that $M^{\ell_q}$ efficiently decides $L$ and there is no machine $M^{\ell_p}$ that efficiently decides $L$. For example, this could be a generalization of the question, is $NP \subseteq BQP$?.

(2) What about $p=\infty$? Here the maximum value of the components of the state vector is 1.

(3) These questions goes beyond unitarity so it is not expected to agree with quantum mechanics. In general, what happens with computation if you relax the unitarity restriction on operations? There are works about allowing non-linear operators (see Aaronson 2005).

(4) Maybe the most important, is it universal? I think this is clear, because for particular cases it is universal. But what happens with universality when $p=\infty$?
This is not a complete answer to the questions, but it is too long to write as a comment.  It expands my previous comment.

The question “What happens to computation if the axioms of quantum mechanics are modified a little?” is addressed in great detail by a fun paper [Aar04] by Scott Aaronson.  I believe that your questions are essentially answered in the first half of Section 2 of [Aar04].

Aaronson shows that if p&gt;0 and p≠2, then a matrix which preserves the p-norm for all vectors is necessarily a generalized permutation matrix (a product of a permutation matrix and a diagonal matrix).  He states that the same holds in the case p=∞.  All these hold for both over ℝ and over ℂ.  Note that this includes the case of p=1: stochastic matrices preserve the 1-norm for nonnegative vectors but not for all vectors in general.

I guess that a probabilistic Turing machine generalized as in [For00] has a generalized permutation matrix as its global transition matrix only if it is a deterministic Turing machine, but I do not have a proof at hand.

Aaronson discusses also several other modifications of the axioms of quantum mechanics in the paper.  For example, if we change the rule of measurement (instead of the set of allowed gates) so that the outcome x occurs with probability |αx|p/∑y|αy|p, where αy is the amplitude of |y⟩, then this “quantum computer” can solve any problems in PP (including NP-complete problems) in polynomial time unless p=2 (Proposition 5).

References

[Aar04] Scott Aaronson.  Is quantum mechanics an island in theoryspace?  In Proceedings of the Växjö Conference “Quantum Theory: Reconsideration of Foundations,” 2004.  arXiv:quant-ph/0401062v2.

[For00] Lance Fortnow.  One complexity theorist’s view of quantum computing.  In Computing: the Australasian Theory Symposium (CATS 2000), pp. 58–72, Jan. 2000.  http://dx.doi.org/10.1016/S1571-0661(05)80330-5