(quantum Merlin Arthur) and QIP (quantum interactive polynomial time). The difficulty of proving what cannot be done with classical computing is a common problem in definitively demonstrating quantum supremacy. Contrary to decision problems that require yes or no answers, sampling problems ask for samples from probability distributions. If there is a classical algorithm that can efficiently sample from the output of an arbitrary quantum circuit, the polynomial hierarchy would collapse to the third level, which is generally considered to be very unlikely. Boson sampling is a more specific proposal, the classical hardness of which depends upon the intractability of calculating the permanent of a large matrix with complex entries, which is a #P-complete problem. The arguments used to reach this conclusion have been extended to IQP Sampling, where only the conjecture that the average- and worst-case complexities of the problem are the same is needed, as well as to Random Circuit Sampling, which is the task replicated by the Google and USTC research groups. Proposed experiments The following are proposals for demonstrating quantum computational supremacy using current technology, often called NISQ devices. Such proposals include (1) a well-defined computational problem, (2) a quantum algorithm to solve this problem, (3) a comparison best-case classical algorithm to solve the problem, and (4) a complexity-theoretic argument that, under a reasonable assumption, no classical algorithm can perform significantly better than current algorithms (so the quantum algorithm still provides a superpolynomial speedup). Shor's algorithm for factoring integers This algorithm finds the prime factorization of an n-bit integer in time whereas the best known classical algorithm requires time and the best upper bound for the complexity of this problem is . It can also provide a speedup for any problem that reduces to integer factoring, including the membership problem for matrix groups over fields of odd order. This algorithm is important both practically and historically for quantum computing. It was the first polynomial-time quantum algorithm proposed for a real-world problem that is believed to be hard for classical computers. Namely, it gives a superpolynomial speedup under the reasonable assumption that RSA, a well-established cryptosystem, is secure. Factoring has some benefit over other supremacy proposals because factoring can be checked quickly with a classical computer just by multiplying integers, even for large instances where factoring algorithms are intractably slow. However, implementing Shor's algorithm for large numbers is infeasible with current technology, so it is not being pursued