量子求和与积分

oracq.algorithms.common.integration

Heinrich quantum summation and numerical integration (FO + QRAM input model).

This implements the quantum summation primitive of Heinrich 2002, "Quantum Summation with an Application to Integration", J. Complexity 18(1), see also the quantum quadrature rate for function classes in Novak 2001, and assembles one-dimensional numerical integration from it. The input model is a function value loader (|i>|0> -> |i>|f(i)>), directly compatible with the three XorDatabase bindings of this repository, abstract, gate and qram.

Readout uses a comparator construction: the threshold register is put into a uniform superposition and compared with the function value, so the good-state probability is exactly E[v]/2**w, linear in v with no small-angle approximation needed; standard amplitude estimation on this marker gives a quadratic improvement in query complexity over classical Monte Carlo, O(1/ε) versus O(1/ε²).

class oracq.algorithms.common.integration.LoaderBundle(database, memory)

基类：tuple

Summation loader and its simulated memory; memory is empty for the gate binding.

database

Alias for field number 0

memory

Alias for field number 1

oracq.algorithms.common.integration.table_loader(values, data_width=None, *, backend='gate', name=None)

Wrap a nonnegative-integer function table into a summation loader.

参数:

• values -- Nonnegative integer sequence of f(0..N-1), its length zero-padded to a power of two.

• data_width -- Value word width w, by default the bit length of the maximum value; all values must be smaller than 2**w.

• backend -- "gate", a truth-table gate implementation, or "qram", a QRAM resource whose data table stays out of the IR.

• name -- Overrides the automatically generated module name.

返回:

database is an XorDatabase with address=index and data=value; for backend="qram" memory provides the memory table needed by simulate, otherwise it is empty.

返回类型:

LoaderBundle

oracq.algorithms.common.integration.sum_preparation(database, *, name=None)

State preparation for quantum summation: uniform index plus function value loading plus threshold comparison, with the flag=1 probability exactly E[v]/2**w.

Register layout: target = index(n) | threshold(w) | flag(1), work = value(w). The value word stays in work entangled with the index, since the comparator readout does not need it cleaned; flag is set by the first of the two comparator calls, and after marking on flag the caller should invoke this preparation in reverse to restore.

参数:

• database -- Function value loader; the address bit width is the index count and the data bit width is the function value bit width.

• name -- Name of the generated preparation module; generated automatically from the database and widths when omitted.

返回:

State preparation operation whose flag=1 probability is exactly E[v]/2**w.

返回类型:

Operation

oracq.algorithms.common.integration.sum_iterate(database)

Grover iterate for summation: structurally identical to grover_iterate, with the marking driven by the flag bit of the preparation target.

参数:

database -- Function value loader, determining the index count and the function value bit width the iterate acts on.

返回:

Grover iterate operation composed of the preparation, the flag phase marking and the zero reflection.

返回类型:

Operation

oracq.algorithms.common.integration.quantum_sum(database, *, precision=4, name=None)

Heinrich quantum summation: estimate the mean E[f] = (1/N) Σ_i f(i) where f takes w-bit nonnegative integer values.

参数:

• database -- Function value loader, an XorDatabase with address=index and data=value.

• precision -- Number of phase register bits, in the range 1..63; the estimation error is on the order of O(1/2**precision).

返回:

Registers target, work and phase. After reading out phase, decode the mean with mean_from_phase. The query complexity is O(1/ε), a quadratic improvement over the O(1/ε²) of classical Monte Carlo, Heinrich 2002.

返回类型:

Operation

oracq.algorithms.common.integration.mean_from_phase(value, precision, data_width)

Decode the phase readout of quantum_sum into the mean estimate E[v] in integer units.

The good-state probability is p = E[v]/2**data_width, hence E[v] = amplitude_from_phase * 2**data_width.

参数:

• value -- Integer count read out from the phase register.

• precision -- Number of phase register bits, which must match the quantum_sum setting.

• data_width -- Function value bit width, in 1..64.

返回:

Mean estimate E[v] in integer value units.

返回类型:

float

oracq.algorithms.common.integration.heinrich_rate(smoothness, dimension)

Optimal convergence rate for numerical integration or summation over a function class, with error ~ M^{-rate} for M function evaluations.

参数:

• smoothness -- Smoothness parameter s, for example the derivative order of a Hölder or Sobolev class; must be positive.

• dimension -- Dimension d; must be a positive integer.

返回:

deterministic is s/d, randomized is s/d + 1/2, and quantum is s/d + 1. The quantum rate is exactly a quadratic improvement over the randomized classical rate, Heinrich 2002 and Novak 2001.

返回类型:

dict

oracq.algorithms.common.integration.quantum_integral(database, *, precision=4, interval=1.0, name=None)

One-dimensional numerical integration: the quantum sum of function values at grid points multiplied by the interval length, the composite rectangle rule.

Function values are quantized to w-bit integers as v/full_scale, with full_scale defaulting to 2**data_width − 1. The total error equals the discretization error, determined by the grid and the smoothness, see heinrich_rate, plus the QAE estimation error. Decoding uses integral_from_phase. The interval length must be positive.

参数:

• database -- Loader of function values at grid points, address=index and data=value.

• precision -- Number of phase register bits, in the range 1..63; the estimation error is on the order of O(1/2**precision).

• interval -- Integration interval length; must be a positive real number.

• name -- Generated module name; generated automatically when omitted.

返回:

One-dimensional integration summation operation whose decoder is integral_from_phase.

返回类型:

Operation

oracq.algorithms.common.integration.integral_from_phase(value, precision, data_width, interval=1.0, full_scale=None)

Decode the phase readout of quantum_integral into the integral estimate.

Function values are quantized as v/full_scale, with full_scale defaulting to 2**data_width − 1; the integral estimate equals E[v]/full_scale × interval.

参数:

• value -- Integer count read out from the phase register.

• precision -- Number of phase register bits, which must match the quantum_sum setting.

• data_width -- Function value bit width, in 1..64.

• interval -- Integration interval length; must be a positive real number.

• full_scale -- Full-scale value of the function values; defaults to 2**data_width − 1.

返回:

The integral estimate over the interval.

返回类型:

float