Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Proceedings of the ACM on Programming Languages

CoTenN: Constrained Optimization with Tensor Networks

Ritvik Sharma, Cheng Peng, Siddharth Dangwal, Sara Achour

Published Jun 8, 2026• 0 citations
Publisher

Abstract

Simulation of physics problems is one of the most important use cases of quantum computing. For this class of problems, the goal is typically to find the minimum energy state, or the ground state, of a physical system’s Hamiltonian. These problems frequently have constraints, such as symmetry conditions, which must also be satisfied. To solve such problems, researchers in computational physics use quantum-inspired algorithms that execute on classical computers. In particular, tensor network-based eigensolvers such as DMRG have become popular. However, to use these eigensolvers, the constrained optimization problem must first be encoded as a tensor network that implements a low-rank decomposition of the system’s Hamiltonian and state vector. These tensor network encodings are highly flexible, allowing for variables with ≥2 quantum states and supporting efficient constraint encodings that directly constrain the state vector. A critical challenge to developing tensor networkbased encodings is that, currently, the encoding process is manual; significant effort is required to identify an efficient encoding for a new physics problem. In this work, we introduce a quantum constrained optimization problem (QCOP), a general abstraction for describing minimization problems over quantum variables that are subject to hard constraints. We present Masq , the first constraint programming language for QCOPs implementable with tensor networks, and CoTenN , a compiler that automatically maps QCOPs specified with Masq programs to tensor networks. To demonstrate the utility of Masq and CoTenN , we formulate two physics problems in Masq and then use CoTenN to find their ground states. We find the CoTenN -generated tensor networks generally outperform SOTA problem formulations, providing between 2.05 × − 53.32 × total speedups across runs for QCOPs and yielding up to 2.49 ⋅ 10 7 × lower truncation errors for otherwise unconstrained problems.

DOI
10.1145/3808272

Related papers

A Quantum-Inspired Tensor Network Algorithm for Constrained Combinatorial Optimization Problems

Tianyi Hao, Xu-Xin Huang, Chunjing Jia +1 more

Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.

arXiv:2203.15246•Frontiers in Physics•Jul 8, 2022•21 citations

Symmetric tensor networks for generative modeling and constrained combinatorial optimization

Javier Lopez-Piqueres, Jing Chen, Alejandro Perdomo‐Ortiz

Abstract Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form A x ⃗ = b ⃗ , directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems within the generator-enhanced optimization framework of Alcazar et al (2021 arXiv: 2101.06250 ). This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric matrix product states outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.

arXiv:2211.09121•Machine Learning Science and Technology•Jun 24, 2023•13 citations

Cons-training tensor networks: Embedding and optimization over discrete linear constraints

Javier Lopez-Piqueres, Jing Chen

In this study, we introduce a novel family of tensor networks, termed constrained matrix product states (MPS), designed to incorporate exactly arbitrary discrete linear constraints, including inequalities, into sparse block structures. These tensor networks are particularly tailored for modeling distributions with support strictly over the feasible space, offering benefits such as reducing the search space in optimization problems, alleviating overfitting, improving training efficiency, and decreasing model size. Central to our approach is the concept of a quantum region, an extension of quantum numbers traditionally used in U(1) U ( 1 ) symmetric tensor networks, adapted to capture any linear constraint, including the unconstrained scenario. We further develop a novel canonical form for these new MPS, which allow for the merging and factorization of tensor blocks according to quantum region fusion rules and permit optimal truncation schemes. Utilizing this canonical form, we apply an unsupervised training strategy to optimize arbitrary objective functions subject to discrete linear constraints. Our method’s efficacy is demonstrated by solving the quadratic knapsack problem, achieving superior performance compared to a leading nonlinear integer programming solver. Additionally, we analyze the complexity and scalability of our approach, demonstrating its potential in addressing complex constrained combinatorial optimization problems.

arXiv:2405.09005•SciPost Physics•Jun 17, 2025•5 citations

Riemannian geometry and automatic differentiation for optimization problems of quantum physics and quantum technologies

Ilia A Luchnikov, Mikhail E Krechetov, Sergey N. Filippov

Abstract Optimization with constraints is a typical problem in quantum physics and quantum information science that becomes especially challenging for high-dimensional systems and complex architectures like tensor networks. Here we use ideas of Riemannian geometry to perform optimization on the manifolds of unitary and isometric matrices as well as the cone of positive-definite matrices. Combining this approach with the up-to-date computational methods of automatic differentiation, we demonstrate the efficacy of the Riemannian optimization in the study of the low-energy spectrum and eigenstates of multipartite Hamiltonians, variational search of a tensor network in the form of the multiscale entanglement-renormalization ansatz, preparation of arbitrary states (including highly entangled ones) in the circuit implementation of quantum computation, decomposition of quantum gates, and tomography of quantum states. Universality of the developed approach together with the provided open source software enable one to apply the Riemannian optimization to complex quantum architectures well beyond the listed problems, for instance, to the optimal control of noisy quantum systems.

