Any many of them were built by the state.
Many things have been done by the state. It doesn't mean it requires a state in order to come about. Can you really not conceive of roads being built by anything other than a state?
On anything other than the most local scale, they would only ever be built by large companies as profit-generators, charging a toll for access.
Then you would end up having to pay lots of different tolls for parts of the same journey, which would be very inefficient and annoying.
So either the companies would end up merging, or form a cartel, which one doesn't really matter, to have one unified toll system.
They would use force to prevent non-payers using their roads.
Rather than paying per use, they would instead charge an annual fee to anyone who ever wanted to use the roads.
And the end result is that you have a single effective monopoly taxing you to maintain the roads.
How different is that from a government?
The single most obvious question that anarchists never address is that if this is such an obviously better way of doing things, where are the examples?
Where are the successful modern-day anarchistic societies, that have all the technological and engineering improvements that 'normal' societies have, but without a central body ruling ultimately by the use or threat of force?
Oh, and doing a little more digging, state finacing of roads in the UK goes back further than 1555.
Pavage was a medieval toll for the maintenance or improvement of a road or street in England. The king by letters patent granted the right to collect it to an individual, or the corporation of a town, or to the "bailiffs and good men" of a neighbouring village.
Pavage grants can be divided into two classes:
Urban grants to enable the streets of a town (or its market place) to be paved. These represent the majority of grants.
Rural grants to enable a particular road to be repaired. These grants were mostly made in the 14th century, and largely for the great roads radiating from London, which were presumably those carrying the heaviest traffic.
The first grant was in 1249 for the Yorkshire town of Beverley, where the pavage was associated with the cult of St John of Beverley, and was ultimately made permanent. Another early one was for Shrewsbury in 1266 for paving the new market place, removed from the churchard of St Alkmund and St Juliana.
So for almost 800 years we've found that roads couldn't been maintained without state taxation.