To enable the accelerated discovery of materials with desirable properties, it is critical to develop accurate and efficient search algorithms. Quantum annealers and similar quantum-inspired optimizers have the potential to provide accelerated computation for certain combinatorial optimization challenges. However, they have not been exploited for materials discovery due to absence of compatible optimization mapping methods. Here we show that by combining cluster expansion with a quantum-inspired superposition technique, we can lever quantum annealers in chemical space exploration for the first time. This approach enables us to accelerate the search of materials with desirable properties 20 times faster over the Metropolis algorithm, with an increase in acceleration factor up to 150 for large systems. Levering this, we search chemical space and find a promising previously unexplored chemical family of Ru-Cr-Mn-Sb-O$_2$. The best catalyst in this chemical family show a mass activity 8 times higher than state-of-art RuO$_2$ and maintain performance for 180 hours while operating at 10mA/cm$^2$ in acidic 0.5M H$_2$SO$_4$ electrolyte.