Topic
IQP sampling
2 records: 2 unsolved, 0 solved. Filter the catalog by this topic →
-
Average-case approximation hardness of random Ising partition functions
Is it \(\#\mathrm{P}\)-hard to approximate \(|Z_R|^2\) to relative multiplicative error \(a+o(1)\) on a \(b\) fraction of random Ising instances?
Unsolved -
Average-case approximation hardness of squared normalized gaps of random cubic polynomials
Is it \(\#\mathrm{P}\)-hard to approximate \(\operatorname{ngap}(f)^2\) to relative multiplicative error \(a+o(1)\) on a \(b\) fraction of uniformly random degree-3 polynomials over \(\mathbb{F}_2\)?
Unsolved