$\ell_p$-norm preserving Turing machines

Question

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

Answer 1

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

Answer 2

There was some article by Aaronson in which it is shown that when $p \not\in \{1,2\}$ there aren't really any norm-preserving matrices. But you can instead consider matrices which do not increase the $\ell_p$ norm. Naturally you would want Born's rule to give probabilities $\left| \psi_i \right|^p$. The problem is that if the norm of the state vector decreases, the probabilities don't add up to one anymore. Aaronson considered the case where you would renormalize the vector after each step (see the links in @Tsuyoshi's answer above). I believe the conclusion was that these machines would have great power.

Alternatively, instead of renormalizing the state vector, you could just accept that the probabilities don't add up to 1, and interpret the "left over" probability as corresponding to a "fail" outcome. In this case, you can modify the arguments in Laplante, Magniez in order to get an adversary bound for $\ell_p$. Basically, you can interpolate between the $\ell_1$ and $\ell_2$ cases which are given in their Theorem 1. It turns out that the complexity of unstructured search (think Grover algorithm) is $\Omega(N^{1/p})$. I never was able to find a matching upper bound here, though. To answer your question on $\ell_\infty$, I was able (IIRC) to show that the computational power of $\ell_p$ circuits for decision problems was equivalent to that of $\ell_q$ where $1/p+1/q=1$ (basically by taking the transpose of all the operators). I conjecture that these $\ell_p$ circuits had strictly increasing power as $p$ increases from 1 (classical) to 2 (quantum).