Skip to content

STOC 2019 travel grants

April 5, 2019

(As you’re working on your FOCS papers, an announcement about STOC 2019 from Eric Allender –Boaz)

STOC registration is now open The deadline to apply for travel grants is April 22 . Apply on

There is also travel support available via TCS Women (deadline April 25), see

FOCS 2019 Real website and submission server

April 3, 2019

The website for the FOCS 2019 conference is , and the submission server is

The deadline is 3:00pm PDT, April 5, 2019.

The reason I am posting this is that there is a fake FOCS website that ranks first or second on searches for “FOCS 2019”. The website is under the domain “aconf dot org” (I don’t want to increase ranking and traffic to it even further by linking to it). This website contains fake pages for many other conferences, and in fact sometimes is ranked highly enough in searchers that conference organizers mistakenly link to it in their own web page. Apparently it is owned by a company called Chaytey who also has a similar webpage for journals under the address xjournal dot net. (Thanks to Sara Cohen ,colleague of FOCS general chair Yuval Rabani for finding this out.)

Physics & Computation Blog Post Round-up

March 30, 2019

In the Fall, Boaz and I co-taught a grad seminar on physics and computation (see here for some of the original press coverage). We were lucky to attract an intrepid group of students from multiple fields, with representatives from computer science, physics, math and biology. As part of the course, we asked our students to give presentations and write expository blog posts on a number of topics at the intersection of computation and physics, including algorithms from statistical physics, quantum area laws, and the firewall paradox. The students worked hard to produce posts that make the physics concepts accessible to a computer science audience, and the result is a nice collection of posts that create a “bridge” from CS to physics.

Here, the aim is to give a (long overdue) table of contents for their posts. Followers of the blog may have noticed a landslide of physics & computation posts around December and January; if you weren’t able to keep up with them all at the time, then here they are, rounded up and organized by topic.

Statistical Physics

Background and intro to phase transitions:

Algorithms from statistical physics: belief propagation and approximate message passing:

Informational and computational phase transitions:

Proving the existence of phase transitions:

 Using convex relaxations to approximate partition functions:

Quantum Computation

Background on Quantum Hamiltonians and tensor network representations:

Area laws:

Quantum algorithms:

Quantum games and quantum PCPs:

Quantum supremacy:

Quantum error correction:

Black Holes and the Firewall Paradox

(See also Boaz’s introductory post)

Background on black holes and the Firewall Paradox:

Firewall Paradox meets Computational Complexity:

Nominate TCS papers for research highlights

March 28, 2019

[Guest post by Aleksander Mądry]

To me, one of the best things about working in theoretical computer
science has always the exciting rate of progress we make as a community. 
On (what appears to be) a regular basis, we produce breakthroughs on 
problems that are absolutely fundamental to our field. Problems that 
often look impossible to tackle, right up until someone actually tackles 

However, as inspiring as all these developments were to me, I also 
always felt that we, as a community, could do more to properly recognize 
and highlight them, both internally and to the outside world. This kind 
of outreach would make it easier for us to capitalize on the 
breakthroughs as well as to accelerate the impact of the underlying 
ideas on the other areas of computer science, and beyond.

Fortunately, this is about to change!

One of the first decisions of our newly (re-)elected SIGACT committee was to create a committee (as committees are wont to do 🙂 whose mission will be to help promote top computer science theory research. This SIGACT Research Highlights Committee – consisting of Boaz Barak, Omer Reingold, Mary Wootters and myself – will, in particular, work to identify results to be recommended for consideration for the CACM Research Highlights section as well as other general-audience research outlets in computer science and other fields.

Of course, to do a proper job here we require your help! To this end, 
the committee solicits two types of nominations:

1) Conference nominations. Each year, the committee will ask the PC 
chairs of a broad set of theoretical computer science conferences to 
send a selection of up to three top papers from these conferences 
(selected based on both their technical merit and the potential 
significant interest to non-theory audiences) and forwarding them to the 
committee for consideration.

2) Community nominations. The committee will accept nominations from the members of the community. Each such nomination should summarize the contribution of the nominated (and recently published) paper and also
argue why this paper particularly merits a broader outreach. The 
nomination should be no more than a page in length and can be submitted 
at any time by emailing it to
Self-nominations are discouraged.

