3 ms·
> QC can only solve two problems more efficiently than classical (and this is proven very thoroughly) Do you mean those are the only two KNOWN problems? Other
by throwaway81523 5y ago
> QC can only solve two problems more efficiently than classical (and this is proven very thoroughly)
Do you mean those are the only two KNOWN problems? Otherwise the claim is very surprising. It is not even known whether QBP=P, I thought, while on the other hand there are some sampling problems in QBP that last I heard were thought to be outside PH (Aaronson and Arkhipov's boson sampling, and whatever the quantum supremacy crowd is currently doing). But, those are probably useless for cryptography.