= Solution
Prepare an ancillary <qubit> in
$$
|-\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2},\qquad X|-\rangle=-|-\rangle.
$$
It can be prepared from $|0\rangle$ by an $X$ operation followed by a <Hadamard gate>, independently of $g$. One call to the <Boolean quantum oracle> then gives <quantum phase kickback>:
$$
U_g|x\rangle|-\rangle=(-1)^{g(x)}|x\rangle|-\rangle.
$$
The data state receives a minus sign precisely on the basis vectors spanning $\mathcal G$, while the ancilla remains unchanged and unentangled. \b[One oracle call realizes the reflection]. By linearity it is the <marked-state phase oracle>
$$
\boxed{I_{\mathcal G}=\sum_x(-1)^{g(x)}|x\rangle\langle x|=I-2\Pi_{\mathcal G}}
$$
with one oracle call. The ancillary preparation and its optional inverse use only fixed operations, so no additional knowledge of $g$ is needed.
Back to article page
