An Exact and Practical Classical Strategy for 2D Graph State Sampling

Constant-depth quantum circuits that prepare and measure graph states on 2D grids are proved to possess a computational quantum advantage over their classical counterparts due to quantum nonlocality and are also well suited for demonstrations on current superconducting quantum processor architectures. To simulate the partial or full sampling of 2D graph states, a practical two-stage classical strategy that can exactly generate any number of samples (bit strings) from such circuits is proposed. The strategy is inspired by exploiting specific properties of a hidden linear function problem solved by the target quantum circuit, which in particular combines traditional classical parallel algorithms and an explicit gate-based constant-depth classical circuit together. A theoretical analysis reveals that on average each sample can be obtained in nearly constant time for sampling specific circuit instances of large size. Moreover, the feasibility of the theoretical model is demonstrated by implementing typical instances up to 25 qubits on a moderate field programmable gate array platform. Therefore, the strategy can be used as a practical tool for verifying experimental results obtained from shallow quantum circuits of this type.