Verification of BosonSampling Devices
summary
BosonSampling uses N identical photons through an M‑mode linear optical network so output probabilities equal the permanent of N×N submatrix amplitudes, giving complexity evidence that exact classical sampling would collapse the polynomial hierarchy. Experiments verify 3–4 photons; scaling stalls because all N photons must arrive simultaneously, but a practical workaround is scattershot boson sampling with many heralded SPDC sources. Verification avoids computing permanents by using row‑norm estimators and collision statistics; main open problems: robust average‑case hardness and interactive verification.
AI-written summary · about