Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 58 2 b Solution Created 2026-10-03 Updated 2026-10-14
Write , which is real and satisfies for . The invariant two-dimensional span has orthonormal eigenvectorswith eigenvalues and . In this basis,Transfer therefore requires the two evolved eigenphases to differ by an odd multiple of :The first positive time isEquivalently, exponentiating on the invariant span gives the full evolutionAt this is , so the requested global phase can be chosen as modulo . Since the two vectors are linearly independent, their relative coefficient cannot produce exact transfer at an earlier positive time. This is continuous-time quantum search, with time proportional to the square root of the search-space dimension for fixed . Restoring units multiplies the stated time by . The degenerate zero-qubit case would already have , so there would be no smallest positive transfer time; the formula concerns the nontrivial search.
Past exam of the mathematics course of the University of Cambridge 2007 iii Paper 58 2 d Solution Created 2026-10-03 Updated 2026-10-14
An oracle can recognize a solution without disclosing it in advance. If an efficiently evaluable or black-box predicate has the promised unique marked input, write exactly for that input. A Boolean quantum oracle computes this predicate reversibly asIts diagonal projector on the search register is . To implement a selectable phase, compute into a zero quantum ancilla, apply a known phase to its component, and uncompute. The search register then undergoesThis requires evaluation access to the predicate, not classical knowledge of which input passes it. The term is known from the Hadamard transform. With Hamiltonian-oracle access, or by controlled short-time simulations of the two terms, their sum can realize continuous-time quantum search.
The unknown projector is supplied through an oracle or a physically encoded recognition rule. It cannot be manufactured for an arbitrary hidden with no such input-dependent resource. The oracle assumption and the fixed energy scale are essential when interpreting the square-root search time as a computational advantage.