Scalable multi-objective genetic algorithm for quantum circuit optimization
Roumaissa Ghlib, Rania Bouhadouza, Faicel Hnaien · Scientific Reports · 2026
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 [Formula: see text]. 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 [Formula: see text] to [Formula: see text], where [Formula: see text], 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 [Formula: see text] reduction in circuit depth, and a [Formula: see text] speedup compared to exact evaluation at 14 qubits.