Why does the military provide the Head of State's honor guard? Why is the Head of State always accompanied by military personnel? Why don't the police escort the Head of State?
I do not know which country do you mean but I suppose that in most countries the head of state is guerded by special services, and not police, not the army. The ceremonial escort though may be by some special military units, but the actual protection do the special services.
The special services usually receive better training.
Note that in the USA, the people responsible for the President's security are The Secret Service. They are not military.
They can be viewed as a kind of Federal-level police. They used to be under the Treasury Department (with the IRS and the folks who make our money), rather than the FBI or Justice Department. In 2003 they got moved into the new Department of Homeland Security (along with a mishmash of other domestic security-related agencies that weren't politically powerfull enough to prevent it).
Piggybacking on what mgb said, it is necessary from a security standpoint that heads of state have a dedicated security force whose sole purpose is the protection of the head of state. Local police forces, or even national police forces, have conflicting agendas that can lower their focus. That said, the Secret Service (in the US) and their counterparts in other countries work with local security whenever the head of state travels.
In addition to the answers posted, a couple of common-sense answers come to mind. First, police aren't specifically trained for that job -- a head of state needs bodyguards, not law-enforcement officers. Second, police serve a city or other locality. A head of state would want one set of guards who traveled with them, rather than having a different set everyplace they went.