To be considered in the upcoming round of our deliberations, we need to 
receive your nomination by April 30.

Looking forward to learning about all the new exciting research that you 
all are doing!

News addicts: Sign up for the CATCS newsletter

March 26, 2019

If, like others following the pace of modern life, you’re the kind of person that needs to get just on time updates on the state of theoretical computer science, consider signing up for the newsletter of CATCS. You can get information about funding opportunities, advocacy efforts, and more. Sure, at the hectic rate of two messages per year, it might flood your inbox, but it is worth it.

Dear Theoretical Computer Scientist,

The Committee for the Advancement of Theoretical Computer Science (CATCS) was established by SIGACT to deal with funding, outreach, and advocacy issues for our community. If you would like to receive our newsletter (no more than twice annually) we encourage you to sign up for the Google group below:!forum/catcs-news
(Navigate to the page above and click “Join group.” You can unsubscribe at any time from the same page.)
Best wishes, CATCS

Submit your failures to CFAIL 2019

March 13, 2019

[Posted at the request of Craig Gentry. I think this is actually a great idea that should be imitated by other sub-areas of TCS as well. –Boaz]

Update: The Conference for Failed Approaches and Insightful Losses in cryptology is celebrating our first failure early: the failure to keep a deadline! We are extending the submission deadline to 11:59 pm EST on April 7 to give everyone more time to work on submissions. In these last weeks leading up to the deadline, you can follow the @cfail2019 twitter account for inspiring jokes about failure to help you reach the finish line!

The CFAIL 2019 program chairs would like to remind you that some failures are good. Failure to attack a cryptosystem? Good! It might be a strong cryptosystem. Failure to publish in Eurocrypt? No problem! You’ll get ’em next time. Failure to cut back on caffeine like you promised in your New Year’s resolution? Good! You must be full of energy!

But failure to submit to CFAIL… lame! 
Work on those submissions, cryptologists! We want to see your failures in all their glory! 
Just a friendly reminder that the CFAIL submission deadline is April 1 April 7th.

Black Holes, a Complexity Theory perspective

February 1, 2019

Guest post by Chi-Ning Chou and Parth Mehta from the physics and computation seminar.


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 semi-classical 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 Harlow-Hayden 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.

\text{A conjecture in CC is true}\Rightarrow\text{Firewalls do not exist}.

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 \mathbf{P}\neq\mathbf{NP} 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 real-world 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 Harlow-Hayden 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


In Quantum Computation, gates are unitary operators. Some common gates used in the Quantum Information literature are as follows:

  • Single-qubit: Pauli matrices (i.e., X,Y,Z), phase operator P, Hadamard matrix H.
  • Two-qubit: CNOT, Toffoli, CZ.

For more details, please refer to [NC02]. Interestingly enough, singe-qubit and two-qubit gates are sufficient to construct any n-qubit gates! Such a set of operators is said to be universal. For example, \{\text{Toffoli},H,P\} and \{\text{CNOT},G\} are universal for almost every single-qubit operator. Furthermore, Kitaev and Solovay gave a qualitative version of the universality theorem by showing that getting an \epsilon approximation to an n-qubit operator in trace norm, only O(\log^21/\epsilon) gates are needed. A final remark on unitary operators: an n-qubit operator is actually a matrix of size 2^n by 2^n. Namely, it requires 2^{2n}-2^n complex numbers to describe an n-qubit operator. (Note the difference between n and 2^n.)

Quantum circuits

A quantum circuit \mathcal{C} has inputs consisting of n-qubits, potentially with m ancilla bits. The computation is done by interior gates from some universal gate set, e.g., \{\text{Toffoli},H,P\}. The outputs are n qubits with potentially m bits of garbage. See the following example of quantum circuit for the n-qubit Hadamard operator H_n| x\rangle=\sum_{y\in\{0,1\}^n}(-1)^{\langle x,y\rangle}|y\rangle in Figure 1.


Figure 1: A quantum circuit for the n-qubit Hadamard operator.

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 n.

Quantum circuit complexity: BQP/poly

