Informal supremacy conjecture for random quantum circuits

Below, random circuit sampling (RCS) means sampling from the output distribution of a random circuit. Here nn denotes the number of qubits, and multiplicative error is measured relative to the amplitudes being approximated.

Informal supremacy conjecture. Approximating to 1/poly(n)1/\operatorname{poly}(n) multiplicative error most amplitudes of most quantum circuits is a #P\#P-hard problem.

This is the informal computational-hardness claim underlying quantum computational supremacy and motivates proving average-case hardness for random circuit sampling. The supplied text does not state whether the conjecture has been resolved.

Sources & referencesView supporting material

Primary source

Ramis Movassagh, “Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling”, arXiv:1810.04681 (2018).

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.