Informal supremacy conjecture for random quantum circuits
Informal supremacy conjecture for random quantum circuits
Below, random circuit sampling (RCS) means sampling from the output distribution of a random circuit. Here denotes the number of qubits, and multiplicative error is measured relative to the amplitudes being approximated.
Informal supremacy conjecture. Approximating to multiplicative error most amplitudes of most quantum circuits is a -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
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.