Function Optimization#

This module provides algorithms for finding minima and maxima of functions encoded as MPS. Unlike eigensolvers in seemps.optimization, which find ground states of Hamiltonians, these methods locate extrema of scalar functions represented in the QTT format.

Finding extrema with optima_tt#

The core algorithm is based on the optima_tt method [RSO22], which performs a probabilistic search through the exponentially large index space of an MPS. The key insight is that, for a canonicalized MPS, the tensor at the orthogonality center contains information about which indices contribute most to the state norm.

The algorithm traverses the MPS tensors sequentially, at each step retaining only the num_indices most promising index combinations based on their contribution to the overall amplitude. By keeping a fixed number of candidates at each step, the computational cost scales linearly with the number of sites rather than exponentially with the grid size.

The optimize_mps() function wraps this algorithm to find both the minimum and maximum values:

from seemps.analysis.optimization import optimize_mps
from seemps.analysis.mesh import RegularInterval
from seemps.analysis.factories import mps_sin

# Create an MPS representing sin(x) on [0, 2π]
n = 10  # 2^10 = 1024 grid points
interval = RegularInterval(0, 2 * 3.14159, 2**n)
mps = mps_sin(interval)

# Find minimum and maximum
(i_min, y_min), (i_max, y_max) = optimize_mps(mps, num_indices=100)
print(f"Minimum: {y_min:.6f} at index {i_min}")
print(f"Maximum: {y_max:.6f} at index {i_max}")

The num_indices parameter controls the trade-off between accuracy and computational cost. Larger values increase the probability of finding the global optimum but require more computation.

Binary search for monotone functions#

For monotone functions (either increasing or decreasing), the binary_search_mps() function provides an efficient method to find the index where the function crosses a given threshold. This is useful for computing inverse functions or finding roots of shifted functions.

from seemps.analysis.optimization import binary_search_mps

# Find index where function crosses threshold 0.5
# Assumes the MPS represents an increasing function
index = binary_search_mps(mps, threshold=0.5, increasing=True)

The search environments can be precomputed and cached for efficiency when performing multiple searches on the same MPS with different thresholds.

API reference#

optimize_mps(mps[, num_indices, make_canonical])

Returns the minimum and maximum values of a given MPS, together with their indices.

optima_tt(mps[, num_indices, ...])

Returns a set of k indices representing k potentially maximum in modulo values of the MPS.

binary_search_mps(mps, threshold[, ...])

Performs a binary search for the smallest MPS index whose value crosses the given threshold.

See also#