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:2505.22924 · New Journal of Physics

Optimizing QUBO on a quantum computer by mimicking imaginary time evolution

Yahui Chai, Alice Di Tucci

Published May 14, 2026• 1 citation
arXivHTMLPDF

Abstract

Abstract We propose a hybrid quantum–classical algorithm for solving quadratic unconstrained binary optimization (QUBO) problems using an imaginary time evolution-mimicking circuit (ITEMC). The circuit parameters are optimized to mimic short-time ITE, using only single- and two-qubit expectation values. This significantly reduces the measurement overhead by avoiding full energy evaluation. By updating the initial state based on results from last step iteratively, the algorithm quickly converges to the low-energy solutions. With a pre-sorting step that optimizes quantum gate ordering based on QUBO coefficients, the convergence is further improved. Our classical simulations achieve approximation ratios above 99 % up to 150 qubits. Furthermore, the linear scaling of entanglement entropy with system size suggests that the circuit is challenging to simulate classically using tensor networks. We also demonstrate hardware runs on IBM’s device for 40, 60, and 80 qubits, and obtain solutions compatible with that from simulated annealing.

DOI
10.1088/1367-2630/ae6ded

Related papers

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•12 citations

Quantum-Inspired Optimization through Qudit-Based Imaginary Time Evolution

Erik M. Åsgrim, Ahsan Javed Awan

Imaginary-time evolution has been shown to be a promising framework for tackling combinatorial optimization problems on quantum hardware. In this work, we propose a classical quantum-inspired strategy for solving combinatorial optimization problems with integer-valued decision variables by encoding decision variables into multi-level quantum states known as qudits. This method results in a reduced number of decision variables compared to binary formulations while inherently incorporating single-association constraints. Efficient classical simulation is enabled by constraining the system to remain in a product state throughout optimization. The qudit states are optimized by applying a sequence of unitary operators that iteratively approximate the dynamics of imaginary time evolution. Unlike previous studies, we propose a gradient-based method of adaptively choosing the Hermitian operators used to generate the state evolution at each optimization step, as a means to improve the convergence properties of the algorithm. The proposed algorithm demonstrates promising results on Min-d-Cut problem with constraints, outperforming Gurobi on penalized constraint formulation, particularly for larger values of d.

quant-pharXiv:2512.04710•Dec 5, 2025•0 citations

Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks

Alejandro Mata Ali, Iñigo Perez Delgado, Marina Ristol Roura +1 more

We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and quadratic unconstrained discrete optimization (QUDO) problems. We also solve the more general Tensor quadratic unconstrained discrete optimization (T-QUDO) problems with one-neighbor interactions in a lineal chain. This method provides an exact and explicit equation for these problems. Our algorithms are based on the simulation of a state that undergoes imaginary time evolution and a Half partial trace. In addition, we address the degenerate case and evaluate the polynomial complexity of the algorithm, also providing a parallelized version. We implemented and tested them with other well-known classical algorithms and observed an improvement in the quality of the results. The performance of the proposed algorithms is compared with the Google OR-TOOLS and dimod solvers, improving their results.

arXiv:2309.10509•Sep 19, 2023•1 citation

Evaluating the Quantum Approximate Optimization Algorithms for QUBO problems Across Quantum Hardware Platforms: Performance Analysis, Challenges, and Strategies

Teemu Pihkakoski, Aravind Plathanam Babu, Pauli Taipale +2 more

Quantum computers are expected to offer advantages in solving optimization problems challenging for classical computers. Quadratic Unconstrained Binary Optimization (QUBO) problems represent an important class of problems with relevance in finance and logistics. The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for solving QUBO problems on near-term quantum devices. In this paper, we evaluate the performance of both the standard QAOA and the adaptive derivative assembled problem tailored QAOA (ADAPT-QAOA) to solve QUBO problems of varying sizes and hardnesses for financial feature selection problems. Our main observation is that ADAPT-QAOA achieves substantially higher approximation ratios than standard QAOA for harder feature-selection problems (α = 0.6) with statistically significant improvements observed for problem sizes n = 6 and 14. However, the standard QAOA remains competitive for simpler problems. Additionally, we evaluate the practical feasibility and limitations of QAOA through a hardware-aware scaling analysis based on the real-device calibration data for various hardware platforms. We estimate that standard QAOA implementation on superconducting quantum computers provides a shorter time-to-solution compared to trapped-ion devices, while trapped-ion devices yield more favorable error rates. Our findings provide a comprehensive overview of the challenges, trade-offs, and strategies for deploying QAOA-based methods on near-term quantum hardware.

arXiv:2510.12336•Oct 14, 2025•0 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo Carro, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•May 27, 2025•0 citations

New QUBO Transformations to Improve Quantum and Simulated Annealing Performance for Quadratic Knapsack

