170 citations · 1.5k across the 46 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
quant-ph2013★ 6 cited
A Constructive Quantum Lovász Local Lemma for Commuting Projectors
Itai Arad, Or Sattath
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lovász Lo…
quant-ph2013★ 31 cited
The Quantum PCP Conjecture
Dorit Aharonov, Itai Arad, Thomas Vidick
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computation…
quant-ph2013
An area law and sub-exponential algorithm for 1D systems
Itai Arad, Alexei Kitaev, Zeph Landau +1
We give a new proof for the area law for general 1D gapped systems, which exponentially improves Hastings' famous result \cite{ref:Has07}. Specifically, we show that for a chain of…