Quantum cryptanalysis of block ciphers with Grover’s search requires synthesis of round function, where the non-linear S-boxes dominate the circuit cost. Efficient quantum implementations of these S-boxes are a bottleneck for cryptanalysis. In this work, we address this problem and present two new generic strategies for synthesis of quantum circuit for large S-boxes that reduces the NISQ-era transpiled depth after decomposition into the hardware-agnostic universal basis gate set U+CX. First, we develop an ANF-based heuristic with global common subexpression elimination and layered scheduling. This approach leverages modest ancilla budgets to eliminate redundant computations and aggressively parallelise low-degree monomials, producing circuits that substantially reduce primitive as well as transpiled depth compared to the classical MMD baseline. Second, we introduce two-phase MILP-based, ancilla-aware synthesis framework for large S-boxes. Phase 1 determines which monomials will be synthesised globally, and how they are reused across outputs. This reduces redundancy and avoids high-degree terms that would lead to deep ladders. Phase 2 arranges the selected monomials into parallel layers. Here the solver explicitly accounts for ancilla usage, balancing the trade-off between fewer layers (smaller depth) and larger ancilla. MILP based synthesis show decisive, multi-fold reductions in transpiled depth in universal basis gate set U+CX. For SKINNY and ZUC S0 S-boxes, our synthesis reduces transpiled depth by factors of 18 and 9, respectively, with ancilla usage raised only to 10 and 13 qubits. For higher-degree S-boxes such as AES, SM4, and ZUC S1, we achieve 5 times reduction in transpiled depth by trading additional ancillas, increasing the budget from 5 to 22. To our knowledge, this is the first demonstration of MILP based ancilla-aware, globally optimised synthesis of 8-bit cryptographic S-boxes. By aligning primitive synthesis with transpiled cost, our methods establish a new baseline for depth-optimised resource estimation in the quantum cryptanalysis of symmetric primitives.