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

arXiv:2511.02739

Efficient Variational Quantum Algorithms for the Generalized Assignment Problem

Carlo Mastroianni, Francesco Plastina, Jacopo Settino, Andrea Vinci

quant-phcs.ETSubmitted Nov 4, 2025• Announced Nov 5, 2025• 0 citations
arXivHTMLPDF

Abstract

Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.

Comments
9 pages, 15 figures

Related papers

Solving Constrained Optimization Problems Using Hybrid Qubit-Qumode Quantum Devices

Rishab Dutta, Brandon Allen, Chuzhi Xu +8 more

Variational Quantum Algorithms (VQAs) provide a promising framework for tackling complex optimization problems on near-term quantum hardware. Here, we demonstrate that hybrid qubit-qumode quantum devices offer an efficient route to solving Quadratic Unconstrained Binary Optimization (QUBO) problems using the Echoed Conditional Displacement Variational Quantum Eigensolver (ECD-VQE). Leveraging circuit quantum electrodynamics (cQED) architectures, we encode QUBO instances across multiple qumodes weakly coupled to a single qubit and extract binary solutions directly from photon-number measurements. We apply ECD-VQE to the Binary Knapsack Problem and show that it outperforms the Quantum Approximate Optimization Algorithm (QAOA) implemented on conventional qubit circuits, achieving higher-quality solutions with dramatically fewer resources. We also demonstrate that ECD-VQE can be extended to chemically motivated tasks such as active-space selection for multireference electronic structure methods. These results highlight the utility of hybrid qubit-qumode platforms for a broad class of NP-hard and chemistry-related optimization problems and demonstrate that variational ECD ansatz can realize expressive state preparation with significantly shallower circuits than qubit-only architectures, positioning qubit-qumode gates as compelling candidates for constrained optimization in early fault-tolerant quantum computing.

arXiv:2501.11735•Journal of Chemical Theory and Computation•May 14, 2026•0 citations

Solving constrained optimization problems via the variational quantum eigensolver with constraints

Thinh Viet Le, Vassilis Kekatos

Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks, including solving optimization problems. Nonetheless, optimization problems with constraints may not have been handled in a disciplined fashion thus far. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed the variational quantum eigensolver with constraints (VQEC) that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically constrained binary optimization problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function, we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.

Physical Review A•Aug 20, 2024•15 citations

Enhancing computational accuracy with parallel parameter optimization in variational quantum eigensolver

Daisuke Tsukayama, Jun‐ichi Shirakashi, Tetsuo Shibuya +1 more

Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.

AIP Advances•Jan 1, 2025•8 citations

Using Variational Quantum Algorithm to Solve the LWE Problem

Lihui Lv, Bao Yan, Hong Wang +4 more

The variational quantum algorithm (VQA) is a hybrid classical-quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions.

Entropy•Oct 8, 2022•9 citations

Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE

Thinh Viet Le, Vassilis Kekatos

Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. Nonetheless, enforcing constraints in a disciplined fashion has been largely unexplored. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically-constrained binary optimization (QCBO) problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs (LP) over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function (PMF), we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.

arXiv:2311.08502•Nov 14, 2023•4 citations

Neural-network-encoded variational quantum algorithms

Jiaqi Miao, Chang‐Yu Hsieh, Shi‐Xin Zhang

We introduce a general framework called neural-network- (NN) encoded variational quantum algorithms (VQAs), or NNVQA for short, to address the challenges of implementing VQAs on noisy intermediate-scale quantum (NISQ) computers. Specifically, NNVQA feeds input (such as parameters of a Hamiltonian) from a given problem to a neural network and uses its outputs to parameterize an ansatz circuit for the standard VQA. Combining the strengths of NN and parameterized quantum circuits, NNVQA can accelerate the training process of VQAs and handle a broad family of related problems with varying input parameters with the pretrained NN. To concretely illustrate the merits of NNVQA, we present results on a NN variational quantum eigensolver (VQE) for solving the ground state of parameterized $XXZ$ spin models in one and two dimensions. Our results demonstrate that NNVQE is able to estimate the ground-state energies of parameterized Hamiltonians with high precision without fine tuning, and significantly reduce the overall training cost to estimate ground-state properties across the phases of the given Hamiltonian. We also employ an active learning strategy to further increase the training efficiency while maintaining prediction accuracy. These encouraging results demonstrate that NNVQAs offer an alternative hybrid quantum-classical paradigm to utilize NISQ resources for solving more realistic and challenging computational problems.

