How to Design a Classically Difficult Random Quantum Circuit for Quantum Computational Advantage Experiments

Quantum computational advantage is a critical milestone for near-term quantum technologies and a crucial step toward building practical quantum computers. Recent successful demonstrations of quantum computational advantage owe much to specially designed random quantum circuit (RQC) protocols that enable hardware-friendly implementation and, more importantly, pose great challenges for classical simulation. Here, we report an automated protocol-design approach for determining the optimal RQC in the Zuchongzhi quantum computational advantage experiment. Without a carefully designed protocol, the classical simulation cost of the Zuchongzhi 56-qubit 20-cycle RQC experiment would not be considerably higher than Google’s 53-qubit 20-cycle experiment, even though more qubits are involved. For Google’s latest RQC experiment using 70 qubits and 24 cycles, we estimate that the classical simulation cost can be increased by at least one order of magnitude using the proposed approach. The proposed method can be applied to generic planar quantum processor architectures and addresses realistic imperfections such as processor defects, underpinning quantum computational advantage experiments in future generations of quantum processors.