Quantum Newton method

oracq.algorithms.qnlss.newton

Implementation of the quantum Newton method (arXiv:2109.08470): the M_F data structure and the finite-difference Jacobian oracle.

The algorithm runs Newton iterations A dx = -F(x) round by round, with the linear solve and data loading using quantum building blocks:

• NewtonTree is the paper’s M_F: leaves store x_i and f_i(x), internal nodes store squared partial sums, and the angle cache is written into the bank under the RY half-angle convention; a single-point update only recomputes equations depending on that component.

• newton_fd_entry is O_A2 (paper Eq. 15-17): given (row, slot), it looks up the variable index via the pattern database O_f1 and fetches the variable value via the x database O_M1, adds delta to the selected variable, and calls the reversibly compiled f_row (O_f2) twice; the difference quotient (f(x+delta e_k)-f(x))/(delta*scale) is produced by compiled arithmetic; all work bits are cleaned via XOR.

• newton_b_preparation is O_b: a signed-residual angle tree prepares |b> = Σ f_i |i> / C_b.

The linear solve (Hermitian dilation + sparse QLSS), l_inf tomography, and norm recovery are assembled by newton_linear_step; semantic validation of all building blocks is in tests/core/test_newton.py.

class oracq.algorithms.qnlss.newton.NewtonFunction(functions, pattern)

Bases: object

Sparse nonlinear system F(x)=0: one pure-Python numeric function per equation with its dependency indices.

functions

pattern

classmethod declare(equations)

Declare a sparse nonlinear system from a sequence of (dependency indices, numeric function) pairs.

Parameters:

equations – A sequence of (indices, function) pairs; indices are the variable indices the equation depends on (in one-to-one correspondence with the positional parameters of function), and function is a pure-Python numeric function.

Returns:

The system description after dimension and sparse-dependency validation.

Return type:

NewtonFunction

Raises:

• ValidationError – The number of equations is not a power of 2, or some equation has duplicate or out-of-range indices.

• OSError – Source code is unavailable for some function (inspect.getsource; required for quantum compilation).

property size

Number of equations; the system is square, so this also equals the number of variables.

property width

Bit width of the variable (equation) index register, i.e. log2(size); declaration guarantees size is a power of 2.

property sparsity

the maximum number of variables a single equation depends on.

Type:

Sparsity

evaluate(x)

Classically evaluate F(x).

Parameters:

x – A real vector of length size.

Returns:

The equation function values f_i(x) in declaration order.

Return type:

list

jacobian(x, delta)

Finite-difference Jacobian (classical mirror, serving as an independent reference for the quantum oracle).

Parameters:

• x – A real vector of length size; the base point of the differences.

• delta – Forward-difference step; a nonzero real number.

Returns:

One sparse dictionary per row, keyed by column index with difference-quotient partials as values.

Return type:

list[dict[int, float]]

class oracq.algorithms.qnlss.newton.NewtonTree(function, x, *, fmt=None, angle_width=10, delta=0.015625)

Bases: object

The M_F data structure (classical side). The heap is 1-based: root at 1, leaves N..2N-1.

function

fmt

angle_width

delta

x

f

tree

banks

property norm_f

The current ||F(x)||_2; the tree root stores the sum of squares of the f_i(x).

update(delta_x)

x <- x + delta_x; only equations depending on changed components are recomputed (the local update of paper III D).

Parameters:

delta_x – Increment vector of the same length as x; zero components trigger no recomputation.

Returns:

The update result recording changed components, recomputed equations, and the updated ||F(x)||.

Return type:

NewtonPatch

pattern_memories()

O_f1 static tables: the full-permutation expansion of each row’s nonzero columns and its inverse (fuse(row, slot) bit order).

Returns:

The two static pattern tables pattern_forward and pattern_inverse, addressed in fuse(row, slot) bit order.

Return type:

dict[str, dict[int, int]]

memories()

Export all QRAM storage tables.

Returns:

Copies of the four data banks (x, f, f_sign, f_angles) plus the two pattern tables produced by pattern_memories; every table is a fresh copy, and modifying them does not affect the tree’s internal state.

Return type:

dict[str, dict[int, int]]

class oracq.algorithms.qnlss.newton.NewtonPatch(changed, recomputed, norm_f)

Bases: object

Record of one local update: changed components, recomputed equations, and the updated ||F(x)||.

changed

recomputed

norm_f

oracq.algorithms.qnlss.newton.newton_fd_entry(function, fmt, *, delta, max_scale)

O_A2: |row, slot>|0> -> |row, slot>|A_{row,slot}>, with A = F’/(delta*scale) semantics.

Each equation is statically specialized to its sparse dependencies (arity variables); the variable word selected by slot gets delta added before evaluating f_row, and the difference quotient is written into value via compiled arithmetic; status propagates arithmetic failures. All work bits (variable words, perturbed words, up/down function values, pattern/x lookups) are cleaned via XOR.

Parameters:

• function – The sparse nonlinear system being encoded.

• fmt – Fixed-point format of the variable words and function values.

• delta – Difference step; must be exactly representable and nonzero under fmt.

• max_scale – Upper bound on the difference-quotient scaling; its product with delta must also be exactly representable.

Returns:

A QRAM-style oracle operation returning difference-quotient matrix elements addressed by (row, slot).

Return type:

Operation

oracq.algorithms.qnlss.newton.newton_b_preparation(function, angle_width)

O_b (paper Eq. 13): signed-residual angle-tree preparation of |b> = Σ_i f_i(x)|i>/C_b.

Parameters:

• function – The sparse nonlinear system being encoded; determines the tree width and sign table addressing.

• angle_width – Quantization bit width of the residual angle tree’s rotation angles.

Returns:

Preparation handle of the signed residual state |b>.

Return type:

StatePreparation