Consuming appropriate amounts of necessary nutrients is important for maintaining or improving general health. One of the healthiest dietaries in the world is the Mediterranean diet as it has been proven to be protective for many diseases in several clinical studies. In scope of this study, we present a service-oriented system to recommend a daily menu according to the Mediterranean diet by considering user's age, gender, weight, height, general health condition, eating habits and daily activities. We proposed a novel approach based on hybrid quantum genetic algorithm (HQGA) to generate the optimized diets. Quantum genetic algorithm (QGA) constitutes a powerful and essential technique for the optimization problems, but the traditional QGA does not have a high performance on a large search space. HQGA, which employs a local search operator; reaches the optimized solution faster, but is not suitable for solving multi-attribute decision-making problems (MADMPs). In this study, the local search operator in the traditional HQGA is improved to achieve better balance between 25 nutrients for solving the MADMPs. The United States Department of Agriculture National Nutrient Database has been used for the nutrition values and the Dietary Reference Intakes Tables of Health Canada has been used to determine the 25 nutrient's daily intake. The algorithm has been tested on 20 different user profiles and the optimized menus are produced with success rate between 97%-100%. Our study shows that, HQGA can be useful to recommend menus to maintain and improve the health conditions of people.