My iPhone 5s was shutting down automatically when it had 80% percent battery. Yesterday I restored it with iTunes and compatible firmware (6.1), now it shuts down at 73% battery.
What is the problem and how I can solve that?
You have essentially eliminated software as a cause by restoring the OS. If it happens consistently around the same percentage remaining, you likely have bad cells in the battery. Batteries cannot be repaired, so you must either have it replaced at an Apple Store or authorized repair center, or consider ordering parts and tools and doing it yourself if you have some technical proficiency (e.g., https://www.ifixit.com/Guide/iPhone+5s+Battery+Replacement/19239).
I had the same issue before. Most likely your iPhone's battery isn't calibrated correctly. Try to calibrate it. If the problem persists, then you have a bad battery, it's time to visit the Apple Store.