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.04700 · Physical Review Research

Approximate quadratization of high-order Hamiltonians for combinatorial quantum optimization

Sabina Drăgoi, Alberto Baiardi, Daniel J. Egger

Published Apr 6, 2026• 5 citations
arXivHTMLPDF

Abstract

Combinatorial optimization problems have wide-ranging applications in industry and academia. Quantum computers may help solve them by sampling from appropriately prepared Ansatz quantum circuits. However, current quantum computers are limited by their qubit count, connectivity, and noise. This is particularly restrictive when considering optimization problems beyond the quadratic order. Here, we introduce Ansätze based on an approximate quadratization of high-order Hamiltonians that do not incur a qubit overhead. The price paid is a loss in the quality of the noiseless solution. Crucially, these approximations yield shallower Ansätze that are more robust to noise than the standard Quantum Approximate Optimization Algorithm one. We show this through simulations with variable noise strengths. Furthermore, we also propose a noise-aware Ansatz design method for quadratic optimization problems. This method implements only a portion of the target Hamiltonian by limiting the number of layers of gates in the Ansatz. We find that for both problem types, under noise, our approximate implementation of the full problem structure can significantly enhance the solution quality. Our work opens a path to enhance the solution quality that approximate quantum optimization achieves on noisy hardware.

DOI
10.1103/9rc4-vj11

Related papers

Performant near-term quantum combinatorial optimization

Titus Morris, Kaushik, Ananth, Martin Roetteler +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•21 citations

Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting

Filip B. Maciejewski, Stuart Hadfield, Oscar Wallis +5 more

Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count. Here, we propose a noise-aware adaptive approach to quantum approximate optimization, Noise-Directed Adaptive Warm-Starting (ND-AWS), that builds on recent concepts such as Warm-Start QAOA and Noise-Directed Adaptive Remapping. By leveraging bitflip gauge transformations, our algorithm exploits amplitude-damping-like noise components. We experimentally implement high-performance quantum optimization ansätze on 100-qubit Ising Hamiltonians, showing that ND-AWS generally improves the performance over a non-gauge-transformed iterative Warm-Starting variant, at no additional circuit cost. This places our results among the highest-quality demonstrations of quantum optimization with similar ansätze at this scale. Crucially, the simplicity of the framework opens the door for future enhancements such as adaptive bias schedules, and integration with classical solvers.

quant-pharXiv:2607.09368•Jul 13, 2026•6 citations

Variational Ansatz preparation to avoid CNOT-gates on noisy quantum devices for combinatorial optimizations

Tsukasa Miki, Ryo Okita, Moe Shimada +2 more

The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.

AIP Advances•Mar 1, 2022•16 citations

The effect of classical optimizers and Ansatz depth on QAOA performance in noisy devices

Aidan Pellow-Jarman, Shane McFarthing, Ilya Sinayskiy +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm for Near-term Intermediate-Scale Quantum computers (NISQ) providing approximate solutions for combinatorial optimization problems. The QAOA utilizes a quantum-classical loop, consisting of a quantum ansatz and a classical optimizer, to minimize some cost function, computed on the quantum device. This paper presents an investigation into the impact of realistic noise on the classical optimizer and the determination of optimal circuit depth for the Quantum Approximate Optimization Algorithm (QAOA) in the presence of noise. We find that, while there is no significant difference in the performance of classical optimizers in a state vector simulation, the Adam and AMSGrad optimizers perform best in the presence of shot noise. Under the conditions of real noise, the SPSA optimizer, along with ADAM and AMSGrad, emerge as the top performers. The study also reveals that the quality of solutions to some 5 qubit minimum vertex cover problems increases for up to around six layers in the QAOA circuit, after which it begins to decline. This analysis shows that increasing the number of layers in the QAOA in an attempt to increase accuracy may not work well in a noisy device.

arXiv:2307.10149•Scientific Reports•Jul 11, 2024•53 citations

Sampling-Based Quantum Optimization Algorithm with Quantum Relaxation

Hiromichi Matsuyama, Yu Yamashiro