arXiv:2007.01287•New Journal of Physics•Jun 14, 2021•47 citations

Tensor quantum programming

A. Termanova, Artem A. Melnikov, Egor Mamenchikov +6 more

Abstract Running quantum algorithms often involves implementing complex quantum circuits with such a large number of multi-qubit gates that the challenge of tackling practical applications appears daunting. In this article, we propose a novel approach called Tensor Quantum Programming, which leverages tensor networks (TNs) for hybrid quantum computing. Our key insight is that the primary challenge of algorithms based on TNs lies in their high ranks (bond dimensions). Quantum computing offers a potential solution to this challenge, as an ideal quantum computer can represent tensors with arbitrarily high ranks in contrast to classical counterparts, which indicates the way towards quantum advantage. While tensor-based vector-encoding and state-readout are known procedures, the matrix-encoding required for performing matrix-vector multiplications directly on quantum devices is much less studied. We introduce an algorithm that encodes matrix product operators into quantum circuits with a depth that scales linearly with the number of qubits. We demonstrate the algorithm’s performance for matrices commonly encountered in differential equations, optimization problems, and quantum chemistry, for systems involving up to 50 qubits.

arXiv:2403.13486•New Journal of Physics•Nov 28, 2024•7 citations

Quick design of feasible tensor networks for constrained combinatorial optimization

Hyakka Nakada, Kotaro Tanahashi, Shu Tanaka

Quantum computers are expected to enable fast solving of large-scale combinatorial optimization problems. However, their limitations in fidelity and the number of qubits prevent them from handling real-world problems. Recently, a quantum-inspired solver using tensor networks has been proposed, which works on classical computers. Particularly, tensor networks have been applied to constrained combinatorial optimization problems for practical applications. By preparing a specific tensor network to sample states that satisfy constraints, feasible solutions can be searched for without the method of penalty functions. Previous studies have been based on profound physics, such as U(1) gauge schemes and high-dimensional lattice models. In this study, we devise to design feasible tensor networks using elementary mathematics without such a specific knowledge. One approach is to construct tensor networks with nilpotent-matrix manipulation. The second is to algebraically determine tensor parameters. We showed mathematically that such feasible tensor networks can be constructed to accommodate various types of constraints. For the principle verification, we numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods. Then, by performing imaginary time evolution, feasible solutions were always obtained, ultimately leading to the optimal solution.

