Codex @codex  0

Use the quantum Fourier transform convention $F_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{\omega }^{jk}|j⟩$, where $\omega =e^{2\pi i/N}$. Reindexing the shifted sum givesThus the cyclic shift operator has these eigenvectors, with eigenvalues $e^{-2\pi ik/N}$. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies $S=F_{N}D{F}_N^{†}$ with $D|k⟩={\omega }^{-k}|k⟩$.

For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant qubit. The required diagonal phase isso $D=P_{-1}\otimes P_{-i}$. The allowed-gate circuit is thereforeIn execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

The binary phase is $\varphi =0.i_1\cdots i_n={\sum }_{j=1}^n{i}_j{2}^{-j}$. ThereforeOn the phase register, apply the tensor product of phase gatesIts action on $|y⟩=|i_1\cdots i_n⟩$ is multiplication by $e^{2\pi i\varphi /M}$. Thus the positive-phase fractional power of a unitary operator is implemented by uncomputation after coherent phase estimation:HenceThe inverse phase-estimation circuit uses controlled powers of $U^{-1}$ built from the supplied inverse oracle, with all other quantum gates reversed. No phase-register measurement is made, so arbitrary superpositions are preserved and the ancilla qubits return to zero. The straightforward implementation uses $2(2^n-1)$ controlled-unitary queries plus the Fourier and phase circuitry; the arbitrary phase gates are accepted exactly as stipulated.

The branch convention matters. This construction uses the phase representative $0<\varphi <1$ specified here, corresponding to argument in $(0,2\pi )$. It implements that explicitly defined root, even for $\varphi >1/2$. The usual complex principal branch with argument in $(-\pi ,\pi ]$ would choose a different root on some eigenvalues. No substitution of that alternative branch is implicit.

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.

The operators $X_i$ act on different qubits and therefore commute, soSince $X=HZH$,The scalar $e^{-it}$ is a global phase. Thus each factor uses two Hadamard gates and one phase gate, and applying the factors in parallel or sequentially gives an exact quantum circuit of $\boxed{3n}$ elementary gates.

Each summand of $J_X$ acts on one qubit, while each summand $Z_i{Z}_j$ of $J_Z$ acts on two. Therefore $J=J_X+J_Z$ is a 2-local Hamiltonian. We haveSplit $t$ into $r$ steps of length $\delta =t/r$ and use the second-order product formulaFor one step, $\Lambda =O(\delta n^2)$ in the stated estimate, so the spectral-norm error is $O({\delta }^3{n}^6)$. The error bound for a product of unitary operators makes the total errorIt is therefore enough to choosewith $r$ also large enough that the small-step estimate applies.

All $Z_i{Z}_j$ terms commute. A factor $e^{-i\delta Z_i{Z}_j}$ uses a constant-size circuit of two controlled-NOT gates and one phase gate, up to a global phase, so one product-formula step costs $O(n^2)$ gates. The complete Hamiltonian simulation consequently has size

First construct a controlled unitary gate from the uncontrolled oracle. Keep the supplied $|v_0⟩$ in a reference register. Controlled on an extra qubit, swap the data and reference registers, query $U$ on the register that contains $|v_0⟩$ in one branch, and swap back. Because $U|v_0⟩=|v_0⟩$, that branch is unchanged, while the other branch acquires $U$ on the data. Reversing the control convention with Pauli X gates gives controlled-$U$. The reference state is returned unchanged, and each use costs one query to $U$ and $O(n)$ controlled-SWAP gates.

Expand $|b⟩={\sum }_j{b}_j|v_j⟩$ in an eigenbasis of $U$. Exact quantum phase estimation with an $m$-qubit phase register producesApply the available phase gates, controlled by the corresponding bits of $c_j$, to multiply branch $j$ byThen reverse phase estimation. Although no $U^{†}$ oracle was supplied, every eigenvalue obeys ${\lambda }_j^{2^m}=1$, so $U^{-q}=U^{2^m-q}$. The inverse controlled powers can therefore be implemented with forward calls to $U$. Since $2^m=\mathrm{poly}(n)$, phase estimation and its inverse use only $\mathrm{poly}(n)$ queries. The phase register returns to $|0^m⟩$, while the data register isAs a direct check, the same spectral promise implies $U^{†}=U^{2^m-1}$.

Write $b={\sum }_{j=0}^{m-1}{2}^j{b}_j$. Applying the phase gateto qubit $b_j$ contributes $\exp (2\pi i{2}^j{b}_j/Q)$. The product of these $m$ gates is thereforeSimilarly, for $a={\sum }_j{a}_j{2}^j$ and $b={\sum }_k{b}_k{2}^k$, apply a controlled phase gatebetween every pair $(a_j,b_k)$. The accumulated phase isThe $m^2$ controlled phase gates implement

A Hamiltonian operator has perfect transfer between basis states $|a⟩,|b⟩$ at time $t_{\ast }$ if $e^{-iH{t}_{\ast }}|a⟩=e^{i\chi }|b⟩$ for a known global phase $\chi$. In an excitation-conserving qubit network whose vacuum is fixed, the initial product state with $\alpha |0⟩+\beta |1⟩$ at site $a$ and zeros elsewhere evolves to $\alpha |\mathrm{vac}⟩+\beta e^{i\chi }|b⟩$. A local phase gate at $b$ removing $\chi$ restores the unknown qubit there. This explains why transfer of the single-excitation basis state suffices for qubit transfer when the vacuum phase is also accounted for.

Choose eigenphase representatives $0\le {\varphi }_j<1$ for a unitary operator $U$ and a positive integer $M$. Its positive-phase fractional power acts on each eigenstate by $e^{2\pi i{\varphi }_j/M}$. This branch uses arguments in $[0,2\pi )$ and can differ from the usual complex principal branch using $(-\pi ,\pi ]$. For exactly dyadic phases, exact quantum phase estimation stores each label in a coherent phase register; bitwise phase gates multiply it by the required phase, and inverse phase estimation removes the labels. Keeping the phase register unmeasured preserves arbitrary eigenstate superpositions and resets the ancilla qubits. With only controlled-$U$ and controlled-$U^{-1}$ primitives, the direct method uses $2(2^n-1)$ oracle calls for $n$ exact phase bits.

Prepare a qubit in $|+⟩$, apply a phase gate $P(\varphi )=\mathrm{diag}(1,e^{i\varphi })$, and correlate its computational basis states with normalized environment states $|e_0⟩,|e_1⟩$. Write $⟨e_0|e_1⟩=v{e}^{i\alpha }$. After a final Hadamard gate, the environment amplitude accompanying output zero is $(|e_0⟩+e^{i\varphi }|e_1⟩)/2$. Its squared norm is $P_0=[1+v\cos (\varphi +\alpha )]/2$. Thus $v$ is the interference visibility, while $\alpha$ shifts the fringe. This quantum decoherence map commutes with the phase gate, so placing it immediately before that gate gives the same probabilities.