Let f:\{0,1\}^n\rightarrow\{0,1\} be a boolean function. Define its quantum circuit complexity as the size of the smallest quantum circuit C such that for any x\in\{0,1\}^n


Let \mathbf{BQSIZE}[s(n)] denote the class of boolean functions of quantum circuit complexity at most s(n). The complexity class \mathbf{BQP/poly} is defined as \cup_{c\in\mathbb{N}}\mathbf{BQSIZE}[n^c]. It immediately follows from definition that \mathbf{P/poly}\subseteq\mathbf{BQP/poly}. As proving lower bound for \mathbf{P/poly} (i.e., finding a problem that is not in \mathbf{P/poly}) is a long-standing extremely difficult problem, it is believed to be hard to prove lower bound against \mathbf{BQP/poly}.

Uniform quantum circuit complexity: BQP

As \mathbf{BQP/poly} 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 \mathcal{C}=\{C_n\}_{n\in\mathbb{N}} is \mathbf{P}-uniform if there exists a polynomial time Turing machine such that on input 1^n, it outputs C_n.

Let f:\{0,1\}^n\rightarrow\{0,1\} be a boolean function. Define its uniform quantum circuit complexity as the size of the smallest uniform quantum circuit C such that for any x\in\{0,1\}^n


Let \mathbf{BQTIME}[s(n)] denote the class of boolean functions of quantum circuit complexity at most s(n). The complexity class \mathbf{BQP} is defined as \cup_{c\in\mathbb{N}}\mathbf{BQTIME}[n^c]. It immediately follows from definition that \mathbf{P}\subseteq\mathbf{BPP}\subseteq\mathbf{BQP}.

Unitary complexity: C(U)

Let U\in\mathbb{C}^{2^n\times2^n} be an unitary matrix. Define C(U) be the smallest quantum circuit C 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 U might not compute a boolean function. Thus, proving a lower bound for \mathbf{BQSIZE} implies a lower bound for unitary complexity while the converse is not clear. Namely, proving a super-polynomial lower bound for the unitary complexity might be an easier task.

However, no non-trivial1 lower bound for the unitary complexity is known and there is, unfortunately, no formal barrier result explaining why this is difficult to prove.

Warm-up: Gottesman-Knill

We defined quantum circuits above, and we hope you find them exotic – at least start-up investors do. But given how fundamental quantum circuits are to the Harlow-Hayden decoding task, we ask: is it possible to efficiently (classically) simulate a quantum circuit made up of a restricted but non-trivial set of quantum gates? We show below a restricted variant of the popular Gottesman-Knill Theorem:

Theorem (Gottesman-Knill).
1. Given: Clifford circuit \mathcal{C}: |\alpha_1\rangle\otimes \cdots \otimes |\alpha_n\rangle \rightarrow \{|0\rangle,|1\rangle\} made up of gates \{CNOT, P, H\}, where \mathcal{C} is measured on its first output line.
2.Task: Show that it is possible to (classically) efficiently sample the output distribution of \mathcal{C}.


\Pr(0) = \langle{\psi_0|\mathcal{C}^{\dag}(|0\rangle}\langle0|)\mathcal{C}|\psi_0\rangle where |\psi_0\rangle = |\alpha_1\rangle\otimes \cdots \otimes |\alpha_n\rangle. Since the projector can be written as |0\rangle\langle0|= \frac{I + Z}{2}, we get

\Pr(0) = \langle\psi_0|\mathcal{C}^{\dag}(\frac{I + Z}{2})\mathcal{C}|\psi_0\rangle =\frac{1}{2}[1 + \langle\psi_0|\mathcal{C}^{\dag}Z_1\mathcal{C}|\psi_0\rangle]

where Z_1 = Z \otimes I\cdots \otimes I since we only measure the first output line of \mathcal{C}. At first glance, \langle\psi_0|\mathcal{C}^{\dag}Z_1\mathcal{C}|\psi_0\rangle might look like a monstrous computation to perform since, in general, the operator in the middle is a 2^n\times 2^n matrix, so the calculating the inner product would require exponential time classically. However, recognizing that Clifford gates are normalizers of the Pauli Group on n qubits, note that \mathcal{C}^{\dag}Z_1\mathcal{C} = P_1 \otimes \cdots \otimes P_n where P_i is some Pauli matrix. It is straightforward to show that these update rules can be computed efficiently. We thus have

