MIP*=RE: What it could possibly mean?

I received a very interesting link to a popular article (see this) explaining a recently discovered deep result in mathematics having implications also in physics. The article (see this) by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen has a rather concise title " MIP*=RE". In the following I try to express the impressions of a (non-mainstream) physicist about the result. In the first posting I discuss the finding and the basic implications from the physics point of view. In the second posting the highly interesting implications of the finding in the TGD framework are discussed.

The result expressed can be expressed by using the concepts of computer science about which I know very little at the hard technical level. The results are however told to state something highly non-trivial about physics.

1. RE (recursively enumerable languages) denotes all problems solvable by computer. P denotes the problems solvable in a polynomial time. NP does not refer to a non-polynomial time but to "non-deterministic polynomial acceptable problems" - I hope this helps the reader- I am a little bit confused! It is not known whether P = NP is true.
2. IP problems (P is now for "prover" that can be solved by a collaboration of an interrogator and prover who tries to convince the interrogator that her proof is convincing with high enough probability. MIP involves multiple l provers treated as criminals trying to prove that they are innocent and being not allowed to communicate. MIP* is the class of solvable problems in which the provers are allowed to entangle.

The finding, which is characterized as shocking, is that all problems solvable by a Turing computer belong to this class: RE= MIP*. All problems solvable by computer would reduce to problems in the class MIP*! Quantum computation would indeed add something genuinely new to the classical computation.

Two physically interesting applications

There are two physically interesting applications of the theorem which are interesting also from the TGD point of view and force to make explicit the assumptions involved.

1. About the quantum physical interpretation of MIP*

To proceed one must clarify the quantum physical interpretation of MIP*.

1. Quantum measurement requires entanglement of the observer O with the measured system M. What is basically measured is the density matrix of M (or equivalently that of O). State function reduction gives as an outcome a state, which corresponds to an eigenvalue of the density matrix. Note that this state can be an entangled state if the density matrix has degenerate eigenvalues.
2. Quantum measurement can be regarded as a question to the measured system: "What are the values of given commuting observables?". The final state of quantum measurement provides an eigenstate of the observables as the answer to this question. M would be in the role of the prover and O_i would serve as interrogators.

   In the first case multiple interrogators measurements would entangle M with unentangled states of the tensor product H₁⊗ H₂ for O followed by a state function reduction splitting the state of M to un-entangled state in the tensor product M₁⊗ M₂.

   In the second case the entire M would be interrogated using entanglement of M with entangled states of H₁⊗ H₂ using measurements of several commuting observables. The theorem would state that interrogation in this manner is more efficient in infinite-D case unless HFFs are involved.

3. This interpretation differs from the interpretation in terms of computational problem solving in which one would have several provers and one interrogator. Could these interpretations be dual as the complete symmetry of the quantum measurement with respect to O and M suggests? In the case of multiple provers (analogous to accused criminals) it is advantageous to isolate them. In the case of multiple interrogators the best result is obtained if the interrogator does not effectively split itself into several ones.

2. Connes embedding problem and the notion of finite measurement/cognitive resolution

Alain Connes formulated what has become known as Connes embedding problem. The question is whether infinite matrices forming factor of type II₁ can be always approximated by finite-D matrices that is imbedded in a hyperfinite factor of type II₁ (HFF). Factors of type II and their HFFs are special classes of von Neumann algebras possibly relevant for quantum theory.

This result means that if one has measured of a complete set of for a product of commuting observables acting in the full space, one can find in the finite-dimensional case a unitary transformation transforming the observables to tensor products of observables associated with the factors of a tensor product. In the infinite-D case this is not true.

What seems to put alarms ringing is that in TGD there are excellent arguments suggesting that the state space has HFFs as building bricks. Does the result mean that entanglement cannot help in quantum computation in TGD Universe? I do not want to live in this kind of Universe!

2. Tsirelson problem

Tsirelson problem (see this) is another problem mentioned in the popular article as a physically interesting application. The problem relates to the mathematical description of quantum measurement.

Three systems are considered. There are two systems O₁ and O₂ representing observers and the third representing the measured system M. The measurement reducing the entanglement between M and O₁ or O₂ can regarded as producing correspondence between state of M and O₁ or O₂, and one can think that O₁ or O₂ measures only obserservables in its own state space as a kind of image of M. There are two manners to see the situation. The provers correspond now to the observers and the two situations correspond to provers without and with entanglement.

Consider first a situation in which one has single Hilbert space H and single observer O. This situation is analogous to IP.

1. The state of the system is described statistically by a density matrix - not necessarily pure state -, whose diagonal elements have interpretation as reduction probabilities of states in this bases. The measurement situation fixes the state basis used. Assume an ensemble of identical copies of the system in this state. Assume that one has a complete set of commuting observables.
2. By measuring all observables for the members of the ensemble one obtains the probabilities as diagonal elements of the density matrix. If the observable is the density matrix having no- degenerate eigenvalues, the situation is simplified dramatically. It is enough to use the density matrix as an observable. TGD based quantum measurement theory assumes that the density matrix describing the entanglement between two subsystems is in a universal observable measure in state function reductions reducing their entanglement.
3. Can one deduce also the state of M as a superposition of states in the basic chosen by the observer? This basis need not be the same as the basis defined by - say density matrix if the system has interacted with some system and this ineraction has led to an eigenstate of the density matrix. Assume that one can prepare the latter basis by a physical process such as this kind of interaction.

   The coefficients of the state form a set of N² complex numbers defining a unitary N× N matrix. Unitarity conditions give N conditions telling that the complex rows and unit vectors: these numbers are given by the measurement of all observables. There are also N(N-1) conditions telling that the rows are orthogonal. Together these N+N(N-1)=N² numbers fix the elements of the unitary matrix and therefore the complex coefficients of the state basis of the system can be deduced from a complete set of measurements for all elements of the basis.

Consider now the analog of the MIP* involving more than one observer. For simplicity consider two observers.

1. Assume that the state space H of M decomposes to a tensor product H=H₁⊗ H₂ of state spaces H₁ and H₂ such that O₁ measures observables X₁ in H₁ and O₂ measuresobservables X₂ in H₂. The observables X₁ and X₂ commute since they act in different tensor factors. The absence of interaction between the factors corresponds to the inability of the provers to communicate. As in the previous case, one can deduce the probabilities for the various outcomes of the joint measurements interpreted as measurements of a complete set of observables X₁ ⊗ X₂.
2. One can also think that the two systems form a single system O so that O₁ and O₂ can entangle. This corresponds to a situation in which entanglement between the provers is allowed. Now X₁ and X₂ are not in general independent but also now they must commute. One can deduce the probabilities for various outcomes as eigenstates of observables X₁ X₂ and deduce the diagonal elements of the density matrix as probabilities.

Are these manners to see the situation equivalent? Tsirelson demonstrated that this is the case for finite-dimensional Hilbert spaces, which can indeed be decomposed to a tensor product of factors associated with O₁ and O₂. This means that one finds a unitary transformation transforming the entangled situation to an unentangled one and to tensor product observables.

For the infinite-dimensional case the situation remained open. According to the article, the new result implies that this is not the case. For hyperfinite factors the situation can be approximated with a finite-D Hilbert space so that the situations are equivalent in arbitrary precise approximation.

See the article MIP*= RE: What could this mean physically? or the chapter Evolution of Ideas about Hyper-finite Factors in TGD.

For a summary of earlier postings see Latest progress in TGD.

Articles and other material related to TGD.