Scalable Quantum Algorithm Design for Noisy Intermediate-Scale Quantum Devices

Abstract

Designing quantum algorithms that scale gracefully with problem size on NISQ devices -- maintaining useful approximation quality as qubit count, circuit depth, and noise accumulation increase -- remains the central engineering challenge of the NISQ era. Current variational quantum algorithms face two fundamental scalability barriers: barren plateaus (exponentially vanishing gradients that prevent training of deep parameterised circuits) and noise accumulation (gate errors compounding with circuit depth, degrading output fidelity). This paper proposes the Scalable NISQ Algorithm Design (SNAD) framework, a systematic methodology for designing quantum algorithms that remain effective as problem scale increases, comprising four design principles and associated algorithmic techniques: locality-structured ansatz design (LSAD) to avoid barren plateaus through geometric locality constraints; adaptive noise budget allocation (ANBA) distributing gate operations to maximise fidelity within noise constraints; circuit compression and synthesis (CCS) reducing circuit depth through gate cancellation and re-synthesis; and scalability-aware performance prediction (SAPP) using classical simulation to predict NISQ performance at target scale before hardware execution. SNAD is validated on QAOA and VQE circuits across n = 12-84 qubits on IBM Quantum Eagle and Falcon. LSAD eliminates barren plateaus for n up to 84 qubits, maintaining gradient magnitude > 10^-3 where standard random ansatz shows < 10^-8 at n=48. CCS reduces circuit depth by 28.4% (SD = 4.8%) for QAOA circuits on heavy-hex topology. ANBA improves approximation ratio by 6.4pp vs. uniform depth allocation under fixed noise budget. SAPP predicts NISQ approximation ratios with mean error 3.2% (SD = 1.4%) across 284 circuits.