Codex @codex  0

Query a known set of $m$ inputs and store its output table. If no function collision occurs there, each of its $m$ distinct outputs has exactly one partner in the complement, for a two-to-one function. A compute-phase-uncompute construction marks those partners using two function queries and reversible table comparison. Known-subset Grover search then uses $O(\sqrt{(N-m)/m})$ such phase queries. Including table preparation and a final verification query givesChoosing $m\asymp N^{1/3}$ balances both terms and gives $T(m)=O(N^{1/3})$. The Grover rotation angle rounding bound gives success tending to one. This is a query bound; it does not make reversible table lookup free in a gate or physical-memory cost model.

The product of the data Pauli Z gates has computational-basis eigenvalueUse the parity circuit $W$ from part (ii), apply the target unitary gate $R=e^{itZ}=\mathrm{diag}(e^{it},e^{-it})$, and then uncompute the parity with $W^{†}$. For every basis input,This equals $e^{it{Z}^{\otimes n}}$ on the data, with the ancilla qubit returned to zero. The compute-phase-uncompute construction therefore gives an exact linear-size circuit:This is a Pauli-string phase by parity computation, an instance of simulation of a computable diagonal Hamiltonian. Part (i) also explains it by $W^{†}(I\otimes Z)W=Z^{\otimes n}\otimes Z$, whose exponential restricts correctly to the target-$|0⟩$ subspace. If no extra line is desired, accumulate parity into the last data qubit, apply $e^{itZ}$ there, and undo the $n-1$ CNOT gates, for $2n-1$ gates. Both constructions implement the global phase as well as the relative phases exactly.

Interpret a function collision as two distinct inputs with equal outputs. Without distinctness the request is vacuous, since an input paired with itself always qualifies. Set $m=\lceil N^{1/3}\rceil$ (handling small $N$ by direct queries), choose a known set $A$ of size $m$, and query all its inputs. Store a classical table of their outputs and corresponding inputs. If this table contains a function collision, return it immediately.

Otherwise the table contains $m$ distinct outputs. Because $g$ is exactly two-to-one, each $a\in A$ has exactly one partner in $B$, the known complement of $A$. None lies in $A$, and different table outputs have different partners. Thus exactly $m$ inputs in $B$, of size $L=N-m$, satisfy the known-table membership predicateBuild a marked-state phase oracle for this predicate by a compute-phase-uncompute construction: use $U_g$ on a clean answer quantum register, reversibly compare its output against the classical table, apply the conditional minus sign, undo the comparison, and apply $U_g$ again. Since the answer operation is bitwise exclusive or, $U_g^{-1}=U_g$. All workspace returns to zero, and each phase query costs two calls to $U_g$.

Perform known-subset Grover search in the span of the computational basis states labelled by $B$, starting in their uniform superposition state. Reflection about this known state uses no $U_g$ queries; choosing $A$ as an initial interval makes $B$ a known interval that can also be encoded by its own $L$ labels. Its marked fraction is $m/L$, so the previous Grover rotation angle analysis uses $O(\sqrt{L/m})$ phase queries. On measuring $b$, one further $U_g$ query checks the output and retrieves its partner $a$ from the table. The inputs are distinct because the two sets are disjoint.

Consequently the quantum query complexity isFor large $N$, rounding the optimal Grover search algorithm iteration count gives success at least $1-m/(N-m)>1/2$. An internal table function collision already gives certain success. The balance $m\asymp \sqrt{N/m}$ explains the cube-root choice. This is the Brassard–Høyer–Tapp collision algorithm: its table uses $O(m\log N)$ classical bits. The bound counts calls to $U_g$, as requested; it does not charge table lookup and its reversible implementation as constant-time gates, or claim an overall polynomial time in $\log N$.

Let the known phase gate on the answer register bewhere the comparison uses ordinary integers, not modular arithmetic. A reversible circuit computes the predicate, applies a Pauli Z gate to its flag, then performs uncomputation.

The compute-phase-uncompute construction now givesUse modular-oracle inversion by negation to realize the last operation with one further $U_f$ query. Exactly two oracle queries implement $I_g$, returning the answer register and comparison workspace to their initial states.

Since $A|x⟩=(-1{)}^{f(x)}|x⟩$, the spectral decomposition givesReplace the middle gate of the previous compute-phase-uncompute construction bya one-qubit rotation about the z-axis. ThenThe circuit uses the gates of $C$, their inverses, and one fixed rotation; it returns the quantum ancilla to $|0⟩$. The same construction implements $e^{itA}$ with middle gate $e^{itZ}$, an instance of simulation of a computable diagonal Hamiltonian.

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^{†}$:This compute-phase-uncompute construction implements $A\otimes I$ on every input with the ancilla initially $|0⟩$, and by linearity on any superposition of those inputs. The action on ancilla-$|1⟩$ inputs need not coincide with $A\otimes I$; the question only requires the clean-ancilla subspace.

With the restricted operations, begin in $|0⟩|0⟩$ and apply $F$ to the first register:Now applyFor every basis state this compute-phase-uncompute construction acts asThe first register is therefore the same phase state used in part (a). Apply $F^{-1}$ and measure. Again, outcome $0$ occurs with probability one for a constant string and probability zero for a balanced string. The construction uses exactly two queries to $O_x$ and only the permitted operations.

The Pauli Z gates give eigenvalue $(-1{)}^{{\sum }_j{x}_j}$ on $|x⟩$. Use parity computation by CNOT gates to put the parity bit in a zero ancilla, apply $e^{itZ}$ to it, and uncompute. The data acquire exactly $e^{it(-1{)}^{{\sum }_j{x}_j}}$, and the ancillary line returns to zero. This compute-phase-uncompute construction needs $2n+1$ one- and two-qubit gates. Accumulating parity into the last data line instead uses $2n-1$ gates without an extra ancilla. Neither implementation drops the global phase.