  Recently, constant-depth quantum circuits are proved more powerful than their
classical counterparts at solving certain problems, e.g., the two-dimensional
(2D) hidden linear function (HLF) problem regarding a symmetric binary matrix.
To further investigate the boundary between classical and quantum computing
models, in this work we propose a high-performance two-stage classical scheme
to solve a full-sampling variant of the 2D HLF problem, which combines
traditional classical parallel algorithms and a gate-based classical circuit
model together for exactly simulating the target shallow quantum circuits.
Under reasonable parameter assumptions, a theoretical analysis reveals our
classical simulator consumes less runtime than that of near-term quantum
processors for most problem instances. Furthermore, we demonstrate the typical
all-connected 2D grid instances by moderate FPGA circuits, and show our
designed parallel scheme is a practically scalable, high-efficient and
operationally convenient tool for simulating and verifying graph-state circuits
performed by current quantum hardware.
