Hayden-Preskill informational mirrors and decryption

Question

I do have a question about an assumption made in the very interesting Hayden-Preskill paper of black holes as informational mirrors. Alice throws her top secret quantum diary which is $k$ qubits long into a black hole hoping to get rid of it. Unfortunately, the top forensic scientist Bob was already maximally entangled with the black hole, and in a sense, "knows" the full microstate of the black hole before Alice dumped her diary into it. If $c$ is the scrambling time, and Bob waits to collect $k+c$ qubits worth of Hawking radiation plus a few more to reduce the margin of error up to the desired level, then in principle, Alice's quantum diary can be read by Bob. This argument is purely quantum informational theoretic. What are the computational resources needed for Bob to decrypt Alice's diary? By assumption, the dynamics of black hole evolution are described by a reversible unitary transformation, and not by Kraus operators.

So, if Bob is willing to wait until the black hole has completely evaporated away and reverse the computations, he can read Alice's diary in polynomial time. However, Bob is too impatient for that, and he wants to read it after only getting $k+c$ plus a few more qubits worth of information. If Bob is willing to wait exponentially long (and he's not), he can create exponentially many identical black holes one by one and go over all possible $k$ qubit combinations to dump into the identical black holes and wait until he finds one which gives Hawking radiation that matches the Hawking radiation he actually got from the original hole. Bob is also unable to reverse the data either because he doesn't know the microstate of the black hole after collecting $k+c$ qubits worth of Hawking radiation. And apparently, neither can Alice if she doesn't already have a copy of her diary.

There is an analogous situation in classical computation. A cryptographic hash function is a polynomially computable function which takes in as arguments a seed which can be publicly known, and some unknown string to be encrypted. It's a one-way function. It's not possible to compute to original string from the encrypted string using polynomial resources. However, if we are given another string and asked to test if it's identical to the original string, we can compute its hash function using the same seed and check if it matches. If it doesn't, they're not identical. If they do, there's a very high chance that they are indeed identical.

Are black holes quantum cryptographic hash functions? What is the best lower bound on the time it would take for Bob to read Alice's diary?

Answer 1

I think a more precise question would be, Is black hole evaporation a quantum one-way function? And I'm not aware of a decisive argument one way or the other. But it's very suggestive that the simplest black holes in string theory, the black holes in AdS3, have an entropy based on representations of the monster group, whose construction features one of Marcel Golay's error-correcting codes. Sending information into a black hole might be like applying an error-correcting code to it and then generating a "remainder", from which the whole original state can in principle be reconstructed, but only in exponential time.

(Thanks to Vikram Dhillon for suggesting that one-way functions might play a role in quantum gravity, it's how I found this question.)

Answer 2

If I may add a little to black hole information paradox as mentioned above, Horowitz and Maldacena wrote a paper a while ago called the final black hole state (here) where they propose the black hole complimentary which states that information that goes into a black hole is copied/cloned and that cloning will cause problems such as providing non-linear corrections to the Shrodinger's equations but Maldacena et. al propose that this copying shouldn't be a problem if it occurs at a place where no one can see it. Excuse the non-technical language being used here. Preskill wrote some comments on that can be found here. This actually relates to another interesting concept called post-selection, the use of cloning allows to some extent for one to employ post-selection to measurements and I talked to Scott Aaronson about this before, here's what he said about this:

The purpose of that footnote was just to give one actual example of someone who had proposed a theory involving postselection. Maybe it wasn't the best example, since when I asked Juan Maldacena about it later, he suggested that he and Horowitz never "really believed" their own proposal! :-) A better example that I could have given is the "multiple times" theory of Yakir Aharonov: that theory explicitly involves postselection, Yakir has been promoting it for decades, and when I pointed out to Yakir the potential for using such a proposal to solve NP-complete and even harder problems in polynomial time, he essentially said "so? what's the problem? Nature does all kinds of hard calculations all the time!"

Now onto one-way functions, let's go with Maldacena's proposal, from that throwing in the diary won't do any good because the information present would be cloned and that means in strict computational sense that once we invert the function (which in this case implies the information coming out as radiation or being cloned) we can still get an output in polynomial time. I suppose that going more into Hawking radiation will give me more answers, however at this time I am not too familiar with it myself.

I do want to say something about the approach though, one of the approaches that IMHO is the easiest to go for one-way functions is Mulmuley's obstructions. I think one can take the following path, first we define physical analogs of the mathematical positivity and mathematical negativity hypothesis, these analogs would include physical problems such as lack of symmetries in AdS and so on. Once those are done we can define a modified version of the flip that they use, our flip would only go from hard nonexistence to easy existence and because we have defined the analogs, that by itself should suffice. Once we can show obstructions exist, then that can be applied to any case.

I speculate, if black-hole evaporation is indeed one-way, and we follow that nonlinear corrections to QM can't happen, then showing that obstructions exist for a specific family of functions called point-functions when they are thrown into a black hole might work. Here's the reason, point-functions can be quantum copy-protected as seen (I can't post the link because SE won't let new users do that, however the name of the paper is: Quantum Copy-Protection and Quantum Money, Scott Aaronson) and we already follow that no cloning can occur, now what happens to the point functions can perhaps be explained by Hawking radiation or the holographic principal, so in that case using the physical analogs we might be able to show that obstructions exist for the information. I'm working on how this approach can be completed.