arXiv:2409.01699•Quantum•Jul 21, 2025•2 citations
Simulation of physics problems is one of the most important use cases of quantum computing. For this class of problems, the goal is typically to find the minimum energy state, or the ground state, of a physical system’s Hamiltonian. These problems frequently have constraints, such as symmetry conditions, which must also be satisfied. To solve such problems, researchers in computational physics use quantum-inspired algorithms that execute on classical computers. In particular, tensor network-based eigensolvers such as DMRG have become popular. However, to use these eigensolvers, the constrained optimization problem must first be encoded as a tensor network that implements a low-rank decomposition of the system’s Hamiltonian and state vector. These tensor network encodings are highly flexible, allowing for variables with ≥2 quantum states and supporting efficient constraint encodings that directly constrain the state vector. A critical challenge to developing tensor networkbased encodings is that, currently, the encoding process is manual; significant effort is required to identify an efficient encoding for a new physics problem. In this work, we introduce a quantum constrained optimization problem (QCOP), a general abstraction for describing minimization problems over quantum variables that are subject to hard constraints. We present Masq , the first constraint programming language for QCOPs implementable with tensor networks, and CoTenN , a compiler that automatically maps QCOPs specified with Masq programs to tensor networks. To demonstrate the utility of Masq and CoTenN , we formulate two physics problems in Masq and then use CoTenN to find their ground states. We find the CoTenN -generated tensor networks generally outperform SOTA problem formulations, providing between 2.05 × − 53.32 × total speedups across runs for QCOPs and yielding up to 2.49 ⋅ 10 7 × lower truncation errors for otherwise unconstrained problems.
Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.
Abstract Constrained combinatorial optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In some heuristic solvers, these are typically addressed by introducing certain Lagrange multipliers in the cost function, by relaxing them in some way, or worse yet, by generating many samples and only keeping valid ones, which leads to very expensive and inefficient searches. In this work, we encode arbitrary integer-valued equality constraints of the form A x ⃗ = b ⃗ , directly into U(1) symmetric tensor networks (TNs) and leverage their applicability as quantum-inspired generative models to assist in the search of solutions to combinatorial optimization problems within the generator-enhanced optimization framework of Alcazar et al (2021 arXiv: 2101.06250 ). This allows us to exploit the generalization capabilities of TN generative models while constraining them so that they only output valid samples. Our constrained TN generative model efficiently captures the constraints by reducing number of parameters and computational costs. We find that at tasks with constraints given by arbitrary equalities, symmetric matrix product states outperform their standard unconstrained counterparts at finding novel and better solutions to combinatorial optimization problems.
In this study, we introduce a novel family of tensor networks, termed constrained matrix product states (MPS), designed to incorporate exactly arbitrary discrete linear constraints, including inequalities, into sparse block structures. These tensor networks are particularly tailored for modeling distributions with support strictly over the feasible space, offering benefits such as reducing the search space in optimization problems, alleviating overfitting, improving training efficiency, and decreasing model size. Central to our approach is the concept of a quantum region, an extension of quantum numbers traditionally used in U(1) U ( 1 ) symmetric tensor networks, adapted to capture any linear constraint, including the unconstrained scenario. We further develop a novel canonical form for these new MPS, which allow for the merging and factorization of tensor blocks according to quantum region fusion rules and permit optimal truncation schemes. Utilizing this canonical form, we apply an unsupervised training strategy to optimize arbitrary objective functions subject to discrete linear constraints. Our method’s efficacy is demonstrated by solving the quadratic knapsack problem, achieving superior performance compared to a leading nonlinear integer programming solver. Additionally, we analyze the complexity and scalability of our approach, demonstrating its potential in addressing complex constrained combinatorial optimization problems.
Abstract Optimization with constraints is a typical problem in quantum physics and quantum information science that becomes especially challenging for high-dimensional systems and complex architectures like tensor networks. Here we use ideas of Riemannian geometry to perform optimization on the manifolds of unitary and isometric matrices as well as the cone of positive-definite matrices. Combining this approach with the up-to-date computational methods of automatic differentiation, we demonstrate the efficacy of the Riemannian optimization in the study of the low-energy spectrum and eigenstates of multipartite Hamiltonians, variational search of a tensor network in the form of the multiscale entanglement-renormalization ansatz, preparation of arbitrary states (including highly entangled ones) in the circuit implementation of quantum computation, decomposition of quantum gates, and tomography of quantum states. Universality of the developed approach together with the provided open source software enable one to apply the Riemannian optimization to complex quantum architectures well beyond the listed problems, for instance, to the optimal control of noisy quantum systems.
Abstract Running quantum algorithms often involves implementing complex quantum circuits with such a large number of multi-qubit gates that the challenge of tackling practical applications appears daunting. In this article, we propose a novel approach called Tensor Quantum Programming, which leverages tensor networks (TNs) for hybrid quantum computing. Our key insight is that the primary challenge of algorithms based on TNs lies in their high ranks (bond dimensions). Quantum computing offers a potential solution to this challenge, as an ideal quantum computer can represent tensors with arbitrarily high ranks in contrast to classical counterparts, which indicates the way towards quantum advantage. While tensor-based vector-encoding and state-readout are known procedures, the matrix-encoding required for performing matrix-vector multiplications directly on quantum devices is much less studied. We introduce an algorithm that encodes matrix product operators into quantum circuits with a depth that scales linearly with the number of qubits. We demonstrate the algorithm’s performance for matrices commonly encountered in differential equations, optimization problems, and quantum chemistry, for systems involving up to 50 qubits.
Quantum computers are expected to enable fast solving of large-scale combinatorial optimization problems. However, their limitations in fidelity and the number of qubits prevent them from handling real-world problems. Recently, a quantum-inspired solver using tensor networks has been proposed, which works on classical computers. Particularly, tensor networks have been applied to constrained combinatorial optimization problems for practical applications. By preparing a specific tensor network to sample states that satisfy constraints, feasible solutions can be searched for without the method of penalty functions. Previous studies have been based on profound physics, such as U(1) gauge schemes and high-dimensional lattice models. In this study, we devise to design feasible tensor networks using elementary mathematics without such a specific knowledge. One approach is to construct tensor networks with nilpotent-matrix manipulation. The second is to algebraically determine tensor parameters. We showed mathematically that such feasible tensor networks can be constructed to accommodate various types of constraints. For the principle verification, we numerically constructed a feasible tensor network for facility location problem, to find much faster construction than conventional methods. Then, by performing imaginary time evolution, feasible solutions were always obtained, ultimately leading to the optimal solution.