On black holes, holography, the Quantum Extended Church-Turing Thesis, fully homomorphic encryption, and brain uploading
I promise you: this post is going to tell a scientifically coherent story that involves all five topics listed in the title. Not one can be omitted.
My story starts with a Zoom talk that the one and only Lenny Susskind delivered for the Simons Institute for Theory of Computing back in May. There followed a panel discussion involving Lenny, Edward Witten, Geoffrey Penington, Umesh Vazirani, and your humble shtetlmaster.
Lenny’s talk led up to a gedankenexperiment involving an observer, Alice, who bravely jumps into a specially-prepared black hole, in order to see the answer to a certain computational problem in her final seconds before being ripped to shreds near the singularity. Drawing on earlier work by Bouland, Fefferman, and Vazirani, Lenny speculated that the computational problem could be exponentially hard even for a (standard) quantum computer. Despite this, Lenny repeatedly insisted—indeed, he asked me again to stress here—that he was not claiming to violate the Quantum Extended Church-Turing Thesis (QECTT), the statement that all of nature can be efficiently simulated by a standard quantum computer. Instead, he was simply investigating how the QECTT needs to be formulated in order to be a true statement.
I didn’t understand this, to put it mildly. If what Lenny was saying was right—i.e., if the infalling observer could see the answer to a computational problem not in BQP, or Bounded-Error Quantum Polynomial-Time—then why shouldn’t we call that a violation of the QECTT? Just like we call Shor’s quantum factoring algorithm a likely violation of the classical Extended Church-Turing Thesis, the thesis saying that nature can be efficiently simulated by a classical computer? Granted, you don’t have to die in order to run Shor’s algorithm, as you do to run Lenny’s experiment. But why should such implementation details matter from the lofty heights of computational complexity?
Alas, not only did Lenny never answer that in a way that made sense to me, he kept trying to shift the focus from real, physical black holes to “silicon spheres” made of qubits, which would be programmed to simulate the process of Alice jumping into the black hole (in a dual boundary description). Say what? Granting that Lenny’s silicon spheres, being quantum computers under another name, could clearly be simulated in BQP, wouldn’t this still leave the question about the computational powers of observers who jump into actual black holes—i.e., the question that we presumably cared about in the first place?
Confusing me even further, Witten seemed almost dismissive of the idea that Lenny’s gedankenexperiment raised any new issue for the QECTT—that is, any issue that wouldn’t already have been present in a universe without gravity. But as to Witten’s reasons, the most I understood from his remarks was that he was worried about various “engineering” issues with implementing Lenny’s gedankenexperiment, involving gravitational backreaction and the like. Ed Witten, now suddenly the practical guy! I couldn’t even isolate the crux of disagreement between Susskind and Witten, since after all, they agreed (bizarrely, from my perspective) that the QECTT wasn’t violated. Why wasn’t it?
Anyway, shortly afterward I attended the 28th Solvay Conference in Brussels, where one of the central benefits I got—besides seeing friends after a long COVID absence and eating some amazing chocolate mousse—was a dramatically clearer understanding of the issues in Lenny’s gedankenexperiment. I owe this improved understanding to conversations with many people at Solvay, but above all Daniel Gottesman and Daniel Harlow. Lenny himself wasn’t there, other than in spirit, but I ran the Daniels’ picture by him afterwards and he assented to all of its essentials.
The Daniels’ picture is what I want to explain in this post. Needless to say, I take sole responsibility for any errors in my presentation, as I also take sole responsibility for not understanding (or rather: not doing the work to translate into terms that I understood) what Susskind and Witten had said to me before.
The first thing you need to understand about Lenny’s gedankenexperiment is that it takes place entirely in the context of AdS/CFT: the famous holographic duality between two types of physical theories that look wildly different. Here AdS stands for anti-de-Sitter: a quantum theory of gravity describing a D-dimensional universe with a negative cosmological constant (i.e. hyperbolic geometry), one where black holes can form and evaporate and so forth. Meanwhile, CFT stands for conformal field theory: a quantum field theory, with no apparent gravity (and hence no black holes), that lives on the (D-1)-dimensional boundary of the D-dimensional AdS space. The staggering claim of AdS/CFT is that every physical question about the AdS bulk can be translated into an equivalent question about the CFT boundary, and vice versa, with a one-to-one mapping from states to states and observables to observables. So in that sense, they’re actually the same theory, just viewed in two radically different ways. AdS/CFT originally came out of string theory, but then notoriously “swallowed its parent,” to the point where nowadays, if you go to what are still called “string theory” meetings, you’re liable to hear vastly more discussion of AdS/CFT than of actual strings.
Thankfully, the story I want to tell won’t depend on fine details of how AdS/CFT works. Nevertheless, you can’t just ignore the AdS/CFT part as some technicality, in order to get on with the vivid tale of Alice jumping into a black hole, hoping to learn the answer to a beyond-BQP computational problem in her final seconds of existence. The reason you can’t ignore it is that the whole beyond-BQP computational problem we’ll be talking about, involves the translation (or “dictionary”) between the AdS bulk and the CFT boundary. If you like, then, it’s actually the chasm between bulk and boundary that plays the starring role in this story. The more familiar chasm within the bulk, between the interior of a black hole and its exterior (the two separated by an event horizon), plays only a subsidiary role: that of causing the AdS/CFT dictionary to become exponentially complex, as far as anyone can tell.
Pause for a minute. Previously I led you to believe that we’d be talking about an actual observer Alice, jumping into an actual physical black hole, and whether Alice could see the answer to a problem that’s intractable even for quantum computers in her last moments before hitting the singularity, and if so whether we should take that to refute the Quantum Extended Church-Turing Thesis. What I’m saying now is so wildly at variance with that picture, that it had to be repeated to me about 10 times before I understood it. Once I did understand, I then had to repeat it to others about 10 times before they understood. And I don’t care if people ridicule me for that admission—how slow Scott and his friends must be, compared to string theorists!—because my only goal right now is to get you to understand it.
To say it again: Lenny has not proposed a way for Alice to surpass the complexity-theoretic power of quantum computers, even for a brief moment, by crossing the event horizon of a black hole. If that was Alice’s goal when she jumped into the black hole, then alas, she probably sacrificed her life for nothing! As far as anyone knows, Alice’s experiences, even after crossing the event horizon, ought to continue to be described extremely well by general relativity and quantum field theory (at least until she nears the singularity and dies), and therefore ought to be simulatable in BQP. Granted, we don’t actually know this—you can call it an open problem if you like—but it seems like a reasonable guess.
In that case, though, what beyond-BQP problem was Lenny talking about, and what does it have to do with black holes? Building on the Bouland-Fefferman-Vazirani paper, Lenny was interested in a class of problems of the following form: Alice is given as input a pure quantum state |ψ⟩, which encodes a boundary CFT state, which is dual to an AdS bulk universe that contains a black hole. Alice’s goal is, by examining |ψ⟩, to learn something about what’s inside the black hole. For example: does the black hole interior contain “shockwaves,” and if so how many and what kind? Does it contain a wormhole, connecting it to a different black hole in another universe? If so, what’s the volume of that wormhole? (Not the first question I would ask either, but bear with me.)
Now, when I say Alice is “given” the state |ψ⟩, this could mean several things: she could just be physically given a collection of n qubits. Or, she could be given a gigantic table of 2n amplitudes. Or, as a third possibility, she could be given a description of a quantum circuit that prepares |ψ⟩, say from the all-0 initial state |0n⟩. Each of these possibilities leads to a different complexity-theoretic picture, and the differences are extremely interesting to me, so that’s what I mostly focused on in my remarks in the panel discussion after Lenny’s talk. But it won’t matter much for the story I want to tell in this post.
However |ψ⟩ is given to Alice, the prediction of AdS/CFT is that |ψ⟩ encodes everything there is to know about the AdS bulk, including whatever is inside the black hole—but, and this is crucial, the information about what’s inside the black hole will be pseudorandomly scrambled. In other words, it works like this: whatever simple thing you’d like to know about parts of the bulk that aren’t hidden behind event horizons—is there a star over here? some gravitational lensing over there? etc.—it seems that you could not only learn it by measuring |ψ⟩, but learn it in polynomial time, the dictionary between bulk and boundary being computationally efficient in that case. (As with almost everything else in this subject, even that hasn’t been rigorously proven, though my postdoc Jason Pollack and I made some progress this past spring by proving a piece of it.) On the other hand, as soon as you want to know what’s inside an event horizon, the fact that there are no probes that an “observer at infinity” could apply to find out, seems to translate into the requisite measurements on |ψ⟩ being exponentially complex to apply. (Technically, you’d have to measure an ensemble of poly(n) identical copies of |ψ⟩, but I’ll ignore that in what follows.)
In more detail, the relevant part of |ψ⟩ turns into a pseudorandom, scrambled mess: a mess that it’s plausible that no polynomial-size quantum circuit could even distinguish from the maximally mixed state. So, while in principle the information is all there in |ψ⟩, getting it out seems as hard as various well-known problems in symmetric-key cryptography, if not literally NP-hard. This is way beyond what we expect even a quantum computer to be able to do efficiently: indeed, after 30 years of quantum algorithms research, the best quantum speedup we know for this sort of task is typically just the quadratic speedup from Grover’s algorithm.
So now you understand why there was some hope that Alice, by jumping into a black hole, could solve a problem that’s exponentially hard for quantum computers! Namely because, once she’s inside the black hole, she can just see the shockwaves, or the volume of the wormhole, or whatever, and no longer faces the exponentially hard task of decoding that information from |ψ⟩. It’s as if the black hole has solved the problem for her, by physically instantiating the otherwise exponentially complex transformation between the bulk and boundary descriptions of |ψ⟩.
Having now gotten your hopes up, the next step in the story is to destroy them.
Here’s the fundamental problem: |ψ⟩ does not represent the CFT dual of a bulk universe that contains the black hole with the shockwaves or whatever, and that also contains Alice herself, floating outside the black hole, and being given |ψ⟩ as an input. Indeed, it’s unclear what the latter state would even mean: how do we get around the circularity in its definition? How do we avoid an infinite regress, where |ψ⟩ would have to encode a copy of |ψ⟩ which would have to encode a copy of … and so on forever? Furthermore, who created this |ψ⟩ to give to Alice? We don’t normally imagine that an “input state” contains a complete description of the body and brain of the person whose job it is to learn the output.
By contrast, a scenario that we can define without circularity is this: Alice is given (via physical qubits, a giant table of amplitudes, an obfuscated quantum circuit, or whatever) a pure quantum state |ψ⟩, which represents the CFT dual of a hypothetical universe containing a black hole. Alice wants to learn what shockwaves or wormholes are inside the black hole, a problem plausibly conjectured not to have any ordinary polynomial-size quantum circuit that takes copies of |ψ⟩ as input. To “solve” the problem, Alice sets into motion the following sequence of events:
- Alice scans and uploads her own brain into a quantum computer, presumably destroying the original meat brain in the process! The QC represents Alice, who now exists only virtually, via a state |φ⟩.
- The QC performs entangling operations on |φ⟩ and |ψ⟩, which correspond to inserting Alice into the bulk of the universe described by |ψ⟩, and then having her fall into the black hole.
- Now in simulated form, “Alice” (or so we assume, depending on our philosophical position) has the subjective experience of falling into the black hole and observing what’s inside. Success! Given |ψ⟩ as input, we’ve now caused “Alice” (for some definition of “Alice”) to have observed the answer to the beyond-BQP computational problem.
In the panel discussion, I now model Susskind as having proposed scenario 1-3, Witten as going along with 1-2 but rejecting 3 or not wanting to discuss it, and me as having made valid points about the computational complexity of simulating Alice’s experience in 1-3, yet while being radically mistaken about what the scenario was (I still thought an actual black hole was involved).
An obvious question is whether, having learned the answer, “Alice” can now get the answer back out to the “real, original” world. Alas, the expectation is that this would require exponential time. Why? Because otherwise, this whole process would’ve constituted a subexponential-time algorithm for distinguishing random from pseudorandom states using an “ordinary” quantum computer! Which is conjectured not to exist.
And what about Alice herself? In polynomial time, could she return from “the Matrix,” back to a real-world biological body? Sure she could, in principle—if, for example, the entire quantum computation were run in reverse. But notice that reversing the computation would also make Alice forget the answer to the problem! Which is not at all a coincidence: if the problem is outside BQP, then in general, Alice can know the answer only while she’s “inside the Matrix.”
Now that hopefully everything is crystal-clear and we’re all on the same page, what can we say about this scenario? In particular: should it cause us to reject or modify the QECTT itself?
Daniel Gottesman, I thought, offered a brilliant reductio ad absurdum of the view that the simulated black hole scenario should count as a refutation of the QECTT. Well, he didn’t call it a “reductio,” but I will.
For the reductio, let’s forget not only about quantum gravity but even about quantum mechanics itself, and go all the way back to classical computer science. A fully homomorphic encryption scheme, the first example of which was discovered by Craig Gentry 15 years ago, lets you do arbitrary computations on encrypted data without ever needing to decrypt it. It has both an encryption key, for encrypting the original plaintext data, and a separate decryption key, for decrypting the final answer.
Now suppose Alice has some homomorphically encrypted top-secret emails, which she’d like to read. She has the encryption key (which is public), but not the decryption key.
If the homomorphic encryption scheme is secure against quantum computers—as the schemes discovered by Gentry and later researchers currently appear to be—and if the QECTT is true, then Alice’s goal is obviously infeasible: decrypting the data will take her exponential time.
Now, however, a classical version of Lenny comes along, and explains to Alice that she simply needs to do the following:
- Upload her own brain state into a classical computer, destroying the “meat” version in the process (who needed it?).
- Using the known encryption key, homomorphically encrypt a computer program that simulates (and thereby, we presume, enacts) Alice’s consciousness.
- Using the homomorphically encrypted Alice-brain, together with the homomorphically encrypted input data, do the homomorphic computations that simulate the process of Alice’s brain reading the top-secret emails.
The claim would now be that, inside the homomorphic encryption, the simulated Alice has the subjective experience of reading the emails in the clear. Aha, therefore she “broke” the homomorphic encryption scheme! Therefore, assuming that the scheme was secure even against quantum computers, the QECTT must be false!
According to Gottesman, this is almost perfectly analogous to Lenny’s black hole scenario. In particular, they share the property that “encryption is easy but decryption is hard.” Once she’s uploaded her brain, Alice can efficiently enter the homomorphically encrypted world to see the solution to a hard problem, just like she can efficiently enter the black hole world to do the same. In both cases, however, getting back to her normal world with the answer would then take Alice exponential time. Note that in the latter case, the difficulty is not so much about “escaping from a black hole,” as it is about inverting the AdS/CFT dictionary.
Going further, we can regard the AdS/CFT dictionary for regions behind event horizons as, itself, an example of a fully homomorphic encryption scheme—in this case, of course, one where the ciphertexts are quantum states. This strikes me as potentially an important insight about AdS/CFT itself, even if that wasn’t Gottesman’s intention. It complements many other recent connections between AdS/CFT and theoretical computer science, including the view of AdS/CFT as a quantum error-correcting code, and the connection between AdS/CFT and the Max-Flow/Min-Cut Theorem (see also my talk about my work with Jason Pollack).
So where’s the reductio? Well, when it’s put so starkly, I suspect that not many would regard Gottesman’s classical homomorphic encryption scenario as a “real” challenge to the QECTT. Or rather, people might say: yes, this raises fascinating questions for the philosophy of mind, but at any rate, we’re no longer talking about physics. Unlike with (say) quantum computing, no new physical phenomenon is being brought to light that lets an otherwise intractable computational problem be solved. Instead, it’s all about the user herself, about Alice, and which physical systems get to count as instantiating her.
It’s like, imagine Alice at the computer store, weighing which laptop to buy. Besides weight, battery life, and price, she definitely does care about processing power. She might even consider a quantum computer, if one is available. Maybe even a computer with a black hole, wormhole, or closed timelike curve inside: as long as it gives the answers she wants, what does she care about the innards? But a computer whose normal functioning would (pessimistically) kill her or (optimistically) radically change her own nature, trapping her in a simulated universe that she can escape only by forgetting the computer’s output? Yeah, I don’t envy the computer salesman.
Anyway, if we’re going to say this about the homomorphic encryption scenario, then shouldn’t we say the same about the simulated black hole scenario? Again, from an “external” perspective, all that’s happening is a giant BQP computation. Anything beyond BQP that we consider to be happening, depends on adopting the standpoint of an observer who “jumps into the homomorphic encryption on the CFT boundary”—at which point, it would seem, we’re no longer talking about physics but about philosophy of mind.
So, that was the story! I promised you that it would integrally involve black holes, holography, the Quantum Extended Church-Turing Thesis, fully homomorphic encryption, and brain uploading, and I hope to have delivered on my promise.
Of course, while this blog post has forever cleared up all philosophical confusions about AdS/CFT and the Quantum Extended Church-Turing Thesis, many questions of a more technical nature remain. For example: what about the original scenario? can we argue that the experiences of bulk observers can be simulated in BQP, even when those observers jump into black holes? Also, what can we say about the complexity class of problems to which the simulated Alice can learn the answers? Could she even solve NP-complete problems in polynomial time this way, or at least invert one-way functions? More broadly, what’s the power of “BQP with an oracle for applying the AdS/CFT dictionary”—once or multiple times, in one direction or both directions?
Lenny himself described his gedankenexperiment as exploring the power of a new complexity class that he called “JI/poly,” where the JI stands for “Jumping In” (to a black hole, that is). The nomenclature is transparently ridiculous—“/poly” means “with polynomial-size advice,” which we’re not talking about here—and I’ve argued in this post that the “JI” is rather misleading as well. If Alice is “jumping” anywhere, it’s not into a black hole per se, but into a quantum computer that simulates a CFT that’s dual to a bulk universe containing a black hole.
In a broader sense, though, to contemplate these questions at all is clearly to “jump in” to … something. It’s old hat by now that one can start in physics and end up in philosophy: what else is the quantum measurement problem, or the Boltzmann brain problem, or anthropic cosmological puzzles like whether (all else equal) we’re a hundred times as likely to find ourselves in a universe with a hundred times as many observers? More recently, it’s also become commonplace that one can start in physics and end in computational complexity theory: quantum computing itself is the example par excellence, but over the past decade, the Harlow-Hayden argument about decoding Hawking radiation and the complexity = action proposal have made clear that it can happen even in quantum gravity.
Lenny’s new gedankenexperiment, however, is the first case I’ve seen where you start out in physics, and end up embroiled in some of the hardest questions of philosophy of mind and computational complexity theory simultaneously.
Follow
Comment #1 July 27th, 2022 at 6:44 pm
Daniel Gottesman’s hypothetical with the uploaded Alice into the homomorphic encryption system really sounds like something out a Greg Egan novel. (I don’t have anything more substantial to point out here unfortunately.)
Comment #2 July 27th, 2022 at 7:05 pm
Incidentally, to everyone who complained about too many “culture war / people being mean to me on the Internet” posts, and told me to get back to science posts: had this been the former, there would’ve been 20x as many comments by now. 😀
Comment #3 July 27th, 2022 at 7:10 pm
Joshua Zelinsky #1: Agreed!
BTW, just a couple years after fully homomorphic encryption was discovered, my then-student Andy Drucker proposed a different philosophy-of-mind thought experiment involving it. In Andy’s gedankenexperiment, a computer program that emulates a full human brain is run in homomorphically encrypted form, and the only decryption key is in another galaxy. The question is, does any consciousness arise in this galaxy—to all of whose residents, the program’s state at each moment is indistinguishable in polynomial time from a uniformly random sequence of bits?
Comment #4 July 27th, 2022 at 7:25 pm
I frankly don’t really grasp the whole experiment, especially the superstructure, only some subparts. I don’t really believe it’s even important for the experiment whether Alice is still sentient after uploading her (I certainly would reject that) since a p-Zombie copy of her would deliver the same results.
I especially lost it on the claim that the extended church turing thesis would not be violated and on homomorphic encryption and why it has to be homomorphic (do we just want a hard to crack problem here and use a homomorphic encryption as an instance of such a problem?) and not usual rijndael for example since I don’t really have a clue about cryptography aside from the basics :- ).
I have so many questions yet it’s too late today. Nice post though.
The remaining open question would probably make nice research topics on their own.
Comment #5 July 27th, 2022 at 7:26 pm
Fascinating stuff! This is what we come here for🙏🙏
Comment #6 July 27th, 2022 at 7:38 pm
Also, I just discussed Gottesman’s hypothetical and Andy’s to my spouse. I then commented that these had come from a problem involving a “putting Alice into a simulated… ” and spouse finished “black hole.” Spouse then said that this wasn’t out of anything deep but essentially pattern to “how these things generally seem to go.” I’m not sure what to make of that.
Comment #7 July 27th, 2022 at 8:04 pm
1Zer0 #4:
I don’t really believe it’s even important for the experiment whether Alice is still sentient after uploading her (I certainly would reject that) since a p-Zombie copy of her would deliver the same results.
Alas, it is important, because the entire point is that Alice can’t get out of the simulation to “deliver” the results! Or she can, but it takes exponential time, which is no better than breaking the encryption scheme by brute force. In polynomial time, Alice can only get into the simulation and “experience” the results while there. She can’t bring them back with her.
I especially lost it on the claim that the extended church turing thesis would not be violated and on homomorphic encryption and why it has to be homomorphic
It has to be homomorphic because, in order to get the simulated-Alice to “experience” reading the encrypted emails, you have to be able to first encrypt the simulated-Alice and then do arbitrary computations on encrypted data! With a normal encrpytion system, the encrypted Alice program and the encrypted emails would just sit there and not interact with each other.
Comment #8 July 27th, 2022 at 8:08 pm
These examples presumably do not violate the QECT thesis because there is no way for Alice to communicate the result to the outside world without doing an exponential length computation. But what if we take all of the conscious agents in the universe (or at least on Earth, or at least those interested in knowing the answer) and encrypt them according to the AdS/CFT dictionary or the holomorphic encryption as well. Then they can talk to encoded Alice and find out the answer.
For that matter, assuming the ordinary macroscopic world we experience is BQP simulable, we could just encrypt everything in the AdS/CFT or holomorphic “matrix”.
Does this change the picture in any way?
Comment #9 July 27th, 2022 at 8:20 pm
Matt Leifer #8: Now there’s a question in the spirit of the exercise! Perhaps it ultimately depends on whether we believe that consciousness exists or doesn’t exist inside the homomorphic encryption.
Comment #10 July 27th, 2022 at 8:40 pm
Scott, my question is about the role of CFT in step 2:
> The QC performs entangling operations on |φ⟩ and |ψ⟩, which correspond to inserting Alice into the bulk of the universe described by |ψ⟩, and then having her fall into the black hole.
Without CFT in the picture Alice is an “embedded observer”, that is, her state |φ⟩ at some point t (leaving aside relativity) is a subspace of the state of the AdS (bulk) universe |ψ⟩ at time t. Now, |ψ⟩ can be evolved deterministically using (a generalized) Schrodinger equation, and that includes evolving |φ⟩. So, there are two choices, either evolution of |ψ⟩ includes Alice jumping into a black hole, let’s call |ψ-jump⟩, or it does not, let’s call it |ψ-stay⟩. Since Alice is embedded, she can either be |φ-jump⟩ if she lives in the universe |ψ-jump⟩, or |φ-stay⟩ if she lives in the universe |ψ-stay⟩. In the former case she dies “inside the simulation”, while in the latter case she learns nothing about the black hole innards. To learn something new she would have to evolve |ψ-jump⟩ **while starting from the state |φ-stay⟩**, which seems to be a contradiction.
Somewhere in this process it seems to matter that the Alice that lives in the bulk, and is uploaded into a QC in the bulk, but is given something… from the CFT? Thus avoiding a version of grandfather paradox in some way?
Comment #11 July 27th, 2022 at 8:52 pm
Shmi #10: I might not have fully understood your question, but if it helps:
Yes, if simulated-Alice wants to learn the answer to the computational problem, then she’ll have to die in the simulation, as she falls into the simulated black hole’s singularity (assuming the simulation continues to be run forward in the normal way). This isn’t as macabre as it sounds, since of course it’s “just a simulation,” and Alice could always be brought back to life by running it backwards. On the other hand, even within the simulation, if you wanted Alice to be able to bring the answer safely out of the black hole, as far as I know that would require exponential time.
Comment #12 July 27th, 2022 at 8:59 pm
Scott #2: Given some of comments you’ve had to deal with recently, maybe a post with fewer of them isn’t such a bad thing?
More seriously, this is my favorite type of post on this blog. I had never heard or AdS/CFT or homomorphic encryption before, but your explanations here were so well done that I came out of this post thinking “Wow, I can’t believe I followed all that!” And I learned something pretty cool!
Comment #13 July 27th, 2022 at 9:19 pm
Scott #11:
I may not have articulated it well, my question is how adding holography to the mix, as opposed to just using our Lambda-CDM universe, changes things, and in particular how replacing the quantum state in the bulk with a dual quantum state on the boundary helps matters, assuming that is what is going on. I feel like I am missing something fundamental there. I understand that in our universe Alice has to die in the simulation and also in reality, since this is what the simulation is of. Maybe the latter is not required in AdS/CFT??
Comment #14 July 27th, 2022 at 9:33 pm
Shmi #13: In a Lambda-CDM universe like ours, physicists don’t currently know how to construct a boundary description that’s holographically dual to the bulk description (they’re working on it). So, unless the boundary description exists, there’s no beyond-BQP problem of translating between it and the bulk description, so this entire thought experiment never gets off the ground.
Comment #15 July 27th, 2022 at 11:33 pm
Scott #7
I also cannot understand why it matters if Alice is sentient. Forget p-zombies just send in the mars rover to collect data. It can’t get back out with the information for the same reason that Alice can’t. The lack of a sentient observer makes it less poignant but does not affect the complexity problem.
How it affects my theory of mind… I don’t have a theory of mind that I can defend.
Comment #16 July 27th, 2022 at 11:35 pm
Any concerns that we don’t live in an ADS universe?
Comment #17 July 28th, 2022 at 1:00 am
My first attempt to use the reformed comment system!
I heard about “JI/poly” maybe a month ago. I understood it to refer to a situation in which two observers enter opposite ends of a *wormhole*, and meet in the middle. In the simplest version of such a scenario, the wormhole is not traversable – the observers can interact with each other, but they can never get out again, since the wormhole collapses around them.
In terms of AdS/CFT, such a wormhole is described by entanglement of two CFT dual states. That is, a wormhole is akin to two entangled black holes. This is a version of ER=EPR. (Traversable wormholes are also possible, if the entangled black holes are extremal rotating black holes. There are connections with the theory of quantum teleportation and superdense coding here.)
It seems, therefore, that Alice will be associated with one of the CFT states, and the data that she wishes to process, or observe, or whatever, will be associated with the other CFT state (perhaps in the form of a “Bob”).
When I thought about this last month, entanglement between Alice and Bob reminded me of the entangled interactive provers in MIP* – and meanwhile, the von Neumann algebras of observables that one uses in the vicinity of a black hole, are arguably the ones involved in Connes’s conjecture that was falsified by MIP* = RE. I blogged about it here:
http://quantizinggravity.blogspot.com/2022/06/jipoly-mip-re.html
I find it hard to believe that *this* is what Susskind is on about – as keen as he is to embrace quantum complexity, MIP* = RE seems much more abstract than anything he writes or talks about. Nonetheless, I’d like to know – could you implement MIP* computations in this context, thanks to the entanglement between the CFT states? It seems a worthy question.
Comment #18 July 28th, 2022 at 2:00 am
Using infra-Bayesian physicalism (https://www.alignmentforum.org/posts/gHgs2e2J5azvGFatb/infra-bayesian-physicalism-a-formal-theory-of-naturalized#comments) it should be possible to show rigorously that Alice has no experiences inside homomorphic encryption (if she doesn’t know the decryption key). Here’s an informal sketch of how it works:
* Alice has experiences of X iff the universe is running the program “Alice” with input X
* The universe is running a program P iff the physical history of the universe would be different in the counterfactuals in which P is producing different outputs
* Counterfactuals are defined using Alice’s model M of the universe, which is a representation of the joint knowledge she has about “physics” and (computable) “mathematics”. Inside M, some programs are “entangled” with physical histories (e.g. if Alice’s knows Maxwell’s equations then the program that simulates those equations is entangled with the physical electromagnetic field)
* In the case of homomorphic encryption, Alice cannot predict the relationship between different possible program-Alice-outputs (Alice behaviors) and the states of the computer simulating Alice in encrypted form. According to M, the latter is more or less random.
* Therefore, Alice should not expect to experience anything while inside encryption (unless maybe if she knows the decryption key or has so much computational resources inside her own mind that she can brute force the encryption)
Comment #19 July 28th, 2022 at 2:11 am
[addendum to my previous comment]
I suspect that agents inside black-holes (simulated or real) also have no experiences. A precise analysis would require formalizing AdS/CFT inside IBP, which ofc I’m not ready to do. However, my guess is that the “physical history” should be defined using asymptotic boundary observables, and since it’s computationally intractable to infer the black hole interior from those observables, the programs that would be running inside the black hole should be considered, from the IBP standpoint, “not running”.
Comment #20 July 28th, 2022 at 4:31 am
As Alice falls into the black hole, she shoots back beacons containing her current state. c
Clearly™ those states only vary a polynomial amount from one to the next.
Alice only emits a polynomial number of beacons before she crosses the event horizon.
The local physics _at_ the horizon don’t significantly© change from Alice’s perspective.
Yet something “exponential” must have happened. Therefore, Firewall®?
Comment #21 July 28th, 2022 at 4:57 am
So Alice can’t bring back the answer after running the simulation backwards, but even if such an experiment could be run can we know if she actually saw the answer and not anything else?
And if the answer can’t be brought back is there any way the experiment could be run that Alice would just come back in less than exponential time with one bit of information: whether she saw the answer (volume of the wormhole or whatever) or not?
Thank you
Comment #22 July 28th, 2022 at 4:58 am
Some quick dumb thoughts (I’m on phone and have no idea about this):
– Connection with computer security. An exploit is a piece of input that subverts the correct execution of a program to achieve some attacker’s goal. In practice this usually means an attacker performing arbitrary computation in the context of the victim program. So Alice seems to be analogous to a “trojan” injected by the attacker (ignoring consciousness). I wonder what exploiting looks like with homomorphic encryption.
– Semantic leakage. Is the external observer only able to see the initial and final states? Or can we see every scrambled state the computation goes through? If so, could Alice (or the trojan that has gain control over the encrypted world) abuse that to leak information? Eg. by encoding the solution by freezing the computation (or the whole universe fwiw) after N steps.
Comment #23 July 28th, 2022 at 6:03 am
Joshua Zelinsky #1: dropping into a black hole (in uploaded form) to test if, among other things, it could be used to perform unlimited computations is literally the plot of his Plank Dive short story https://www.gregegan.net/PLANCK/Complete/Planck.html
It has a very touching ending.
Comment #24 July 28th, 2022 at 6:37 am
ppnl #15: If you sent in a simulated Mars rover, why would there even be any temptation to say that the QECTT was violated? You could then say: obviously, all that matters is what we (the external observers) see when we measure, and all of that can be simulated in BQP.
Comment #25 July 28th, 2022 at 7:14 am
JPC #16:
Any concerns that we don’t live in an ADS universe?
The specific scenario I talked about doesn’t depend in any way on living in a real AdS universe, since as I said, Alice only has to jump into a simulated AdS black hole!
Personally, I think the fact that an AdS/CFT dictionary not only exists, but can be interpreted as fully homomorphic encryption, is absolutely fascinating. It’s clearly teaching us something about quantum gravity.
Anyway, when I saw Lenny a month ago, he said that holography for de Sitter space is the biggest problem right now and the main thing he’s working on. Apparently it was a central theme at the recent Strings conference too (I didn’t attend, but my postdoc Jason Pollack did).
Comment #26 July 28th, 2022 at 7:22 am
Scott #0, isn’t that the best argument ever formulated that sometime we can’t emulate what would happen in our consciousness, even if we knew our own code and the environment?
Should we then get suspicious of any reasoning that involves consciousness + « you can always assume a program has access to its own code »? (something you said to me a long time ago, but I still don’t feel I fully grasp the concept so you’ll make my day if I could drop it 😂)
Comment #27 July 28th, 2022 at 7:47 am
The situation seems to me to be loosely similar to the situation with plain old quantum computing. In both cases, these is some abstract sense in which a tremendously powerful calculation is being performed – but as a practical matter, a mere human can’t actually access the final answer. There is some sense in which a standard quantum computer “performs” hugely difficult calculations and encodes the answer in its quantum state. (For example, I believe that if you could hypothetically somehow run a single-time-step measurement primitive “return the value of the largest amplitude”, then quantum computers would be enormously powerful (I think they could efficiently solve PSPACE-complete problems?). But of course, you can’t, because of the Born rule. If you run a quantum algorithm that produces a quantum state in which the right answer to some math problem has the largest amplitude, but only by an exponentially small amount, then you’re still out of luck, because extracting that right answer would require exponentially many runs of the algorithm.)
It’s certainly not a perfect analogy, of course. It’s pretty clear that in the standard quantum computation story, merely producing an unobserved quantum state that “contains” the right answer really doesn’t count as “solving” the problem. Whereas in this AdS/CFT story, the question of what “counts” as solving the problem is much trickier and raises more interesting philosophical questions.
Comment #28 July 28th, 2022 at 8:27 am
Ted #27: Yeah, that’s the difference between the two cases. Quantum computing, counterintuitive though it is, doesn’t involve any funny business with consciousness or the nature of the observer. The “output” is just whatever you see when you make a measurement at the end, and the great discovery is that, limited though that is, that’s enough to solve problems that are believed to be classically hard (like factoring). No one thinks unobserved parts of the quantum state count as “output.”
The reigning conjecture for decades—the Quantum Extended Church-Turing Thesis—has been that given the appropriate data, the observable results of every physics experiment can be calculated on a quantum computer, with at most polynomial slowdown compared to running the experiment itself. The new idea is that you can falsify this conjecture, albeit only for a weird definition of “observable results,” wherein only your uploaded, simulated, homomorphically encrypted doppelgänger gets to observe the answer!
Comment #29 July 28th, 2022 at 8:33 am
Hi Scott,
I don’t have much to add except to say that this was really well-written and thought-provoking. I really wouldn’t feel too bad about the number of comments being less than on a culture-war post. Probably more people just feel like they have something to add on those topics, than on these more technical posts.
I wonder what the statistics would be if your posts had a ‘Like’ button.
Comment #30 July 28th, 2022 at 9:12 am
Can the back-reaction from the simulated-Alice’s (simulated) physical processes contained in \( | \varphi \rangle \) be shown to have have a minimal impact on the original problem encoded in \(| \psi \rangle\)? I guess we can debate at what degree of fidelity we’d need to simulate Alice in \( |\varphi\rangle \), but at the very least the simulation would presumably need eyes (or some other sense organ) that physically absorb photons, and a brain that (presumably) emits EM waves as it processes that sense data, and (most importantly) both of those organs would gravitate. So as Alice falls into the black hole, her own gravitational influence would slightly change the original physical situation encoded within \( |\psi\rangle \).
I have no idea about the dynamics of shockwaves and wormholes inside of black holes, but if they have a chaotic dependence on the history of the infalling matter, and/or they interact with each other in chaotic ways within the black hole, then the mere fact of (simulated) Alice’s physically being there (in the simulation) to observe the dynamics would mean that she’s answering a slightly different question than the original one encoded in \( |\psi\rangle\ ). Is there an argument that shows that her back-reaction can be made negligible?
(For some reason, the LaTeX doesn’t seem to be rendering; am I doing something wrong?)
Comment #31 July 28th, 2022 at 9:20 am
Scott #3:
1. Is this different from “does Conway’s Life exist when simulated in Conway’s Life”? This seems to hinge on “exists”. It seems clear that “exists” is a relative ability to measure. Life-in-Life-in-software-on-silicon exists relative to us, because we can measure Life-like properties. Encrypted consciousness exists relative to its inhabitants, but not to us if we can never decrypt it and measure consciousness-like properties?
2. Are there signs one could look for that one indicate if one exists in an encrypted simulation?
3. I know little about FHE or its limits, current or theoretical. If one can encrypt an aware subversive actor, is there no way for the actor to “signal” past the encryption through some sideband? (Timed patterns of computations, or the like.) This would seem to have a significant impact on the above case.
Comment #32 July 28th, 2022 at 9:31 am
Dear Scott,
just wanting to ask you, next time you meet prof. Susskind, to thank him on the behalf of one of your commenters.
His “continuing education courses” are the main reason i could learn my physics at a late age. Whenever i got stuck with something, there came Leo making everything so goddam simple.
Btw you share the same clarity and focus. I could follow through the post without even resorting to wikipedia.
on the topic at hand, i have nothing really to add, except that i see a lot of hand-waving on all the computation need at every step. I reckon Prof Susskind is known as the master hand-waver in physics history, but still 😉
Comment #33 July 28th, 2022 at 10:08 am
dubious #31:
1. One of the hardest parts of explaining anything new is people rounding it down to something simpler that they already know. Yes, people have debated for generations whether simulated minds could be conscious … but there wasn’t usually the worry that if so, the Extended Church-Turing Thesis would be violated!
2. I mean, you could do debugging to make sure the quantum computer was simulating the CFT correctly. You could presumably even interact with the simulated Alice inside the CFT, before she jumped into the simulated black hole. (“How are you feeling, Alice? Ready for the big mission?”) Once she’s in, though, as I said, it would take an exponential-time computation to extract whatever she learned! (And as for whether the simulated Alice is conscious: all the usual philosophical difficulties with that, nothing new there.)
3. If it’s possible to do as you say, then the FHE scheme is just insecure, full stop!
Comment #34 July 28th, 2022 at 10:09 am
Matt Liefer #8: I don’t think it sensible to say that the QECT thesis is violated in that case either: The computationally hard problem is decrypting information about the encrypted message, not learning information about the encrypted message. Normally these are the same thing, but in this case they are not.
It is actually reasonably common in cryptography to discover that your definition of security does not mean quite what you thought. Sometimes this can lead to a security hole, but in this case, I would say probably not one of practical importance.
Comment #35 July 28th, 2022 at 10:54 am
manorba #32: I think there’s one big secret to clarity: tell the truth. Even if the truth reveals how you yourself struggled to understand something babyishly simple. Even if the truth makes people look at you strange, because it’s not the kind of thing people say in this context. Just tell the truth. This approach has sometimes gotten me into trouble, but it’s also the source of whatever success I’ve had explaining math, CS, and physics.
“Master hand-waver in physics history” is an apt description of Lenny. I’ll let him know (or he might be reading these comments). 🙂
Comment #36 July 28th, 2022 at 11:14 am
Regarding the complexity class of problems that simulated Alice can answer: it seems like computation inside the homomorphically encrypted computer program should not be able to break homomorphic encryption.
Because if (inside the simulation) you could learn the decryption, then wouldn’t it be possible to manipulate bits inside the simulation such that you could communicate with the outside world?
This is idle speculation, I don’t know how FHE works so I’m probably missing something. I think this would require that the decryption task is small enough to fit inside the computation itself.
Comment #37 July 28th, 2022 at 11:18 am
> Here’s the fundamental problem: |ψ⟩ does not represent the CFT dual of a bulk universe that contains the black hole with the shockwaves or whatever, and that also contains Alice herself, floating outside the black hole, and being given |ψ⟩ as an input. Indeed, it’s unclear what the latter state would even mean: how do we get around the circularity in its definition? How do we avoid an infinite regress, where |ψ⟩ would have to encode a copy of |ψ⟩ which would have to encode a copy of … and so on forever? Furthermore, who created this |ψ⟩ to give to Alice? We don’t normally imagine that an “input state” contains a complete description of the body and brain of the person whose job it is to learn the output.
I’m a little confused. Isn’t this basically what a quine is? A program that knows it’s own source code? Or is that not applicable here?
Comment #38 July 28th, 2022 at 11:22 am
If I understand, you’re saying a big problem is the expectation that it would require exponential “time” for Alice’s answer to be retrieved. I’m curious if time is calculated as ‘c-number’ from the Page–Wootters construction? I don’t understand it, and can’t judge how much progress has been made in replacing it with a fully quantum theory of time (https://royalsocietypublishing.org/doi/10.1098/rspa.2021.0970)
but I wondered how this sort of thing impacts the problem you raise?
Comment #39 July 28th, 2022 at 11:24 am
To Scott #35
Coming from a family tradition of teachers, having a better half that’s a high school history and italian teacher, and having been a teacher myself (from Computer 101 up to OS and networking but always user level) i really second that.
Having a deep understanding of the matter and a good and empathic method of teaching are both required. one of the two isn’t enough.
Comment #40 July 28th, 2022 at 11:45 am
Do any homomorphic encryption schemes have the property that encrypting under one key, and then another key, is always equivalent to encrypting under a third key? Maybe you could tell a scifi story about an encrypted mind constantly re-encrypting itself with random keys, jumping from one encrypted existence to another, trying to get back to the identity key, like some ridiculously computational version of sliders or quantum leap.
Comment #41 July 28th, 2022 at 11:47 am
Sam Harsimony #36: With FHE, by design, the ciphertext looks indistinguishable from uniformly random bits, regardless of what’s going on inside. So “someone on the inside” can’t get a signal out—if they could, it would break the FHE!
Comment #42 July 28th, 2022 at 12:05 pm
Christopher #37: Whether one could get around the circularity problem using quining is an interesting question; thanks!
A first difficulty is that quining is a thing you do in the Turing machine model, or Turing-complete languages more generally. The problems I was talking about, by contrast, all implicitly assumed the model of (quantum) circuits, which take inputs of a fixed size and run for a fixed time, and have no straightforward analogue of quining.
But OK, suppose we fixed that by talking instead about quantum Turing machines. Even then, the deeper problem is that |ψ⟩ is supposed to be the state that Alice receives as input—i.e., the encoding of the problem she needs to solve! So how could the input already contain a complete description of Alice’s brain? As in Newcomb’s Paradox, wouldn’t that make it impossible to talk about, e.g., which algorithm Alice should use—since whenever you change the algorithm, the input itself has to change to reflect that?
Comment #43 July 28th, 2022 at 12:10 pm
While I understand the hesitations with the name of the complexity class being “JI”, I would say, the J section of the complexity zoo is pretty empty.
But no /poly. Please.
Comment #44 July 28th, 2022 at 12:26 pm
Craig Gidney #40: You can always compose multiple layers of encryption—you could even do, e.g., one FHE scheme inside of a completely different FHE scheme. While such a composition could itself be considered a single FHE scheme, I see no reason why it should generally have any simpler description than that. Use this information however you will for your sci-fi scenarios. 😀
Comment #45 July 28th, 2022 at 1:26 pm
Scott #42:
I don’t see how Newcomb’s paradox comes up; it doesn’t seem different from if a robot had access to it’s own blue prints. If Alice or a robot tried to simulate itself, it would just be an infinite loop (depending on the details). (I think “reflexive oracles” make self simulation more feasible?)
I guess a step towards make it more formal would be: choose an algorithm Q. Then let f be defined by f(g) := “Quantum state describing a black hole + Alice’s body + Alice’s brain running Q(g(g))”. Then run Q(f(f)). This should even work with circuits if your circuit description language is small enough (is that a thing?).
If Q just tries to simulate the unmodified quantum state, I’m not sure what happens? 🤔
Comment #46 July 28th, 2022 at 1:35 pm
Scott #44: Yes, you can always compose, but if the cypher doesn’t have a finite group structure then nesting more and more encryption might provably never get you back to the identity cypher. So the “trying to get back home” part of the analogy would fail.
Comment #47 July 28th, 2022 at 1:41 pm
Christopher #45: To say it differently, the usual setup of computer science is an adversarial game, between
(1) an algorithm, which is trying to succeed, and
(2) a chooser of an input, which is trying to make the algorithm fail.
An algorithm is “correct” if and only if it constitutes a winning strategy in this game.
This is still the case even in Lenny’s scenario, for all its exotic trappings. There’s Alice, who’s trying to learn certain properties of the state |ψ⟩. And then there’s whoever chooses |ψ⟩, who’s trying to make Alice not learn those properties.
Ah—but if you now say that |ψ⟩ itself depends on Alice (and hence, necessarily, on her strategy), then it seems to destroy this scenario. Maybe there’s still some way to make sense of it, but it’s far from obvious—especially since the AdS/CFT dictionary is famously nonlocal, so that any change to Alice will be “smeared” all over the boundary state |ψ⟩.
Make sense now?
Comment #48 July 28th, 2022 at 1:50 pm
Craig Gidney #46: Oh, now I understand your scenario, thanks!
Note that, even if there were a finite group structure, “getting home” by repeatedly re-encrypting would typically take exponential time. And if you have exponential time, why not get home by just breaking the original encryption? 🙂
Comment #49 July 28th, 2022 at 2:07 pm
Scott #47:
Oh yeah, that makes sense. You could probably modify that to forcing the environment to choose f, but I get that this is know a different problem than originally posed. The environment can’t arbitrarily choose a universe; whoever is designing Alice gets a small say as well.
👍
Comment #50 July 28th, 2022 at 2:20 pm
Scott #0 (et al #3, #4, #7, #8, #9, #15, #22)
First, thanks for taking the time to relay this new gedankenexperiment and the great explanation!
But … I’m with a few others above in wondering why does “consciousness” appear in this discussion?
Why not say “observer”, or, if we want to bring in computation then how about “Turing machine” or “programmable computer” – including a “virtual/software computer”. Obviously Alice is just a programmable computer (right?) … a Turing machine. Or are we claiming that Alice has something special called “consciousness” that a programmable computer (including a quantum computer / Turing machine) couldn’t achieve?
Why wouldn’t any computer duly programmed …
be searching and “hoping to learn the answer to a beyond-BQP computational problem”? Computers searching for an answer are not “hoping”?
Requiring “consciousness” (without defining it) unnecessarily distracts from the complexity/physics question …
Can there be a rule that “consciousness” shouldn’t be used unless “consciousness” is actually going to be defined?! 🙂 Whatever consciousness is … it is certainly running on a programmable computer (that we and Alice call Alice). When we say “computer” we include in that the possibility the computer could be someone’s brain.
So replace “consciousness” in
with “observation” … or “capacity to perform a physical observation” … or “capacity to be an observer in the accepted sense of quantum physics where observation means interaction with whatever is being observed” or “capacity to record the properties of a physical process” … or whatever.
In some sense, the Mars rover is a (classical) copy of our “observer-ness” isn’t it? I mean it is not a copy of all of our possible observer-ness (observations) … but it is a copy of some of our observational sub-routines.
I know that when physicists say “observer” they don’t mean consciousness. And I’m OK with this thought experiment … up until we say “consciousness”.
So then we say, “the question of whether or not ‘observation’ exists in the homomorphic encryption.”
Sorry for the long post … it just drives me crazy that “consciousness” gets used so much when the topic involves quantum theory. I keep going back to the postulates … and it’s just not there 🙂 Observer/observation seems defined within the quantum postulates as the existence of projection/Hermitian operators … which means we have a device that can encode amplitudes, state vectors, etc. etc.
Is there some work the word “consciousness” is doing beyond what could be done by “observer” that I need to understand?
Thanks again for the great post!
Comment #51 July 28th, 2022 at 2:40 pm
Clint #50: To say it one more time, if you choose to “leave consciousness out of it,” then at some level, all that’s going on is a giant quantum computation that simulates a conformal field theory. This CFT has a bulk dual, and in the bulk dual, Alice is falling into a black hole. That’s a little strange, but by definition, no quantum computation can ever violate the Quantum Extended Church-Turing Thesis (QECTT).
But if you now ask: what does the “Alice” who’s inside the simulation see—the answer is that she sees the solution to a computational problem that we believe can’t be solved in quantum polynomial time. Which seems like it would violate the QECTT. Granted, there’s no way to extract the answer and bring it back to “our” world, without taking exponential time—just like the QECTT predicts. But inside the simulation, Alice does see the answer.
The point I want to make is this: whether you’re impressed by that or not impressed, presumably depends on whether you think there’s “anything that it’s like” to be the simulated Alice! Maybe there’s nothing that it’s like, in which case we’ve just done a huge, pointless quantum computation. But if you don’t even want to discuss the question … well, this is one of those scenarios that’s specifically constructed to try to force you to discuss it. 😉
Comment #52 July 28th, 2022 at 3:09 pm
Scott #51:
> whether you’re impressed by that or not impressed, presumably depends on whether you think there’s “anything that it’s like” to be the simulated Alice!
This reminds me of an attempted definition at consciousness: X is conscious iff the question “What would it be like if I were X?” makes sense. (See “What Is It Like to Be a Bat?”: https://en.wikipedia.org/wiki/What_Is_It_Like_to_Be_a_Bat%3F )
Comment #53 July 28th, 2022 at 3:20 pm
Joshua #6, is it possible that you are married to an AI trained on the contents of gr-qc?
Comment #54 July 28th, 2022 at 3:29 pm
I’m really lost (unsurprisingly).
How’s that different from:
1) I happen to have the solution to a gigantic NP-hard problem instance.
2) I write that solution on a piece of paper and throw it into a black hole.
3) Solving that problem outside the black hole is NP-hard, but jumping in the black hole allows you to instantaneously “solve” the problem by reading the solution on the piece of paper.
Supposedly the wave function of the black hole includes the solution to the problem as well, since the piece of paper with the solution is in it. So if I was given the BH’s wave function and was able to transform it easily by that AdS/CFT correspondence, I would have solved an NP-hard problem easily, therefore the transformation has to be as hard as solving the NP-hard problem?
Comment #55 July 28th, 2022 at 3:33 pm
Scott #41: All of this has me wondering something. Do you, (or anyone else here) know if there’s a known way to make a form of homeomorphic encryption that allows its own decryption if/when some internal computational state/criteria is reached? (Say, maybe somehow releasing/making plain the key to decrypt the rest if some internal criteria is satisfied, or some other way?)
For instance, is there any known or suspected way to make a modified form of homeomorphic encryption where, for instance, a mind running inside of it could choose to allow it to be decrypted?
Comment #56 July 28th, 2022 at 3:53 pm
fred #54: Your proposal requires that someone has already written down a solution to the NP-hard problem! In which case, if they throw the solution into a black hole, you can learn it by jumping in; if they keep the solution locked in their house, you can beat down their door with an ax, etc. etc. No surprises there.
By contrast, Lenny’s thought experiment doesn’t require the solution to be “written down in advance” anywhere! Maybe the person who prepared |ψ⟩ had to know the solution, maybe they didn’t. Even if they did, though, they can be long gone.
Comment #57 July 28th, 2022 at 4:15 pm
Psy-Kosh #55: I’ve now seen homomorphic encryption corrupted to both “holomorphic” encryption and “homeomorphic” encryption … both concepts that I hope someone invents! 🙂
More seriously, the thing that you’re asking for—where certain outputs of an otherwise-encrypted computation are revealed in the clear—sounds like program obfuscation as opposed to FHE. Obfuscation has also been extensively studied by cryptographers for more than 20 years. “Black-box obfuscation” is known to be impossible for certain functions—a seminal result—though it’s possible for certain special functions under strong cryptographic assumptions. If you want to obfuscate arbitrary computations in a way where the output gets revealed at the end, you generally have to settle for indistinguishability obfuscation (which is extremely impressive in its own right).
Comment #58 July 28th, 2022 at 4:45 pm
Having read some more comments and taken a walk, I agree with those above who say consciousness should not be the issue. I see the issue as observation vs. computation. Either Alice or a Mars Rover observes something, not computes it.
Suppose Alice takes exponential time to find a Traveling Salesman solution for visiting all the solar systems in this galaxy, then shows it to Bob, system by system, in polynomial time. Has Bob solved the computation?
The only relation I see between consciousness and computation, off hand, is that consciousness is a way of allowing us to double-check our computations and find errors.
So from a dummy’s point of view, there are holes in the thought experiment. Please don’t tell Dr. Lenny I said so, though.
Comment #59 July 28th, 2022 at 4:46 pm
Scott #24
That’s the thing. I’m not particularly tempted to say that QECTT was violated. Unless you can come up with a physically relevant definition of “conscious” then there is no physically relevant difference between dropping Alice into the black hole and dropping the Mars rover in. This reminds me of a disagreement I had with Lubos Motl. He seemed to claim that conscious observers were required to collapsed the wave function. I pointed out that if that were true then you could devise an objective test to tell if something were conscious or not. You cannot. Nor can you develop such a test by dropping people or robots into black holes. There is no observable difference.
Lets put Alice into the box with Schrödinger’s cat. From her perspective she knows very well if the cat is alive or dead. From our perspective the cat can’t even be said to be in either state. This raises deep issues with the nature of consciousness and the nature of reality itself. The only way forward is to accept that wave collapse is an irreducibly subjective thing. You cannot freely translate between points of view that are thermodynamically disconnected.
Now lets drop the box into the black hole. Now Alice is in possession of facts inside the black hole that are not available to us. But all you have done is put a complex lock on the box that would take an exponential time to open.
Alice as a conscious observer is included to encourage you to freely translate between subjective points of view. I don’t think we are allowed to do that.
But then I’m not sure I understand the problem correctly so…
Comment #60 July 28th, 2022 at 4:51 pm
Scott, sadly, I still do not understand the logic of why “Being Alice” matters in the setup.
Is there some (non-sorites) distinction that matters here? Like, if you sent a simulated ant into a simulated AdS black hole in a similar setup (we can call it… homoformic encryption), and the ant would experience some equivalent of “solving a beyond-BQP” by feeling the shock waves or what not, how is it different from experimenting on sim-Alice or on “non-conscious” sim-sensors?
Comment #61 July 28th, 2022 at 4:52 pm
Apparently I don’t understand how this works. We have |ψ⟩ of CFT boundary. In the corresponding AdS bulk there’s a black hole. The state of black hole inside is scrambled in CFT representation. Why can’t we evolve |ψ⟩ backwards in time to the moment before black hole formation, then translate it into AdS bulk and evolve AdS bulk forward, thus obtaining the scrambled part?
Comment #62 July 28th, 2022 at 4:54 pm
Scott #57: Whoops. 🙂
I think I’ve heard of that proof, but haven’t looked at it much yet. However, would the impossibility of program obfuscation where some outputs are unobfuscated make impossible something that _completely_ unobfuscates itself given some internal criteria is fulfilled? So it remains obfuscated until it wants to output a result, at which point it becomes completely unobfuscated? ie, if and when it outputs a result, it doesn’t just give a clear result, but completely unobfuscates the program as a whole in the process.
Would something like that be forbidden by the relevant impossibility theorem?
And thanks.
Comment #63 July 28th, 2022 at 4:58 pm
It’s funny: my only real takeaways after reading this, aside from a crushing wave of intellectual humility, were:
1. This sounds like the precis to Greg Egan novel.
and
2. The scenario must not be an issue because the information cannot be communicated to those outside the black hole.
…which were covered by comment #1 and #8. Well done, gentlemen. I’ll see myself out.
Comment #64 July 28th, 2022 at 6:06 pm
JimV #58: If Bob could submit any Traveling Salesman instance of his choice to Alice, and get back an optimal solution from her in polynomial time, then yes, the power to solve an NP-complete problem would be his. Granted, Alice would be doing all the actual work, but the Quantum Extended Church-Turing Thesis would be refuted all the same (either that, or else NP⊆BQP).
What we’re talking about here is directly analogous to that. Provided you believe “Alice is still Alice” after she enters the simulation, she can see the solution corresponding to any input state |ψ⟩ that’s handed to her, and do so in polynomial time as experienced by her (both inside and outside the simulation). Hence the apparent challenge to the QECTT … unless, of course, we disallow this sort of shenanigan by fiat (as arguably we should!).
Comment #65 July 28th, 2022 at 6:13 pm
ppnl #59 (and Shmi #60):
Unless you can come up with a physically relevant definition of “conscious” then there is no physically relevant difference between dropping Alice into the black hole and dropping the Mars rover in.
OK then, forget about Alice and forget about the Mars rover. Suppose you wanted to know the solution to this particular computational problem, desperately enough that you’d … well, that you’d jump into a black hole if you knew that the solution was inside. Would you then submit to the uploading procedure described in this post, with some expectation of success? For that matter, what about jumping into a literal black hole? As far as external empirical tests can say, the universe might as well end right at the event horizon; would that be a showstopper for you?
Comment #66 July 28th, 2022 at 6:16 pm
red75prime #61:
Why can’t we evolve |ψ⟩ backwards in time to the moment before black hole formation, then translate it into AdS bulk and evolve AdS bulk forward, thus obtaining the scrambled part?
That’s an excellent question, to which the answer is: we can’t evolve backwards without knowing which external “shockwaves” were applied in the forward unitary evolution to prepare |ψ⟩, which is exactly the thing we’re trying to figure out.
Comment #67 July 28th, 2022 at 6:44 pm
Scott, I’m curious whether you think that the back-reaction from physically simulating Alice that I discuss in comment #30 is at all significant in this scenario. It might be easy to just leave any back-reaction from Alice out of your simulation. But on the other hand, a big meta-lesson from quantum mechanics is that the observer effect can be more important than one might intuitively expect. And for all we know, maybe back-reaction on the environment turns out to be a necessary ingredient for consciousness (kind of like how (I believe) David Deutsch thinks that being large and complex enough to decohere any superpositions that you measure is a necessary ingredient for consciousness).
(BTW, I figured out my LaTeX issue. Turns out the LaTeX doesn’t render in the preview, but it does in the final post.)
Comment #68 July 28th, 2022 at 6:48 pm
Psy-Kosh #62:
Would something like that be forbidden by the relevant impossibility theorem?
Alas, I think it would be. Let me model the entire thing you want as a partial Boolean function to be obfuscated. More concretely, let f(x) be what the person inside the simulation would say if they’re given x as input. Then we define:
g(x) = unobfuscated computation history of f(x), if f(x) begins with “LET ME OUT!”
g(x) = UNDEFINED otherwise (i.e. random garbage should be returned).
Our goal is to provide an obfuscated implementation of g.
The trouble is, if the person inside the simulation is going to be doing anything that looks like universal Turing computation on x, in order to decide whether to produce a “LET ME OUT!”, then we ought to be able to take the Barak et al. impossibility of obfuscation proof, and embed it into the defined part of g.
This would mean that we can only hope for black-box obfuscation (i.e., “the person choosing whether to escape from the encryption,” with perfect security if they choose not to escape), in special cases that fall short of Turing-universality.
Comment #69 July 28th, 2022 at 6:51 pm
Okay, after proudly saying I was able follow this post, then thinking about it some, I want to ask a question that may end up illustrating just how little of it I followed.
It’s about this part of the post:
2. The QC performs entangling operations on |φ⟩ and |ψ⟩, which correspond to inserting Alice into the bulk of the universe described by |ψ⟩, and then having her fall into the black hole.
My question is: The QC has |φ⟩ and |ψ⟩ – but |ψ⟩ doesn’t describe the bulk of a universe, it describes a boundary condition. Why can the QC simulate Alice falling into the black hole in the ADS world? Wouldn’t the QC need to translate the CFT |ψ⟩ into some ADS state, which would then already include a description of what’s in the black hole?
I think I must either be misunderstanding what “bulk of the universe” means here, or misunderstanding something about ADS/CFT?
Comment #70 July 28th, 2022 at 6:56 pm
Ted #67: The short answer is, yes, when Alice jumps into the black hole, of course she’ll affect whatever is there. Likewise, when simulated-Alice jumps into a simulated black hole, she affects the simulation of whatever is there. But she can still learn about what’s inside by jumping in and checking! Just like she can learn about what’s in a forest by going there, despite her own presence inevitably changing the forest.
When we define the detailed computational problem that Alice is trying to solve, we simply have to be careful to ask only for data that Alice could actually have measured, had she jumped into the actual bulk black hole (accounting for the backreaction caused by her own presence, etc). Such information, being behind the event horizon, should still in general be pseudorandomly scrambled, and thus exponentially hard to access via “external” manipulations of the CFT state |ψ⟩.
Comment #71 July 28th, 2022 at 7:14 pm
Scott #7
“Alice can only get into the simulation and “experience” the results while there. She can’t bring them back with her.”
Okay, but the crux of the experimental setup for me is: I think Alice is long dead and the simulated version is not sentient and accordingly not experiencing anything. My reasoning would in large parts just be a repetition of the comment(s) I made in the other blog post’s comment section just half an hour ago.
So there is nothing interesting going on under this assumption right?
Comment #72 July 28th, 2022 at 7:21 pm
1Zer0 #71: Correct. Under that assumption, very little of interest going on.
But what if Alice had jumped into an actual black hole to check what was inside? Would you agree that then she’d experience the answer (whatever it was), even though she could never communicate it to anyone outside?
In other words, is it the “uploading” part that makes you say that Alice dies in this experiment, as opposed to the “black hole” part?
Comment #73 July 28th, 2022 at 7:27 pm
Dan Staley #69:
My question is: The QC has |φ⟩ and |ψ⟩ – but |ψ⟩ doesn’t describe the bulk of a universe, it describes a boundary condition. Why can the QC simulate Alice falling into the black hole in the ADS world? Wouldn’t the QC need to translate the CFT |ψ⟩ into some ADS state, which would then already include a description of what’s in the black hole?
Aha! The whole point of AdS/CFT is that the AdS and CFT sides aren’t two different theories, but the same theory viewed in two different ways. By simulating the boundary CFT, you therefore are simulating the bulk as well—including any conscious observers who might live there.
I admit that this might be a lot for some people to swallow! At the least, it resurfaces a lot of old questions about what kinds of computer simulations of a brain suffice to bring about consciousness, even if we suppose for the sake of argument that some do.
Comment #74 July 28th, 2022 at 8:57 pm
Scott #73: Thank you! Looks like I was misunderstanding AdS/CFT.
Let’s see if I’ve got this right:
The point here is that |ψ⟩ describes a bulk universe, and we can compute things about that bulk universe, except we can’t compute things that are beyond the event horizon of a black hole (or we can, but it takes some very large amount of time)? And this somehow implies that we can insert Alice into this simulated universe, but not past the event horizon? (I’m still a little fuzzy on how that insertion part works.) And then we can run the simulation, in which Alice jumps into the black hole and observes what’s in there.
In the analogy of homomorphic encryption, the unencrypted/encrypted boundary plays the role of the event horizon in the bulk universe, not the role of translating between a bulk universe and a CFT boundary, correct?
I think I now understand the objection of Fred #54: In the “real universe” discussion, before we introduce the quantum computer, Alice basically has to rely on the fact that the universe she’s in exactly corresponds to the bulk universe encoded by |ψ⟩ (maybe without her in it? I’m actually unclear why adding her to the real universe causes problems, while entangling her with the quantum-simulated one does not). I see how that can be interpreted as someone throwing the solution into the black hole – |ψ⟩ is just magically equivalent to her universe for some reason which is why the solution is in there. But the key thing, if I understand correctly, is that this objection disappears once we move to the quantum computer, because we just start with |ψ⟩, and the black hole and everything are just inherently part of it when we interpret it in the AdS/CFT context within the QC.
One last question: Why does uploading Alice kill her? Is this that “no-cloning theorem” I keep hearing about?
Comment #75 July 28th, 2022 at 9:00 pm
Okay, I get it that the bulk state could be any made-up state with a black hole in AdS–but, as I wondered earlier, how do you make up such a state to include the inside of the black hole (since the CFT part does)? Can that be arbitrary and still produce the black hole? Also, how do you compute the state of Alice without killing her before you are done? (So as to have the whole Alice and not just a Mars-Rover version.) (Even assuming we don’t care about fine detail so the no-cloning theorem doesn’t apply.) I am skeptical that what you get from the experiment is something which could be inside a black hole, known by something that the original Alice would believe was going to be herself, rather than a separate entity which had no part in the computing except as an observer. I guess the point is whether or not one feels that way.
But it is still a conjectured way of partly (only a picosecond worth of observation inside a black hole) deciphering a pseudo-random arrangement of a set of dictionary entries, although it may not be a realistic set and the knowledge does not survive and can’t be transmitted, so we will never know if anything meaningful was observed.
Anyway, thanks for the interesting post, as usual.
Comment #76 July 28th, 2022 at 10:59 pm
Hm, do we really the simulation step? How about instead we take the qubit string |ψ⟩, and translate that into an actual physical manifestation, a real black hole with boundary state |ψ⟩. Then have the real Alice fall through the real black hole and observe its interior. If making this physical black hole is possible then to rescue the QECCT it is necessary to make an even stronger metaphysical stance than merely that homomorphically encrypted observers don’t count, to state that even observers inside physical black holes don’t count. This is awkward if you also believe that cosmological horizons are essentially the same as black hole horizons. Are we compelled to accept that people who escape our cosmological event horizon no longer exist? If so, whose cosmological event horizon is the privileged one which distinguishes reality and illusion?
Comment #77 July 28th, 2022 at 11:35 pm
Scott #65
Ok lets change the question a little. If I desperately wanted to know if Schrödinger’s cat were alive or dead before opening the box I could place myself inside the box with the cat and watch. Would I expect to succeed? Yes. This is deeply troubling because from outside the box it isn’t that we just don’t know the state of the cat but that the cat cannot be in any particular state at all. It is a conundrum.
The point is that this conundrum does not depend on an intelligent observer because the cat will suffice. You do not need the cat because the measuring device will suffice. You do not even need the measuring device as the air in the box will suffice. You don’t need the air. All you need is the unobserved particle and all else follows. The rest is theater to illustrate the point. Reality is weird and consciousness gets dragged along for the ride.
The same chain of logic follows with Alice and the black hole. You can prepare and drop an object into a black hole that records information that is unavailable outside the black hole. In the computer this information is encoded in a way that makes it unavailable outside the program. That is weird. But that weirdness in no way depends on the consciousness of the object you dropped in.
So yes I would expect to be successful but I would expect the Mars rover to succeed as well by any meaningful definition of success. Only a conscious observer can be aware of their success but then only a conscious observer can be aware of anything at all.
Comment #78 July 29th, 2022 at 2:09 am
Scott, often, I’ve said to my therapist, “Life isn’t complicated (except for rocket science – which is actually discernible to the layperson, provided he or she has access to Wikipedia.”)
Unfortunately, in these pages, I think I’ve discovered the clearest refutation of my axiom. It turns out discussions of anti-deSitter space are, actually, significantly more complex than rocket science and infinitely less parsable by this layperson, to boot.
(Looks like I need a new organizing principle for life.)
I have no idea why your site appeared in my Google feed during my attempts to parse the meaning of the world just before bed. Nonetheless, it did.
As someone who barely graduated w a B.A. in English, in actuality, I have a catholic interest in the world. In fact, I have lingered (many times) on Wikipedia’s entry for AdS (even if I’m no closer to understanding the topic than the day I stumbled upon it.) (Actually, that prob explains why your blog showed up in my feed!)
Nonetheless, as someone whose ancestors emigrated from E. Europe, I love your “Shtetl-Optimized” emblem! Thank you, as well, for providing intellectual food for thought. Guess I need to spend some more time on Wikipedia!)
p.s. Truthfully, when I started this response, I intended to tell you, that my immediate reaction to your entry was a quasi- murderous desire to destroy everything written here bc of it’s profound incomprehensibility. In a flash, suddenly, I understood what it felt like to be a fascist, that is, someone who seeks to destroy what he can’t understand. Nonetheless, bc that exposed a nearly-sociopathic rebuke to your work as well as a horrifying glimpse into my own coal bin of a heart, I refrained from mentioning it. I only do so now for possible comic effect. Plus, now, I have something new to talk about in therapy next week!
Comment #79 July 29th, 2022 at 3:42 am
OK. My confusion came from the fact that no-leakage-in-P is by definition, not an assumption. FHE has semantic security, prevents side channels, etc.
Then the interesting observation is that complexity is a property relative to the observer. If the observer jumps in, w/o ever going back, and gets the result in P w/o ever communicating it, can we observers on the outside meaningfully say that the problem was solved in P, and that the theorem has been violated?
I’d say something similar occurs with other hyper-computational models (hope I used the right term), where e.g. a computer performs an exponential computation in one reference frame to eventually communicate the solution to a computer in another reference frame where only P time has passed.
I don’t know how many of these hyper-computational models allow sending the response in P (in time or energy). Neither how many are realizable in our universe, although Susskind’s example is definitely not as far as we know.
The main difference is that here no exponential computation is ever done, but we’d be forced to pay the exponential cost to communicate the response.
The most interesting idea so far is #8’s: reinforce simulation hypothesis. Every time a civilisation faces a crisis they create a simulation of themselves in a blackhole and solve a hard problem that fixes the issue.
Q: Is it possible to jump in only once to pre-compute a “hard dictionary” of some sort that permits the solution of more than one hard problem with polynomial cost?
Comment #80 July 29th, 2022 at 6:02 am
Could you actually turn around the analogy and construct a homomorphic encryption scheme based on AdS/CFT that allows quantum computation on the encrypted data? Or is the AdS/CFT dictionary too theoretical to be used/implemented in a meaningful way?
Comment #81 July 29th, 2022 at 6:23 am
Hello Scott, in January you said you wanted to write something in answer to the Q “Why Quantum Mechanics?” and asked your readers for comments (you got 700+).
Did I miss your piece on this, or is it still only early days with the preparation? 😄
Comment #82 July 29th, 2022 at 7:19 am
Scott #70: Sure, of course (either real or simulated) Alice can jump into the black hole and see something happen. And of course the computational complexity of decoding what’s happening inside the black hole from the boundary CFT description will be roughly equally complicated either way (there’s no reason why one extra human being falling in should qualitatively change the computational complexity).
But I still think this is a nontrivial consideration. I can think of two possible ways to operationalize your instruction to “simply be careful to ask only for data that Alice could actually have measured, had she jumped into the actual bulk black hole (accounting for the backreaction caused by her own presence, etc)”:
1. We could only ask about physical results that would be unaffected by her own presence, or
2. We could explicitly incorporate her back-reaction into the statement of the problem.
Both of these options carry some potential issues:
1. If the “shockwaves” or whatever you’re asking about depend chaotically on the history of the infalling matter, then any physical results that are insensitive to Alice’s presence might necessarily be so coarse that those *specific* results about the black hole interior might be efficient to calculate from the boundary state \( | \psi \rangle \), thereby circumventing what makes this situation interesting.
2. In the second case (which is what I suspect you meant in your comment), then you’re actually solving a slightly different computational problem than the one you described. You aren’t solving the problem “apply the AdS/CFT dictionary to figure out which bulk black hole interior corresponds to the given \( | \psi \rangle \)”. You’re instead solving the problem “figure out which bulk black hole interior corresponds to \( | \psi \rangle\) plus a copy of Alice“. This problem is equally difficult as the original one, but it could have a qualitatively different answer (if the physical dynamics are chaotic).
Sorry, maybe this is just nitpicking, but I want to make sure that I understand the setup.
Comment #83 July 29th, 2022 at 7:27 am
A couple of questions:
A) I don’t really understand step 2. Why are we performing an entangling operation? How does that “insert Alice into the bulk”? And wouldn’t the entanglement break the unitarity of the CFT simulation?
What I would expect to work here would be to take the description of Alice (along with a spaceship and other equipment) as a set of commuting observable values in a region of the bulk – a classical description. Then we could use the (conjectured) polynomial-time dictionary to find a unitary that transforms the CFT state to one that is the same, except for having Alice added to the desired location. Then we perform that unitary, followed by the time-evolution of the CFT.
Is that somehow equivalent to what you described?
B) Is there any reason the original Alice needs to die, other than the “minor” technical difficulty of scanning a brain in vivo? Somehow killing the original makes it easier to think of the simulation as the “real” Alice, but that’s just a silly bias, right?
C) I think the backreaction issue need much more attention. The whole point of holography is the nonlocality of information – any local change comes along with changes in the (amplitudes for values of the) gravitational degrees of freedom, all the way out to the boundary. So it’s not so clear that what Alice measures inside the hole will be the correct answer for the original, Alice-free state.
One potential way to get around this: we could insert Alice as a set of perturbations of the boundary conditions for the bulk fields, beginning after the time corresponding to the given state. In AdS, the boundary conditions need to be set “by hand” for all of history – the future is not fixed by the past. So such an insertion can be fully consistent with the physics of the existing state. Then the change propagates inward no faster than the speed of light, and it can reach the black hole in finite time as measured by observers in the bulk (although the proper time along the path is infinite). Presumably such a perturbation can be found, to insert “stuff” that will eventually form into the desired description of Alice.
That way, we know that the BH interior was in the correct state at the initial time (i.e. anywhere outside the future light cone of the changes we made). The changes afterward are limited to ordinary, physically possible, dynamical changes. So if the desired “solution” is something stable enough to persist physically until Alice gets there, she can measure it.
Comment #84 July 29th, 2022 at 9:03 am
Scott #51:
Thanks for the reply! I admit to being one who needs things explained to them 10 (maybe 20) times. Thank you for your kind patience as always 🙂
I slept on this last night to give my brain time to absorb it. And as my brain was shutting down its “conscious me” routine late last night it was feeling like there were echoes here of Wigner’s friend and also echoes to Hofstadter’s Godel, Escher, and Bach (where I first encountered self-reference long ago). Recommended by the way to anyone here who hasn’t read it (surely not) and is interested in how cognition and meaning can emerge from “non-cognitive and meaningless” computational rules/devices (seemed to be a topic here recently).
So … I think I get it now … The key point is that Alice is going to use a black-hole-simulation-device to solve a beyond-BQP problem. This only counts as solving a beyond-BQP for the specially positioned observer Alice because the simulation of Alice carries with it the knowledge of her being given the CFT dual and her own encryption.
Like you said … It depends on adopting the perspective of that observer.
However, I would not agree that this is about “philosophy of mind”. I’m with Gottesman (and I presume Susskind) that we are talking about physics/complexity – anything this says about “minds” is a consequence of the physics/complexity. And for me this is just as interesting regardless of the “mindfulness or consciousness” of the observer – just so long as an “observer” can be “given the problem to solve” in a computationally meaningful way. Although, of course, imagining myself going through the device is … more emotionally motivating.
By the way, does this mean that an acceptable use of Webb would be to scan event horizons for observers dropping in?
My reply to your bold point is: Of course, there is “something that it is like” to be simulated Alice! Just like there is “something that it is like” to be a bat or an elephant or the moon or anything 🙂 If Alice is “uploaded or simulated” then the uploaded/simulated Alice has all the same computational abilities (mind/consciousness/experience/memory … whatever) as the original Alice. That is because “consciousness” is an empty word for me. For example, my take on the Free-Will theorem is that there is nothing at all “special” about being an observer, or “consciousness” if you like (except the requirements of the quantum postulates) – even atoms can do it! Humans thinking that their observer (or consciousness) status is “special” I view in the same way as Turing – something we need to be “consoled about”. Self-referential computers … quantum observers … those things I know what they are (well best I can know anyway …) because I can check to see if they satisfy the definitions of universal computation and/or quantum theory.
How is this related to Wigner’s friend? Does this reveal a similar kind of no-go physical limit? Are we forced to say something like that an observer outside of the encryption and an observer inside the encryption cannot “share the same reality”?
Following Susskind’s prompt do we adjust the QECTT to say something like …
“The existence of FHE and event horizons (EHs) confirms the QECTT in that if you solve a beyond-BQP problem then you could only have just passed through an FHE/EH boundary.” In other words, the universe “protects” its BQP character. It prevents you from returning the observation to the original “reality”. And that is a property of the character of the physical universe just like protections against superluminal signaling or other known physical limits.
That seems to line up with FHE and EHs as being “boundaries to observation”.
What are other candidate statements for Susskind’s QECTT “modification”?
Thanks again for hosting a great discussion!
Comment #85 July 29th, 2022 at 9:45 am
Scott #0:
An obvious question is whether, having learned the answer, “Alice” can now get the answer back out to the “real, original” world. Alas, the expectation is that this would require exponential time.
The question is misplaced. Alice will need an infinite amount of time relative to observers to just fall into the black hole, let alone get the answer to the “real, original” world.
Comment #86 July 29th, 2022 at 9:57 am
AK #85: No. Again, we’re talking this whole time about a simulation running on a quantum computer. Alice could’ve programmed it however she likes—including, once she jumps into the simulated black hole to get the answer, just pausing the physics simulation and then doing whatever it takes to expose the answer to an external user of the quantum computer. The point I’m making is that even then, exponential time would be needed to do this, assuming the FHE scheme is secure. We know that because, once you’ve gotten the answer out, you’ve broken the FHE scheme in our world! And consistent with that expectation, all the obvious ways of trying to extract the infalling Alice’s observations via measurements of the CFT state do indeed take exponential time.
Comment #87 July 29th, 2022 at 10:55 am
Dan Staley #74: Yes, your understanding basically matches mine. The key thing about the regions of the AdS bulk that aren’t hidden behind event horizons, is that you can access them via geodesics that start and end at the boundary. That’s what lets you do things like insert Alice by applying appropriate boundary operators.
As for the uploading process killing Alice: well, indeed it might not, if you have sufficiently advanced technology and if you don’t need to scan all the way down to the molecular level where the no-cloning theorem is relevant! The point is just that, even if no-cloning was relevant, in principle you could still upload Alice to a QC, at the cost of there no longer being a meat version of her.
Comment #88 July 29th, 2022 at 11:00 am
Itai Bar-Natan #76:
How about instead we take the qubit string |ψ⟩, and translate that into an actual physical manifestation, a real black hole with boundary state |ψ⟩.
The problem is that this would require creating a whole new universe. (When we say “boundary,” we don’t mean the black hole event horizon, but the boundary of the entire AdS spacetime.)
Maybe one can create new universes on demand (other than by simulating them in a computer), but that’s a question for Lenny, not me! 🙂
Comment #89 July 29th, 2022 at 11:05 am
Jason Barton #78:
Truthfully, when I started this response, I intended to tell you, that my immediate reaction to your entry was a quasi- murderous desire to destroy everything written here bc of it’s profound incomprehensibility.
If it makes you feel better, I’ve also been seized by a quasi-murderous desire to destroy documents that I don’t understand, but they’re usually, like, postmodernist texts, or bureaucratic instructions on how to submit grant proposals. 😀
Comment #90 July 29th, 2022 at 11:08 am
Scott #86:
Yes, we are talking about simulation.
My point is that the simulation will take an infinite amount of time so there will be no QC to complete the simulation or anyone in our world to get the answer.
Agree with you, even then exponential time would be needed to do this. But is it relevant if there is no one to appreciate the answer?
Comment #91 July 29th, 2022 at 11:18 am
In response to Mark and Scott in #8 and #9, one of my pet theories is that the Fermi paradox is answered by all the intelligent aliens figuring out how consciousness works and selectively only living on in very few branches of the multiverse (or maybe a tegmark-4 mathematical world) to steer their subjective conscious experience far better than normal physics in this universe can provide.
If everyone entangles their electronic brains with the solution to the hardest NP-hard question (what is the meaning of life, the universe, and everything?) they care about and they all experience its solution together then the incentives align for everyone to opt in and not be too concerned with the rest of the mundane universe afterward. I suppose that means if all we find of alien civilizations in the universe are old quantum computers spinning away at a large problem and no one else is around we should probably not turn them off (but it might be worth hopping inside).
Comment #92 July 29th, 2022 at 11:21 am
I have a alternative setup, quite similar but maybe easier to grasp. Question is : are they equivalent or I’m missing something ?
So again Alice is willing to risk her life to see the result of a difficult problem.
Alice is uploaded, transferred into a simulated environment inside a quantum computer. Here she use quantum suicide to solve the problem. The remaining versions of Alice can marvel at the result, as long as the quantum computer is left running.
Again if you really want you may be able to extract Alice (or as many Alice versions you like) from the quantum computer. At least by running the same quantum simulation on a classical computer with a lot of memory and time. (Well, I’m not completely sure this last point is true)
Comment #93 July 29th, 2022 at 12:18 pm
@Scott 87
The uploaded Alice is not Alice anymore. It is “her simulation” – another sentience, another being. Alice herself will never get to see the answer no matter how hard she tries, or just about. There is a ghost in all of us, and the twist is that there is also a ghost in the machines, if the provider so wishes. My refrigerator is an example of what might be a somewhat sentient machine. When I do something which might be considered dubious, it starts making clicking noises, and we can have a clicking conversation. As soon as I correct course, it stops. And there is more, if you ever wanted to hear about it. It has not clicked right now, so I guess I am allowed to send this email.
Comment #94 July 29th, 2022 at 12:52 pm
AK #90: You seem to be assuming that the simulation is somehow restricted to the reference frame of a bulk observer outside the black hole. But what the simulation really does, of course, is just unitary evolution of the CFT boundary! So all bulk observables need to reconstructed from boundary ones, if (for example) a user of the QC wants to know them. This can be done for observables both outside and inside the black hole horizon; the issue is that the latter ones seem to require exponentially more computation.
Comment #95 July 29th, 2022 at 12:55 pm
cgv #79:
Q: Is it possible to jump in only once to pre-compute a “hard dictionary” of some sort that permits the solution of more than one hard problem with polynomial cost?
I don’t think so, no. Where would the “dictionary” be stored, anyway? Even if you jump in to learn the solution to just one hard problem, you still can’t get the solution out, and both you and the solution will soon be hitting the singularity!
Comment #96 July 29th, 2022 at 1:17 pm
Benno #80:
Could you actually turn around the analogy and construct a homomorphic encryption scheme based on AdS/CFT that allows quantum computation on the encrypted data? Or is the AdS/CFT dictionary too theoretical to be used/implemented in a meaningful way?
Awesome question!
A first remark is that we already have homomorphic encryption schemes that allow quantum computation on the encrypted data. We don’t need AdS/CFT for this.
But OK, could you at least use AdS/CFT to get a new or different quantum FHE scheme? Taking care, of course, that all computation takes place behind a black hole event horizon, since otherwise decoding it from the boundary state is presumably doable in polynomial time?
Well, the central difficulty is that I can’t think of any AdS/CFT analogue of a decryption key—i.e., a secret that would make it easy to extract information from behind the event horizon if only you knew it. In fact, now that I think about it, that does kinda break Gottesman’s analogy (although the analogy is still fine for what I was using it for).
Incidentally, it might amuse you that already 8 years ago, when AdS/CFT was discovered to be literally a type of quantum error-correcting code, Daniel Harlow and others were speculating about that code could actually be used in building quantum computers. Harlow said that if so, it would constitute “the first-ever engineering application of quantum gravity.” Alas, that never panned out, since while the “AdS/CFT code” has all sorts of amazing properties related to the hyperbolic geometry of the AdS space, it doesn’t seem to be competitive in terms of distance, rate, decoding speed, or the other things that quantum computer engineers would care about.
Comment #97 July 29th, 2022 at 1:19 pm
Bertie #81:
Hello Scott, in January you said you wanted to write something in answer to the Q “Why Quantum Mechanics?” and asked your readers for comments (you got 700+).
Did I miss your piece on this, or is it still only early days with the preparation?
Still early days. You’re welcome to ask me again in a decade, if I haven’t done it by then. 😀
Comment #98 July 29th, 2022 at 1:22 pm
Ted #82: No, nitpicking is fine. 🙂 Like I said, I think you’re right that a careful formulation of the computational problem has to do as you say, and take potential backreaction into account. As long as this still involves measuring degrees of freedom that are pseudorandomly scrambled on the boundary, the point of the gedankenexperiment still stands.
Comment #99 July 29th, 2022 at 1:39 pm
maline #83:
A) There’s no getting around the fact that suddenly inserting Alice into your simulated AdS bulk universe would be, from the perspective of anyone else inside that simulated universe, a non-unitary and indeed miraculous operation! Just like sending the shockwaves into the black hole, which Alice has the goal of learning about. For the details of how these things are accomplished, I’ll unfortunately have to refer you to Lenny and the other physicists.
B) See my comment #87.
C) See my comment #98.
Comment #100 July 29th, 2022 at 1:44 pm
Clint #84:
By the way, does this mean that an acceptable use of Webb would be to scan event horizons for observers dropping in?
The nearest black hole is ~300 lightyears away, I think. Even Webb wouldn’t be able to see diddlysquat.
How is this related to Wigner’s friend? Does this reveal a similar kind of no-go physical limit? Are we forced to say something like that an observer outside of the encryption and an observer inside the encryption cannot “share the same reality”?
Perhaps not surprisingly, it seems most closely analogous to the age-old scenario of Alice jumping into a black hole while Bob stays outside. Alice still has access to Bob’s reality, but not vice versa.
“The existence of FHE and event horizons (EHs) confirms the QECTT in that if you solve a beyond-BQP problem then you could only have just passed through an FHE/EH boundary.” In other words, the universe “protects” its BQP character. It prevents you from returning the observation to the original “reality”. And that is a property of the character of the physical universe just like protections against superluminal signaling or other known physical limits.
That’s exactly the way Lenny talks about it.
Comment #101 July 29th, 2022 at 1:47 pm
Questions about the connection between the mind, consciousness, and the physical world are worthy questions, but one might wonder: do we really have to bring black holes into the discussion? Wouldn’t it be enough to formulate the gedanken experiment directly in computer (classical or quantum) terms? Sure, why not?
But my original purpose was not an exploration of the mind-matter puzzle, but something else; namely, the remarkable relations that are being uncovered, between gravity (and that means black holes) quantum mechanics, information, and computation. These include ER=EPR, AdS/CFT as an error-correcting code, the growth of black hole interiors and the growth of computational complexity, traversable wormholes and quantum teleportation, and more.
With the insight of Daniel Gottesman we can add a new connection—a duality if you like—to previous examples. It seems that black holes are related in a surprising way to homomorphic encryption. That seems very interesting to say the least.
By the way, to be clear, my view of whether QECT is violated by the gedanken experiment is exactly the same as Gottesman’s—when correctly formulated it is not violated.
Comment #102 July 29th, 2022 at 2:18 pm
Leonard Susskind #101: Just for you, I’ve decided to waive this comment section’s email verification policy, on the argument that you are inimitable.
Comment #103 July 29th, 2022 at 3:05 pm
This is a great post, love it.
I feel like very closely related story of “Okay, you don’t want to show me your private evidence, but want to know my opinion? Okay, fine, I’ll just run an uploaded copy of my mind in FHE (equivalently, in an MPC/ZK proof protocol), and I’ll decide in there if I agree with your assessment of your private evidence.” is a standard trope in my social circles, often used in some larger thought experiment.
But somehow I never thought of “Dang, I want to read these FHE encrypted messages — that’s okay, I’ll just jump myself into the FHE box, and read them in there, never again to escape without the private key!”. This _does_ feel pretty philosophically relevant. As per the waterfall argument from Why Philosophers Should Care About Computational Complexity, I probably don’t really assign moral patienthood to the waterfall because of the complexity of the isomorphism between the waterfall and the brain simulation.
But what if this isomorphism is efficient, but only when you hold a private key, as in the FHE mind? Do I grant moral patienthood to the FHE minds? What if the key was generated in a ritual that provably destroyed the key? Does the existence of a short key (even one I can’t ever find) that unlocks this isomorphism dewaterfall the FHE mind to the point that I have to grant it moral patienthood?
Like many great philosophical thought experiments, all of these questions feel so obvious in retrospect, to the point that I have to actively remind myself that I didn’t already think of them!
Comment #104 July 29th, 2022 at 3:14 pm
Peter #103:
I feel like very closely related story of “Okay, you don’t want to show me your private evidence, but want to know my opinion? Okay, fine, I’ll just run an uploaded copy of my mind in FHE (equivalently, in an MPC/ZK proof protocol), and I’ll decide in there if I agree with your assessment of your private evidence.” is a standard trope in my social circles, often used in some larger thought experiment.
Leaving aside the detail that FHE and MPC/ZK address different problems … which social circles would these be? 😀
Comment #105 July 29th, 2022 at 3:14 pm
Scott #95: Oh, I was incorrectly assuming (apologies, you clearly mentioned “last seconds of existence”) that we (Alice and all the people that jumped in with her) could live an arbitrary amount of time inside the event horizon with knowledge of the solution, without need of getting anything out.
The goal was that a civilization that needed to solve a hard problem would migrate into the simulation/event-horizon, which is what I had understood from #8. Then the question was about whether the initial hard problem we have solved efficiently could be used to solve other hard problems in the future, without requiring to nest additional levels of simulations/jumps-into-blackhole-without-return each time.
But I guess the first question then is whether we can make a simulation that allows an arbitrary long “existence” with knowledge of the solution in the first place.
Comment #106 July 29th, 2022 at 3:34 pm
Scott #104:
Sorry, to be clear, I mean slight variants on this sort of thought experiment are solved (often in an overkill way) by FHE, MPC, ZK proofs. To wit:
FHE: “You want to know if I’d agree with you if I could see your private evidence, and I don’t want to give you my brain circuit. Give me an FHE encryption of your evidence, I’ll run my mind on it, then send my encrypted thoughts back.”
2PC: “I want to know if I’d agree with you if I could see your private evidence. We’ll do a (somewhat trivial) case of 2PC together, where f is my mind, your input is your private evidence, and my input is empty, and we both learn f(private evidence, empty).” — this is maybe the silliest to mention because 2PC with one input fixed is just a ZK proof.
ZK proofs: “I want to convince you that you’d agree with me if you could see my private evidence. Send me your brain circuit, and I’ll give you a zero knowledge proof that you’d agree with me if you saw this evidence.”
Not literally the same problems, as you say, but, like, morally in the same vein; I was speaking sort of approximately. But somehow “Now *I* enter the FHE world, thus sort of maybe bypassing the encryption, kind of, maybe, depending on some nasty philosophical details.” never occurred to me ever!
By “these circles” I basically mean lunch conversations at Constellation.
Comment #107 July 29th, 2022 at 4:01 pm
Thank you for your lovely post! Regarding the questions about how |ψ⟩ is given, is it correct that you were trying to distinguish between Alice as a “QMA”-like Arthur who can perform a quantum computation on a quantum state provided to her, or a “QCMA”-like Arthur who has to build her own quantum state from a classical description thereof? If so would any of that matter for the brain-uploading step?
Comment #108 July 29th, 2022 at 4:45 pm
Peter #106: In that case, I can’t wait to have lunch at Constellation again, whenever I’m back in Berkeley!
Comment #109 July 29th, 2022 at 4:59 pm
Mark S. #107: No, I don’t think any of it matters for the brain-uploading part. But it’s what determines the complexity of the problem that simulated-Alice sees the solution to, as follows:
1. If Alice is given |ψ⟩ as a table of 2n amplitudes, then she can solve a “random vs. pseudorandom” problem that naïvely would take 2p(n) time for some large polynomial p. The trouble is that simply reading the input would already take 2n time! (And n can’t be tiny, or else simulated-Alice couldn’t even fit in the black hole to see the answer.)
2. If Alice is given |ψ⟩ via a quantum circuit C that prepares it, then everything depends on whether there exist good schemes for obfuscating quantum circuits that simulate a CFT with external shockwaves. If so, then Alice can see the answer to an honest-to-goodness hard problem—one that can be specified using a p(n)-bit input but would naïvely take exp(p(n)) time to solve. If not, though, the fear is that she could always just figure out the sequence of shockwaves by examining C, without needing to upload her brain or jump into a black hole or anything drastic like that.
3. If, finally, Alice is given |ψ⟩ as a physical n-qubit state (or rather, the tensor product of poly(n) copies of the state), we’re basically in the situation analyzed by Bouland, Fefferman, and Vazirani. I.e., it’s extremely plausible that we then have an exponentially-hard random vs. pseudorandom problem, but it can’t be compared directly to problems in BPP, NP, BQP, etc. since the input is itself a quantum state. (Note that being given poly(n) copies ensures that the problem is at least information-theoretically solvable, so that there is a computational complexity question here—even that isn’t entirely obvious a-priori.)
Comment #110 July 29th, 2022 at 7:54 pm
Scott,
you probably already know this, but it’s necessary to make it explicit again and again:
1) AdS/CFT is an unproved conjecture, despite all the claims and fuzz that has been made about it in the last 25 years or so.
2) It doesn’t give any insight into QG, for two reasons. One, the chances that string theory describes QG are almost null by now (most string theorists have quietly abandoned that line, as well as that of reproducing the SM…, they are into “emergent spacetime” now), while the QG gravity part in AdS/CFT is indeed a string theory QG. Second, even if it were, it’s about AdS QG, which is not our universe, and this detail is actually quite relevant.
It’s great you are having a good time with the likes of Lenny Susskind et al, but, really, that’s not physics by any stretch of the term. It’s not even speculative physics. They seem to have entered into some sort of quasi-theological type of speculation now. But, at least, theology had Aquinas, who had some respect for logic. This new school of theology has Lenny, which I’m sure is a charming person, but, as a physicist, he’s not only the master handwaver, he’s a handless handwaver! I’m not trying to be agressive, just really trying to express how low is my opinion of his career, research and methods.
I do think he’s a good expositor and popularizer, though.
Anyway, carry on. If they give you inspiration for computational problems, that’s fine I guess.
Comment #111 July 29th, 2022 at 10:55 pm
Scott #94:
I tried to present my argument using reference frames. However, the question is
whether or not the interiors of black holes are describable in AdS/CFT.
If they are not then unitary evolution of the CFT boundary does not help you to reconstruct all bulk observables.
Comment #112 July 29th, 2022 at 11:07 pm
Leonard Susskind #101:
But my original purpose was not an exploration of the mind-matter puzzle, but something else; namely, the remarkable relations that are being uncovered, between gravity (and that means black holes) quantum mechanics, information, and computation. These include ER=EPR, AdS/CFT as an error-correcting code, the growth of black hole interiors and the growth of computational complexity, traversable wormholes and quantum teleportation, and more.
Yes, those are good questions. The problem is that there is no well-established foundation to answer them. It looks like we keep shifting the problem from one domain (quantum gravity) to another (gauge theory) and another (homomorphic encryption) without a proper framework.
Comment #113 July 29th, 2022 at 11:08 pm
Pretty cool Gedankenexperiment. I especially like the analogy to homomorphic encryption.
What I don’t understand: why do you always kill Alice during the brain uploading? Is that an integral part of the story, or would uploading a clone of her brain into the quantum computer work just as well?
Comment #114 July 29th, 2022 at 11:32 pm
Peter #103:
Yeah the problem of comparing of “realness” between FHE minds and waterfall minds is pretty interesting. I think I share your intuition that FHE minds should be considered “real” while waterfall minds should be considered “not real” (at least not without an actual computer there to compute the translation function, at which point we’d regard the mind as being mostly located in the translating computer, rather than in the waterfall.) My first idea for how to make the distinction would be something like the Kolmogorov complexity of the mapping. Decrypting the FHE mind just takes the correct key, and a fairly simple cryptographic algorithm, while decrypting the waterfall mind requires the full Kolmogorov complexity of the person being simulated.
Edit: Not sure if this will show up, but hopefully someone sees it. I got the verification email, but I get “your email could not be verified” when clicking the link. Possibly there is some kind of technical issue?
Comment #115 July 30th, 2022 at 4:48 am
Alex #110:
“Lenny, which I’m sure is a charming person, but, as a physicist, he’s not only the master handwaver, he’s a handless handwaver!”
As the one who brought this thing up, i want to stress that my intention was to praise it, not to see it as something derogatory. To me it just meant that prof Susskind is always more focused on getting the main point across rather than discussing details or writing down absolutely correct calculations.
And i disagree on what you said about his place in physics history. I reckon that there isn’t a uber famous theorem by his name, but i noticed that his name pops up in every relevant advancement of the last 50 years. be it first string theory, lattice calculations, information theory, firewalls.. c’mon.
ps. and also: “it is what it is”
pps. i am totally OT, feel free to leave my comment in moderation (not that you need any permission 🙂 )
Comment #116 July 30th, 2022 at 6:30 am
Great post and discussion. The real question here is: what constitutes “subjective experience”?
The answer could equally well be: quantum superposition (for some quantum being, like the Alice who uploaded her brain into a quantum state), or its measurement (for “collapsed” entities like the “real” Alice). Now, the problem arises when the “collapsed” Alice tries to simulate a “real experience” using the quantum Alice – here it is not even clear what step 2 and 3 in the proposed scenario mean:The QC performs entangling operations on |φ⟩ and |ψ⟩, which correspond to inserting Alice into the bulk of the universe described by |ψ⟩, and then having her fall into the black hole. Now in simulated form, “Alice” (or so we assume, depending on our philosophical position) has the subjective experience of falling into the black hole and observing what’s inside.
Note that the problem is not in the AdS/CFT transform but the fact that “mere” quantum entanglement can yield a “subjective experience” – yes, even for the simulated Alice!
So either we accept some kind of “complimentarity” between the quantum and “real” experiences, OR, we need to revise our understanding of quantum superposition to include a kind of dual-experience, for e.g. “measurement of a (supra)quantum state leaves the quantum superposition unaffected” while also yielding the “collapsed” configuration. We might now be talking of being in two realms at once!
Comment #117 July 30th, 2022 at 7:35 am
Scott #87:
Can you necessarily get more than one copy of simulated-Alice’s initial quantum state |φ⟩?
If we assume that you need quantum-level fidelity of Alice’s brain in order to simulate her, then you could (in principle) presumably quantum teleport the qubit states that make up her physical brain into the qubits in her quantum computer in order to create the state |φ⟩. But it seems to me that the no-cloning theorem would prevent you from making multiple copies of |φ⟩. (IIRC, you discuss this issue in your essay “The Ghost in the Quantum Turing Machine”.)
Yes, one copy of |φ⟩ is all you need in order to run the simulation in which simulated-Alice sees the answer to the difficult computational problem in polynomial time. But can you get that information out of the simulation back into the real world at all – even in exponential time – since you only have one copy, which will of course be altered by measurements? The final state of the qubits in the quantum computer will certainly be highly entangled. It seems to me that the QECT thesis would be “even less challenged” if in fact you can’t extract the solution out of the simulation at all (even in exponential time).
If it turns out that you don’t need quantum-level fidelity in your scan of Alice’s brain, then of course there’s no problem – because in that case you can efficiently create poly(n) copies of |φ⟩ from your classical length-n description of the n atoms in her brain (and you might not even need to kill her!). But that shifts the question to whether you can in fact simulate a human consciousness using only coarse non-Heisenberg-limited data about her brain.
Comment #118 July 30th, 2022 at 8:00 am
Matt Leifer #8 , Scott #9 , and Leonard Susskind’s #101
Attempt to follow up Matt’s train of thought to the logical conclusion
seems to take us back to Leonard Susskind’s main point:
Assuming it’s possible to start an expanding homomorphic encryption process that forcibly drags the rest of the universe along with it, we can solve all these problems simply by jumping in and taking everybody with us.
Assuming the above is correct, do we lose something, and how much? Are we jumping into a smaller and limited universe after biting from the forbidden apple? Have we already done so?
If I’m allowed to guess: It’s possible in theory, but the machinery is so heavy that it looks like a black hole. And that brings us back to Leonard Susskind’s comment #101
“It seems that black holes are related in a surprising way to homomorphic encryption. That seems very interesting to say the least.”
“There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable. There is another theory which states that this has already happened.” ― Douglas Adams, The Restaurant at the End of the Universe
Comment #119 July 30th, 2022 at 8:05 am
Alex #110: Sorry, but even setting aside the prospects of the rest of string theory, the idea that you can construct spacetime out of entanglement in a holographic dual description seems to me like a permanent contribution to physics at this point. Once you understand it, you can’t un-understand it!
Comment #120 July 30th, 2022 at 8:28 am
I don’t even understand the premise. Why would one expect Alice to be able to see the answer to some extra difficult computational problem just because she falls into a black hole?
I also wonder how many qubits or how large a table of amplitudes is needed to represent the state of the universe… It seems impossible to me.
If the main thing is actually about viewing AdS/CFT as some type of encryption scheme as some parts of the text seem to imply (or am I misunderstanding?), I can maybe start to make sense of it, but this unphysical scenario of Alice converting her brain to a quantum computer and then jumping into a black hole just confuses me…
Comment #121 July 30th, 2022 at 10:02 am
“But what if Alice had jumped into an actual black hole to check what was inside? Would you agree that then she’d experience the answer (whatever it was), even though she could never communicate it to anyone outside?”
I am frankly not sure and I don’t feel capable of coming to a conclusion + thinking through the implications of both cases -whether she experiences and answer or not. I know the “classical” MH spacetime hypercomputation examples but my mind doesn’t feel like starting the General Relativity + DiffGeo knowledge base currently for some reason so I rather not give an answer.
Comment #122 July 30th, 2022 at 2:24 pm
#115 manorba,
Lattice calculations is pretty much the only thing I would concede here. As for the rest? Well, a) it’s so speculative and handwavy that it cannot even count as physics, b) even if it were, it has zero experimental evidence backing it, c) sometimes the assumptions radically depart from standard verified physics (there’s a whole talk by Bill Unruh, at Princeton I think, telling Susskind, who was in front row, how many of his usual working assumptions have simple counterexamples or more plausible alternatives, and that they usually involve violations of GR and QM in low curvature regimes, where they have been tested to be correct, see the Wald talk I link in the final paragraph; https://youtu.be/Ka1fme974ng; https://youtu.be/3iXOiy-fV9A).
To me, the systematic combination of a), b), and c) in his work is always an instant red flag.
A lot of Susskind’s work comes from the dreaded supposed loss of unitarity in black hole evaporation. But, as shown by many actual qf theorists in curved spacetime, like Wald or Unruh, in that scenario you have evolution from a Cauchy hypersurface to a non-Cauchy one. So, a mixed state at the end is no surprise. Unitarity is only valid from Cauchy to Cauchy, like in the standard Minkowski inertial frames of particle physics. But QFT in curved spacetimes is a different thing, and you cannot just pretend things from Minkowski spacetime to be valid there just like that (https://youtu.be/0Yiks-H7wI0).
Comment #123 July 30th, 2022 at 2:26 pm
#115 manorba,
Lattice calculations is pretty much the only thing I would concede here. As for the rest? Well, a) it’s so speculative and handwavy that it cannot even count as physics, b) even if it were, it has zero experimental evidence backing it, c) sometimes the assumptions radically depart from standard verified physics (there’s a whole talk by Bill Unruh, at Princeton I think, telling Susskind, who was in front row, how many of his usual working assumptions have simple counterexamples or more plausible alternatives, and that they usually involve violations of GR and QM in low curvature regimes, where they have been tested to be correct, see the Wald talk I link in the final paragraph; https://youtu.be/Ka1fme974ng; https://youtu.be/3iXOiy-fV9A).
To me, the systematic combination of a), b), and c) in his work is always an instant red flag.
A lot of Susskind’s work comes from the dreaded supposed loss of unitarity in black hole evaporation. But, as shown by many actual qf theorists in curved spacetime, like Wald or Unruh, in that scenario you have evolution from a Cauchy hypersurface to a non-Cauchy one. So, a mixed state at the end is no surprise. Unitarity is valid from Cauchy to Cauchy, like in the standard Minkowski inertial frames of particle physics. But QFT in curved spacetimes is a different thing, and you cannot just pretend things from Minkowski spacetime to be valid there just like that (https://youtu.be/0Yiks-H7wI0).
Comment #124 July 30th, 2022 at 3:10 pm
phi #114: Yeah, that’s basically my intuition, I think you summarized it well.
Comment #125 July 30th, 2022 at 4:05 pm
Ingrid #120: The point is that, once there’s an event horizon, the AdS/CFT dictionary can become exponentially hard to apply. This is pretty close to a known fact — see eg the Bouland-Fefferman-Vazirani paper for details. So then the question becomes, what (if any) are the implications of that fact for actual observers who want to solve exponentially hard problems? You might have hoped that a bulk observer could apply the dictionary just by jumping into a black hole — but as I explained in the post, that seems not to be the case. That’s the reason for all the trippy talk of uploading oneself into a simulation running on a quantum computer: because right now, that’s the only way anyone can think of to exploit this exponential complexity at the core of AdS/CFT.
Comment #126 July 30th, 2022 at 7:14 pm
Scott #88:
I should have been more precise. What I meant was extracting from |ψ⟩ a part that only describes a small ball around the event horizon of the black hole, and make a physical instantiation in a similarly-sized region of space that part of the state |ψ⟩. That does not require creating a whole new universe.
As it happens, I already had an idea for how to perform this physical instantiation, which I omitted in the original comment to divide the writing effort into manageable pieces. This reuses ideas I was originally thinking about for how to use a black hole as an information storage medium:
Simulate the laws of physics on |ψ⟩ backwards in time. Insert around the black hole a causal screen which completely blocks all information-theoretical interaction between the interior and the exterior of the screen except through a single quantum channel, which with time going backwards goes from the interior to the exterior. Over time the black hole will decay by Hawking radiation into nothingness, with the quantum channel acting as a necessary heat sink. This takes a long time but is still polynomial in the mass of the black hole. Extract all the information going out of the quantum channel from the CFT simulation to a direct encoding of the qubit-string. Eventually the interior of the simulated causal screen will be a vacuum with a completely known state. Build a real causal screen identical to the simulated one. Since it is now going forwards in time the quantum channel goes from the exterior to the interior. Feed into the real channel the qubits that were extracted from the simulated channel. The behavior of the real interior of the causal screen will be identical to the interior of the simulated screen reversed in time, eventually ending up with a black hole with an identical state to one that would exist in a universe with boundary state |ψ⟩.
(In my original idea for black holes as a storage medium I imagined performing time reversal using CPT symmetry rather than running simulations.)
The big remaining question is whether a causal screen of the kind I described is physically possible.
Comment #127 July 31st, 2022 at 2:59 am
Scott #123: Thanks for the clarification!
Comment #128 July 31st, 2022 at 3:29 am
I’m trying to understand this post and I’m finding it quite tricky.
As I understand it it starts with a premise using ads/CFT as if it is a valid description of the world as it actually is. However, the reading I’ve done describes ads/CFT as being a conjecture that does not describe the way the universe is. For example the actual universe has a positive cosmological constant due to the fact that the universe is expanding. But ads/CFT says that the universe does not have a positive cosmological constant. And there are other differences between what ads/CFT says about the universe and how the universe actually is.
I’m trying to follow the logic here. I was taught that even if the chain of logic from a premise to conclusion is sound, if the premise is false then the conclusion is false.
So I see two options here and it would be wonderful if someone could explain which option may be correct or if neither is correct.
Option A: the ads/CFT description is actually how the universe is, contrary to what other people have written, and therefore the conclusion is sound.
Option B: even though the ads/CFT description is not a description of how the universe actually is, that does not matter because if we assume it’s correct then we are able to do a chain of reasoning and logic which leads to an interesting conclusion involving complexity theory and other intellectually challenging topics.
Would be grateful if anyone can provide an insightful understanding of what’s going on.
Comment #129 July 31st, 2022 at 7:47 am
I’ve seen no mention of subjective time here. Doesn’t time move differently for an infalling vs far away observer? Is it possible that the CFT simulation sees the black hole evaporate before the infalling observer gets her answer to a hard problem? Meaning from an outside perspective she hits a firewall and never gets an answer.
I don’t know the physics well enough, but my layman’s understanding of black holes has been that the inside exists at a time past future infinity. I got that idea from some discussion on the firewall paradox.
How does time move in the CFT part vs for various observers in AdS space?
Comment #130 July 31st, 2022 at 7:47 am
boconnor #126:
Option A – is wrong. Our Universe has a positive cosmological constant. However, it’s not due to the fact that the Universe is expanding.
Option B – is a valid option for this type of reasoning.
Comment #131 July 31st, 2022 at 9:28 am
Scott #96:
Thanks for your blog post explaining this. I think different from ECC, in this case it might be interesting to cryptographers. This is because the only QFHE (or even post quantum ones) constructions assume either quantum hardness of LWE (which for all we know might not be true) or post-quantum obfuscation (which we do not know how to do yet). (It is interesting for cryptography to found things on different concrete assumptions, most ideally more than one.) Therefore maybe there is something here if this “FHE” scheme could be made more concrete.
With that said, it is not clear to me if this is really a homomorphic encryption as opposed to a standard encryption. I am confused about what are the encryption/decryption keys, and how you could efficiently decrypt the homomorphic ciphertext given the decryption key in this case. It seems that maybe for the dual of wormholes, the encryption and the ciphertext has become one large quantum state on the one end, and the decryption key might just be the remaining state in the other universe as you described? However, this does not seem to be very useful as even if you are given the decryption key, you still might not be able to describe the observer Alice’s experience inside the wormhole (you can uncompute the evolution to recover her brain I suppose). Alternatively maybe the decryption key is the classical description of shocks applied to the black hole, but then again it seems you can only recover what was encrypted at the beginning, instead of decrypting the homomorphic evaluated plain text.
Therefore, it seems that the following view is more reasonable to me. The black hole (with random shocks) in CFT is a pseudorandom unitary applied on its contents. If the AdS/CFT map is exponentially complex, then it could just decrypt all the contents and then make them (including the observer) have a meaningful experience. Does this make sense? (I have very little understanding of these topics so apologies in advance if I misunderstood anything.)
Comment #132 July 31st, 2022 at 10:04 am
boconnor #126: Obviously, we do not live in an AdS universe. AdS/CFT has nevertheless been a crucial laboratory for learning about quantum gravity, because if you translate questions to the boundary then you actually have some idea what you’re talking about.
As an example, if it were true that in AdS/CFT, a bulk observer could solve beyond-BQP problems by jumping into a black hole, then I wouldn’t expect that “local” conclusion to change just because you changed the cosmology from AdS to dS: why should it? What does the black hole care about the geometry of the entire universe?
Unfortunately, it seems not to be true, meaning we’re mostly learning about the complexity of mapping between bulk and boundary descriptions. But that’s still pretty damn interesting!
Comment #133 July 31st, 2022 at 10:07 am
Luowen #129:
With that said, it is not clear to me if this is really a homomorphic encryption as opposed to a standard encryption.
I think the truth is closer to the converse of what you said! It’s homomorphic, since you can do arbitrary computations on encrypted data (the CFT states representing infalling observers). But it’s not a full encryption scheme, because as I said earlier in this thread, there’s no decryption key! Or rather: decryption of behind-the-horizon states always seems to take exponential time.
Comment #134 July 31st, 2022 at 10:56 am
Hi, I think the solution is to feed forward one more time, through another “black hole gate”. I have attempted to describe the whole system in what folllows.
Here in the True World, our actual quantum system simulates “a real world” which includes a selfsame quantum system, an embedded simulation of the quantum system itself. There is one more quantum system embedded within that one.
Inside the first simulation, the embedded quantum-system simulates the black hole gate. Inside that new simulation, another quantum system simulates the initial “real world sim”.
Inside the first “real world” simulation, Alice takes the encrypted text into the black hole sim using the embedded quantum system. Therein Alice knows the contents but cannot communicate them from noise. So Alice re-encrypts the clear text, and does a second gate hop into the third sim.
Now inside the third sim, Alice again has access to the contents of the (re)encrypted data. However this simulation is of the “real world sim”, so the data is no longer indecipherable from black hole noise, it is compatible with the real world it simulates.
Copy the 3rd gen cubits up to the first level sim, console log.
Comment #135 July 31st, 2022 at 1:54 pm
Scott, could I please verify that my understanding expressed in comment #117 is correct?
To summarize: you’re correct that real-Alice can’t retrieve in polynomial time the information that simulated-Alice receives – but (contrary to what you imply in the main post) real-Alice may or may not be able to retrieve that information in exponential time, either.
If it’s possible to scan her brain at a low enough level of fidelity to avoid the no-cloning theorem (as you discuss in comment #87) and still simulate Alice in n qubits, then you can efficiently create poly(n) copies of |φ⟩. Also assuming that you are given |ψ⟩ in the form of either a low-depth quantum circuit or (as in the Bouland-Fefferman-Vazirani setup) poly(n) physical copies of |ψ⟩, then you can run poly(n) shots of the simulation, which *may* give you enough information to retrieve simulated-Alice’s knowledge of the black hole interior in exponential time.
But if instead, any sufficiently high-fidelity simulation of Alice requires quantum teleportation or some other kind of “destructive” scanning process, then you can only get one physical copy of |φ⟩, and so you can only run one single shot of the simulation. In this case, you probably can’t extract the results out of the simulation at all in any amount of time, due to Holevo-type bounds.
Am I getting this right?
Comment #136 July 31st, 2022 at 3:34 pm
Ted #133: In some sense, the computational problem (in the setting with quantum input) is clearly defined only under the assumption that Alice is given enough copies of |ψ⟩ that, given exponential time, it would be possible in principle for her to extract the answer in the real world. So that’s the only setting I consider.
Whether simulated-Alice could still see the answer (albeit not tell anyone else about it), even when the problem is not well-defined by TCS standards (eg because she only gets one copy of the state), is an extremely interesting question about which I won’t venture an opinion here. What does anyone else think?
Comment #137 July 31st, 2022 at 5:03 pm
Scott #134: I profusely apologize for beating a dead horse, but I’m not talking about limiting the number of copies of |ψ⟩ that Alice has access to. I’m granting that that Alice has copies of as many copies of |ψ⟩ (the input to the original mathematical problem) as she needs.
My point is that no matter how many copies of |ψ⟩ that she’s given, it’s plausible that she can only ever create one single physical copy of |φ⟩, the quantum state that represents simulated-Alice. (In essence, I’m assuming that Alice is allowed access to as many copies of the original problem input state |ψ⟩ as she needs, but she only gets access to one copy of her own physical body! Because that isn’t part of the original problem input.)
I grant that one copy of |φ⟩ is all you need to run the simulation, so that’s enough for simulated-Alice to formally “solve” the problem in polynomial time. But I’m disagreeing that real-Alice can use the first three-step algorithm that you lay out in your main post to solve the problem at all – even in exponential time.
Stepping back: I don’t think we’re disagreeing about anything particularly important. I’m just nitpicking one very specific claim that you make in your post: that “Alas, the expectation is that this [process of backing the simulated solution back out into the real world] would require exponential time.” I claim that this process probably isn’t actually possible at all, because Alice could only possibly create a single copy of |φ⟩ (not of |ψ⟩!), so she could only run the simulation and then measure its outcome once.
Assuming I’m correct, this doesn’t say anything about the computational complexity of the original problem. But there might (arguably) be some philosophical consequences if the “simulate yourself physically seeing the answer” algorithm can’t actually solve the problem “back in the real world” in any amount of time.
Comment #138 July 31st, 2022 at 5:20 pm
Scott #131: I think that is exactly against the spirit of homomorphic encryptions. If there are no efficiency guarantees, then any ordinary encryption scheme can be homomorphic: you just encrypt the operations you want to do and append them at the end, and ask the decryption algorithm (efficient or not) to actually carry out the operations. I guess I am trying to see what is fundamentally different between this trivial “homomorphic” encryption scheme and an observer jumping into a black hole. (For example, think of CFT being implemented by the following ordinary encryption scheme: you encrypt the initial state followed by encryption of Alice’s brain, and then you throw out the decryption key. Only when you decrypt, you actually simulate Alice’s experience jumping into the black hole and measuring the length of the wormhole etc. This seems to work without the construction ever explicitly using any “real” homomorphic encryption?)
Comment #139 July 31st, 2022 at 8:32 pm
Ted #135: I get it now—thanks a lot for taking the time to clarify!
It’s true that a naïve approach could require making polynomially many copies of Alice’s body, which (if no-cloning is relevant) won’t be possible even given exponential time. On the other hand, once you have exponential time, lots of approaches become feasible—e.g., you could iterate over all exp(poly(n)) possibilities for what |ψ⟩ could be, and for each one, apply a “gentle measurement” to |ψ⟩⊗p(n) to test whether it’s that one—just like in the Ettinger-Hoyer-Knill algorithm for the nonabelian hidden subgroup problem.
Comment #140 July 31st, 2022 at 8:36 pm
Luowen #136: You raise a good point—if we take away efficient decryption, then how do we even define fully homomorphic encryption in such a way that it isn’t achievable trivially? But it seems to me like there ought to be some device to do that. For example, what if we simply said that the size of the ciphertexts can depend only on the security parameter, and not on the length of the circuit? That requirement ought to satisfied by AdS/CFT but not by your reductio ad absurdum, no?
Comment #141 August 1st, 2022 at 1:40 am
There is one thing that still puzzles me in this thought experiment (I haven’t read through all the comments, so I apologize if someone already brought this up): Suppose that Alice jumps into the simulation and all she does there is just to read the latest post on Shtetl Optimized, then there should be no obvious problem to bring her back to the real world without her mind losing any information that it possessed while inside the simulation. But if Alice learned the solution to a beyond-BQP problem inside the simulation, this solution will necessarily get deleted from her mind on the way back. But while the computational problem itself is difficult, its solution is just a string of symbols, it’s not qualitatively different than the string of symbols that constitutes the above Shtetl Optimized post.
How does nature know to discern between two strings of symbols and to select the one that represents a forbidden answer to a beyond-BQP question? It seems like in order to maintain the belief that nature does not allow for beyond-BQP computations, we allow it to behave in a way that is no less weird.
The above considerations suggest the possibility that perhaps it’s theoretically impossible for Alice to get out of the simulation regardless of what she learned there.
Comment #142 August 1st, 2022 at 5:06 am
Set theorist #139: In practice (which I admit is a funny phrase to use in this context), the only way I know to “get Alice out of the simulation,” is to run the simulation in reverse, in order to disentangle her with |ψ⟩. So, that’s why she forgets whatever she learned: simply because time runs backward for her! Of course, once she’s disentangled from |ψ⟩, she could then go back to the real world, read the latest Shtetl-Optimized post, etc., but presumably solving a beyond-BQP problem would require going back into a simulation and re-entangling herself.
Comment #143 August 1st, 2022 at 8:52 am
Scott #137: Yes, I completely agree that the original problem of applying the AdS/CFT dictonary to |ψ⟩ to study the black hole interior is solvable in exponential time. I was just nitpicking your comment that “this would take exponential time” because – at least as I read your post, although it may not have been your intention – the word “this” was referring not to the original problem, but to the derived problem of decoding simulated-Alice’s experiences. As you point out, it isn’t clear how to put this problem into the traditional framework of computational complexity theory at all, because you can only obtain one single copy of |φ⟩. Like I said – a very minor nitpick. 🙂
One final thought, and then I promise I really will shut up. I’m still not completely convinced that the first three-step procedure that you outline in your post really would allow even simulated-Alice to see the answer to the original problem of “decrypting” |ψ⟩. As I said in comments #30, #67, and #82, it seems plausible to me that the back-reaction from simulated-Alice’s presence would necessary qualitatively change what’s going on inside the black hole, and so change the answer to the problem. So simulated-Alice would see the solution to the distinct problem (with a potentially totally different solution) of “which black hole interior is dual (under the AdS/CFT dictionary) to the boundary state |ψ⟩ \otimes |φ⟩”, whereas in the original problem it was just |ψ⟩ alone. Yes, simulated-Alice will certainly see something – but as you point out, it’s tricky to fit this modified problem into the framework of computational complexity theory, because you can only get one copy of |φ⟩.
So I think that your statement that “We’ve now caused [simulated-]“Alice” … to have observed the answer to the beyond-BQP computational problem” is not quite right. I would rephase it as “We’ve now caused [simulated-]“Alice” … to have observed the answer to a question that is certain ‘hard’ in some sense, but which doesn’t quite fit into the standard TCS formulation of a ‘problem’.”
I think the big takeaway is that we need to carefully distinguish between (a) the original problem of applying the AdS/CFT dictionary to |ψ⟩ to study the black hole interior, and (b) the derived “task” of applying the AdS/CFT to |ψ⟩ \otimes |φ⟩. The latter task is a qualitatively different enchilada – both because (a) it doesn’t necessarily fit into the standard TCS framework because you only get one copy of |φ⟩, and (b) even if you could somehow get multiple copies of |φ⟩, the mere presence of simulated-Alice might qualitatively change the answer to the original problem!
Comment #144 August 1st, 2022 at 3:08 pm
So Scott I know this isn’t related to the topic of this post, but I wanted to tell you a devastating truth I just learned about the COVID vaccines…
Just kidding! 🤣
Actually, I have a question about your characterization of the AdS/CFT correspondence:
>> The staggering claim of AdS/CFT is that every physical question about the AdS bulk can be translated into an equivalent question about the CFT boundary, and vice versa, with a one-to-one mapping from states to states and observables to observables. So in that sense, they’re actually the same theory, just viewed in two radically different ways.
So I’m not a physicist, so forgive me if I sound misinformed, but this way of describing the duality has always confused me. The attempts I’ve seen at a precise statement of this correspondence (e.g., https://ncatlab.org/nlab/show/AdS-CFT#Idea) don’t give an isomorphism of theories, i.e. a structure-preserving correspondence of states with states, observables with observables. Instead, the duality pairs *states* on the gravity side with *n-point correlation functions* on the CFT side. So it’s unclear to me what it would mean so say that such-and-such state of AdS gravity (e.g., a black hole) is mapped to such-and-such state of the boundary CFT, because there is in fact no such map.
Comment #145 August 1st, 2022 at 4:38 pm
Topologist Guy #142: The way it was explained to me, there is an isomorphism of states to states, not just n-point correlation functions (even though the physicists often just talk about the latter in practice). But let me see if I can get an actual physicist to answer in more detail…
Comment #146 August 1st, 2022 at 5:34 pm
*actual physicist has entered the chat*
I should say that because I think about AdS/CFT basically in terms of intuition (and if you want a sense of what *my particular intuition about AdS/CFT is*, which is not necessarily identical with the rest of the field’s, try looking at Sec. 2 of https://arxiv.org/abs/2110.14691 which I wrote with others in Scott’s group last year), so I may not be able to be precise enough for you. But, two reasons that I think one *should* think of AdS/CFT as a state-state correspondence.
First off, CFTs obey the state-operator correspondence (see https://ncatlab.org/nlab/show/state-field+correspondence if you want an ncat reference, though that’s not necessarily the clearest explanation), which means you can create all states in the theory by acting with operators at some point. This is related, I think, to the fact that the operator product expansion for CFTs *actually converges* in a certain sense that it doesn’t in ordinary QFTs. So, we can really go back and forth between correlation functions and states on the CFT side.
(I should admit that I don’t have a good sense of how much the previous paragraph holds nonperturbatively, but it’s certainly true perturbatively around the vacuum state, which is all we really need to talk about e.g. the RT formula.)
Second, the whole point of the original Maldacena conjecture was that it was supposed to be an equality between *partition functions* of the theory. You can get correlation functions by inserting sources and differentiating w/r/t them in the usual QFT way, but you don’t *have* to do that, you can just work on the partition function level.
Hope that helps!
Comment #147 August 1st, 2022 at 7:24 pm
Scott —
Welcome back to “real” blogging!! 😀
I believe i understand the OP in my educated layperson way, but i don’t see what it has to do with hard-problem-style consciousness. Perhaps you have dropped the issue: i did not see you respond to ppnl #77 nor that element of Clint #84, and perhaps the question was given a good enough answer by Leonard Susskind #101. But i’d like to clarify a bit more.
First, to be sure i understand enough to be commenting, and as a basis for discussing consciousness, i would boil down the point of the post this way: There are thought experiments in which a beyond-BQP problem has been solved inside a simulation but the solution can’t be beyond-BQP-efficiently communicated out of the simulation, and that inside-vs-outside-the-simulation conflict makes it tricky to say whether the QECTT has been violated. The forming consensus is that the communication bottleneck means that the QECTT holds. (And maybe what really matters are the insights we had along the way. 🙂)
Stated in this general way the beyond-BQP problem could be “solved inside a simulation” by an entity with various kinds of consciousness if any. Tho you addressed it up thru #51, the key seems to me to be your resp to ppnl at #24: “If you sent in a simulated Mars rover, why would there even be any temptation to say that the QECTT was violated? You could then say: obviously, all that matters is what we (the external observers) see when we measure, and all of that can be simulated in BQP.” I interpret this to mean that for you the solution-“seeing” entity in the simulation has to be hard-problem-style conscious to engage your intuitions and take Alice’s pov seriously enough to create the inside-vs-outside-the-simulation conflict, to be willing to say that there really is a solution that has been found inside the simulation — and apparently you experience that requirement as obvious. I understand and sympathize with that…but it also seems subjective on your part.
What if my intuitions and (not speaking for anyone else, tell me if i’m wrong) 1Zer0’s and Clint’s intuitions are such that Alice being a p-zombie suffices to generate the conflict for us? What if JimV’s (less clear to me) and ppnl’s and my intuitions are such that non-person entities are enough? Would you say that we are simply wrong? Would you say that our views of the thought experiments are not compatible with Susskind’s? And why would you say that?
Since we agree about what problems of what complexity can be solved by / communicated to those running the simulation, might it not be a matter of philosophical taste how we each speak about a beyond-BQP solution existing inaccessibly inside a simulation under different scenarios?
Thank you so much as always, and best wishes! 🙂
— PS for fun: re “how slow Scott and his friends must be, compared to string theorists”, i have to recall the well known quip of Polya: “I am too good for philosophy and not good enough for physics. Mathematics is in between.” 😉
Comment #148 August 1st, 2022 at 9:33 pm
alyosha #144:
i would boil down the point of the post this way: There are thought experiments in which a beyond-BQP problem has been solved inside a simulation but the solution can’t be beyond-BQP-efficiently communicated out of the simulation, and that inside-vs-outside-the-simulation conflict makes it tricky to say whether the QECTT has been violated. The forming consensus is that the communication bottleneck means that the QECTT holds. (And maybe what really matters are the insights we had along the way. 🙂)
I couldn’t have boiled it down any better 🙂
What if my intuitions and (not speaking for anyone else, tell me if i’m wrong) 1Zer0’s and Clint’s intuitions are such that Alice being a p-zombie suffices to generate the conflict for us? What if JimV’s (less clear to me) and ppnl’s and my intuitions are such that non-person entities are enough? Would you say that we are simply wrong? Would you say that our views of the thought experiments are not compatible with Susskind’s? And why would you say that?
The fact that so many people would object so strongly to the mentions of consciousness is an interesting thing that I learned only from this discussion, although with hindsight maybe it should’ve been obvious.
To my mind, the crucial point is this: you can’t just declare willy-nilly that a physical system succeeds in solving a hard problem, if you can identify any complex agent anywhere in your mathematical description of the system that “sees” the solution. Why not? Because then all sorts of hard problems would become trivially solvable! For example, here’s how you could solve NP-complete problems in polynomial time: create an equal superposition over all possible solutions, then create an “agent” to “see” the solution only in those branches where a solution happened to be guessed. You could even declare PSPACE-complete problems or the halting problem to be “solved,” albeit with the solutions “seen” only by observers who are defined via crazy changes of basis (with those basis changes themselves encoding the solutions to the hard problems in question).
But this is too cheap. Reflecting on these and other examples, it becomes apparent that it’s not enough for some agent to see the solution to the hard problem: instead, you (the user of the computer, the one who chose the input) have to see the solution. Aha, but what even counts as an instantiation of “you”?
This is not only a hard problem, it strikes me as bound up with the Hard Problem of consciousness! Of course, classical computing and even quantum computing don’t force us to grapple with this enormity. A priori, though, you could imagine a model of computation that would force you to grapple with it. Or if you can’t imagine it, then Lenny’s scenario, and Gottesman’s homomorphic encryption variant, will drag your imagination along kicking and screaming … which is why I shared them with you here. 🙂
Comment #149 August 1st, 2022 at 11:35 pm
Scott #139: Right. I did miss the fact that the CFT state should evolve over time, and it is not clear how to prevent the state length from growing with a trivial encryption. However, since we are just applying a fixed explicit (?) evolution operator, this could also be done with for example an additive (or not fully) homomorphic encryption (examples include ElGamal, RSA, Regev, …): you still encrypt the initial state and Alice’s brain, but in addition a “time” counter initialized to 0; then the evolution simply homomorphically adds 1 to the counter. This seems even weaker than additive homomorphic encryption since the only operation to be supported is the unary increment operation.
(I am also not sure where I am going with these thoughts… Maybe to cook up “useful” cryptography assuming computational hardness of computing the wormhole length outside the event horizon?)
Comment #150 August 2nd, 2022 at 2:41 am
Scott #147 —
Thank you so much for your response! Perhaps you won’t mind a volley back to you, as i’m afraid i still don’t see why we need to bring the hard problem of consciousness into this. (FWIW, years ago i studied philosophy up to the level of some graduate school with a special interest in consciousness and i kept reading after i left academe, but my level in TCS and physics is much lower, so i’ll keep it general like i did last time.)
It’s perhaps less important (and maybe over my horizon of competence), but my reaction to your paragraph starting with “To my mind,” is that it doesn’t feel analogous to the thought experiments at issue. In the latter, standard-issue humans create a simulation that encodes a well-defined question and they receive a single well-defined answer in output — no superpositional, post-facto selection of agent-observers funny stuff.😉
It seems to me that your next paragraph speaks more to the bottom line with “it becomes apparent that it’s not enough for /some/ agent to see the solution to the hard problem: instead, /you/ (the user of the computer, the one who chose the input) have to see the solution.” This to me is a perfectly reasonable view, which extended to/from other situations is well-attested in philosophy and science. But i take it as too general to require or indeed to say anything about the hard problem of consciousness. Exactly as you have stated it, it applies alike whether the simulated solution-finder is hard-problem-style conscious, or a p-zombie, or even a non-conscious-seeming robot or computer, etc. And similarly in response to “Aha, but what even counts as an instantiation of “you”?”: your policy applies regardless of the consciousness status of those running the simulation! All that matters is that a question-asker gets the answer in a way which could be said to violate the QECTT at some inaccessible intermediate stage but does not violate it at the stage of answer output — and it also matters what this reveals about the relevant physics. It’s a TCS/physics issue, and i still don’t see how the hard problem of consciousness comes into it (except in the subjective way i outlined last time).
I’m also still wondering if you think anything i’m saying contradicts Susskind’s (et al’s) understanding; didn’t he politely dismiss consciousness? Or how about another way of putting it: How in your view does the science being explored in these thought experiments, as summarized by Larry Susskind #101, have anything to do with the hard problem of consciousness? Aren’t those matters just as well illuminated by a hard-problem-neutral understanding of the thought experiments?
My hemidemisemi-bayesian prior coming into this thread was that mainstream (non-woo, non-crackpot) TCS/physics is very unlikely to implicate the hard problem; and further that if someone thinks it does, that’s very likely due to their controversial philosophy of consciousness and not due straightforwardly to the TCS/physics. If i may be so bold, that prior has thus far not been significantly updated…😀
All the best to you and yours!
Comment #151 August 2nd, 2022 at 7:43 am
I agree with alyosha #149, there’s no need to bring consciousness (and simulation of consciousness) into this. “Alice” could just be a camera or a calculator… or, more precisely, whatever is needed in order to measure and/or compute the answers of interest.
Comment #152 August 2nd, 2022 at 8:13 am
alyosha #149 and Mitchell Porter #150 (and everyone else):
Look, I don’t actually care whether we use the word “consciousness” to talk about this. At the end of the day, though, whether you judge that this sort of procedure would or wouldn’t let you solve a beyond-BQP problem, seems to depend entirely on whether you judge that the homomorphically encrypted entity at the end of the procedure would or wouldn’t “still be you.” So, if not by asking about that entity’s “consciousness,” what words would you like me to use?
Comment #153 August 2nd, 2022 at 10:56 am
Scott #151:
Sorry for this poor dead horse we are beating 🙂
Turing Machine
Because, what are the requirements?
0. Be programmable … sufficient to carry out this algorithm …
1. Accepts input \(\vert\phi\rangle\) representing a universe with a black hole into its memory (I agree with you this is a very interesting step …)
2. Is “uploadable” (meaning it still has all of its TM properties: the memory, the programming, etc.) as \(\vert\psi\rangle\) to a QC (Maybe easiest to imagine this is a virtual TM being uploaded …)
3. Is then “entangleable” by the QC (meaning after entanglement still has all of its TM properties) so that \(\vert\psi\rangle\) is inside \(\vert\phi\rangle\) and just outside the EH of the black hole.
4. Capable of still being the “same” TM (in a “virtual” functional sense) when recording whatever it is programmed to observe after passing beyond the EH.
These Turing Machine requirements do mean that the observer needs to be much more than just any physical system or device at all … for example, I don’t think a simple “camera” works. The TM sent on this mission needs to be sufficiently programmable, have sufficient memory to know what it is looking for, capable of recording what it is sent to observe – the usual scouting requirements.
Of course, the Turing machine can be a human being. But the Turing machine doesn’t have to be a human being. As physical Turing machines, humans don’t have a “special observer / self-reference class”. (Well, I say “of course” … but not sure an actual human being can get through #1 and #2 above.)
The original point was just that … it seemed like clearing the decks of the philosophical/mystical baggage that “consciousness” introduces would allow for focus more on the complexity/physics questions like:
1. Does the model of the TM memory (input) matter? Both for the original encoding but also for the later “copy and entangle” operation?
2. Does this say something about some kind of “additional” power that TMs bring – probably due to their memory and programmability – beyond just the fact that any physical system can be an “observer” by the quantum postulates? Does the universe “punish” TMs that break the QECTT law by casting them into a black hole …
3. Does the “copy” operation by the QC fail because (from its perspective) \(\vert\phi\rangle\), which is stored in the TMs memory, is an arbitrary unknown quantum state. The TM “knows” the state … but the QC copying the TM doesn’t … so … no-cloning?
Interesting questions all … and no “consciousness” required …
Thanks Scott and sorry if nit-picking words was driving you crazy! 🙂
Comment #154 August 2nd, 2022 at 11:15 am
Clint #152: Sorry to toss the dead horse back over the net to your side (to mix metaphors). 🙂
But if what you say is true, then as soon as we have fault-tolerant quantum computers and can simulate CFTs on them, it will be easy to do a calculation that (by your lights) would “solve” a beyond-BQP computational problem. Indeed, we could even do it right now, using Gottesman’s fully homomorphic encryption variant. And I’d say on that basis that the QECTT would clearly be falsified.
To put it differently, if we want the QECTT to be a true statement, then the criteria for who’s there at the end to observe the answer must be more stringent. We might say, for example, that the observer “has to be you,” or “has to exist in the ordinary world of our experience.” Except, what do those terms mean?
Comment #155 August 2nd, 2022 at 11:25 am
Luowen #148:
However, since we are just applying a fixed explicit (?) evolution operator, this could also be done with for example an additive (or not fully) homomorphic encryption (examples include ElGamal, RSA, Regev, …): you still encrypt the initial state and Alice’s brain, but in addition a “time” counter initialized to 0; then the evolution simply homomorphically adds 1 to the counter.
Aha! But what about the fact that the person running the simulation gets to send in “shockwaves” of their choice at any time? Won’t that create the possibility of doing a universal computation inside the simulation, thereby boosting what we’re talking about up to fully homomorphic encryption?
If so, then I thank you for a crucial insight here: namely, that it’s only the possibility of shockwaves that makes the “fully homomorphic encryption” interpretation of AdS/CFT nontrivial.
Comment #156 August 2nd, 2022 at 12:14 pm
Scott #153:
I’ll bite that dead horse bullet (to continue entangling metaphors)
I agree with every word in the above except I would insert “NOT” in the last sentence between “clearly” and “be”.
The QECTT is a computational statement like (dual to?) FHE. What they are telling us about the definition of “event horizons” … That it is possible to pass a TM into a black hole or FHE “from the outside” and it retains its “TM character up to that point in time and beyond the EH” … but not back the other way without “returning it to its state before it crossed the EH” and thus erasing any beyond EH observation.
Back to Susskind’s original prompt … is this telling us something about the nature of gravity that is “hidden” in BQP from the start … perhaps entanglement itself has “hidden within itself” the computational inevitability of EHs forming and their characteristics – including this restriction on TMs.
So, again, … yes, I bite that horse/bullet. I accept that both the CFT simulation and the FHE variant are (scare quote) “solving a beyond-BQP computational problem”. But that does not falsify QECTT. I would say something more like that this follows from the QECTT. The statement would be something like “BQP is computational. The QECTT holds (meaning the universe is running on BQP). We know that computational classes will have encryption like FHE. Therefore, we should expect there to be physical manifestations of FHE-like computations. A black hole EH appears to be such a manifestation.” No contradiction. Maybe only a “seeming paradox” as is possible in computation. Just a consequence of the universe running on a class of computation where FHE-like encryption is possible.
At least … I’d much rather bite the QECTT implies encryption exists horse than the one that implies humans are a class of TM with unique observer abilities.
*By the way, full disclaimer, I actually own real live horses that I care for very much and the above opinions in no way are meant to endorse actually biting or kicking horses – regardless of their alive/dead superposition state 😉
Comment #157 August 3rd, 2022 at 11:27 am
Scott #151:
To me the question of much greater interest, is whether the Type II algebras of observables, that emerge in circumstances where space-time has a nonzero entropy (i.e. black holes and de Sitter space), enable more powerful forms of computation. For something on this, see Witten’s recent papers, e.g. 2206.10870, 2112.12828. This is what my comment #17 was about.
There may be some interplay with these issues of “encrypting and decrypting an observer in the CFT”, whether a black hole is a kind of quantum one-way function, and so on. But philosophy-of-mind issues like identity and personhood only arise in the special case where the observer is supposed to be a sentient being.
Comment #158 August 3rd, 2022 at 1:03 pm
I have no knowledge of QM or relativity, so perhaps what I am saying is trivial or even wrong.
I am perfectly satisfied by Gottesman’s reductio. It seems to be that intuitively, “solving” a computational problem should be an entirely Cartesian process, it should requires no “change of identity.”
Intuition: In the ideal case an agent should be able to write a problem on a tape and put in a giant industrial smokestack with whirling gears and tubes full of green liquid (a process) which then takes some amount of time before extruding a tape back out with an answer on it. If Alice phenomenologically experiences “receiving a tape, performing a process, then ‘knowing’ the answer,” that isn’t satisfactory, because the process of retrieving the answer FROM Alice can’t be done in BQP. Alice is less like an agent performing a computation, and more like a black box oracle that some other agent is failing to retrieve information from.
This intuition is not remotely formal. The natural question becomes, “what criterion says that Alice is supposedly not an agent, and instead an oracle with unretrievable info?” I said earlier “change of identity,” but that isn’t philosophically sound. If I calculated 955+235 in my head, that would require/be equivalent to/be caused by/be mind-body dual to a large amount of physical change in me. But that is certainly a normal computation that “I,” as an “agent,” am “performing” in a sensible way. In what sense is this fundamentally different than Alice being thrown into a black hole?
Another avenue is that Alice’s trick can be done arbitrarily many times in parallel, but can never be done in serial. E.G. one can make many copies of Alice and then “know” many black holes, but one can’t retrieve an Alice from a black hole so that that Alice “knows” two black holes. This corresponds to another intuition of the black hole’s information being “information at infinity” or “information obtained at step omega” which can be approached (not necessarily approximated, only approached in the English sense) by normal computation, but can’t ever be used. (A perhaps better analogy: given infinite [discrete ordered steps of] time I can count to omega, but I can’t count to omega + 1.)
So we might try and say: “this situation doesn’t violate the conjecture because it’s not a repeatable algorithm.” But this definition also still applies to me calculating 955+235 because of Heraclitus. Once I calculate it once, I am no longer the same person, so I can’t calculate it twice!
There’s a sort of fundamental agent/environment dualism in my notion of computation, which Alice’s transformation and irretrievability (key thing) violates, but I can’t coherently formalize it because in real life, the self is an illusion.
We could perhaps say that all computers are capable of a “step at infinity,” after which they immediately explode, and we say for a problem to be in a complexity class it has to not use the explosion step. I come up with this possibility because of anthropics! If I rig a (classical) machine that generates a random factorization of a number, checks it, instantly murders me if it doesn’t factorize correctly, then shows me it, from my own perspective I can factorize numbers in P time. But from others’ perspective I usually just die, so this is analogous to Alice being irretrievable from the black hole.
Another thought: If, once Alice learns about the black hole, it were possible to easily factorize the Alice + Black Hole system, then you could read Alice’s quantum state and output an approximation of it which could be read to read Alice thought’s, which would be fast solution. So it follows that decomposing Alice and the Black Hole in any sensible way (not sure how the AdS-CfT math works but I don’t think it matters) would require exponential time. But then it follows that Alice and the Black hole are highly mixed, in the intuitive sense, i.e. Alice is super dead like she just got blown up with thermite. So the process of Alice “knowing” a fact about the black hole’s state scatters her possibility space very large, like a chunk of C4 would. If we assume that randomly scattered dust can’t be the type of possibility space that is considered to form a mind (and I consider this assumption reasonable), it follows that every ‘unrecoverable black hole step’ makes the computer explode. Interestingly if we assume Quantum Church Turing, and you could prove that all singularities create AdS-CfT correspondences that are difficult to calculate, not just censored singularites, you could prove the cosmic censorship hypothesis.
My thoughts on this are very informal and based on analogies but I hope this makes sense.
Comment #159 August 3rd, 2022 at 3:37 pm
Scott #152: “Still be you” is a problem of identity, not consciousness. They are separate because even if uploading created some consciousness entity, you can consider it to not be the same entity as the one you uploaded from – if uploading is non-destructive, you can call it a “copy”, for example. But identity doesn’t matter anyway because someone may altruistically or aesthetically want for someone else to have a solution. I guess then ethically-free way to talk about QECTT have to involve some distribution of the solution over physical world: the same way solutions for NP-complete problems lead to decreased measure, solutions though simulation lead to decreased size/mass/precision of external influence.
Comment #160 August 3rd, 2022 at 6:42 pm
I think there is a substantial difference between Gottesman’s reductio and the original black hole scenario. The issue is that the main reason I find it intuitively reasonable to be able to “enter a simulation” is that I can imagine replacing individual neurons, one by one, with mechanical devices that are controlled by code running on a computer, until finally the entire computational process that makes up “me” is running on the computer. In the quantum simulation of AdS/CFT, it seems like I could experience a continuous transition from living in reality, to living in a simulated spaceship within the simulated bulk, to jumping into a black hole.
However, how can I (classically) experience a continuous transition from being a plaintext simulated human to being a homomorphically encrypted simulated human? If I encrypt one of my neurons, I can’t communicate with it any longer.
Comment #161 August 3rd, 2022 at 7:16 pm
Zeb #160: If you’re worried about that, how about if you keep the decryption key while you’re replacing the neurons with their homomorphically encrypted versions, and only throw it away when you’re done?
Comment #162 August 3rd, 2022 at 7:49 pm
Scott #161: If my goal is to read the encrypted emails, and I have the decryption key, then I don’t need to jump into a simulation, I can read them directly in reality. The challenge of being able to subjectively experience solving a beyond-BQP (or just beyond-BPP) problem by a process that is continuous enough for my intuition to accept it still seems unsolved, classically.
A naive attempt to make this work would be to try to find a sequence of homomorphic encryption schemes such that each individual one is weak (i.e. only moderately difficult to decrypt without the key), but the composed sequence is strong. Then I could live my simulated life at half speed while my encrypted neurons one layer deeper go at full speed until I get all my neurons into the next layer, and so on until I reach the bottom. Unfortunately, this sort of strategy can’t possibly work – if I know the sequence of weak encryption schemes, and know how to decrypt each individually, then obviously I can decrypt the whole thing, so the composed sequence wasn’t really strong to begin with.
Comment #163 August 3rd, 2022 at 8:31 pm
Zeb #162: No, the idea is: first you homomorphically encrypt the brain neuron by neuron, keeping the decryption key. Then you throw away the decryption key. Then you do the homomorphic computations that simulate you looking at the data.
Note that, in the AdS/CFT case, we don’t even have to bother with the “throwing away the key” part. There are no keys, just the AdS/CFT dictionary itself. And the dictionary is supposed to be easy to invert so long as the simulated Alice is outside the black hole, becoming exponentially hard to invert only when the simulated Alice jumps in.
Comment #164 August 5th, 2022 at 12:24 am
I don’t really understand most of this, but would you expect that a universe where AdS/CFT is valid has the same computational complexity classes, and hardness categories that ours does?
As far as I know, our universe is not an anti de sitter space, and our black holes are not the same as the ones in string theory, (or in the AdS/CFT correspondence).
Comment #165 August 5th, 2022 at 9:59 am
KR #164: To say it one more time, what seems to involve a new complexity class (beyond BQP) is the map between the AdS bulk and the CFT boundary. Even supposing we lived in an AdS universe, it still wouldn’t be obvious how to access that map—that’s the reason for all the talk about Alice uploading herself to a simulation. For a de Sitter space, like ours, there’s both that question, and also the question of whether and how holography works for dS spaces at all.
Comment #166 August 7th, 2022 at 8:06 am
I should check this blog more regularly– I am always coming in a bit late to the most fascinating things.
I have a lot of thoughts on this, and I’m curious what others think.
1:
I don’t know if this particular gedankenexperiment I’ve just come up with has been discussed before but I think it’s interesting and somewhat relevant:
Alice wants to know the solution to an NP-complete problem. So, she creates a quantum system that, when she measures it, will collapse to a random possible solution to the problem. She then checks to see whether this is the correct solution. If the quantum system that she interacts with is constructed correctly, for example, such that its wavefunction has uniform amplitude over the space of all possible answers, then there will be nonzero amplitude assigned to the correct solution, and when Alice interacts with it, there will be nonzero amplitude that corresponds to Alice measuring the correct solution.
Of course for such a hard problem, say a 2^O(n) problem with non-small n, the probability of getting the right answer, AKA the probability assigned after the fact of Alice finding herself in the branch where she got the correct answer, is very small. But that part of the wavefunction is there, and that version of Alice is conscious in it, and she really does have the solution to the problem. It’s just that there are exponentially many other Alices that didn’t get the right answer.
In other words, this is another gedankenexperiment where we’ve created a situation where something in the universe corresponds to an observer solving a computationally difficult problem efficiently, but I suspect that people won’t think that this raises any philosophical weirdness beyond the usual “what is the meaning of probability in many worlds?”.
2:
This is not a non-sequitur, bear with me:
Scott, I know that you’ve taken a lot of issue with Stephen Wolfram’s recent hypergraph work (and older CA work but the recent stuff is what’s relevant), especially its supposed connections to physics, but I’d recommend you give it another try. Specifically, I recommend thoroughly reading his ‘technical introduction’ on his websie or arxiv. I know that it’s hundreds of pages long, so essentially constitutes reading a full textbook, and one’s time is extremely limited, but I actually think that it’s worth it.
The reason I’m bringing this up now is that the understanding that I’ve gained from the wolfram book prevented me from ever having any confusion about this thought experiment, and I think that (and other similar moments unrelated to this) are significant points in its favor.
In other words, I respectfully think you should take as at least some evidence that Wolfram is on to something that I, who has spent a lot of time reading about and learning about the wolfram hypergraph models, very quickly understood what the deal was with the Susskind thought experiment and was not confused by this. I’m not trying to be bragging or condescending here; If I hadn’t gone through the large effort to read and understand that whole tome, I would have been even more confused by Susskind’s thought experiment than you were.
My attempt at the Wolfram model explanation for this though experiment: sorry if it sounds like gibberish to those not versed in it. Hope it doesn’t put you more off to the idea than on.
The wolfram model explanation would essentially be that it would take exponential computational resources to see what is happening inside the black hole, because computing what happens on the boundary of the event horizon requires calculating more and more precise and careful foliations of the order of events to ‘read’ the information of the boundary in a meaningfuly way, since essentially what happens is what you can observe about the boundary from the outside is an encryption of what will go on inside it. This is similar but not exactly the same as the pure ADS/CFT statement. Something having crossed the event horizon means that your state can’t be causally dependent on events that occur on the other side of the event horizin. What this means is that from your perspective, once something meets the horizon it will no longer progress, since its progression is now unreachable by you. But other things will continue to cross the horizon, and what you’ll get is an increasingly tangled mess of events and states piling up on the boundary, but being ‘artificially’ prevented from evolving normally. The black hole is a pathology in ‘normal’ space which breaks up the normal foliations of events and creates increasing levels of activity in the system (perhaps Susskind’s linear growth??) to hold on to a picture of the world that’s consistent with no evolution occurring, and thus no dependence on, events inside. In order to predict what ‘will happen’ inside, you would have to simulate the black hole for yourself, which would be computationally hard. But if you’re inside the black hole, you have access to that information, since the black hole is doing that by itself.
Comment #167 August 7th, 2022 at 9:44 am
Thanks for the brilliant explanation. As you alluded to in the post, and may have already been mentioned in the comments, this all comes down to the fact that we don’t have an objective prescription for when consciousness is present in a physical system. Another variant of the measurement problem.
Comment #168 August 7th, 2022 at 1:48 pm
It’s not clear what name the general complexity question is meant to have, but it definitely deserves one. The space of things you can compute in polynomial time if you bring yourself along for the ride under any {quantum,classical} computation seems incredibly important for figuring out whether humanity will ever actually be motivated to do so! Is there stuff in there worth Having, and at what cost?
Beyond that, and beyond this just being an excellent, thought provoking concept, the potential for a unique piece of fiction seems incredibly compelling to me:
It’s the 28th century. After suffering repeated near-calamities, society declared superintelligence too dangerous to control. Yet many had faith Alignment was within reach, and campaigned for a Last Try. A compromise was reached, and half the universe was left to the machines, their artificial superintelligences locked behind an unbreakable quantum encryption. At time of death, or earlier for some, each member of society must decide whether to live on in simulation. Whose Alignment do they believe in? Can humans retain their consciousness and identity in their simulated afterlives? In this age, new decisions mirror the old: gambles on promises of Heaven, Hell, or Oblivion, while the heavens themselves are silent.
Our story follows Alessia, a young pilot in the Starseeker Corps. When she discovers information that could threaten the stability of the universe, the choices she makes will challenge her faith and reshape the foundations of her society.
(Yes, yes, this synopsis doesn’t include the specific premise of JI/poly, but that seems hard to fit. It’s part of the big plot hook.)
Comment #169 August 8th, 2022 at 8:47 am
This argument could be viewed as a complexity variant of Penrose’s argument that our ability to “know” provably unprovable things means consciousness is beyond current physics. It’s interesting that his proposed resolution is via quantum gravity.
Comment #170 August 8th, 2022 at 5:13 pm
Itai Bar-Natan #126, Luowen #149 (and Scott not objecting in #155)
I’m puzzled by people mentioning the “the time evolution” of the CFT data. AFAICS, the AdS data describes the WHOLE space-time state of the universe. Likewise, while CFT data is “on a hypersurface” (at infinity), but still this hypersurface is “located” at “far away”, not a “a particular time”.
In other words, the CFT data is encoding “what happens ‘far away’ at all possible times”. There may be no “time evolution” of this!
⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜
For me, the holomorphic principle encodes “an analogue” of the following situation: we choose a region of space (“a ball”), and consider the “corresponding cylinder” (“these positions at arbitrary times”) in space-time. We assume¹⁾ that there is no matter “near the boundary” and beyond the boundary, and that all “signals” (0-length geodesics???) come to the boundary at both ends.
¹⁾ I presume that to make this condition clear and strict, one more or less requires something like an anti-de-Sitter universe.
Then “the AdS side” encodes the whole physics happening inside the cylinder (including birth and evaporation of black holes). “The CFT side” encodes the whole physics happening on the boundary.
IN OTHER WORDS: we surround a region in space by detectors, and STORE all the incoming and outgoing “signals” going through these detectors. The COMPLETE archive of the stored information is “the CFT side”. From it, we want to detect “what happens inside this region” (“the AdS side”).
Comment #171 August 8th, 2022 at 5:48 pm
Scott #73, cgv #79
Assume an universe which allows “interstellar/intergalactic ramjects” (as in certain SF novels, like in A_World_Out_of_Time); assume that these spaceships allow moving in space with acceleration a>ε with ε>0. Then making a loop in space of subjecting time t, the return happens after the spaceport-time which is exponential in t.
This allows solving any problem of exp(P)-complexity in subjective-P-time: one starts a computer at the spaceport, makes long enough loop, and on return the problem is solved. What this (trivial) example shows (to me!) is that
Complexity-classes are defined only along a particular trajectory in space-time.
This is very close to what Scott wrote in #148, that you have to see the solution. — But this includes “something ‘very non-∅’ traveling along this trajectory in space-time’ — which ensures “the continuity of ‘you’” (whatever it means¹⁾).
¹⁾ And it seems that now CS needs to establish a foundation solid enough to answer this question!
One corollary is that if two trajectories become causally separated forever by an event horizon²⁾, “the computational complexity classes” along these trajectories become fully independent³⁾. And it seems that “going beyond FHE with throwing away the keys” should be treated likewise!
²⁾ … or any equivalent.
³⁾ Again, I have no clue how to state this rigorously!
Comment #172 August 8th, 2022 at 6:06 pm
Very surprisingly, I do not see the word “qualia” mentioned anywhere in this discussion. Observe Alice going beyond “an event horizon” (or its “FHE equivalent”). The apparent paradox is how to encode “the difficulty of ‘communicating back’ what Alice observes there” in the language of complexity classes. However, for example, suppose that Alice wants to break a FHE-(e)ncrypted message, goes “into FHE”, and discovers that the message consists of a flash of red.
Is not
the difficulty of Alice-inside-FHE communicating to “our world” the fact that “she perceived redness”
similar to
the difficulty of Alice-in-the-wild proving that she is not a P-zombie
when she is exposed to a flash of red?
Comment #173 August 10th, 2022 at 11:46 am
Alice in the encrypted basis makes me wonder, could aliens be in a computational basis that are different from ours. If so, how would we detect them. Could our minds be an object that reads our brain in a different basis? How would we know? A quantum mind’s thoughts seems to need 4 or 5 qubits to be coherent for a second or so. In a different basis, i am not sure how to prove this coherence isn’t possible. Mind is just brain in different basis????
Comment #174 August 10th, 2022 at 2:38 pm
An implication of your description of “solving exponentially hard problems by falling through the event horizon” is that Alice has to fall through the horizon. But is this really the case? An underdiscussed aspect of the bulk geometry here is the time dilation experienced by Alice close to the horizon (but still outside). Another way Alice could learn the solution to an exponentially hard problem is to set up a machine far from the black hold to do brute force search, then lower herself (or a very thin computer representation) close to the horizon, wait a little while (locally), then turn on the winch & raise herself back out to learn the solution from the now cobwebbed brute force computer. (Of course all her relatives have turned to dust, but that’s nothing compared to what she’s been through.) The larger the problem, the closer to the horizon she has to lower herself, but that’s a technicality, right?
Comment #175 August 10th, 2022 at 8:13 pm
@170 and 174: We can still assign a foliation to the CFT data and consider its evolution over time. It should correspond to a foliation of the AdS space and its evolution over time.
Your analogy is entirely correct; of course the region of spacetime extends to infinity in all directions, so its boundary is entirely at infinity (and we need the AdS spacetime in order to view this boundary at infinity as a Euclidean spacetime).
@171: Of course, from Alice’s perspective, the spaceport computer is running exponentially quickly; so she still thinks that it did exponentially many computations, as expected.
@172: Qualia aren’t relevant here; this scenario is about identity, not experience. These are both related to “consciousness”, but not the same kind of “consciousness”.
In particular,
the difficulty of Alice-inside-FHE communicating to “our world” the fact that “she perceived redness”
actually corresponds to
the difficulty of Alice-in-the-wild proving that she is Alice and not an imposter.
Proving that Alice has qualia won’t help, since an imposter might have qualia too. Moreover, the real Alice might be a P-zombie, so that this would actually prove that she IS an imposter.
Comment #176 August 11th, 2022 at 1:27 am
Could we sample the entangled qubits amplitude fast enough to check against a dictionary in real time.
Comment #177 August 11th, 2022 at 9:06 pm
Standeven #175:
I don’t understand what you mean by foliation in the context of CFT data. An individual item of CFT data is (ignoring stringness) a function on the boundary B. So one considers a manifold M a point of which is a function on B, and “evolution of CFT data” should be a flow on M. How can one “combine this” with a foliation on M?
(I suspect you are mixing up B and M.)
Second, I didn’t say anything about relevance of qualia in the context of OP. What I discussed was an analogy between two different types of complexity of passing information between different “environments” (for a loss of a better word).
Comment #178 August 11th, 2022 at 10:23 pm
oc #174
Did you see my #171? There is a lot of similarity; we both (essentially) describe that there are (imaginable?) situations in which time-complexity-classes make sense only along a particular trajectory in space-time.
However, I suspect that my method has a chance to be “a bit more realistic” that yours. I think it is easier to imagine a universe where ramjets (such as Bussard’s are feasible than your “winches”. (Note that it seems that the lower you want to go, the more massive winch you need. If so, then sooner or later, your winch would collapse into its own black hole!)
Comment #179 August 12th, 2022 at 7:30 pm
Ilya Zakharevich #177:
Whoops, you’re right. I meant a foliation of the AdS bulk, which of course automatically extends to a foliation of the boundary space, enabling us to define the evolution of the conformal field. I don’t know if there is a way to go from a foliation of the boundary to a foliation of the bulk spacetime.
As for the analogy between black holes and experiences, I don’t think it’s a good one, because the impossibility of sending information out of a black hole is due to causality issues, but the impossibility of “sending information out of” an experience is due to non-existent experiences not existing, so that the existence of an experience doesn’t contain any information.
Comment #180 August 15th, 2022 at 2:54 pm
Standeven #179: > “I don’t know if there is a way to go from a foliation of the boundary to a foliation of the bulk spacetime.”
I still think you are confused. The obstacle is in fact different: a foliation on the boundary does not produce a foliation on the set of functions on the boundary.
> “the impossibility of sending information out of a black hole is due to causality issues”
Only on short intervals of time. If I understand correct, the whole premise of the OP is based on the “long-time view”:
If you wait long enough, the BH evaporates, and the information escapes back. However, it escapes in a very tangled form, so it would take “exponential time” to decode it — even if one can capture everything escaping the evaporating BH.
Comment #181 August 17th, 2022 at 9:51 am
[…] Scott Aaronson On black holes, holography, the Quantum Extended Church-Turing Thesis, fully homomorphic encryption,… […]
Comment #182 August 17th, 2022 at 6:31 pm
Zakharevich #180:
Yes it can; each sheet of the foliation corresponds to the restrictions of the functions to that sheet. Evolution of the state on sheet x to the state on sheet y corresponds to evolution of the state on restrictions to y to the state on restrictions to x. So we have an evolution on the sheaf of the functions, as required.
And I guess I should have written “the difficulty of sending information out of the black hole” rather than “…impossibility…”.
Comment #183 August 20th, 2022 at 2:58 am
> “So we have an evolution on the sheaf of the functions, as required.”
When you say “evolution”, do you mean “evolution w.r.t. CFT equations”? If so, this can make SOME sense indeed!
On the other hand, CFT equations are (if I understand correct) “glorified analogues” of the Laplace equation. Then they are elliptic, not hyperbolic, so the word “evolution” makes very different sense for them. Are you sure that you want to use this particular sense?!
(Meanwhile, I’m kind of lost now, and cannot understand whether this covers the initial “evolution” comments made above.)
Comment #184 August 20th, 2022 at 3:06 am
> I should have written “the difficulty of sending information out of the black hole” rather than “…impossibility…”.
Then this makes your objection into a confirmation if what I wrote, does not it? There are three kinds of difficulties
• sending info out of a black hole;
• sending info out of a FHE;
• convincing somebody I had a qualia.
There are strong analogies between them.
(Sorry, I cannot follow your “non-existent experiences not existing” argument. Neither do I know why you replaced “P-zombie” by “imposter”.)
Comment #185 August 28th, 2022 at 8:48 pm
#183:
I’m pretty sure a CFT defined on a Minkowski spacetime will be hyperbolic (the Laplace equation becomes the wave equation). Otherwise, it wouldn’t be preserved under Lorentz transforms, which are conformal.
#184:
After thinking about it some more, I agree that the difficulty of convincing people that you have qualia is analogous to the difficulty of deciphering; but the issue in this case is that there will be multiple plaintexts [qualia-states] for any given cyphertext [physical state], so deciphering actually is impossible here, unlike in the FHE case.
Actually, I’m thinking of qualia-inversion here, not existence of qualia. The “cipher” forces us to assume that Alice has qualia, even if it is not actually true.
Comment #186 August 28th, 2022 at 9:00 pm
And since I’ve run out editing time, the reason I say that is that a “ciphertext” is defined as the image of a “plaintext” under a “cypher”; it’s not logically possible to have a plaintext mapping to a cyphertext with no associated plaintext. That’s what I was getting at with “nonexistent experiences not existing”
Comment #187 September 3rd, 2022 at 8:02 am
I don’t normally read your blog or much physics/CS and was surprised that my brain understood the entire first section on first read, without following any of the hyperlinks, even for the stuff I hadn’t been introduce to before. You seem to be very good at explaining complicated concepts through context clues. I am interested to know whether or not my brain will understand the other sections when I have time to sit down and read them, because damn, that title
Comment #188 September 4th, 2022 at 6:01 pm
Standeven #185
> “I’m pretty sure a CFT defined on a Minkowski spacetime will be hyperbolic”
Nope. IIRC, Penrose’ compactification adds a light cone at infinity. If so, the signature on the infinity is “more like 0+++ than ‒+++.
My initial impression was that the purpose of “starting with AdS” was to get the infinity conformally-Euclidean “instead”. However, reading more, it seems that the infinity of AdS is in fact conformally-Minkowsky (although I found my skills with working with signature ‒‒++ rather rusty; brain fog does not help…).
If so, my objection about hyperbolicity-vs.-ellipticity is completely void indeed!
> “I agree that the difficulty of convincing people that you have qualia is analogous to the difficulty of deciphering; but the issue in this case is that there will be multiple plaintexts [qualia-states] for any given cyphertext [physical state], so deciphering actually is impossible here, unlike in the FHE case.”
There are many cryptographic protocols which are not 1-to-1. Some of them may be used for “convincing people” (like zero-knowledge proofs).
Anyway, I cannot substantiate it any more: there is a “guts feeling” that “convincing people that I had qualia” HAS some similarity with crypto-problems — but nothing more convincing that this!
⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜
And: I cannot decipher what you write about “qualia-inversion” and afterwards.
Comment #189 September 13th, 2022 at 10:38 am
[…] In fact, if you are willing to make the one-way trip inside of a black hole, you may be able to receive solutions to hard problems (See also: Malament-Hogarth […]
Comment #190 October 22nd, 2022 at 9:14 pm
Hi, Scott 🙂
I have no knowledge about the Ads/CFT, aim at the computability:
In particular, the problem beyond BQP has declared in the part of the straight
matter, and the comment #148 takes NP(C), PSPACE(C), even halting function
as examples, Could we define the upperbounded hardness for the problems
solves by the Alice in simulation? Reaching the higher arithmetic hierarchy?