Isaac Kim

We show that the $T$-depth of any single-qubit $z$-rotation can be reduced to $3$ if a certain catalyst state is available. To achieve an $\epsilon$-approximation, it suffices to have a catalyst state of size polynomial in $\log(1/\epsilon)$. This implies that $\mathsf{QNC}^0_f/\mathsf{qpoly}$ admits a finite universal gate set consisting of Clifford+$T$. In particular, there are catalytic constant $T$-depth circuits that approximate multi-qubit Toffoli, adder, and quantum Fourier transform arbitrarily well. We also show that the catalyst state can be prepared in time polynomial in $\log (1/\epsilon)$.

We prove a nontrivial circuit-depth lower bound for preparing a low-energy state of a locally interacting quantum many-body system in two dimensions, assuming the circuit is geometrically local. For preparing any state which has an energy density of at most ε with respect to Kitaev's toric code Hamiltonian on a two dimensional lattice Λ, we prove a lower bound of Ømegałeft(minłeft(1/epsilon^frac1-alpha2, sqrtabsŁambdaright)right) for any alpha >0. We discuss two implications. First, our bound implies that the lowest energy density obtainable from a large class of existing variational circuits (e.g., Hamiltonian variational ansatz) cannot, in general, decay exponentially with the circuit depth. Second, if long-range entanglement is present in the ground state, this can lead to a nontrivial circuit-depth lower bound even at nonzero energy density. Unlike previous approaches to prove circuit-depth lower bounds for preparing low energy states, our proof technique does not rely on the ground state to be degenerate.

Abstract We introduce the entanglement bootstrap program, a powerful new approach to study topologically ordered quantum many-body systems. In this program, we posit that local reduced density matrices of the underlying system obey a set of simple constraints that are motivated by the entanglement entropy calculations in the literature. We show that these constraints lead to a highly nontrivial set of identities that can be interpreted as the basic axioms of the emergent theory describing the topological charges in such systems. The surprising nature of our work lies in the fact that these basic axioms of the emergent theory, which are typically assumed in the literature, can actually be derived from a simple entanglement property of the ground state. Furthermore, we apply this line of reasoning to systems with gapped domain walls and derive a hitherto unknown set of topological charges and identities that those topological charges need to satisfy. Thus, our work establishes a deep connection between entanglement and the exotic behaviors of topological charges in topologically ordered systems.

Abstract We reconsider the black hole firewall puzzle, emphasizing that quantum error-correction, computational complexity, and pseudorandomness are crucial concepts for understanding the black hole interior. We assume that the Hawking radiation emitted by an old black hole is pseudorandom, meaning that it cannot be distinguished from a perfectly thermal state by any efficient quantum computation acting on the radiation alone. We then infer the existence of a subspace of the radiation system which we interpret as an encoding of the black hole interior. This encoded interior is entangled with the late outgoing Hawking quanta emitted by the old black hole, and is inaccessible to computationally bounded observers who are outside the black hole. Specifically, efficient operations acting on the radiation, those with quantum computational complexity polynomial in the entropy of the remaining black hole, commute with a complete set of logical operators acting on the encoded interior, up to corrections which are exponentially small in the entropy. Thus, under our pseudorandomness assumption, the black hole interior is well protected from exterior observers as long as the remaining black hole is macroscopic. On the other hand, if the radiation is not pseudorandom, an exterior observer may be able to create a firewall by applying a polynomial-time quantum computation to the radiation.