Jordan Quantum Gradient Estimation

English · 简体中文

Category C3 · Module oracq.algorithms.optimization.gradient · Stage V1

Overview

Estimates the gradient \(\nabla f\) of a \(d\)-dimensional real function \(f\) at a given point. Implementation basis: Jordan 2005 (PRL 95, 050501), with the scaling convention matching the generalization of Gilyén–Arunachalam–Wiebe 2019: the phase oracle implements

\[ O\,|x\rangle = e^{2\pi i \cdot N \cdot f(x)}\,|x\rangle, \qquad N = 2^{m}, \]

where each coordinate takes an \(m\)-bit fixed-point grid (the integer value \(k\) corresponds to the grid point \(x = k/N\)). When \(f\) is approximately linear on the grid, a single oracle call writes \(N \cdot \partial f/\partial x_i\) into the Fourier basis of the \(i\)-th coordinate register; after a per-coordinate inverse QFT all \(d\) components are read out at once, while a classical deterministic evaluation of the same gradient requires \(O(d)\) function queries.

Interface and input model

gradient_estimation(oracle, *, dimension, grid_bits)

API entry point: gradient_estimation

• oracle: a PhaseOracle or a phase-oracle operation with a target signature, input model FO (phase oracle); its phase_scale attribute must equal \(2^{\text{grid\_bits}}\), otherwise it raises as an INPUT_PROMISE violation.

• dimension: the grid dimension \(d\), range 1..16.

• grid_bits: the bits per coordinate \(m\), range 1..32; the total width \(d \cdot m\) must not exceed 64.

The oracle’s three construction entry points: abstract_phase_oracle(name, width, *, phase_scale) (an open declaration, with the implementation left for bind), gate_phase_oracle(width, angles, *, phase_scale, name=None) (an explicit phase table, whose length must be \(2^{\text{width}}\)), and function_phase_oracle(source, *, dimension, grid_bits, fmt=None, scale=None, ...) (compiles \(f\) via mathfunc arithmetic and then applies phase kickback).

Returns an Operation with register target (width \(d \cdot m\)). After readout, decode with gradient_from_readout(value, *, dimension, grid_bits): the \(i\)-th component interprets the bit segment \([i \cdot m, (i+1) \cdot m)\) as two’s complement and divides by \(2^m\). Module attributes:

Attribute	Meaning
algorithm	"jordan_gradient"
readout_register / decoder	"target" / "gradient_from_readout"
dimension / grid_bits	the dimension \(d\) and the bits per coordinate \(m\)
oracle_queries / classical_queries	1 / O(dimension)

Implementation notes

The generation chain is: prepare a uniform superposition over all coordinate registers → a single call to the phase oracle → apply inverse_qft(grid_bits) to each coordinate bit segment. The register layout is the single target, with the \(i\)-th coordinate occupying the segment \([i \cdot m, (i+1) \cdot m)\); there is no work register, and the arithmetic work bits inside function_phase_oracle are restored after the phase kickback by the inverse call.

Design decision: the phase-scaling convention (phase_scale == 2**grid_bits) is checked at generation time rather than implicitly assumed, and the oracle width must also equal \(d \cdot m\); both mismatches raise ValidationError at generation time. function_phase_oracle defaults to the fixed-point format FixedFormat(grid_bits+12, grid_bits+8) and requires a signed format with fraction ≥ grid_bits so that the grid coordinates are represented exactly.

Applicability boundary: the readout components are distinguishable only mod 1 (the phase \(e^{2\pi i N a j}\) is the same for \(a\) and \(a \pm 1\)), so the witnesses use components with \(|\partial f/\partial x_i| < 1/2\); larger gradients require the caller to pre-scale \(f\). When \(f\) deviates from linearity, the readout peak broadens around the true value, and the failure probability decays at an approximately quadratic rate as the grid is refined (see the validation approach).

Validation approach

Category C3 (probability-distribution semantics; acceptance criteria in ../development/validation-plan.md §2): the output distribution must equal the closed-form expectation. Three layers of evidence:

