量子计算在不久的将来的一个关键问题是,没有纠错的量子器件能否超出超级计算机的能力执行明确的计算任务。这种被称为量子优势的证明需要用经典方法来解决任务所需的资源的可靠评估。在这里,我们提出从随机量子电路的输出分布中取样的任务,作为量子优势的证明。我们扩展先前计算复杂度的结果,认为这个抽样任务必须在经典计算机中处于指数时间。我们引入交叉熵基准来获得复杂多位动态的实验保真度。这可以通过估计和外推来给出量子优势论证的成功指标。我们研究相关经典算法的计算成本,并得出结论:量子优越性可以通过7×7量子位和大约40个时钟周期的二维晶格中的电路来实现。这需要两个量子比特门(对于一个量子比特门为0.05%)的误差率约为0.5%,并且它将演示容错量子计算机的基本构建块。