🔬 applied physics

Convolutional Formulation of Large-Scale Quadratic Unconstrained Binary Optimization with Dense Interactions

This paper introduces spatial quadratic unconstrained binary optimization (spQUBO), a convolutional formulation that enables efficient, multiplexing-free implementation of dense interaction problems on spatial photonic Ising machines while leveraging Fast Fourier Transforms for scalable computation.

Original authors: Hiroshi Yamashita, Hideyuki Suzuki

Published 2026-06-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hiroshi Yamashita, Hideyuki Suzuki

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive, complicated puzzle. You need to arrange thousands of pieces (let's call them "spins") to find the perfect pattern that solves a problem, like organizing a city or grouping photos. Usually, solving this requires a supercomputer to check every possible connection between every single piece. If you have 10,000 pieces, the number of connections explodes, making it incredibly slow and expensive.

This paper introduces a new way to think about these puzzles so that a special type of "optical computer" (called a Spatial Photonic Ising Machine, or SPIM) can solve them much faster.

Here is the breakdown of their idea using simple analogies:

1. The Problem: The "Dense Web" vs. The "Light Beam"

Think of the SPIM as a machine that uses light to solve puzzles. Light is amazing because it can do many things at once (parallelism). However, this machine has a limitation: it naturally sees connections between pieces based on how close they are to each other, like ripples in a pond.

The Old Way: To solve complex problems where pieces are connected in a messy, random way (a "dense web"), researchers had to use a trick called "multiplexing." Imagine trying to fit a giant, tangled ball of yarn into a small box by squishing it down. It works, but it takes up a lot of space and slows the machine down.
The Paper's Insight: The authors realized the machine doesn't actually need to squish the yarn. If you arrange the puzzle pieces in a specific, orderly way, the machine's natural "light vision" can solve them perfectly without any squishing.

2. The Solution: "Spatial QUBO" (The Grid City)

The authors invented a new way to write down these puzzles, which they call spQUBO (Spatial Quadratic Unconstrained Binary Optimization).

The Analogy: Imagine your puzzle pieces aren't just floating randomly in space; they are placed on a giant, perfect grid (like a city map with streets and avenues).
The Rule: In this new format, the "cost" or "interaction" between two pieces depends only on the distance between them. If two pieces are 3 blocks apart, they interact in the exact same way, no matter where they are on the map.
Why this helps: This "distance-based" rule is exactly what light does naturally. Light waves spread out in circles; they don't care about the specific identity of the objects, just how far apart they are. By forcing the puzzle into this "grid city" format, the optical computer can solve it using a single flash of light, without needing the slow "squishing" tricks.

3. The Magic Trick: Flattening the 3D World into 2D

Many real-world problems (like clustering data or placing facilities) happen in 3D or even higher dimensions. The SPIM, however, is a flat, 2D device (like a piece of paper).

The Paper's Claim: The authors proved a mathematical "magic trick." They showed that you can take any high-dimensional puzzle (even a 100-dimensional one) and flatten it onto a 2D grid without losing the "distance rules."
The Analogy: Imagine you have a 3D sculpture. Usually, you can't fit it on a 2D piece of paper. But this paper says: "If you cut the sculpture into thin slices and lay them out in a specific pattern on the paper, the 2D drawing still holds all the 3D information."
The Result: You can now take a complex, high-dimensional problem, flatten it onto the SPIM's 2D surface, and solve it instantly using light, all while keeping the "distance-based" structure intact.

4. Real-World Examples They Tested

The authors didn't just do math; they tested this on two specific types of problems:

The "Facility Placement" Problem: Imagine you are a city planner trying to decide where to put new coffee shops. You want them spread out so they don't compete (too close), but you also want them in good locations. The paper shows how to map this onto their grid so the light machine finds the best spots automatically.
The "Clustering" Problem: Imagine you have a huge photo album and want to sort photos into groups (e.g., "Beach," "Mountain," "Party"). The paper shows how to arrange these photos on the grid so the machine naturally groups similar ones together based on how "far" they are from each other in terms of content.

5. The Bonus: Faster Math on Regular Computers

Even if you don't have a fancy light machine, this new way of writing the puzzle helps regular computers too.

The Analogy: Usually, calculating the connections between all pieces is like checking every pair of people in a stadium (very slow). Because the authors' method relies on "distance rules," you can use a mathematical shortcut (called a Fast Fourier Transform) to calculate everything much faster. It's like realizing that instead of counting every person, you can just count the rows and columns and multiply.

Summary

The paper claims that by reformatting complex optimization problems into a "grid-based, distance-only" style (spQUBO), we can:

Unlock the full power of optical computers (SPIMs) to solve dense, complex problems without slowing them down.
Flatten high-dimensional problems onto a 2D surface efficiently.
Speed up calculations on both optical machines and regular digital computers using mathematical shortcuts.

They demonstrated this works for problems involving placing facilities and grouping data, proving that this "grid city" approach is a powerful new way to tackle hard optimization puzzles.

Technical Summary: Convolutional Formulation of Large-Scale Quadratic Unconstrained Binary Optimization with Dense Interactions

Problem Statement
Large-scale combinatorial optimization problems, often formulated as Quadratic Unconstrained Binary Optimization (QUBO) or Ising problems, face significant scalability challenges when implemented on hardware solvers. While the Spatial Photonic Ising Machine (SPIM) offers superior scalability for dense interactions through optical spatial parallelism, its primitive implementation is limited to representing coupling matrices of rank-one. Although multiplexed versions have been proposed to handle higher-rank interactions, they incur a multiplexing cost that reduces implementation efficiency. Furthermore, existing methods for mapping general QUBOs to SPIMs often fail to exploit the intrinsic spatial structures of real-world problems, leading to inefficient use of the optical hardware's spatial volume. The core challenge addressed is clarifying the intrinsic representation power of the non-multiplexed SPIM and identifying a formulation that allows efficient implementation of dense, structured interactions without sacrificing scalability.

Methodology
The authors introduce Spatial QUBO (spQUBO), a formulation of Ising problems where variables are associated with grid points in a $D$ -dimensional integer lattice, and interactions are defined by a spatially convolutional structure. In this framework, the coupling weight between two variables depends on their relative spatial position rather than arbitrary indices.

Key methodological components include:

spQUBO Definition: The problem is defined by a spatial coupling function $f(\mathbf{d}_i - \mathbf{d}_j)$ , where $\mathbf{d}_i$ represents the grid location of the $i$ -th variable. This structure naturally captures distance-based interactions.
Equivalence to SPIM: The authors demonstrate that the Hamiltonian of an idealized SPIM corresponds exactly to a two-dimensional periodic spQUBO. The coupling coefficients in the SPIM are determined by the discrete Fourier transform (DFT) of a reference image used in the optical setup.
Reduction Algorithm: A central contribution is a reduction algorithm that transforms any $D$ $D$ -dimensional spQUBO (whether periodic or not) into an equivalent two-dimensional periodic spQUBO. This is achieved by:
- Expanding the configuration domain with "padding" to resolve periodicity conflicts (where distinct relative positions map to the same periodic index).
- Mapping higher-dimensional grid coordinates to a 2D grid using a specific bijection that preserves the convolutional structure.
- The resulting spatial volume is determined by the product of the original dimensions plus the locality of the interaction function.
Computational Efficiency: The paper establishes that the convolutional structure of spQUBO allows for efficient numerical computation of the Hamiltonian and matrix-vector products using Fast Fourier Transforms (FFT), reducing computational complexity from $O(N^2)$ to $O(V \log V)$ , where $V$ is the spatial volume.

Key Contributions

Formulation of spQUBO: The paper defines a new class of QUBO problems characterized by spatially convolutional structures, explicitly linking them to the physical capabilities of the SPIM.
Theoretical Reduction: It proves that any spQUBO can be reduced to a 2D periodic spQUBO while preserving the convolutional structure, thereby enabling implementation on a single-shot SPIM without multiplexing.
Scalability Analysis: The authors provide a scaling analysis comparing spQUBO against spatial multiplexing and spin-pair mapping. They show that for problems with spatial structure and dense interactions, the spQUBO approach requires a significantly smaller spatial volume (SLM size) compared to generic mapping schemes, particularly as the interaction locality increases.
Numerical Validation: The study demonstrates the applicability of the framework through numerical examples of a placement problem (maximizing utility with distance-based penalties) and a clustering problem (minimizing intra-cluster distances). These problems are successfully mapped to 2D spQUBOs and solved using momentum annealing.

Results

Implementation Feasibility: The reduction algorithm successfully transforms complex, high-dimensional problems (e.g., 3D clustering) into 2D periodic forms suitable for SPIM hardware.
Performance Comparison: In numerical experiments, the proposed spQUBO approach required a spatial volume of approximately $1.4 \times 10^5$ for a clustering instance, whereas spatial multiplexing would require $2.4 \times 10^7$ and spin-pair mapping approximately $1.2 \times 10^7$ .
Computational Speed: Numerical comparisons of Hamiltonian computation times show that the FFT-based method for spQUBO scales significantly better with problem size ( $N$ ) than direct matrix-vector multiplication, confirming the theoretical efficiency gains.
Solution Quality: Approximate solutions obtained for placement and clustering problems exhibit expected behaviors, such as facilities being spaced to avoid utility loss and data points being grouped into distinct clusters.

Significance and Claims
The paper claims to advance the understanding of the specific class of optimization problems where SPIMs exhibit a unique advantage in efficiency and scalability. By clarifying that the SPIM's intrinsic power lies in handling dense interactions with convolutional structures, the work moves beyond the limitation of rank-one matrices without incurring the overhead of multiplexing.

The authors assert that the spQUBO formulation provides a foundational step for enhancing the applicability of SPIMs to practical, real-world problems that possess spatial or distance-based characteristics, such as facility placement, clustering, and image restoration. They emphasize that while the study focuses on an idealized SPIM to isolate the spatial volume constraints, the framework offers a systematic way to implement dense, high-dimensional problems on optical hardware. Furthermore, the paper highlights that the efficiency of spQUBO is not limited to optical hardware; the convolutional structure enables efficient computation on digital computers via FFT, suggesting broad utility for both hardware and software solvers. The work concludes that future research should explore the integration of spQUBO with multiplexing techniques and the application of statistical machine learning to exploit the reduced degrees of freedom in dense interaction models.