Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2016/iii/paper-324/2/b/solution

Prepare an ancillary qubit in
It can be prepared from by an operation followed by a Hadamard gate, independently of . One call to the Boolean quantum oracle then gives quantum phase kickback:
The data state receives a minus sign precisely on the basis vectors spanning , while the ancilla remains unchanged and unentangled. One oracle call realizes the reflection. By linearity it is the marked-state phase oracle
with one oracle call. The ancillary preparation and its optional inverse use only fixed operations, so no additional knowledge of is needed.

New to topics? Read the docs here!