MIP*=RE and hypercomputation

[Dmytro Taranovsky]

The recent stunning result MIP*=RE has important, if limited, potential 
implications for hypercomputation, which I will detail here.  It does 
not upset our understanding of BQP as a proxy for being feasibly 
physically computable (under current physics). However,
- under certain conditions, it would allow efficient verification of 
arbitrarily powerful recursive computation, which would be useful if we 
had sufficiently powerful but untrustworthy quantum blackboxes.
- it may allow experimental testing of some claims of an infinite number 
of quantum bits.

An important caveat is that the result https://arxiv.org/abs/2001.04383 
, while getting a positive online reception and having multiple 
respectable authors, has not yet been peer reviewed, so I am also 
interested whether any FOM subscribers have independently verified the 
proof (which is long).

The result has been discussed online, including at:
https://www.scottaaronson.com/blog/?p=4512
https://rjlipton.wordpress.com/2020/01/15/halting-is-poly-time-quantum-provable/
https://gilkalai.wordpress.com/2020/01/17/amazing-zhengfeng-ji-anand-natarajan-thomas-vidick-john-wright-and-henry-yuen-proved-that-mip-re-and-thus-disproved-connes-1976-embedding-conjecture-and-provided-a-negative-answer-to-tsirelso/
https://www.nature.com/articles/d41586-020-00120-6


The proof of MIP*=RE (assuming it holds up) implies that for every 
recursively enumerable problem, there is a nonquantum polynomial time 
verifier (allowing randomness) such that
- for each 'yes' instance, there are two independent provers with finite 
initial quantum entanglement that, with probability 1, will convince the 
verifier to answer 'yes' (the proof of MIP*=RE gives perfect completeness)
- for each 'no' instance, there are no such provers that, with 
probability at least 0.5, will convince the verifier the verifier to 
answer 'yes' (0.5 can be improved through repetition).

The verifier sends a message to each prover and then gets a (polynomial 
size) reply from each prover; additional rounds and additional provers 
are not needed for the result.  The provers do not communicate with each 
other during the verification, but because of quantum entanglement, 
there may be correlations between prover replies that would be 
impossible in nonquantum world (for example, see Bell inequalities).

The analogous complexity result without entanglement is MIP = NEXP, and 
with just one prover (which limits the ability to detect prover 
deception) -- IP = PSPACE.

Because of the unlimited power of the provers, the result does not upset 
our understanding of BQP (bounded error quantum polynomial time) as the 
best natural reasonably closed complexity class that approximates the 
notion of being feasibly computable.  Actually, even for BQP, current 
quantum computers have high error rates (far above what we can handle 
with quantum error correction) to the point of being nearly useless 
(though this may change in near future); and in addition, there remain 
residual doubts about quantum coherence of complex large scale systems.  
For most practical purposes, "feasible" (on moderate data sizes) remains 
being in P (or BPP) with reasonable constants.

However, MIP*=RE can help hypercomputation in two ways.

First, it can allow testing of some potential hypercomputers, albeit 
only for their Sigma^0_1 claims.  In classical physics, an observer 
limited to N units of compute cannot distinguish hypercomputers from 
ordinary computers with about 2^N bits of storage, with the bits 
initially chosen to impress the observer.  Quantumly, however, if a 
black box purportedly does, say, A(10,0) computes (A is the Ackermann 
function), then under certain conditions we can test that it is not 
cheating:  Take two blackboxes, touch one with the other (or otherwise 
cause entanglement), put them in separate rooms, and then use MIP*=RE 
for both the problem instance and its negation. The conditions 
essentially are:
* The blackboxes claim to have programmable quantum computation and 
entanglement in an amount commensurate with the required compute.
* The blackboxes are not directly playing tricks on our minds (and 
similar assumptions).
* The blackboxes do not have a secret communication channel (but we can 
arrange that this requires faster than light communication).
* Quantum mechanics is correct.
* The blackboxes can be approximated by finite quantum systems.

In physics, a common heuristic is that unfalsifiable theories tend to be 
false ("not even wrong").  The mere potential to partially test 
purported hypercomputation is (admittedly weak) evidence in its favor.  
However, the above assumptions may well be false, and in any case, if we 
know how the blackboxes work, then using philosophy and Occam's razor, 
we should have indirect ways to convincingly test hypercomputation.


Second, the result has a potential to break the ordinary approximability 
of physical models by finite systems.  Real numbers are extensively used 
in physics, but through various continuity assumptions, and 
(essentially) existence of finite approximations, we avoid 
hypercomputation there.  However, MIP*=RE implies existence of finite 
correlations that are consistent with quantum mechanics, but cannot be 
approximated by finite quantum systems.  There is a function such that 
(caveats: I do not know if 100 is sufficient, and whether 'random' 
works) if you send 100 random bits to one blackbox and another 100 
random bits to another blackbox that is kept separate, and receive 100 
bits from each blackbox, and apply the function, then
(1) if the blackboxes have a finite number of qubits, then with 
probability >99% you get 0; also, the supremum of probabilities to get 1 
is (presumably) undecidable.
(2) there are blackboxes consistent with quantum mechanics such that 
with probability >99%, you get 1.

The safest bet for the near term (and current theories) is that (1) is 
the physically realizable structure.  However, it is conceivable (but 
not expected) that relativistic quantum field theories (QFT) will lead 
to (2).  My guess is that the perturbative expansions can be shown with 
current techniques to be limited to (1), but these expansions may not 
converge, and we do not really understand QFTs nonperturbatively.  
Still, (2) need not lead to hypercomputation or infinite energy if there 
are symmetries between different qubits (and it is also possible that 
symmetry will neutralize infinite energy but not hypercomputation).  And 
symmetry is crucial for QFTs.  For example, the perturbative expansions 
use renormalization, which can arguably be viewed as a cancellation of 
infinities.  We do not know where symmetries will lead us in the future.

Sincerely,
Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm