QNR Problem Offers a More Feasible NISQ Demo Than Large-Integer Factoring

A comparison argues that demonstrating quadratic non-residue (QNR) problems on today's noisy intermediate-scale quantum hardware is far more practical than factoring large integers. QNR is a decision problem that is BQP-complete and needs only a few qubits and shallow circuits, which makes it workable on cloud quantum platforms. Shor's factoring algorithm, by contrast, requires deep circuits that noise overwhelms, so on current machines it can only factor very small numbers such as 15 or 21. Real-world factoring of cryptographic-size numbers would need fault-tolerant quantum computers, and the QNR demo is better suited to showing quantum interference principles than to dramatic cryptographic breaks.