Black Holes, a Complexity Theory perspective
Guest post by ChiNing Chou and Parth Mehta from the physics and computation seminar.
Abstract
The firewall paradox (introduced here) is a bewitching thought experiment that mandates a deeper understanding of our reality. As luck would have it, QFT predictions seem sound, GR calculations appear valid, and semiclassical approximations look reasonable: no one is willing to budge! To save Alice from burning in the miserable firewall, therefore, we must come up with a radically new proposal. This blog post aims to map what seems to be a hard, physics dilemma into a Computer Science problem that we can, using the grace of a lazy programmer, show to be hard to solve. In particular, we present an overview of the HarlowHayden decoding task and show how it maps the Firewall Paradox to a hard computation on a quantum computer. We end by rigorously defining quantum circuit complexity, Aaronson’s improved proof, AdS/CFT correspondence, and some fascinating homework (open) problems.
Why all the fuss?
Have you ever confessed to yourself that you don’t quite understand Black Hole complementarity well? In the past decade or so, physicists realized they did not grasp the concept thoroughly either. The firewall paradox is a natural result of bewildered physicists trying to make sense of reality. Thus far, no satisfying physical explanation reaches people’s consensus. Nevertheless, Daniel Harlow and Patrick Hayden [HH13] proposed a tempting solution to the firewall paradox using Computational Complexity (CC). Concretely, they showed the following.
We elaborate on this deep connection throughout this post.
Problem Solving: Physics v.s. Computer Science
The notion of a `conjecture’ has different implications for either field. In Physics, a wrong conjecture often delights physicists since there is more work left to do and better theory required to explain the physical phenomenon under study. For complexity theorists, however, if, say, the famous is proved to be false, a few consequences follow. First, the authors of the proof win a million dollars (See the Millennium problems.). Second, such a result would break almost all the foundations of computational complexity and cryptography. That is, refuting an (important) conjecture in computational complexity is tantamount to resulting in realworld catastrophes! Below in Table 1 is a short summary.
Theoretical Physics  Theoretical Computer Science  
Object  Are the mathematical models for our physical world correct?  Is our intuition about the mathematical models we defined correct? 
Consequences of disproving  After few days/months/years, physicists will come up with a new model and try to falsify it.  The belief system of complexity theorists collapses. Some super algorithms might show up and shake the world. 
How to prove/disprove  Checking mathematical consistency, doing both thought and empirical experiments.  Using fancy mathematics or designing super algorithms. 
Table 1: “Conjecture”, as used in Physics and Computer Science.
We labour above to convince the reader about these differences because the HarlowHayden decoding task has vital implications for both, Physics and Computer Science. The connections between Black Holes and Computational Complexity can be thought of as a new testbench for physical models.
Reckless review: Quantum Information
Gates
In Quantum Computation, gates are unitary operators. Some common gates used in the Quantum Information literature are as follows:

Singlequbit: Pauli matrices (i.e., ), phase operator , Hadamard matrix .

Twoqubit: CNOT, Toffoli, CZ.
For more details, please refer to [NC02]. Interestingly enough, singequbit and twoqubit gates are sufficient to construct any qubit gates! Such a set of operators is said to be universal. For example, and are universal for almost every singlequbit operator. Furthermore, Kitaev and Solovay gave a qualitative version of the universality theorem by showing that getting an approximation to an qubit operator in trace norm, only gates are needed. A final remark on unitary operators: an qubit operator is actually a matrix of size by . Namely, it requires complex numbers to describe an qubit operator. (Note the difference between and .)
Quantum circuits
A quantum circuit has inputs consisting of qubits, potentially with ancilla bits. The computation is done by interior gates from some universal gate set, e.g., . The outputs are qubits with potentially bits of garbage. See the following example of quantum circuit for the qubit Hadamard operator in Figure 1.
Similarly, the size of a quantum circuit is defined as the number of interior gates. In Figure 1 for example, the size of the circuit is .
Quantum circuit complexity: BQP/poly
Let be a boolean function. Define its quantum circuit complexity as the size of the smallest quantum circuit such that for any
Let denote the class of boolean functions of quantum circuit complexity at most . The complexity class is defined as . It immediately follows from definition that . As proving lower bound for (i.e., finding a problem that is not in ) is a longstanding extremely difficult problem, it is believed to be hard to prove lower bound against .
Uniform quantum circuit complexity: BQP
As is too powerful to work with, one might want to define a weaker version of the quantum complexity measure. A natural choice is considering a uniform computational model.
In the classical setting, a uniform computational model is defined using a Turing machine. However, it is not clear how to define the corresponding version, a quantum Turing machine. One way to do so is via uniform circuits, defined as follows. We say a circuit family is uniform if there exists a polynomial time Turing machine such that on input , it outputs .
Let be a boolean function. Define its uniform quantum circuit complexity as the size of the smallest uniform quantum circuit such that for any
Let denote the class of boolean functions of quantum circuit complexity at most . The complexity class is defined as . It immediately follows from definition that .
Unitary complexity: C(U)
Let be an unitary matrix. Define be the smallest quantum circuit such that
This unitary complexity can be thought of as a relaxation of the quantum circuit complexity. The reason is that here a unitary matrix might not compute a boolean function. Thus, proving a lower bound for implies a lower bound for unitary complexity while the converse is not clear. Namely, proving a superpolynomial lower bound for the unitary complexity might be an easier task.
However, no nontrivial^{1} lower bound for the unitary complexity is known and there is, unfortunately, no formal barrier result explaining why this is difficult to prove.
Warmup: GottesmanKnill
We defined quantum circuits above, and we hope you find them exotic – at least startup investors do. But given how fundamental quantum circuits are to the HarlowHayden decoding task, we ask: is it possible to efficiently (classically) simulate a quantum circuit made up of a restricted but nontrivial set of quantum gates? We show below a restricted variant of the popular GottesmanKnill Theorem:
Theorem (GottesmanKnill).
1. Given: Clifford circuit made up of gates , where is measured on its first output line.
2.Task: Show that it is possible to (classically) efficiently sample the output distribution of .
Proof:
where . Since the projector can be written as , we get
where since we only measure the first output line of . At first glance, might look like a monstrous computation to perform since, in general, the operator in the middle is a matrix, so the calculating the inner product would require exponential time classically. However, recognizing that Clifford gates are normalizers of the Pauli Group on qubits, note that where is some Pauli matrix. It is straightforward to show that these update rules can be computed efficiently. We thus have
which is a product of terms. We have thus reduced the (exponentially large) burden of computing a giant matrix
to computing matrices size , so we can sample the output distribution efficiently.
The Firewall paradox and the HarlowHayden decoding task
Physics to CS
All of the black hole physics covered in the previous blog post leads to the moment (we hope) you have been waiting for: a charming resolution of the firewall paradox. Consider the interior of an old, rusty black hole that has radiated away more than half of its matter. Let be the old Hawking radiation, and let represent the fresh Hawking radiation coming right out of the boundary of the Black Hole. Alice is our canonical Ph.D. student who is brave enough to risk her life for physics. Since is a giant information scrambler, we expect to find entanglement between and with overwhelming probability. We know from QFT that there are bell pairs straddling the event horizon of the black hole, so and should be maximally entangled. But this is a problem because cannot be entangled with both and ! The AMPS argument shows that if Alice is able to distill a bell pair between and , then we should see a firewall of photons at the event horizon, thus violating the nodrama postulate. See Figure 2 for more intuition about the set up. (Note that the ‘s represent Bell Pairs, as consistent with the 3DQuon Language) If we take Black Hole complimentary seriously, then we have an answer! If Alice does not distill a Bell pair between and , then nothing really happens. However, if Alice does manage to distill the entanglement between and , then we witness a firewall. Is not this answer so very unsatisfactory? Why should the existence of a firewall depend on Alice’s ability to distill entanglement? What is so special about this decoding task?
The HH decoding task answers precisely this question. Intuitively, it says that if Alice manages to distill a Bell pair between and , she could also invert a oneway function, a task we believe is very hard to perform! We conjecture that Alice would take exponential time to decode the entanglement, so the Black Hole would disappear long before Alice even makes a dent in the problem! Before we provide an in depth resolution of the paradox through the HH decoding, let us (as good philosophers do) briefly review assumptions:
 The Black Hole can be modelled by a finite collection of qubits, say qubits.
 Alice is told that the initial state of is the product basis .
 Black Hole dynamics are assumed to be unitary, so Alice need not worry about some spooky Mtheory that may claim to evolve in a nonunitary fashion.
 is a giant information scrambler, represented by some random circuit .
 Fresh radiation is a single qubit, w.l.o.g., since any additional qubits could be made a part of .
 is not HaarRandom. Miniexercise: prove that if is HaarRandom, our job becomes easy because the circuit complexity of the HH decoding task grows exponentially with , the size of .
 Alice has access only to circuit and but not . Trivial Miniexercise: prove that if Alice has access to , then it is easy to distill the entanglement between and .
 Alice may be an intellectual Goddess who just knows which unitary to apply, or, more realistically, someone who has exponential time to prepare before the Black Hole forms. Of crucial importance therefore is the circuit complexity of the unitary Alice applies to distill the Bell pair, not so much the process of finding the unitary.
Distilling the BR Bell pair
Let us jump into the definition of the HarlowHayden decoding task.
Definition (HarlowHayden decoding task).
Given a (polynomialsize) quantum circuit as input such that where are three disjoint part of the qubits. Furthermore, it is guaranteed that there exists a unitary operator acting only on the qubits in such that after applying , the rightmost bit of and the leftmost bit of forms a bell pair . The goal of the HarlowHayden decoding task is then to find a quantum circuit for such U on the qubits in . See Figure 3.
A necessary condition for the firewall paradox to make sense is that the HarlowHayden decoding task should be easy. If Alice cannot distill the entanglement efficiently, the black hole will evaporate before Alice is ready to witness the firewall!
To refute the firewall paradox, Harlow and Hayden proved the following theorem.
Theorem 1.
If the HarlowHayden decoding task can be done in , then .
We won’t formally define the complexity class . However, it is important to know that the foundation of the latticebased cryptography, a promising quantumsecure crypto framework, is based on the hardness of some problem in . If , then all latticebased cryptosystems can be broken by polynomial time quantum algorithm!
Instead of a proof for Theorem 1, which is more involved, we give a proof for an improvement of the HarlowHayden theorem due to Scott Aaronson. (Aaronson also showed that there might not even exist quantumsecure cryptography if the HarlowHayden decoding task can be efficiently solved!)
Aaronson’s improvement
In Aaronson’s lecture notes [Aar16], he showed the following improvement on Theorem 1.
Theorem 2.
If the HarlowHayden decoding task can be done in , then quantumsecure injective oneway function does not exist.
Before formally defining a one way function, it is paramount to understand its impact: modern cryptosystems are built from some variant of a oneway function. Intuitively, primitives that have the oneway property are (i) easy to implement (e.g., encrypt) but (ii) hard to invert (e.g., be attacked). As a result, if there is no quantumsecure injective oneway function, then that is strong evidence that quantumsecure cryptography might not exist.
Now, let us formally define what quantumsecure injective oneway function is and give a formal proof for Theorem 2.
Definition 1 (Quantumsecure injective oneway function).
A boolean function is a quantumsecure injective oneway function if
 is injective,
 , and
 for any polynomial time quantum algorithm
Note that since is injective, the last condition can actually be phrased as . Also, the condition should be read as “on input , the quantum algorithm outputs ”, namely, inverts .
Suppose the HarlowHayden decoding task is in , we are going to show that for any injective computable by some polynomial size quantum circuit, there is a polynomial time quantum algorithm that inverts . Namely, is not a quantumsecure injective oneway function.To get an efficient inverting algorithm for , let us first prepare a special circuit from and treat it as an input to the HarlowHayden decoding task. The circuit will simply map the to the following state
Note that as has a polynomial size quantum circuit, the circuit can also be implemented in polynomial size.Next, the easiness of the HarlowHayden decoding task guarantees us the existence of a unitary operation on the qubits in such that for any
for some state . By restricting on the first qubits, one can get unitary operators and such that for all ,
Thus, inverts because for any ,
Furthermore, as we are guaranteed that the HarlowHayden decoding task is in , as well as and all have polynomial size quantum circuits! Namely, can be efficiently inverted by a quantum algorithm and thus is not a quantumsecure injective oneway function.
What’s next?
The HarlowHayden decoding task as well as the Aaronson’s improvement can be interpreted as (strong) evidence that distilling the BR Bell pair is hard (in the worstcase^{2}). One might hope for an averagecase hardness for the HarlowHayden decoding task and thus infer that most black holes are difficult to distill. However, even if such averagecase hardness results existed, physicists would still remain dissatisfied! The foremost grievance a physicist may have is the lack of a coherent causal framework to model reality. That is, what happens if, in the
very small but nonzero chance, a black hole is easy to distill? Does that mean that a firewall exists in such black hole? How can a unifying theory explain such situation coherently? An ideal theory for theoretical physicists should work for every black hole instead of for most black holes! Second, physicists seem to dislike the abstract, processtheoretic approach undertaken by computer scientists. Here, we have completely ignored talking about the internal dynamics of a black hole or even a full description of its evolving Hilbert space. They would, for instance, like to see a differential equation that captures the difficulty of distilling a black hole throughout its evolution. Resolutions to the firewall paradox or effort towards building a theory of quantum gravity should be somewhat explicit in the sense that one can really instantiate some (toy) examples from the theory and see how the system evolves and examine whether this fits the real experience from the world. In other words, a theory with a black box (i.e., a complexity conjecture) might not be regarded as a resolution.
Homework
 What powers would Alice need to ensure that she can efficiently distill the BR bell pair. What if we assume ?
 Can we show that the decoding is hard on average, rather than for the worst case?
 What are some similar deep connections between black holes and complexity theory?
 For people interested in the quantum complexity theory, there are many open problems regarding the quantum circuit complexity: consider the unitary synthesis problem^{3} proposed by Scott Aaronson [Aar16].
 Another interesting problem is connecting the difficulty of proving quantum circuit lower bounds to other complexity problem such as classical circuit lower bounds or cryptographic assumptions.
Footnotes
^{1}Nontrivial here means the unitary matrix is explicit in the sense that given , one can efficiently compute .
^{2}Hard in worstcase means that there does not exist efficient algorithm that works on every input. Another hardness notion is hard on average, by which we mean there does not exist efficient algorithm the works for most of the input. Showing averagecase hardness is in general a more difficult task than proving worstcase hardness.
^{3}Does the following hold: for any unitary matrix , there exists a classical oracle such that where is the minimum size of quantum circuit that approximates with oracle access to .
Comments are closed.