Random circuit sampling

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

Do computational-basis outputs of one-dimensional Haar-random circuits with fixed amplitude damping have conditional mutual information that decays exponentially with separation, uniformly in circuit depth?

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

Is the exact Haar-mixing spectral gap of uniformly random Pauli rotations equal to \(2^n(2^n-3)/(8(4^n-1))\) for every \(n\geq4\)?

• Quantum Algorithm
• Random circuit sampling
• Quantum circuit complexity

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