MIP*=RE and hypercomputation
dmytro at mit.edu
Mon Feb 3 22:31:44 EST 2020
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:
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
* 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
* 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.
More information about the FOM