45 citations · 280 across the 30 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
quant-ph2009★ 25 cited
A Quantum Lovasz Local Lemma
Andris Ambainis, Julia Kempe, Or Sattath
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria.…
quant-ph2009
On the power of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg +3
In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their…