How to switch from a physics PhD. to complexity theory? Somewhere around the 3rd year of my physics PhD. program I came into this amazing subject of complexity theory. May be a motivating factor was that I was digging in my spare-time into this physics/complexity interface. Anyhow I took up courses in complexity theory and a few associated regions in the CS theory department in my university and I started attending one of the group meetings there and tried to contribute to a project (sadly the project turned out to be very hard and didn't move enough) 

But how do I actually go about finding a career in this subject? 
Either in academia or industry? 

I won't be taken seriously if I make a regular CS PhD. application because my background has no overlap with an usual CS grad student and neither am I interested in CS per se. (like I found the graduate "algorithms" course extremely boring though the mathematical algorithms part was fascinating where they did stuff like LP, SDP, entropy extraction, pseudorandomness etc.)  My interest is complexity theory and its interface with physics : which I see as a fascinating branch of mathematics! (and I do have quite a strong background in mathematics)
I would suggest you to continue studying in your physics Ph.D. program and successfully graduate. However, considering your interest in complexity theory (which I share with you, by the way, though, unfortunately, my math background is more limited than yours), I would advise to find a topic on the intersection of physics and complexity theory (aka complex systems) and write dissertation on that topic. That way will have a nice and flexible general physics education and, at the same time, you will stay motivated (which is extremely important for writing a dissertation) throughout the whole dissertation writing period. As for the complex systems field of study, please see my relevant question on Cross Validated site and references within. Good luck to both of us!