\langle\psi_0|\mathcal{C}^{\dag}Z_1\mathcal{C}|\psi_0\rangle = \langle\psi_0|P_1 \otimes \cdots \otimes P_n|\psi_0\rangle = \prod_{i = 1}^{n} \langle\alpha_i|P_i|\alpha_i\rangle

which is a product of n terms. We have thus reduced the (exponentially large) burden of computing a giant 2^n\times 2^n matrix
to computing n matrices size 2\times 2, so we can sample the output distribution efficiently.

The Firewall paradox and the Harlow-Hayden decoding task

Physics to CS


Figure 2: A cartoon representing drama (no pun intended) near the Black Hole.

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 H that has radiated away more than half of its matter. Let R be the old Hawking radiation, and let B 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 H is a giant information scrambler, we expect to find entanglement between R and B with overwhelming probability. We know from QFT that there are bell pairs straddling the event horizon of the black hole, so B and H should be maximally entangled. But this is a problem because B cannot be entangled with both R and H! The AMPS argument shows that if Alice is able to distill a bell pair between R and B, then we should see a firewall of photons at the event horizon, thus violating the no-drama postulate. See Figure 2 for more intuition about the set up. (Note that the \cup‘s represent Bell Pairs, as consistent with the 3D-Quon Language) If we take Black Hole complimentary seriously, then we have an answer! If Alice does not distill a Bell pair between R and B, then nothing really happens. However, if Alice does manage to distill the entanglement between R and B , 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 H-H decoding task answers precisely this question. Intuitively, it says that if Alice manages to distill a Bell pair between R and H, she could also invert a one-way 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 H-H decoding, let us (as good philosophers do) briefly review assumptions:

  1. The Black Hole H can be modelled by a finite collection of qubits, say n qubits.
  2. Alice is told that the initial state of H is the product basis |0\rangle^{\otimes n}.
  3. Black Hole dynamics are assumed to be unitary, so Alice need not worry about some spooky M-theory that may claim to evolve H in a non-unitary fashion.
  4. H is a giant information scrambler, represented by some random circuit \mathcal{C}.
  5. Fresh radiation B is a single qubit, w.l.o.g., since any additional qubits could be made a part of R.
  6. |\psi\rangle_{RBH} is not Haar-Random. Mini-exercise: prove that if |\psi\rangle_{RBH} is Haar-Random, our job becomes easy because the circuit complexity of the H-H decoding task grows exponentially with n, the size of H.
  7. Alice has access only to circuit \mathcal{C} and R, B but not H. Trivial Mini-exercise: prove that if Alice has access to R,B,H, \mathcal{C}, then it is easy to distill the entanglement between R and B.
  8. 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 B-R Bell pair

Let us jump into the definition of the Harlow-Hayden decoding task.

Definition (Harlow-Hayden decoding task).
Given a (polynomial-size) quantum circuit C as input such that |\psi\rangle_{RBH}=C|0^n\rangle where R,B,H are three disjoint part of the n qubits. Furthermore, it is guaranteed that there exists a unitary operator U acting only on the qubits in R such that after applying U, the rightmost bit of R and the leftmost bit of B forms a bell pair \frac{|00\rangle+|11\rangle}{\sqrt{2}}. The goal of the Harlow-Hayden decoding task is then to find a quantum circuit for such U on the qubits in R. See Figure 3.


Figure 3: The Harlow-Hayden decoding task.

A necessary condition for the firewall paradox to make sense is that the Harlow-Hayden 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 Harlow-Hayden decoding task can be done in \mathbf{BQP/poly}, then \mathbf{SZK}\subseteq\mathbf{BQP/poly}.

