I don't think they are 100% strict about having BS physics. I thought about doing physics grad school with just a math degree, plus one extra physics class and some engineering classes, like electromagnetism, and self-studying some stuff. Talked to some profs and they thought it would be okay, as long as I did well on the entrance exams. That's with math/EE background, though. It would be harder with something that doesn't teach you enough of the physics. It may be true that computer skills could be valuable, but you still have to know physics to make it through. And furthermore, it would be hard to make a case that you have those skills based only on self-study. You need recommendation letters, preferably from physics profs.
Ed Witten was a history major. Turns out his dad was a physicist, so that fact isn't quite as surprising as it might seem without that other bit of info. Plus, it may have been a sort of an unorthodox and lucky admissions decision. I'm not sure exactly what Witten brought to the table, but whatever it was, it worked out!
So, yes, they will accept computer science or information science, but only under extraordinary circumstances. Maybe if you got a minor in physics. Why wouldn't you just study physics? If you want a back-up plan in case physics doesn't work out, a double major is good, or maybe a minor, plus devoting a large amount of thought and planning into stuff like networking/career counseling and so on.