You could have a special "California tyre" which has a state approved logo on the side, and require all cars registered in the state use them.

They could be designed to last however many miles the state likes by putting more or less tread on them. And have a very obvious marker they are worn out so police can easily give tickets for people driving on worn out tyres.