= Solution
Use a clean <quantum ancilla> and apply the <quantum circuit> $C$, then the <Pauli Z gate> on the ancilla, then the <inverse quantum circuit> $C^\dagger$:
$$
|x,0\rangle\xrightarrow{C}|x,f(x)\rangle
\xrightarrow{I\otimes Z}(-1)^{f(x)}|x,f(x)\rangle
\xrightarrow{C^\dagger}(-1)^{f(x)}|x,0\rangle.
$$
This <compute-phase-uncompute construction> implements $A\otimes I$ on every input with the ancilla initially $|0\rangle$, and by <linearity> on any superposition of those inputs. The action on ancilla-$|1\rangle$ inputs need not coincide with $A\otimes I$; the question only requires the clean-ancilla subspace.
Back to article page