Nicolás Borrajo, Juan Marcos Ramírez, Farzam Nosrati +3 more

Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.

•Jan 1, 2026•0 citations
Abstract We propose a hybrid quantum–classical algorithm for solving quadratic unconstrained binary optimization (QUBO) problems using an imaginary time evolution-mimicking circuit (ITEMC). The circuit parameters are optimized to mimic short-time ITE, using only single- and two-qubit expectation values. This significantly reduces the measurement overhead by avoiding full energy evaluation. By updating the initial state based on results from last step iteratively, the algorithm quickly converges to the low-energy solutions. With a pre-sorting step that optimizes quantum gate ordering based on QUBO coefficients, the convergence is further improved. Our classical simulations achieve approximation ratios above 99 % up to 150 qubits. Furthermore, the linear scaling of entanglement entropy with system size suggests that the circuit is challenging to simulate classically using tensor networks. We also demonstrate hardware runs on IBM’s device for 40, 60, and 80 qubits, and obtain solutions compatible with that from simulated annealing.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Imaginary-time evolution has been shown to be a promising framework for tackling combinatorial optimization problems on quantum hardware. In this work, we propose a classical quantum-inspired strategy for solving combinatorial optimization problems with integer-valued decision variables by encoding decision variables into multi-level quantum states known as qudits. This method results in a reduced number of decision variables compared to binary formulations while inherently incorporating single-association constraints. Efficient classical simulation is enabled by constraining the system to remain in a product state throughout optimization. The qudit states are optimized by applying a sequence of unitary operators that iteratively approximate the dynamics of imaginary time evolution. Unlike previous studies, we propose a gradient-based method of adaptively choosing the Hermitian operators used to generate the state evolution at each optimization step, as a means to improve the convergence properties of the algorithm. The proposed algorithm demonstrates promising results on Min-d-Cut problem with constraints, outperforming Gurobi on penalized constraint formulation, particularly for larger values of d.
We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and quadratic unconstrained discrete optimization (QUDO) problems. We also solve the more general Tensor quadratic unconstrained discrete optimization (T-QUDO) problems with one-neighbor interactions in a lineal chain. This method provides an exact and explicit equation for these problems. Our algorithms are based on the simulation of a state that undergoes imaginary time evolution and a Half partial trace. In addition, we address the degenerate case and evaluate the polynomial complexity of the algorithm, also providing a parallelized version. We implemented and tested them with other well-known classical algorithms and observed an improvement in the quality of the results. The performance of the proposed algorithms is compared with the Google OR-TOOLS and dimod solvers, improving their results.
Quantum computers are expected to offer advantages in solving optimization problems challenging for classical computers. Quadratic Unconstrained Binary Optimization (QUBO) problems represent an important class of problems with relevance in finance and logistics. The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for solving QUBO problems on near-term quantum devices. In this paper, we evaluate the performance of both the standard QAOA and the adaptive derivative assembled problem tailored QAOA (ADAPT-QAOA) to solve QUBO problems of varying sizes and hardnesses for financial feature selection problems. Our main observation is that ADAPT-QAOA achieves substantially higher approximation ratios than standard QAOA for harder feature-selection problems (α = 0.6) with statistically significant improvements observed for problem sizes n = 6 and 14. However, the standard QAOA remains competitive for simpler problems. Additionally, we evaluate the practical feasibility and limitations of QAOA through a hardware-aware scaling analysis based on the real-device calibration data for various hardware platforms. We estimate that standard QAOA implementation on superconducting quantum computers provides a shorter time-to-solution compared to trapped-ion devices, while trapped-ion devices yield more favorable error rates. Our findings provide a comprehensive overview of the challenges, trade-offs, and strategies for deploying QAOA-based methods on near-term quantum hardware.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. How- ever, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transfor- mations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated An- nealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total num- ber of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.
Recent advancements in quantum computing have demonstrated significant potential for solving combinatorial optimization problems, like the quadratic knapsack problem, a constrained binary optimization problem. However, current quantum and quantum-inspired algorithms often require transforming these constrained problems into an unconstrained form, known as Quadratic Unconstrained Binary Optimization (QUBO). Such transformations can significantly impact the algorithms’ speed and efficiency. In this study, we evaluate five existing transformation methods and propose four novel approaches. We assess all nine methods using Simulated Annealing and find that three of our approaches outperform existing methods in terms of execution time and the quality and quantity of feasible solutions found. Additionally, we tested these transformations on quantum annealers, which were unable to solve even small problem instances, due to limitations in connectivity and error rates. However, our results highlight the advantages of the new approaches, which reduce the total number of variables in the QUBO representation. This is a critical factor for enhanced performance on emerging quantum hardware, since it also reduces the required number of qubits and the embedding chain lengths.