Understanding of MIP* = RE

On the previous page, we dealt with sorting. This is known as a function problem: The input is a list, and the output is the sorted list. Another common type of problem is an optimization problem: Ask what is the best possible output given some input and evaluation criteria. However, for us the focus are decision problems: reframing such that the output is a binary YES or NO.

We can often transform function and optimization problems into decision problems, although the complexity introduced on the previous page does not have to be kept in that transformation. For example, a sorting problem might be rephrased as "is this list sorted?". Obviously, this solves a slightly different problem, and is also way easier, just compare each pair of elements in turn and check their order.

There is a lot of theory already for all sorts of problems, but decision problems are the most examined. Technically, "class P" on the previous page refers only to the decision problem of "is this list sorted?" and since we can do this in linear time checking if a list is sorted would belong to an even smaller class.

Similarly, the rest of this website deals with other decision problems, to which the answers are either YES or NO, and complexity of these problems explores how long it takes to make this decision, in relation to the input size.

We can also define space complexity, which constrains the memory the algorithm needs to decide a problem instead of time.

Up until now, the machines we were dealing with were solvers. Given an input, they worked through it and showed the process by which to determine the YES/NO answer. Another typical machine used in the theoretical models of decision problems is a verifier. Instead of solving the problem itself, a verifier receives a proof that the problem is solvable, and checks it in some given timeframe.

Take for example a partially filled sudoku grid. Is it solvable? To determine the answer, the computer can try all possible fills for each possible cell, and check if all the conditions are satisfied, but this will take a lot of time. For a 9x9 grid, with each cell having 9 options, the runtime will be $O(9^{9^2})$. However, given a valid fill for the sudoku as proof, a verifier can check that it's valid in linear time. The proof is called a certificate.

Another similar situation is in the sorting example - a machine can take a long time to sort a list, but checking that it's sorted is a strictly linear operation - just check that all neighbouring pairs are in the right order.

The question remains how to generate such certificates. Since it's useful to work with them, the theory of computation has an all-powerful machine that can generate such a certificate instantly, called an oracle. The set-up is such that once the verifier receives the problem, it sends it over to the oracle, who responds with a certificate.

However, if it responded with no certificate for problems without a solution, it wouldn't be a very useful theoretical construct (the verifier wouldn't have to do any work, just trust the oracle). Instead the oracle is malicious, and always sends a certificate. The verifier must work through it to determine whether it's a valid proof.

To solidify the ideas a little, we impose two constraints on our system. If the true answer is YES, the verifier should accept the oracle's proof in a certain percentage of cases (e.g. 95%), and similarly for NO, the verifier should reject in a given percentage of cases (e.g. 95%). Similarly to the previous problem, we can amend this probability by making this a multi-round game, with the verifier asking more questions.

As we move on, we will need to expand the interactive proof idea from our Arthur-Merlin argument. We remain in the verifier seat, but this time question two provers at once. This setup is called a multiprover interactive proof. The provers can setup a common strategy beforehand, but cannot communicate once the protocol starts. The notion is that this allows us to cross-check their answers and be more certain in our analysis.

We will only have 2 provers and a single round of interaction (1 question to each prover and their answer). This class is called $MIP(2,1)$ (it also turns out that any larger number of provers or rounds can be reduced down to 2 provers and 1 round, but that's beyond our current discussion). This system can also be reformulated as a so-called Nonlocal game.

In this game, our two provers are players, and the verifier is a referee. The referee sends each player a question, and based on their answers decides whether they win. The players know the full rules of the game and can setup a strategy, but cannot communicate once the game starts. However, since the referee's questions are probabilistic (drawn from a known distribution), the players generally can't be sure that they always win.

Instead, their goal is to setup the best strategy possible that would win them the highest percentage of games. Their best strategy success rate is called the value of the game.

Finding the value of the game is an optimization problem; to turn it into a decision problem, we instead ask whether the game's value is for example $\geq\frac{2}{3}$. This way, we can use our decision problem complexity classes to categorize a game. Let's see an example on the next page.

We're finally arriving at the crux of our exploration. We now have two provers whose answers need to be coordinated, but who aren't allowed to communicate. One way they can improve their correlation is via quantum entaglement. There's limited space to explain here, so let's layout the basics and feel free to consult the linked resources for further explanations!

Until now, we've worked in the classical world, where bits are either $0$ or $1$. A qubit, on the other hand, can be in a superposition of $\ket{0}$ and $\ket{1}$, with a certain probability of us observing either of the two when we measure it. For example, a qubit could be in the state $\ket{\psi} = \frac{\ket{0}}{\sqrt{2}} + \frac{\ket{1}}{\sqrt{2}}$. When measured, it has a 50% chance of showing a $\ket{0}$. Refer to the linked sources to see how this is calculated from the state description!

If we have two qubits, we can describe their state at once with a so-called tensor product, e.g. $\ket{\psi}_A \otimes \ket{\phi}_B$. For example, if $\ket{\psi} = \frac{\ket{0} + \ket{1}}{\sqrt{2}}$ and $\ket{\phi} = \ket{0}$, then $\ket{\psi} \otimes \ket{\phi} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \otimes \ket{0} = \frac{\ket{00} + \ket{10}}{\sqrt{2}}$.

However, some states cannot be split into a tensor product. Take for example $\ket{\psi} = \frac{\ket{00} + \ket{11}}{\sqrt{2}}$. No matter how hard you try, you won't find a tensor product to generate it. This is called an entangled state. If we calculate the measurement probabilities, we find out that there is a 50% chance of measuring $\ket{00}$ and 50% chance of measuring $\ket{11}$. If we give the two qubits to Alice and Bob while entangled, and Alice measures a $\ket{0}$ state on her qubit, Bob's MUST be also $\ket{0}$, because from the formula the probability of a $\ket{01}$ state is 0%!

Finally, it's possible to measure in different ways than just to figure out zeros and ones. Depending on the axis of measurement, you can determine other directions of the qubit's spin. We measured along the $\ket{0}, \ket{1}$ axis, but you could for example measure along the $\ket{+} = \frac{\ket{0}}{\sqrt{2}} + \frac{\ket{1}}{\sqrt{2}}, \ket{-} = \frac{\ket{0}}{\sqrt{2}} - \frac{\ket{1}}{\sqrt{2}}$ axis. The only important thing in choosing the axis is to ensure that its two states are perpendicular (which you can check using their vector representations, or by reading the linked resources).

The previous exercises established the MIP* class, but it's also important to talk about the RE class. RE stands for recursively enumerable, the class of languages whose 'yes' instances a Turing machine can list one by one. In a less cryptic way, it can also be defined as language to which a Turing machine can verify the 'yes' problems, but might run indefinitely for 'no' problems.

A famous example of a language belonging to RE is the Halting Problem, asking whether a given program will stop running; you can run it, and say 'yes' if it stops, but it might just keep running forever if the true answer is no. Because of an ensuing paradox, it is undecidable whether a program will halt, and a reduction to this problem is often used to show other problems are undecidable. A reduction is a statement of the type "if you could solve this problem, you could also solve the halting problem, and that's impossible."

This is exactly the type of structure Ji et al. used to show that it's also undecidable whether a string belongs to MIP*. Their idea translates the question of whether a program halts into a quantum nonlocal game - if the game has quantum value 1, the machine halts, and if it has value less than 1/2, it doesn't halt.

If there was a way to calculate (or at least approximate) the quantum value of a game, to figure out if a string belongs to MIP*, Ji et al.'s procedure would allow us to use this algorithm and figure out the Halting problem - which is impossible! So there cannot be a solver for MIP*, which must thus be undecidable and equal to RE.