244 citations · 2.1k across the 51 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
quant-ph2020★ 2 cited
StoqMA vs. MA: the power of error reduction
Dorit Aharonov, Alex B. Grilo, Yupan Liu
StoqMA characterizes the computational hardness of stoquastic local Hamiltonians, which is a family of Hamiltonians that does not suffer from the sign problem. Although error reduc…
cs.CC2020
Two combinatorial MA-complete problems
Dorit Aharonov, Alex B. Grilo
Despite the interest in the complexity class MA, the randomized analog of NP, just a few natural MA-complete problems are known. The first problem was found by (Bravyi and Terhal,…