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:2411.10737 · Physical Review A

Classical optimization with imaginary-time block encoding on quantum computers: The MaxCut problem

Dawei Zhong, Akhil Francis, Ermal Rrapaj

Published Sep 3, 2025• 2 citations
arXivHTMLPDF

Abstract

Optimization problems in finance, physics, and computer science are typically very hard to tackle in classical computing; quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat a problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. We develop a method, called imaginary-time evolution block encoding (ITE-BE), based on a recent imaginary-time algorithm, which requires no variational parameter optimization, as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as the quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the postselection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block-encoding scheme to allow for a deterministic application of the first layer of the circuit.

DOI
10.1103/gtq3-j37b

Related papers

Imaginary Hamiltonian variational Ansatz for combinatorial optimization problems

Xiaoyang Wang, Yahui Chai, Xu Feng +3 more

Obtaining exact solutions to combinatorial optimization problems using classical computing is computationally expensive. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the Ansatz being of the utmost importance. It is known that popular approaches such as the quantum approximate optimization algorithm (QAOA) and quantum annealing suffer from adiabatic bottlenecks, which lead to either larger circuit depth or evolution time. On the other hand, the evolution time of imaginary-time evolution is bounded by the inverse energy gap of the Hamiltonian, which is constant for most noncritical physical systems. In this work we propose an imaginary Hamiltonian variational Ansatz ($i\mathrm{HVA}$) inspired by quantum imaginary-time evolution to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round $i\mathrm{HVA}$. For randomly generated $D$-regular graphs, we numerically demonstrate that the $i\mathrm{HVA}$ solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming the QAOA, which requires rounds increasing with the graph size. Furthermore, our Ansatz solves the MaxCut problem exactly for graphs with up to 24 nodes and $D\ensuremath{\le}5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm. We validate our simulated results with hardware demonstrations on a graph with 67 nodes.

arXiv:2408.09083•Physical Review A•Mar 18, 2025•4 citations

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Roetteler, Martin +1 more

Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.

arXiv:2404.16135•Apr 24, 2024•1 citation

Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution

Xin Lee, Hoong Chuin Lau

Solving combinatorial optimization problems using variational quantum algorithms (VQAs) has emerged as a promising research direction. Since the introduction of the Quantum Approximate Optimization Algorithm (QAOA), numerous variants have been proposed to enhance its performance. QAOA was later extended to the Quantum Alternating Operator Ansatz (QAOA+), which generalizes the initial state, phase-separation operator, and mixer to address constrained problems without relying on the standard Quadratic Unconstrained Binary Optimization (QUBO) formulation. However, QAOA+ often requires additional ancilla qubits and a large number of multi-controlled Toffoli gates to prepare the superposition of feasible states, resulting in deep circuits that are challenging for near-term quantum devices. Furthermore, VQAs are generally hindered by issues such as barren plateaus and suboptimal local minima. Recently, Quantum Imaginary Time Evolution (QITE), a groundstate preparation algorithm, has been explored as an alternative to QAOA and its variants. QITE has demonstrated improved performance in quantum chemistry problems and has been applied to unconstrained combinatorial problems such as MaxCut. In this work, we apply the variational form of QITE (VarQITE) to solve the Multiple Knapsack Problem (MKP), a constrained problem, using a Max-Cut-tailored ansatz. To the best of our knowledge, this is the first attempt to address constrained optimization using VarQITE. We show that VarQITE achieves significantly lower mean optimality gaps compared to QAOA and other conventional methods. Moreover, we demonstrate that scaling the Hamiltonian coefficients can further reduce optimization costs and accelerate convergence.

arXiv:2504.12607•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•3 citations

A Comparative Study on Solving Optimization Problems With Exponentially Fewer Qubits

David Winderl, Nicola Franco, Jeanette Miriam Lorenz

Variational quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Additionally, we propose a method to embed the linear interpolation of the MaxCut problem on a quantum device. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.

IEEE Transactions on Quantum Engineering•Jan 1, 2024•5 citations

Understanding Quantum Imaginary Time Evolution and its Variational form

Andreu Anglés-Castillo, Luca Ion, Tanmoy Pandit +3 more

Many computationally hard problems can be encoded in quantum Hamiltonians. The solution to these problems is given by the ground states of these Hamiltonians. A state-of-the-art algorithm for finding the ground state of a Hamiltonian is the so-called Quantum Imaginary Time Evolution (QITE) which approximates imaginary time evolution by a unitary evolution that can be implemented in quantum hardware. In this paper, we review the original algorithm together with a comprehensive computer program, as well as, the variational version of it.

