  Sampling problems demonstrating beyond classical computing power with noisy
intermediate-scale quantum (NISQ) devices have been experimentally realized. In
those realizations, however, our trust that the quantum devices faithfully
solve the claimed sampling problems is usually limited to simulations of
smaller-scale instances and is, therefore, indirect. The problem of verifiable
quantum advantage aims to resolve this critical issue and provides us with
greater confidence in a claimed advantage. Instantaneous quantum
polynomial-time (IQP) sampling has been proposed to achieve beyond classical
capabilities with a verifiable scheme based on quadratic-residue codes (QRC).
Unfortunately, this verification scheme was recently broken by an attack
proposed by Kahanamoku-Meyer. In this work, we revive IQP-based verifiable
quantum advantage by making two major contributions. Firstly, we introduce a
family of IQP sampling protocols called the \emph{stabilizer scheme}, which
builds on results linking IQP circuits, the stabilizer formalism, coding
theory, and an efficient characterization of IQP circuit correlation functions.
This construction extends the scope of existing IQP-based schemes while
maintaining their simplicity and verifiability. Secondly, we introduce the
\emph{Hidden Structured Code} (HSC) problem as a well-defined mathematical
challenge that underlies the stabilizer scheme. To assess classical security,
we explore a class of attacks based on secret extraction, including the
Kahanamoku-Meyer's attack as a special case. We provide evidence of the
security of the stabilizer scheme, assuming the hardness of the HSC problem. We
also point out that the vulnerability observed in the original QRC scheme is
primarily attributed to inappropriate parameter choices, which can be naturally
rectified with proper parameter settings.
