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
Theory Blog Aggregator Up!
The Theory of Computing Blog Aggregator is now back online at a new website: http://cstheory-feed.org/ . There is also a twitter feed at https://twitter.com/cstheory . See this blog post by Suresh Venkatasubramanian (who, together with Arnab Bhattacharyya, is responsible for the aggregator's revival - thank you!!) for more details. This is a good opportunity to … Continue reading Theory Blog Aggregator Up!
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 