244 citations · 2.1k across the 51 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
quant-ph2022★ 78 cited
A polynomial-time classical algorithm for noisy random circuit sampling
Dorit Aharonov, Xun Gao, Zeph Landau +2
We give a polynomial time classical algorithm for sampling from the output distribution of a noisy random quantum circuit in the regime of anti-concentration to within inverse poly…
cs.CC2022
Translationally Invariant Constraint Optimization Problems
Dorit Aharonov, Sandy Irani
We study the complexity of classical constraint satisfaction problems on a 2D grid. Specifically, we consider the complexity of function versions of such problems, with the additio…