The Internet of Vehicles (IoV) offers various services for road safety and user comfort. However, they face security vulnerabilities such as false data injections which need to be mitigated for public safety. The security solutions for IoV should have minimal processing delay and be scalable to deal with the large-scale IoV. While classical machine learning techniques have been adopted for malicious node detection in IoV, these solutions face computational challenges and scalability limitations. To deal with these challenges, in this paper, we propose a novel quantum-based MaxCut graph detection mechanism for identifying malicious nodes transmitting false messages in IoV. As validated by the performance evaluation results, the proposed quantum-based detection approach offers significantly lower data processing delay compared to the classical approach, especially as the data size increases.