Average-case hardness of approximating probabilities for FLO circuits
Average-case hardness of approximating probabilities for FLO circuits
Let be a passive or active fermionic linear-optics circuit initialized in the state , let be a fiducial outcome, and let denote its output probability. Let be the Haar distribution, with for passive FLO circuits and for active FLO circuits. Average-case hardness conjecture. Computing a -multiplicative approximation to for a fraction of circuits sampled from is -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.