  Decoherence of a quantum system arising from its interaction with an
environment is a key concept for understanding the transition between the
quantum and classical world as well as performance limitations in quantum
technology applications. The effects of large, weakly coupled environments are
often described as a classical, fluctuating field whose dynamics is unaffected
by the qubit, whereas a fully quantum description still implies some
back-action from the qubit on the environment. Here we show direct experimental
evidence for such a back-action for an electron-spin-qubit in a GaAs quantum
dot coupled to a mesoscopic environment of order $10^6$ nuclear spins. By means
of a correlation measurement technique, we detect the back-action of a single
qubit-environment interaction whose duration is comparable to the qubit's
coherence time, even in such a large system. We repeatedly let the qubit
interact with the spin bath and measure its state. Between such cycles, the
qubit is reinitialized to different states. The correlations of the measurement
outcomes are strongly affected by the intermediate qubit state, which reveals
the action of a single electron spin on the nuclear spins.
