We analyze different holographic complexity proposals for black holes that include corrections from bulk quantum fields. The specific setup is the quantum BTZ black hole, which encompasses in an exact manner the effects of conformal fields with large central charge in the presence of the black hole, including the backreaction corrections to the BTZ metric. Our results show that Volume Complexity admits a consistent quantum expansion and correctly reproduces known limits. On the other hand, the generalized Action Complexity fails to account for the additional contributions from bulk quantum fields and does not lead to the correct classical limit. Furthermore, we show that the doubly-holographic setup allows computing the complexity coming purely from quantum fields - a notion that has proven evasive in usual holographic setups. We find that in holographic induced-gravity scenarios the complexity of quantum fields in a black hole background vanishes to leading order in the gravitational strength of CFT effects.