Fixed-Point Search¶

Category C2 · Module oracq.algorithms.common.qsvt · Stage V2

Overview¶

Fixed-point amplitude amplification: a search amplification that requires no advance knowledge of the initial amplitude and never overshoots from too many iterations. The construction follows the closed-form complementary polynomial of Yoder–Low–Chuang (cited in the source docstring): let \(L\) be the number of BE calls (it must be odd) and \(c = T_{1/L}(1/\delta)\); the complementary polynomial is \(Q(x) = \delta c\, R(c^2(1 - x^2))\) (\(R(u) = T_L(\sqrt{u})/\sqrt{u}\), an analytic polynomial), and \(P\) is obtained from the root-finding spectral decomposition of \(1 - (1 - x^2)Q^2\). The success probability achieved by the phase-sequence implementation is exactly

\[ P_S(x) = 1 - \delta^2\, T_L^2\!\bigl(c\sqrt{1 - x^2}\bigr), \]

so \(P_S \ge 1 - \delta^2\) whenever \(|x| \ge \sqrt{1 - 1/c^2}\), and the threshold decreases monotonically toward 0 as \(L\) grows (the fixed-point property).

Interface and input model¶

fixed_point_search_phases(delta, degree)
fixed_point_search(a, delta, degree)

API entry points: fixed_point_search_phases, fixed_point_search

fixed_point_search_phases: a purely numerical routine with no input model. delta is the error \(\delta \in (0, 1)\); degree is \(L\), which must be a positive odd number no greater than 20. Returns a tuple of phases in time order (length \(L + 1\)).
fixed_point_search: a is a BlockEncoding (input model BE); delta / degree as above. Returns a BlockEncoding whose zero-signal block is the complex polynomial \(P(A/\alpha)\), with success probability \(|P(x)|^2\) satisfying the YLC guarantee above.

Module attributes (fixed_point_search):

Attribute	Meaning
`algorithm`	`"fixed_point_search"`
`be_alpha`	normalization of the output BE (1.0 for this algorithm)
`delta` / `qsp_degree`	echo of the error parameter / \(L\)
`threshold`	amplification threshold \(\sqrt{1 - 1/c^2}\): for \(\|x\| \ge\) this value, the success probability is \(\ge 1 - \delta^2\)

Implementation notes¶

\(Q\) is expanded analytically from the odd Chebyshev coefficients plus powers of \((1 - x^2)\); the spectral decomposition of \(P\) uses Durand–Kerner root finding, clustering of repeated roots, and conjugate sign-flipped quadruple factors, with a factor-count self-check \(1 + 2\times(\text{factor count}) = L\); layer stripping then recovers the phases (same pipeline as QSP phase synthesis), with a self-check that \(|P(x)|^2\) and \(1 - (1 - x^2)Q(x)^2\) agree pointwise on a 512-point grid (an error above 1e-5 raises ValidationError).

This algorithm performs no real-part extraction: \(P\) itself is the target (\(|P| \le 1\) keeps the block encoding valid). The degree cap is 20 (half of the synthesis pipeline’s cap of 40). Applicability boundary: unlike Grover / amplitude amplification in search.py, which act on marked oracles, this entry point acts on the singular-value structure of a block encoding, and the spectral variable must lie in \([-1, 1]\).

Validation approach¶

Category C2 (approximate continuous semantics; acceptance criterion in ../../development/validation-plan.md §2). Three layers of evidence:

Structure: tests/core/test_qsvt.py:TransformWitnessTests.test_transform_input_validation (negative cases such as \(\delta \ge 1\) and even degrees).
Numerical: tests/core/test_qsvt.py:TransformWitnessTests.test_fixed_point_search_phase_properties — \(\delta = 0.4\), \(L \in \{3, 5, 7\}\): phase length \(L + 1\); a 400-point sweep gives \(|P(x)|^2 \le 1 + 10^{-9}\) and agrees pointwise with the YLC closed form \(1 - \delta^2 T_L^2(c\sqrt{1-x^2})\) (delta = 1e-5); above the threshold, \(P_S \ge 1 - \delta^2\); the threshold decreases monotonically with \(L\). test_fixed_point_search_circuit_amplifies — a 2×2 diagonal BE (\(\alpha = 0.6\), spectral variables 1.0 and \(1/6\)), \(\delta = 0.4\), \(L = 5\): the threshold attribute is cross-checked against \(\sqrt{1 - 1/c^2}\) (places = 3); the squared zero-signal amplitude in the circuit’s \(x = 1\) column is \(\ge 1 - \delta^2 - 10^{-9}\).
Binding: this algorithm has no independent binding witness (the input already requires a concrete BE).

Known gaps and planned stages¶

Consistent with the qsvt.py row of the validation coverage matrix: convergence scans are missing (batch curves of the threshold–error trade-off versus \(L\) are not automated, pending the convergence-scan framework of stage V2); the ill-conditioned negative cases (degree ≳ 16 or too-low precision) are partially covered by the parametrized input_validation tests, and a separate batch parametrization of “ill-conditioned inputs must raise” is still to be added.

Numerical validation¶

Experiment design: with \(\delta=0.3\) and \(L=5\) (threshold \(\sqrt{1-1/c^2}\approx0.3582\)), a diagonal block encoding encodes the scalar \(x\) into the zero-signal block (diagonal_block_encoding, both basis-state diagonal entries equal to \(x\)); the zero-signal success probability of the output BE of fixed_point_search is measured on the four backend paths (reference, rir-pysparq, adapter-pysparq, originir-ext) and compared against the YLC closed form \(P_S(x)=1-\delta^2 T_L^2(c\sqrt{1-x^2})\). Two spectral points sit on either side of the threshold: \(x=\cos(\pi/6)\approx0.8660\) (above the threshold, where \(P_S\ge1-\delta^2=0.91\) must hold) and \(x=0.3\) (below the threshold).

Case	Scale	Paths	Metric	Value
fixed-point-search-above-threshold	x=0.8660, δ=0.3, L=5	4 paths	success probability (closed form 0.991311) / error	0.991311 / 8.9e-16
fixed-point-search-below-threshold	x=0.3, δ=0.3, L=5	4 paths	success probability (closed form 0.772035) / error	0.772035 / 1.1e-16

The above-threshold instance satisfies the \(1-\delta^2\) guarantee (0.991311 ≥ 0.91), and the below-threshold instance still agrees pointwise with the closed form, showing that the success-probability curve of the phase-sequence implementation matches the theory across the whole spectral interval.

Reproduction command:

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_search_walks.py

Artifacts: out/verification/search_walks.json (cases fixed-point-search-above-threshold and fixed-point-search-below-threshold).