Combinatorial optimization is one of the promising applications of quantum computation. Variational Quantum Algorithm (VQA) is a classical-quantum hybrid algorithm framework for noisy quantum devices. However, the quality of the solution is readily affected by statistical fluctuations and physical noise, making it challenging to maintain applicability for largescale problems. In contrast, sampling-based quantum algorithms have recently been successfully applied to large-scale quantum chemistry problems. In the sampling-based framework, the quantum device is used only for sampling, while the ground state and its energy are estimated on the classical device. In this study, we propose the Sampling-based Quantum Optimization Algorithm (SQOA) that leverages these advantages for combinatorial optimization. There are two challenges in constructing SQOA. The first challenge is that we need to encode the optimization problem in a non-diagonal Hamiltonian, even though many VQAs encode it into the Ising Hamiltonian, which is diagonal. The second challenge is that we need a method for efficient preparation of the input state to be sampled. To address the first challenge, we utilize the Quantum Relaxation (QR) method for encoding an optimization problem within a Hamiltonian. This method achieves a higher encoding density by mapping multiple variables to a single qubit, thus requiring fewer qubits for larger problems compared to the Ising Hamiltonian approach. Moreover, to address the second challenge, we investigate the parameter transferability within the Quantum Alternating Operator Ansatz for QR Hamiltonians. We show that restricting parameters to a linear form exhibits moderate transferability for 3-regular Max-Cut problems, similar to transferability observed in the Quantum Approximate Optimization Algorithm. Therefore, this property allows us to efficiently prepare the input state for a large problem instance using the parameters obtained from a small problem instance. We leveraged transferability to create input states and applied SQOA with QR to the Max-Cut instances. By transferring parameters from a 20-node problem, we demonstrate that SQOA with QR provides high-quality solutions for 40-node problems without variational parameter optimization.

arXiv:2504.12629•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•4 citations

Ion-native variational ansatz for quantum approximate optimization

Daniil Rabinovich, Soumik Adhikary, Ernesto Campos +6 more

Variational quantum algorithms involve training parametrized quantum circuits using a classical coprocessor. An important variational algorithm, designed for combinatorial optimization, is the quantum approximate optimization algorithm. Realization of this algorithm on any modern quantum processor requires either embedding a problem instance into a Hamiltonian or emulating the corresponding propagator by a gate sequence. For a vast range of problem instances this is impossible due to current circuit depth and hardware limitations. Hence we adapt the variational approach---using ion-native Hamiltonians---to create ansatz families that can prepare the ground states of more general problem Hamiltonians. We analytically determine symmetry protected classes that make certain problem instances inaccessible unless this symmetry is broken. We exhaustively search over six qubits and consider up to 20 circuit layers, demonstrating that symmetry can be broken to solve all problem instances of the Sherrington-Kirkpatrick Hamiltonian. Going further, we numerically demonstrate training convergence and levelwise improvement for up to 20 qubits. Specifically these findings widen the class problem instances which might be solved by ion based quantum processors. Generally these results serve as a test bed for quantum approximate optimization approaches based on system native Hamiltonians and symmetry protection.

