The development of tailored materials for specific applications is an active field of research in chemistry, material science and drug discovery. The number of possible molecules obtainable from a set of atomic species grow exponentially with the size of the system, limiting the efficiency of classical sampling algorithms. On the other hand, quantum computers can provide an efficient solution to the sampling of the chemical compound space for the optimization of a given molecular property. In this work, we propose a quantum algorithm for addressing the material design problem with a favourable scaling. The core of this approach is the representation of the space of candidate structures as a linear superposition of all possible atomic compositions. The corresponding ‘alchemical’ Hamiltonian drives the optimization in both the atomic and electronic spaces leading to the selection of the best fitting molecule, which optimizes a given property of the system,e.g., the interaction with an external potential as in drug design. The quantum advantage resides in the efficient calculation of the electronic structure properties together with the sampling of the exponentially large chemical compound space. We demonstrate both in simulations and with IBM Quantum hardware the efficiency of our scheme and highlight the results in a few test cases. This preliminary study can serve as a basis for the development of further material design quantum algorithms for near-term quantum computers.