We define the deconstruction cost of a tripartite quantum state on systems ABE as the minimum rate of noise needed to apply to the AE systems, such that there is negligible disturbance to the marginal state on the BE systems, while the system A of the resulting state is locally recoverable from the E system alone. We refer to such actions as deconstruction operations and protocols implementing them as state deconstruction protocols. State deconstruction generalizes Landauer erasure of a single-party quantum state as well the erasure of correlations of a two-party quantum state. We find that the deconstruction cost of a tripartite quantum state on systems ABE is equal to its conditional quantum mutual information (CQMI) I (A; B vertical bar E), thus giving the CQMI an operational interpretation in terms of a state deconstruction protocol. We also define a related task called conditional erasure, in which the goal is to apply noise to systems AE in order to decouple system A from systems BE, while causing negligible disturbance to the marginal state of systems BE. We find that the optimal rate of noise for conditional erasure is also equal to the CQMI I (A; B vertical bar E). State deconstruction and conditional erasure lead to operational interpretations of the quantum discord and squashed entanglement, which are quantum correlation measures based on the CQMI. We find that the quantum discord is equal to the cost of simulating einselection, the process by which a quantum system interacts with an environment, resulting in selective loss of information in the system. The squashed entanglement is equal to half the minimum rate of noise needed for deconstruction and/or conditional erasure if Alice has available the best possible system E to help in the deconstruction and/or conditional erasure task.