Designing compact and efficient quantum circuits that are compatible with Noisy Intermediate-Scale Quantum (NISQ) hardware remains a central challenge in quantum computing. Most existing optimization approaches rely on fidelity-based fitness functions that require computing the full unitary matrix of the circuit. However, this quickly becomes computationally intractable beyond 10–12 qubits due to the exponential memory and time complexity \(O(2^{2n})\) . In this work, we propose a scalable multi-objective genetic algorithm for quantum circuit optimization tailored to NISQ devices. Although evolutionary algorithms have demonstrated strong potential for circuit synthesis, current methods generally depend on full-unitary fidelity evaluation, which severely limits scalability. To address this bottleneck, we introduce two complementary strategies: (1) an independent block-based evaluation using graph partitioning, and (2) an overlapping sliding-window decomposition approach. Both strategies reduce computational complexity from \(O(2^{2n})\) to \(O(2^{2k})\) , where \(k \ll n\) , making it possible to optimize circuits with more than 20 qubits in practice. Our methods are integrated into the NSGA-II multi-objective framework, enabling simultaneous optimization of fidelity, circuit depth, and gate cost, while maintaining structural compatibility with NISQ hardware–without requiring full-unitary simulation. Experimental results on benchmark circuits demonstrate high fidelity (above 0.94 for small circuits up to 8 qubits, above 0.85 for medium-scale circuits of 10–16 qubits, and above 0.80 for large-scale circuits up to 32 qubits), up to \(45\%\) reduction in circuit depth, and a \(10\times\) speedup compared to exact evaluation at 14 qubits.
