Secure polynomial approximation is a fundamental operation in privacy-preserving computation. However, traditional secure multi-party computation protocols rely on computational complexity assumptions, which face threats from quantum computing and exhibit insufficient efficiency in high-dimensional data processing. To address these issues, this study proposes a secure polynomial approximation scheme under a semi-quantum and quantum fusion architecture, enabling multiple parties to collaboratively compute an optimal approximation polynomial while preserving the privacy of their individual functions. The framework consists of two core protocols. First, to overcome the vulnerability of traditional secure Chebyshev distance computation to quantum attacks, a semi-quantum secure multi-party Chebyshev distance computation protocol is designed. By integrating quantum key distribution and quantum state operations, a triple-encryption mechanism is established to achieve secure Chebyshev distance computation between any two parties. Second, a multi-dimensional quantum private query protocol is further developed, breaking the limitation of conventional single-value queries. Theoretical analysis demonstrates that the proposed framework satisfies information-theoretic security, with a controllable upper bound on the attacker’s success probability, while maintaining feasible communication and computational efficiency.