arXiv:2308.01068•Physical Review Applied•Jan 26, 2024•25 citations
Quantum algorithms offer a compelling new avenue for addressing difficult NP-complete optimization problems, such as the Generalized Assignment Problem (GAP). Given the operational constraints of contemporary Noisy Intermediate-Scale Quantum (NISQ) devices, hybrid quantum-classical approaches, specifically Variational Quantum Algorithms (VQAs) like the Variational Quantum Eigensolver (VQE), promises to be effective approaches to solve real-world optimization problems. This paper proposes an approach, named VQGAP, designed to efficiently solve the GAP by optimizing quantum resources and reducing the required parametrized quantum circuit width with respect to standard VQE. The main idea driving our proposal is to decouple the qubits of ansatz circuits from the binary variables of the General Assignment Problem, by providing encoding/decoding functions transforming the solutions generated by ansatze in the limited quantum space in feasible solutions in the problem variables space, by exploiting the constraints of the problem. Preliminary results, obtained through both noiseless and noisy simulations, indicate that VQGAP exhibits performance and behavior very similar to VQE, while effectively reducing the number of qubits and circuit depth.
Variational Quantum Algorithms (VQAs) provide a promising framework for tackling complex optimization problems on near-term quantum hardware. Here, we demonstrate that hybrid qubit-qumode quantum devices offer an efficient route to solving Quadratic Unconstrained Binary Optimization (QUBO) problems using the Echoed Conditional Displacement Variational Quantum Eigensolver (ECD-VQE). Leveraging circuit quantum electrodynamics (cQED) architectures, we encode QUBO instances across multiple qumodes weakly coupled to a single qubit and extract binary solutions directly from photon-number measurements. We apply ECD-VQE to the Binary Knapsack Problem and show that it outperforms the Quantum Approximate Optimization Algorithm (QAOA) implemented on conventional qubit circuits, achieving higher-quality solutions with dramatically fewer resources. We also demonstrate that ECD-VQE can be extended to chemically motivated tasks such as active-space selection for multireference electronic structure methods. These results highlight the utility of hybrid qubit-qumode platforms for a broad class of NP-hard and chemistry-related optimization problems and demonstrate that variational ECD ansatz can realize expressive state preparation with significantly shallower circuits than qubit-only architectures, positioning qubit-qumode gates as compelling candidates for constrained optimization in early fault-tolerant quantum computing.
Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks, including solving optimization problems. Nonetheless, optimization problems with constraints may not have been handled in a disciplined fashion thus far. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed the variational quantum eigensolver with constraints (VQEC) that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically constrained binary optimization problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function, we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.
Variational quantum algorithms have promising applications in noisy intermediate-scale quantum (NISQ) devices. These algorithms rely on a classical optimization outer loop that minimizes a parameterized quantum circuit function. The optimization in variational quantum eigensolver (VQE) is NP-hard, meaning that finding the optimal solution is infeasible in the worst-case scenario. One way to address this challenge is through parallel optimization of parameters using multiple-parameterized quantum circuits. However, this approach is unsuitable for cloud-based quantum processing unit utilization due to the increased number of quantum circuit executions. Although NISQ devices have limitations in terms of gate depth, their size has been growing in recent years. Therefore, implementing multiple-parameterized quantum circuits in NISQ devices can suppress the increase in the number of executions. In this study, we propose a parallel-VQE, which leverages the parallel execution of parameterized quantum circuits to perform parallel parameter optimization in VQE, achieving convergence to solutions closer to the ground state. We validate the effectiveness of parallel-VQE in solving the random weighted max-cut problem using numerical simulations and a real quantum device. We present the results of running up to six circuits in parallel (120 qubits) and demonstrate the advantages of using multiple units to improve computational accuracy. This study provides a potential method for solving eigenvalue problems and combinatorial optimization problems for future quantum devices.
The variational quantum algorithm (VQA) is a hybrid classical-quantum algorithm. It can actually run in an intermediate-scale quantum device where the number of available qubits is too limited to perform quantum error correction, so it is one of the most promising quantum algorithms in the noisy intermediate-scale quantum era. In this paper, two ideas for solving the learning with errors problem (LWE) using VQA are proposed. First, after reducing the LWE problem into the bounded distance decoding problem, the quantum approximation optimization algorithm (QAOA) is introduced to improve classical methods. Second, after the LWE problem is reduced into the unique shortest vector problem, the variational quantum eigensolver (VQE) is used to solve it, and the number of qubits required is calculated in detail. Small-scale experiments are carried out for the two LWE variational quantum algorithms, and the experiments show that VQA improves the quality of the classical solutions.
Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. Nonetheless, enforcing constraints in a disciplined fashion has been largely unexplored. To address this gap, this work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC that extends the celebrated VQE to handle optimization with constraints. As with the standard VQE, the vector of optimization variables is captured by the state of a variational quantum circuit (VQC). To deal with constraints, VQEC optimizes a Lagrangian function classically over both the VQC parameters as well as the dual variables associated with constraints. To comply with the quantum setup, variables are updated via a perturbed primal-dual method leveraging the parameter shift rule. Among a wide gamut of potential applications, we showcase how VQEC can approximately solve quadratically-constrained binary optimization (QCBO) problems, find stochastic binary policies satisfying quadratic constraints on the average and in probability, and solve large-scale linear programs (LP) over the probability simplex. Under an assumption on the error for the VQC to approximate an arbitrary probability mass function (PMF), we provide bounds on the optimality gap attained by a VQC. Numerical tests on a quantum simulator investigate the effect of various parameters and corroborate that VQEC can generate high-quality solutions.
We introduce a general framework called neural-network- (NN) encoded variational quantum algorithms (VQAs), or NNVQA for short, to address the challenges of implementing VQAs on noisy intermediate-scale quantum (NISQ) computers. Specifically, NNVQA feeds input (such as parameters of a Hamiltonian) from a given problem to a neural network and uses its outputs to parameterize an ansatz circuit for the standard VQA. Combining the strengths of NN and parameterized quantum circuits, NNVQA can accelerate the training process of VQAs and handle a broad family of related problems with varying input parameters with the pretrained NN. To concretely illustrate the merits of NNVQA, we present results on a NN variational quantum eigensolver (VQE) for solving the ground state of parameterized XXZXXZXXZ spin models in one and two dimensions. Our results demonstrate that NNVQE is able to estimate the ground-state energies of parameterized Hamiltonians with high precision without fine tuning, and significantly reduce the overall training cost to estimate ground-state properties across the phases of the given Hamiltonian. We also employ an active learning strategy to further increase the training efficiency while maintaining prediction accuracy. These encouraging results demonstrate that NNVQAs offer an alternative hybrid quantum-classical paradigm to utilize NISQ resources for solving more realistic and challenging computational problems.