Quantum supremacy

Can weak final-layer depolarizing noise make constant-depth two-dimensional Haar-random circuits classically samplable to inverse-polynomial total-variation error?

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

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 Gaussian permanent estimation task \(\#\mathrm P\)-hard under randomized polynomial-time oracle reductions?

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

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