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
Category: physics
Introduction to AMP and the Replica Trick
(This post from the lecture by Yueqi Sheng) In this post, we will talk about detecting phase transitions using Approximate-Message-Passing (AMP), which is an extension of Belief-Propagation to “dense” models. We will also discuss the Replica Symmetric trick, which is a heuristic method of analyzing phase transitions. We focus on the Rademacher spiked Wigner model (defined below), … Continue reading Introduction to AMP and the Replica Trick
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
Quantum Games
Nilin Abrahamsen nilin@mit.edu Daniel Alabi alabid@g.harvard.edu Mitali Bafna mitalibafna@g.harvard.edu Emil Khabiboulline ekhabiboulline@g.harvard.edu Juspreet Sandhu jus065@g.harvard.edu Two-prover one-round (2P-1R) games have been the subject of intensive study in classical complexity theory and quantum information theory. In a 2P-1R game, a verifier sends questions privately to each of two collaborating provers , who then aim to respond … Continue reading Quantum Games
Towards Quantum PCP: A Proof of the NLETS Theorem
By Abhijit Mudigonda, Richard Wang, and Lisa Yang This is part of a series of blog posts for CS 229r: Physics and Computation. In this post, we will talk about progress made towards resolving the quantum PCP conjecture. We'll briefly talk about the progression from the quantum PCP conjecture to the NLTS conjecture to the … Continue reading Towards Quantum PCP: A Proof of the NLETS Theorem
Quantum Approximate Optimization Algorithm and Applications
Motivation Quantum computers have demonstrated great potential for solving certain problems more efficiently than their classical counterpart. Algorithms based on the quantum Fourier transform (QFT) such as Shor's algorithm offer an exponential speed-up, while amplitude-amplification algorithms such as Grover's search algorithm provide us with a polynomial speedup. The concept of "quantum supremacy" (quantum computers … Continue reading Quantum Approximate Optimization Algorithm and Applications
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 