Average-case hardness of approximating probabilities for FLO circuits

Let VV be a passive or active fermionic linear-optics circuit initialized in the state Ψin>\left|\Psi_{\mathrm{in}}\right>, let x0\mathbf{x}_0 be a fiducial outcome, and let px0(V,Ψin)p_{\mathbf{x}_0}(V,\Psi_{\mathrm{in}}) denote its output probability. Let ν\nu be the Haar distribution, with (C,ν)=(Cpas,νpas)(C,\nu)=(C_{\mathrm{pas}},\nu_{\mathrm{pas}}) for passive FLO circuits and (C,ν)=(Cact,νact)(C,\nu)=(C_{\mathrm{act}},\nu_{\mathrm{act}}) for active FLO circuits. Average-case hardness conjecture. Computing a (1/4+o(1),1/(8C))(1/4+o(1),1/(8C))-multiplicative approximation to px0(V,Ψin)p_{\mathbf{x}_0}(V,\Psi_{\mathrm{in}}) for a 1/(8C)1/(8C) fraction of circuits VV sampled from ν\nu is #P\#\mathrm{P}-hard. This conjecture supplies the average-case hardness assumption needed to convert the sampling-to-computation theorem into a classical hardness result for fermionic sampling; its resolution is not established in the source.

Sources & referencesView supporting material

Primary source

Michał Oszmaniec, Ninnat Dangniam, Mauro E. S. Morales and Zoltán Zimborás, “Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states”, arXiv:2012.15825 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.