# Equivalence of the Frame and Halting Problems
## 3 Discussion
### Undecidability of the QFP  
The FP has been considered above in completely classical terms; the systems \(A\) and \(E\) in Figure 1, for example, are there considered classical systems. What is the status of the FP, however, if we allow quantum computation instead of classical computation? Considered broadly, the FP is the problem of deciding about relevance in an open domain. From a formal perspective, \(x\) and \(y\) are mutually relevant if they are statistically connected, that is, if they have a joint probability distribution. While the limiting case of connection in classical statistics is perfect correlation, the limiting case of connection is quantum theory is (monogamous) entanglement, that is, a joint state \(\ket{xy}\) with an entanglement entropy of unity (and hence von Neumann entropy of zero). Such states are not separable, that is, \(\ket{xy}\
eq\ket{x}\ket{y}\). Suppose then that the environment \(E\) in Figure 1 is a quantum system. In this case, predicting the next state of \(E_{A}\) requires knowing both the classical correlation between \(E_{A}\) and \(E_{U}\) and the entanglement entropy of the joint state \(\ket{E_{A}E_{U}}\). Hence we can formulate the QFP in general form as:  
**QFP:**: Given a quantum agent \(A\) interacting with a quantum environment \(E\), how does an action \(a(t)\) of \(A\) on \(E\) at \(t\) affect the entanglement entropy of \(E\) at \(t+\Delta t?\)  
We can now ask: Is the QFP decidable by a finite quantum agent (i.e., a finite quantum computer) \(A?\) The answer to this question is known, and is negative:  
**Theorem 2**: _The QFP is undecidable by finite quantum agents._  
Proof. : The QFP can only be stated for agents that are separable from the systems with which they interact; in the notation of Figure 1, the joint state \(\ket{AE}\) must be separable as \(\ket{AE}=\ket{A}\ket{E}\) and hence have entanglement entropy of identically zero. In this case, Theorem 1 of Reference [39]applies, showing that (1) the communication channel between \(A\) and \(E\) is classical, and (2) the information communicated is limited to finite, bit-string representations of the eigenvalues of the Hamiltonian operator \(H_{AE}\) that physically implements the \(A\)-\(E\) interaction. This Hamiltonian is, however, independent of the internal self-interactions \(H_{A}\) and \(H_{E}\), and even of the dimensions of the Hilbert spaces \(\mathcal{H}_{A}\) and \(\mathcal{H}_{E}\) provided that they are sufficiently large. Its eigenvalues, in particular, reveal nothing about tensor decompositions of \(\mathcal{H}_{E}\) or their entanglement entropies. As \(A\) is in-principle ignorant of the entanglement entropy of \(E\), changes in that entanglement entropy are clearly unpredictable. Indeed \(A\) cannot determine, solely on the basis of finite observations, that \(E\) is not a classical computer (see Reference [40] for the needed extension of classical probability theory to include \"quantum\" contextuality). The undecidability of the QFP has immediate consequences for the construction of multi-prover interactive proof systems in which the provers are assumed to share quantum resources, for example, entangled states [24]. A two-prover set-up is illustrated in Figure 2, using the canonical labels \(A\) and \(B\) for the provers. This set-up obviously replicates a canonical Bell/EPR experiment [41; 42] with the verifier playing the role of the third observer, [PERSON], who is able to communicate classically with [PERSON] and [PERSON]. Hence it replicates many real experimental set-ups, beginning with that of [PERSON] et al. in 1982 [43]. Any such experiment requires that the \"detectors\" \(A\) and \(B\) be identifiable by the verifier, who must also be capable of establishing that \(A\) and \(B\) share the entangled state \(\psi\). Hence the verifier must solve both the FP (to identify \(A\) and \(B\)) and the QFP (to determine the entanglement entropy of the joint system \(AB\psi\)). Theorems 1 and 2 show that neither can be accomplished by finite observation.