Physics & Computation Blog Post Round-up

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:

• Statistical Physics: an introduction in two parts (by Tselil Schramm)

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

• Belief Propagation and the Stochastic Block Model (by Thomas Orton)
• Introduction to AMP and the Replica Trick (by Preetum Nakkiran and Yueqi Sheng)

Informational and computational phase transitions:

• Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code (by Jeremy Dohmann, Vanessa Wong, and Venkat Arun)

Proving the existence of phase transitions:

• Ising Perceptron under Gaussian Disorder, and k-NAE-SAT (based on a guest lecture by Nike Sun, as scribed by Patrick Guo, Vinh-Kha Le, Shyam Narayanan, and David Stoner)

 Using convex relaxations to approximate partition functions:

• Approximating Partition Functions (based on a guest lecture by Andrej Risteski as scribed by Alex Kelser, Alex Lin, Amil Merchant, and Suproteem Sarkar)

Quantum Computation

Background on Quantum Hamiltonians and tensor network representations:

• What is Quantum Hamiltonian Complexity? (by Ben Edelman)
• Tensor Networks, Matrix Product States and Density Matrix Renormalization Group (by Fred Zhang)

Area laws:

• A 1D Area Law for Gapped Local Hamiltonians (by Boriana Gjura and Prayaag Venkat)

Quantum algorithms:

• Introduction to Quantum Walks (by Beatrice Nash)
• Efficient preparation of thermal states of quantum systems: natural or artificial (based on a guest lecture by Aram Harrow as scribed by Sinho Chewi, William S. Moses, Tasha Schoenstein, Ary Swaminathan)
• Quantum Approximate Optimization Algorithm and Applications (by
  Amir Karamlou)

Quantum games and quantum PCPs:

• Towards Quantum PCP: A Proof of the NLETS Theorem (by Abhijit Mudigonda, Richard Wang, and Lisa Yang)
• Quantum Games (by Nilin Abrahamsen, Daniel Alabi, Mitali Bafna, Emil Khabiboulline, and Juspreet Sandhu)

Quantum supremacy:

• Quantum circuits and their role in demonstrating quantum supremacy (by Hikari Sorensen)

Quantum error correction:

• Peter Shor on Quantum Error Correction (based on a guest lecture by Peter Shor as scribed by Annie Wei)

Black Holes and the Firewall Paradox

(See also Boaz’s introductory post)

Background on black holes and the Firewall Paradox:

• Why physicists care about the Firewall Paradox (by Noah Miller)
• Black hole paradoxes: A conservative yet radical journey (by Abhishek Anand and Noah Miller)

Firewall Paradox meets Computational Complexity:

• Black Holes, a complexity theory perspective (by Chi-Ning Chou and Parth Mehta)