Guest post by Abhishek Anand and Noah Miller from the physics and computation seminar. In 2013, Harlow and Hayden drew an unexpected connection between theoretical computer science and theoretical physics as they proposed a potential resolution to the famous black hole Firewall paradox using computational complexity arguments. This blog post attempts to lay out the … Continue reading Black hole paradoxes: A conservative yet radical journey
Tag: cs229r
Why physicists care about the Firewall Paradox
[Guest post by Noah Miller - a Harvard Physics Ph.D student that took our seminar. Noah's webpage contains wonderful and extensive notes that can be of interest to computer scientists. --Boaz] (The following blog post serves as an introduction to the following notes:) Black Holes, Hawking Radiation, and the Firewall There are many different types of "theoretical physicists." There are theoretical … Continue reading Why physicists care about the Firewall Paradox
Tensor Networks, Matrix Product States and Density Matrix Renormalization Group
In this note, we introduce the notions of tensor networks and matrix product states (MPS). These objects are particularly useful in describing quantum states of low entanglement.
We then discuss how to efficiently compute the ground states of the Hamiltonians of 1D quantum systems (using classical computers). The density matrix renormalization group (DMRG), due to White (1992, 1993), is arguably the most successful heuristic for this problem. We describe it in the language of tensor networks and MPS.
What is Quantum Hamiltonian Complexity?
by Ben Edelman This is the first installment of a three-part series of posts on quantum Hamiltonian complexity based on lectures given by the authors in Boaz and Tselil's seminar. The second installment is here, and the third installment is here. Quantum Hamiltonian complexity is a growing area of study that has important ramifications for … Continue reading What is Quantum Hamiltonian Complexity?
A 1D Area Law for Gapped Local Hamiltonians
(This post is based on part of a lecture delivered by Boriana Gjura and Prayaag Venkat. See also posts by Ben Edelman and Fred Zhang for more context on Quantum Hamiltonian Complexity.) Introduction In this post we present the Area Law conjecture and prove it rigorously, emphasizing the emergence of approximate ground state projectors as … Continue reading A 1D Area Law for Gapped Local Hamiltonians
Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code
by Jeremy Dohmann, Vanessa Wong, Venkat Arun Abstract We will discuss error-correcting codes: specifically, low-density parity-check (LDPC) codes. We first describe their construction and information-theoretical decoding thresholds, $latex p_{c}$. Belief propagation (BP) (see Tom's notes) can be used to decode these. We analyze BP to find the maximum error-rate upto which BP succeeds. After this … Continue reading Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code
Windows On Theory 