We won’t formally define the complexity class \mathbf{SZK}. However, it is important to know that the foundation of the lattice-based cryptography, a promising quantum-secure crypto framework, is based on the hardness of some problem in \mathbf{SZK}. If \mathbf{SZK}\subseteq\mathbf{BQP/poly}, then all lattice-based 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 Harlow-Hayden theorem due to Scott Aaronson. (Aaronson also showed that there might not even exist quantum-secure cryptography if the Harlow-Hayden 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 Harlow-Hayden decoding task can be done in \mathbf{BQP/poly}, then quantum-secure injective one-way 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 one-way function. Intuitively, primitives that have the one-way 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 quantum-secure injective one-way function, then that is strong evidence that quantum-secure cryptography might not exist.

Now, let us formally define what quantum-secure injective one-way function is and give a formal proof for Theorem 2.

Definition 1 (Quantum-secure injective one-way function).
A boolean function f:\{0,1\}^n\rightarrow\{0,1\}^m is a quantum-secure injective one-way function if

  • f is injective,
  • f\in\mathbf{BQP/poly}, and
  • for any polynomial time quantum algorithm A

Note that since f is injective, the last condition can actually be phrased as x=A(f(x)). Also, the condition should be read as “on input f(x), the quantum algorithm A outputs x”, namely, A inverts f.


Suppose the Harlow-Hayden decoding task is in \mathbf{BQP/poly}, we are going to show that for any injective f:\{0,1\}^n\rightarrow\{0,1\}^m computable by some polynomial size quantum circuit, there is a polynomial time quantum algorithm that inverts f. Namely, f is not a quantum-secure injective one-way function.To get an efficient inverting algorithm for f, let us first prepare a special circuit C from f and treat it as an input to the Harlow-Hayden decoding task. The circuit C will simply map the |0^{m+2+n}\rangle to the following state


Note that as f has a polynomial size quantum circuit, the circuit \mathcal{C} can also be implemented in polynomial size.Next, the easiness of the Harlow-Hayden decoding task guarantees us the existence of a unitary operation U on the qubits in R such that for any x\in\{0,1\}^n

U\left(\frac{|x,0^{m-n},0\rangle_R+|f(x),1\rangle_R}{\sqrt{2}}\right) = |\phi_x\rangle_R\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)

for some state |\phi_x\rangle_R. By restricting U on the first m qubits, one can get unitary operators V and W such that for all x\in\{0,1\}^n,

V|x,0^{m-n}\rangle=|\phi_x\rangle\text{ and }W|f(x)\rangle=|\phi_x\rangle.

Thus, V^\dagger W inverts f because for any x\in\{0,1\}^n,

V^\dagger W|f(x)\rangle=|x,0^{m-n}\rangle.

Furthermore, as we are guaranteed that the Harlow-Hayden decoding task is in \mathbf{BQP/poly}, U as well as V and W all have polynomial size quantum circuits! Namely, f can be efficiently inverted by a quantum algorithm and thus f is not a quantum-secure injective one-way function.

What’s next?

The Harlow-Hayden decoding task as well as the Aaronson’s improvement can be interpreted as (strong) evidence that distilling the B-R Bell pair is hard (in the worst-case2). One might hope for an average-case hardness for the Harlow-Hayden decoding task and thus infer that most black holes are difficult to distill. However, even if such average-case 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 non-zero 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, process-theoretic 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.


  1. What powers would Alice need to ensure that she can efficiently distill the B-R bell pair. What if we assume \mathbf{P = PSPACE}?
  2. Can we show that the decoding is hard on average, rather than for the worst case?
  3. What are some similar deep connections between black holes and complexity theory?
  4. For people interested in the quantum complexity theory, there are many open problems regarding the quantum circuit complexity: consider the unitary synthesis problem3 proposed by Scott Aaronson [Aar16].
  5. 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.


1Non-trivial here means the unitary matrix U is explicit in the sense that given i,j\in[2^n]], one can efficiently compute U_{ij}.
2Hard in worst-case 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 average-case hardness is in general a more difficult task than proving worst-case hardness.
3Does the following hold: for any unitary matrix U\in\mathbb{C}^{2^n\times2^n}, there exists a classical oracle A such that C^A(U)=n^{O(1)} where C^A(U) is the minimum size of quantum circuit that approximates U with oracle access to A.


[Aar16] Scott Aaronson. The complexity of quantum states and transformations: from quantum money to black holes. arXiv preprint arXiv:1607.05256, 2016.
[HH13] Daniel Harlow and Patrick Hayden. Quantum computation vs. firewalls.
Journal of High Energy Physics, 2013(6):85, 2013.
[NC02] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.