arXiv:2206.11908•Physical Review A•Sep 14, 2022•10 citations
Combinatorial optimization problems have wide-ranging applications in industry and academia. Quantum computers may help solve them by sampling from appropriately prepared Ansatz quantum circuits. However, current quantum computers are limited by their qubit count, connectivity, and noise. This is particularly restrictive when considering optimization problems beyond the quadratic order. Here, we introduce Ansätze based on an approximate quadratization of high-order Hamiltonians that do not incur a qubit overhead. The price paid is a loss in the quality of the noiseless solution. Crucially, these approximations yield shallower Ansätze that are more robust to noise than the standard Quantum Approximate Optimization Algorithm one. We show this through simulations with variable noise strengths. Furthermore, we also propose a noise-aware Ansatz design method for quadratic optimization problems. This method implements only a portion of the target Hamiltonian by limiting the number of layers of gates in the Ansatz. We find that for both problem types, under noise, our approximate implementation of the full problem structure can significantly enhance the solution quality. Our work opens a path to enhance the solution quality that approximate quantum optimization achieves on noisy hardware.
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.
Progress towards a quantum advantage using known heuristic methods for combinatorial optimization is impeded by hardware noise and limited qubit count. Here, we propose a noise-aware adaptive approach to quantum approximate optimization, Noise-Directed Adaptive Warm-Starting (ND-AWS), that builds on recent concepts such as Warm-Start QAOA and Noise-Directed Adaptive Remapping. By leveraging bitflip gauge transformations, our algorithm exploits amplitude-damping-like noise components. We experimentally implement high-performance quantum optimization ansätze on 100-qubit Ising Hamiltonians, showing that ND-AWS generally improves the performance over a non-gauge-transformed iterative Warm-Starting variant, at no additional circuit cost. This places our results among the highest-quality demonstrations of quantum optimization with similar ansätze at this scale. Crucially, the simplicity of the framework opens the door for future enhancements such as adaptive bias schedules, and integration with classical solvers.
The variational quantum eigensolver (VQE), which is a quantum–classical hybrid approach, has latent powers to leverage near-term quantum devices by effectively managing a limited number of qubits with finite coherent lifetimes. While it is generally argued that the quantum approximate optimization algorithm (QAOA), which is a special case of VQE with a variational Ansatz based on the adiabatic theorem, may enable practical applications of noisy quantum devices for classical combinatorial optimizations, the strategy to improve the performance of this algorithm by increasing the circuit depth conflicts with the limited coherence time of near-term quantum devices. Here, we introduce strategies involving the VQE to reduce the circuit resources required for solving combinatorial optimizations. Our concept of a parameterized quantum circuit allows the Ansatz preparation to be achieved by only single-qubit operation. We find that the variational Ansatz without controlled X-gates leads to quick convergence in a classical subroutine used to determine the variational parameters. In addition, the variational Ansatz with optimized parameters maintains performance over the problem sizes both on the numerical simulation and IBM 27-qubit processor “ibm_kawasaki.” Therefore, the variational Ansatz introduced in this study has several advantages considering the total calculation time and performance scaling over the problem sizes. We also show that the variational Ansatz consisting of a lower number of gate operations than that of QAOA can approximate the eigenstates of diagonal Hamiltonians with high accuracy. We illustrate our ideas with a maximum-cut problem and show that near-term quantum applications may be feasible using short-depth circuits.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational quantum algorithm for Near-term Intermediate-Scale Quantum computers (NISQ) providing approximate solutions for combinatorial optimization problems. The QAOA utilizes a quantum-classical loop, consisting of a quantum ansatz and a classical optimizer, to minimize some cost function, computed on the quantum device. This paper presents an investigation into the impact of realistic noise on the classical optimizer and the determination of optimal circuit depth for the Quantum Approximate Optimization Algorithm (QAOA) in the presence of noise. We find that, while there is no significant difference in the performance of classical optimizers in a state vector simulation, the Adam and AMSGrad optimizers perform best in the presence of shot noise. Under the conditions of real noise, the SPSA optimizer, along with ADAM and AMSGrad, emerge as the top performers. The study also reveals that the quality of solutions to some 5 qubit minimum vertex cover problems increases for up to around six layers in the QAOA circuit, after which it begins to decline. This analysis shows that increasing the number of layers in the QAOA in an attempt to increase accuracy may not work well in a noisy device.
Combinatorial optimization is one of the promising applications of quantum computation. Variational Quantum Algorithm (VQA) is a classical-quantum hybrid algorithm framework for noisy quantum devices. However, the quality of the solution is readily affected by statistical fluctuations and physical noise, making it challenging to maintain applicability for largescale problems. In contrast, sampling-based quantum algorithms have recently been successfully applied to large-scale quantum chemistry problems. In the sampling-based framework, the quantum device is used only for sampling, while the ground state and its energy are estimated on the classical device. In this study, we propose the Sampling-based Quantum Optimization Algorithm (SQOA) that leverages these advantages for combinatorial optimization. There are two challenges in constructing SQOA. The first challenge is that we need to encode the optimization problem in a non-diagonal Hamiltonian, even though many VQAs encode it into the Ising Hamiltonian, which is diagonal. The second challenge is that we need a method for efficient preparation of the input state to be sampled. To address the first challenge, we utilize the Quantum Relaxation (QR) method for encoding an optimization problem within a Hamiltonian. This method achieves a higher encoding density by mapping multiple variables to a single qubit, thus requiring fewer qubits for larger problems compared to the Ising Hamiltonian approach. Moreover, to address the second challenge, we investigate the parameter transferability within the Quantum Alternating Operator Ansatz for QR Hamiltonians. We show that restricting parameters to a linear form exhibits moderate transferability for 3-regular Max-Cut problems, similar to transferability observed in the Quantum Approximate Optimization Algorithm. Therefore, this property allows us to efficiently prepare the input state for a large problem instance using the parameters obtained from a small problem instance. We leveraged transferability to create input states and applied SQOA with QR to the Max-Cut instances. By transferring parameters from a 20-node problem, we demonstrate that SQOA with QR provides high-quality solutions for 40-node problems without variational parameter optimization.
Variational quantum algorithms involve training parametrized quantum circuits using a classical coprocessor. An important variational algorithm, designed for combinatorial optimization, is the quantum approximate optimization algorithm. Realization of this algorithm on any modern quantum processor requires either embedding a problem instance into a Hamiltonian or emulating the corresponding propagator by a gate sequence. For a vast range of problem instances this is impossible due to current circuit depth and hardware limitations. Hence we adapt the variational approach---using ion-native Hamiltonians---to create ansatz families that can prepare the ground states of more general problem Hamiltonians. We analytically determine symmetry protected classes that make certain problem instances inaccessible unless this symmetry is broken. We exhaustively search over six qubits and consider up to 20 circuit layers, demonstrating that symmetry can be broken to solve all problem instances of the Sherrington-Kirkpatrick Hamiltonian. Going further, we numerically demonstrate training convergence and levelwise improvement for up to 20 qubits. Specifically these findings widen the class problem instances which might be solved by ion based quantum processors. Generally these results serve as a test bed for quantum approximate optimization approaches based on system native Hamiltonians and symmetry protection.