New Algorithm Swiftly Finds Optimal Solutions to Complex Classical Problems

Researchers are increasingly exploring quantum-inspired algorithms to tackle complex classical computational problems. Ryo Watanabe from the Graduate School of Engineering Science, The University of Osaka, Joseph Tindall of the Center for Computational Quantum Physics at the Flatiron Institute, and Shohei Miyakoshi and Hiroshi Ueda from the Center for Quantum Information and Quantum Biology at Osaka University, present a novel tensor-network approach for solving classical spin Hamiltonians. Their work, detailed in a new paper, utilises matrix product operators and draws inspiration from spectral filtering techniques used in quantum systems. This method offers a systematic pathway to improved optimisation, potentially circumventing the limitations of existing techniques like the density-matrix renormalization group, and demonstrates promising performance on challenging higher-order Ising Hamiltonians, establishing a valuable benchmark for future algorithm development.

This work introduces a method for efficiently identifying low-energy configurations in challenging energy landscapes, surpassing limitations found in conventional algorithms.

The core innovation lies in transforming a cost function, represented as an Ising Hamiltonian, into a matrix product operator and then systematically amplifying the lowest energy states through repeated contractions. This process effectively filters and enhances the desired solutions, allowing for accurate sampling within the computational basis.
Specifically, the study begins by shifting and scaling the Ising Hamiltonian to ensure all eigenvalues are non-negative, thereby aligning ground states with the largest eigenvalues. This transformed Hamiltonian is then expressed as a matrix product operator, a compact representation that facilitates efficient computation.

By repeatedly multiplying this operator with itself, a process akin to power iteration, the researchers create a massively amplified operator embedded within a matrix product state. This allows for direct sampling of potential solutions, offering a streamlined path to systematic improvement simply by increasing the bond dimension of the tensor network.

Unlike the density-matrix renormalization group, which can become trapped in local minima, this new approach demonstrates enhanced robustness in navigating complex energy landscapes. Numerical experiments conducted on both Edwards, Anderson spin glass models and higher-order Ising spin-glasses on heavy-hexagonal lattices reveal significant performance gains.

The powered-MPO method consistently identifies superior solutions compared to both simulated annealing and DMRG, even in instances with hundreds of variables. These results establish a promising baseline for developing and evaluating quantum-inspired algorithms for tackling computationally intensive optimization problems.

Ising Hamiltonian transformation and tensor network state preparation

A tensor-network approach underpinned this work, drawing inspiration from spectral filtering and sampling of states to address classical optimization problems. Researchers began by shifting and scaling an Ising Hamiltonian representing the cost function, ensuring all eigenvalues were non-negative and ground states corresponded to the largest eigenvalues.

Power iteration then amplified these ground states, preparing the Hamiltonian for representation as a matrix product operator (MPO). Subsequently, the transformed Hamiltonian underwent repeated MPO-MPO contractions, generating a massively powered operator. This operator was then embedded within a matrix product state, enabling sampling directly in the computational basis.

Unlike the density-matrix renormalization group, this methodology facilitates systematic improvement by simply increasing the bond dimension, while also mitigating the risk of becoming trapped in local minima. The performance of this power method was further investigated using a higher-order Ising Hamiltonian defined on a heavy-hexagonal lattice.

Results were compared against those obtained via simulated annealing, allowing for a direct assessment of the proposed technique’s efficacy. This comparison highlighted the potential of quantum-inspired algorithms for solving optimization problems and established a baseline for future algorithm development.

The study employed a positive semi-definite MPO representation of the cost function, constructing GK with K exceeding 1 to amplify low-energy configurations. This powered MPO, being diagonal in the computational basis, was efficiently transformed into an MPS for high-quality candidate solution extraction.

Benchmarking involved the Edwards, Anderson spin glass model on hypercubic lattices and higher-order Ising spin-glass models on the heavy-hexagonal lattice, a standard benchmark for quantum approximate optimization algorithms on IBM quantum devices. The powered-MPO approach consistently identified low-energy configurations even with hundreds of variables, demonstrating a more robust escape from local minima compared to DMRG sweeps.

Eigenvalue amplification and perfect sampling using powered matrix product states

Shifted and scaled Ising Hamiltonians enabled eigenvalue amplification via power iteration, forming the basis of a new tensor network approach to classical optimization. The research demonstrates a method for systematically improving solutions by increasing the bond dimension, avoiding the local minima often encountered in other algorithms.

Specifically, the study focuses on transforming a cost function Hamiltonian into a positive semi-definite form, allowing for the construction of a matrix product operator. Repeated multiplication of this operator, raising it to the Kth power with K exceeding 1, massively amplifies the lowest energy configurations.

This powered matrix product operator is then directly transformed into a matrix product state, facilitating perfect sampling within the computational basis. The work highlights the efficiency of this approach, which remains entirely Trotter-free and avoids the complexities of gate decompositions required by quantum imaginary time evolution methods.

Numerical experiments were conducted on Edwards, Anderson spin glass models on hypercubic lattices and higher-order Ising spin-glass models defined on the heavy-hexagonal lattice. Results indicate the powered-MPO approach reliably identifies low-energy configurations even with hundreds of variables. Comparisons with the density-matrix renormalization group reveal that the powered-MPO method exhibits more systematic improvement with increasing bond dimension, χ.

This contrasts with DMRG, which can stagnate in complex cost landscapes. Furthermore, the powered-MPO approach consistently identified superior solutions compared to simulated annealing in challenging instances where SA became trapped in suboptimal local minima. The study establishes a baseline for assessing and developing quantum-inspired algorithms for solving optimization problems.

Eigenvalue manipulation and powered matrix product operators for robust optimisation

A tensor network approach to solving classical optimization problems has been developed, drawing inspiration from spectral filtering and sampling techniques. The method transforms an Ising Hamiltonian by shifting and scaling its eigenvalues to ensure non-negativity and amplify ground states through power iteration.

Representing this transformed Hamiltonian as a matrix product operator, the framework utilises truncated contractions to embed the operator into a matrix product state, enabling sampling within the computational basis. This differs from density-matrix renormalization group methods by offering a systematic path to improvement via increased bond dimension and demonstrating greater resilience against local minima.

This powered-MPO framework benefits from the incorporation of heuristic strategies, such as applying single-qubit rotations to identified classical configurations, which effectively warm-starts the optimization process without introducing additional entanglement. The pipeline amplifies the weight of ground-state configurations through tensor contractions and truncation, resulting in a sampling distribution sharply peaked around optimal bit strings as the exponent on the cost function increases.

Compared with simulated annealing and density-matrix renormalization group, this approach consistently yields higher quality solutions, although it requires more computational steps to converge. The authors acknowledge that achieving exact solutions still requires overcoming high entanglement barriers and that the scaling of the required bond dimension across different problem types warrants further investigation.

Future research will focus on implementing parallel processing and leveraging the acceleration potential of graphics processing units to increase computational efficiency. Additionally, exploring lattice-specific tensor network architectures, such as tree and projected entangled-pair operator networks, could reduce bond dimension requirements for complex lattice topologies and improve the stability of truncation methods.