arXiv:2510.02015•Oct 2, 2025•0 citations
Optimization problems in finance, physics, and computer science are typically very hard to tackle in classical computing; quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat a problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. We develop a method, called imaginary-time evolution block encoding (ITE-BE), based on a recent imaginary-time algorithm, which requires no variational parameter optimization, as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as the quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the postselection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block-encoding scheme to allow for a deterministic application of the first layer of the circuit.
Obtaining exact solutions to combinatorial optimization problems using classical computing is computationally expensive. The current tenet in the field is that quantum computers can address these problems more efficiently. While promising algorithms require fault-tolerant quantum hardware, variational algorithms have emerged as viable candidates for near-term devices. The success of these algorithms hinges on multiple factors, with the design of the Ansatz being of the utmost importance. It is known that popular approaches such as the quantum approximate optimization algorithm (QAOA) and quantum annealing suffer from adiabatic bottlenecks, which lead to either larger circuit depth or evolution time. On the other hand, the evolution time of imaginary-time evolution is bounded by the inverse energy gap of the Hamiltonian, which is constant for most noncritical physical systems. In this work we propose an imaginary Hamiltonian variational Ansatz (iHVAi\mathrm{HVA}iHVA) inspired by quantum imaginary-time evolution to solve the MaxCut problem. We introduce a tree arrangement of the parametrized quantum gates, enabling the exact solution of arbitrary tree graphs using the one-round iHVAi\mathrm{HVA}iHVA. For randomly generated DDD-regular graphs, we numerically demonstrate that the iHVAi\mathrm{HVA}iHVA solves the MaxCut problem with a small constant number of rounds and sublinear depth, outperforming the QAOA, which requires rounds increasing with the graph size. Furthermore, our Ansatz solves the MaxCut problem exactly for graphs with up to 24 nodes and $D\ensuremath{\le}5$, whereas only approximate solutions can be derived by the classical near-optimal Goemans-Williamson algorithm. We validate our simulated results with hardware demonstrations on a graph with 67 nodes.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
Solving combinatorial optimization problems using variational quantum algorithms (VQAs) has emerged as a promising research direction. Since the introduction of the Quantum Approximate Optimization Algorithm (QAOA), numerous variants have been proposed to enhance its performance. QAOA was later extended to the Quantum Alternating Operator Ansatz (QAOA+), which generalizes the initial state, phase-separation operator, and mixer to address constrained problems without relying on the standard Quadratic Unconstrained Binary Optimization (QUBO) formulation. However, QAOA+ often requires additional ancilla qubits and a large number of multi-controlled Toffoli gates to prepare the superposition of feasible states, resulting in deep circuits that are challenging for near-term quantum devices. Furthermore, VQAs are generally hindered by issues such as barren plateaus and suboptimal local minima. Recently, Quantum Imaginary Time Evolution (QITE), a groundstate preparation algorithm, has been explored as an alternative to QAOA and its variants. QITE has demonstrated improved performance in quantum chemistry problems and has been applied to unconstrained combinatorial problems such as MaxCut. In this work, we apply the variational form of QITE (VarQITE) to solve the Multiple Knapsack Problem (MKP), a constrained problem, using a Max-Cut-tailored ansatz. To the best of our knowledge, this is the first attempt to address constrained optimization using VarQITE. We show that VarQITE achieves significantly lower mean optimality gaps compared to QAOA and other conventional methods. Moreover, we demonstrate that scaling the Hamiltonian coefficients can further reduce optimization costs and accelerate convergence.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
Variational quantum optimization algorithms, such as the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), are among the most studied quantum algorithms. In our work, we evaluate and improve an algorithm based on VQE, which uses exponentially fewer qubits compared to the QAOA. We highlight the numerical instabilities generated by encoding the problem into the variational ansatz and propose a classical optimization procedure to find the ground-state of the ansatz in less iterations with a better or similar objective. Additionally, we propose a method to embed the linear interpolation of the MaxCut problem on a quantum device. Furthermore, we compare classical optimizers for this variational ansatz on quadratic unconstrained binary optimization and graph partitioning problems.
Many computationally hard problems can be encoded in quantum Hamiltonians. The solution to these problems is given by the ground states of these Hamiltonians. A state-of-the-art algorithm for finding the ground state of a Hamiltonian is the so-called Quantum Imaginary Time Evolution (QITE) which approximates imaginary time evolution by a unitary evolution that can be implemented in quantum hardware. In this paper, we review the original algorithm together with a comprehensive computer program, as well as, the variational version of it.