Quantum supremacy

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?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• IQP sampling

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\)?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• IQP sampling

Does there exist a fixed family of \(n\)-qubit circuit layouts with \(m=\operatorname{poly}(n)\) one- and two-qubit gates for which the following task is \(\#\mathrm{P}\)-hard?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• Random circuit sampling

Is the following estimation task \(\#\mathrm{P}\)-hard under randomized polynomial-time Turing reductions?

• Quantum algorithm
• Computational complexity and computability
• Quantum supremacy
• Boson sampling