• Structure: tests/core/test_gradient.py:GradientTests.test_invalid_inputs_fail_at_generation covers all entry-point violations — out-of-range dimension / bit counts, oracle-width mismatch, phase-table length mismatch, non-positive phase_scale, out-of-range readout values, etc.

• Numerical: test_linear_function_exact_two_dimensions — for a linear function (components \(3/16\) and \(-2/16\), \(m = 4\)) the readout distribution lands deterministically on the encoded values (probability 1.0, places = 12) and the decoding equals the gradient exactly; test_function_phase_oracle_from_mathfunc — the mathfunc path \(f(x) = 0.25x\) recovers the component \(0.25\) exactly; test_perturbed_linear_concentrates_with_grid_bits — for \(f(x) = ax + x^2/N^2\) (\(a = 3/8\)) at \(m = 3, 4, 5\) the peak position stays at the true value, the success probability rises monotonically, and the failure-probability decay rate is asserted as \(q_{m+1} \le 0.34 \cdot q_m\) (under the phase perturbation \(o(1/N)\) the out-of-peak leakage converges approximately quadratically; measured ratios 0.292 / 0.268).

• Binding: test_abstract_oracle_binds_to_gate_implementation — after the abstract declaration is bound via bind to the gate phase table, the readout decoding agrees with the direct construction, covering declaration/implementation two-layer consistency.

Known gaps and planned stages

No known gaps; the stage-V1 witnesses are complete (exact linear readout + the mathfunc path + the failure-probability decay-rate assertion \(q_{m+1} \le 0.34 \cdot q_m\), measured 0.292 / 0.268 + binding consistency).

Related links

• Source: src/oracq/algorithms/optimization/gradient.py

• API reference: quantum gradient estimation

• Validation matrix: Validation coverage matrix

Numerical validation

tests/verification/verify_estimation.py performs readout-level numerical validation of this interface on real backends (11 cases in total, all passing). Experiment design:

• Exact linear readout: gate_phase_oracle phase tables, \(d=1\) (\(m=3,4,5\), gradient components \(3/8\), \(-5/16\), \(9/32\)), \(d=2\) (\(m=4\)), \(d=3\) (\(m=3\)); the readout distribution must land deterministically on the encoded values.

• mathfunc phase oracle: function_phase_oracle compiles \(f(x)=0.25x\) (\(d=1,m=4\)) and \(f(x_0,x_1)=0.25x_0-0.125x_1\) (\(d=2,m=3\)), also compared against central finite differences (for linear functions they agree with the truth exactly, gap \(0\)). The workspace of this path is budgeted at \(1768\) / \(1638\) qubits by workspace_table, exceeding the 24-qubit OriginIR budget, so it runs only on the three register-level paths reference / rir-pysparq / adapter-pysparq.

• Perturbed-linear convergence: \(f(x)=ax+x^2/N^2\) (\(a=3/8\)), \(m=3,4,5\); the peak position stays at the true value, and the failure-probability decay rate is compared against the approximately-quadratic-convergence criterion; the informational metric gives the central finite difference at \(x=1/2\) (which differs from the linear coefficient by \(O(1/N^2)\) when \(f\) is nonlinear).

• Backend paths: reference, rir-pysparq, adapter-pysparq, originir-ext (gate phase-table cases, total width \(\le 9\) qubits).

Case	Scale	Path	Value
linear readout (gate table)	\(d=1\), \(m=3,4,5\)	all four paths	decode error \(=0\), peak probability \(=1\)
linear readout (gate table)	\(d=2\), \(m=4\); \(d=3\), \(m=3\)	all four paths	decode error \(=0\), peak probability \(=1\)
mathfunc oracle	\(d=1,m=4\); \(d=2,m=3\)	ref/rir/adp	decode error \(=0\), peak probability \(=1\), consistent with finite differences
perturbed convergence	\(d=1\), \(m=3,4,5\)	all four paths	success probabilities \(0.9588/0.9880/0.9968\), decay rates \(0.2922/0.2678\) (\(<0.34\)); finite differences \(0.3906/0.3789/0.3760\to 0.375\)

Reproduction command:

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

Artifact path: out/verification/estimation.json (case names prefixed jordan-).