Yes, we can use frozen cauliflower to make this shahi gobhi subzi. Make sure to carefully cook the frozen cauliflower so that it does not become mushy.