(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
Quantum circuits and their role in demonstrating quantum supremacy
There's a lot of discussion and (possibly well-deserved) hype nowadays about quantum computation and its potential for computation at speeds we simply can't reach with the classical computers we're used to today. The excitement about this has been building for years, even decades, but it's only very recently that we've really been approaching a solid … Continue reading Quantum circuits and their role in demonstrating quantum supremacy
Looking a postdoc opportunity?
This is the season that people are applying for postdoc positions. Unlike student and faculty hiring, which each have a fairly fixed schedule, postdoc availability can change from time to time, with new opportunities opening up all the time. So, I encourage everyone looking for a postdoc position to periodically check out https://cstheory-jobs.org/ . (For … Continue reading Looking a postdoc opportunity?
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
Introduction to Quantum Walks
author: Beatrice Nash Abstract In this blog post, we give a broad overview of quantum walks and some quantum walks-based algorithms, including traversal of the glued trees graph, search, and element distinctness [3; 7; 1]. Quantum walks can be viewed as a model for quantum computation, providing an advantage over classical and other non-quantum walks … Continue reading Introduction to Quantum Walks
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.
Efficient preparation of thermal states of quantum systems: natural or artificial
Cross-posted from https://wsmoses.com/blog/2018/12/18/boaz/Lecturer: Aram HarrowScribes: Sinho Chewi, William S. Moses, Tasha Schoenstein, Ary SwaminathanNovember 9, 2018OutlineSampling from thermal states was one of the first and (initially) most important uses of computers. In this blog post, we will discuss both classical and quantum Gibbs distributions, also known as thermal equilibrium states. We will then discuss Markov chains … Continue reading Efficient preparation of thermal states of quantum systems: natural or artificial
Windows On Theory 