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

Driver Hamiltonians for constrained optimization in quantum annealing

Itay Hen, M. S. Sarandy

Published Jun 13, 2016• 59 citations
arXivHTMLPDF

Abstract

One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.

DOI
10.1103/physreva.93.062312

Related papers

Constructing driver Hamiltonians for optimization problems with linear constraints

Hannes Leipold, Federico M. Spedalieri

Abstract Recent advances in the field of adiabatic quantum computing and the closely related field of quantum annealing have centered around using more advanced and novel Hamiltonian representations to solve optimization problems. One of these advances has centered around the development of driver Hamiltonians that commute with the constraints of an optimization problem—allowing for another avenue to satisfying those constraints instead of imposing penalty terms for each of them. In particular, the approach is able to use sparser connectivity to embed several practical problems on quantum devices in comparison to the standard approach of using penalty terms. However, designing the driver Hamiltonians that successfully commute with several constraints has largely been based on strong intuition for specific problems and with no simple general algorithm for generating them for arbitrary constraints. In this work, we develop a simple and intuitive algebraic framework for reasoning about the commutation of Hamiltonians with linear constraints—one that allows us to classify the complexity of finding a driver Hamiltonian for an arbitrary set of linear constraints as NP-complete. Because unitary operators are exponentials of Hermitian operators, these results can also be applied to the construction of mixers in the quantum alternating operator ansatz framework.

arXiv:2006.12028•Quantum Science and Technology•Jul 21, 2021•14 citations

Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally

Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.

quant-pharXiv:2602.03101•Feb 4, 2026•0 citations

Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation

Hannes Leipold, Federico M. Spedalieri, Stuart Hadfield +1 more

Driver Hamiltonians and Mixing Operators that satisfy constraints is an important part of ansatz construction for many quantum algorithms. In this manuscript, we give general algebraic expressions for finding Hamiltonian terms and analogously unitary primitives, that satisfy constraint embeddings and use these to give complexity characterizations of the related problems. We prove that knowing if operators exist that enforce classical constraints is NP-Complete in the general case, but give algorithmic procedures with worst-case polynomial runtime to find any operators with a constant locality bound; a useful result since many constraints imposed admit local operators to enforce them in practice. We then give algorithmic procedures to turn these algebraic primitives into Hamiltonian drivers and unitary mixers that can be used for Constrained Quantum Annealing (CQA) and Quantum Alternating Operator Ansatz (QAOA) constructions by tackling practical problems related to finding an appropriate set of reduced generators and defining corresponding drivers and mixers accordingly. We consider a new QAOA approach based on the maximally disjoint subset as well as higher order constraint satisfaction terms for 1-in-3 SAT, which dramatically outperform the X-mixer.

arXiv:2407.01975•ACM Transactions on Quantum Computing•Jun 19, 2026•2 citations

Qubit-efficient embedding of parity-encoded Hamiltonians in quantum annealers

Ryoji Miyazaki

The Sourlas-Lechner-Hauke-Zoller (SLHZ) scheme for quantum annealing uses the parity to encode logical variables and has several advantages, but it has not been implemented for large-scale quantum annealers. If the SLHZ-based approach can be implemented on currently available quantum annealers, we can evaluate its performance. An efficient method to embed the parity-encoded model into the hardware graphs of available quantum annealers is one of the key elements for this approach. We propose a qubit-efficient embedding scheme for parity-encoded Hamiltonians on quantum annealers with the Zephyr connectivity. We give an explicit constructive embedding of the interaction graph of an intermediate Hamiltonian, which contains only one- and two-body interactions, into the Zephyr graph. Our embedding maps each spin to a two-qubit chain using systematic chain-assignment rules. Its validity is verified via the resulting chain-to-chain connectivity. Our embedding also provides practical flexibility. Chains assigned to ancillary spins allow reduction to a single physical qubit, leading to options to avoid inactive qubits. The number of required qubits per spin in the parity Hamiltonian is three, which is fewer than that for a known embedding scheme for the Pegasus graph.

quant-pharXiv:2603.28667•Mar 31, 2026•0 citations

Scalable embedding of parity constraints in quantum annealing hardware

Michele Cattelan, Jemma Bennett, Sheir Yarkoni +1 more

One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.

arXiv:2405.14746•Physical Review A•Jan 23, 2025•3 citations

Ground-State Sampling Correspondence between Penalty-Based and Constrained Quantum Annealing

Shunta Ide, Shu Tanaka

Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.

quant-pharXiv:2610.26687•Oct 20, 2026•0 citations
One of the current major challenges surrounding the use of quantum annealers for solving practical optimization problems is their inability to encode even moderately sized problems, the main reason for this being the rigid layout of their quantum bits as well as their sparse connectivity. In particular, the implementation of constraints has become a major bottleneck in the embedding of practical problems, because the latter is typically achieved by adding harmful penalty terms to the problem Hamiltonian, a technique that often requires an all-to-all connectivity between the qubits. Recently, a novel technique designed to obviate the need for penalty terms was suggested; it is based on the construction of driver Hamiltonians that commute with the constraints of the problem, rendering the latter constants of motion. In this work we propose general guidelines for the construction of such driver Hamiltonians given an arbitrary set of constraints. We illustrate the broad applicability of our method by analyzing several diverse examples, namely, graph isomorphism, not-all-equal three-satisfiability, and the so-called Lechner-Hauke-Zoller constraints. We also discuss the significance of our approach in the context of current and future experimental quantum annealers.
Abstract Recent advances in the field of adiabatic quantum computing and the closely related field of quantum annealing have centered around using more advanced and novel Hamiltonian representations to solve optimization problems. One of these advances has centered around the development of driver Hamiltonians that commute with the constraints of an optimization problem—allowing for another avenue to satisfying those constraints instead of imposing penalty terms for each of them. In particular, the approach is able to use sparser connectivity to embed several practical problems on quantum devices in comparison to the standard approach of using penalty terms. However, designing the driver Hamiltonians that successfully commute with several constraints has largely been based on strong intuition for specific problems and with no simple general algorithm for generating them for arbitrary constraints. In this work, we develop a simple and intuitive algebraic framework for reasoning about the commutation of Hamiltonians with linear constraints—one that allows us to classify the complexity of finding a driver Hamiltonian for an arbitrary set of linear constraints as NP-complete. Because unitary operators are exponentials of Hermitian operators, these results can also be applied to the construction of mixers in the quantum alternating operator ansatz framework.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
Driver Hamiltonians and Mixing Operators that satisfy constraints is an important part of ansatz construction for many quantum algorithms. In this manuscript, we give general algebraic expressions for finding Hamiltonian terms and analogously unitary primitives, that satisfy constraint embeddings and use these to give complexity characterizations of the related problems. We prove that knowing if operators exist that enforce classical constraints is NP-Complete in the general case, but give algorithmic procedures with worst-case polynomial runtime to find any operators with a constant locality bound; a useful result since many constraints imposed admit local operators to enforce them in practice. We then give algorithmic procedures to turn these algebraic primitives into Hamiltonian drivers and unitary mixers that can be used for Constrained Quantum Annealing (CQA) and Quantum Alternating Operator Ansatz (QAOA) constructions by tackling practical problems related to finding an appropriate set of reduced generators and defining corresponding drivers and mixers accordingly. We consider a new QAOA approach based on the maximally disjoint subset as well as higher order constraint satisfaction terms for 1-in-3 SAT, which dramatically outperform the X-mixer.
The Sourlas-Lechner-Hauke-Zoller (SLHZ) scheme for quantum annealing uses the parity to encode logical variables and has several advantages, but it has not been implemented for large-scale quantum annealers. If the SLHZ-based approach can be implemented on currently available quantum annealers, we can evaluate its performance. An efficient method to embed the parity-encoded model into the hardware graphs of available quantum annealers is one of the key elements for this approach. We propose a qubit-efficient embedding scheme for parity-encoded Hamiltonians on quantum annealers with the Zephyr connectivity. We give an explicit constructive embedding of the interaction graph of an intermediate Hamiltonian, which contains only one- and two-body interactions, into the Zephyr graph. Our embedding maps each spin to a two-qubit chain using systematic chain-assignment rules. Its validity is verified via the resulting chain-to-chain connectivity. Our embedding also provides practical flexibility. Chains assigned to ancillary spins allow reduction to a single physical qubit, leading to options to avoid inactive qubits. The number of required qubits per spin in the parity Hamiltonian is three, which is fewer than that for a known embedding scheme for the Pegasus graph.
One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
Quantum annealing generally samples degenerate ground states with nonuniform probabilities. This unfair sampling depends on how the driver Hamiltonian couples these states near the end of annealing. For combinatorial optimization problems with a cardinality constraint, the penalty method and constrained quantum annealing (CQA) differ in these couplings. The transverse-field driver of the penalty method does not directly couple feasible ground states, whereas the fully connected XY driver of CQA couples pairs of them related by a single spin exchange. We investigate how this difference affects ground-state sampling, using closed-system simulations of random graph bipartitioning instances together with degenerate perturbation theory. For the instances studied, the conditional ground-state distribution of penalty-based quantum annealing approaches that of CQA at sufficiently large penalties and long annealing times. This convergence can be explained by the effective Hamiltonian of penalty-based quantum annealing, in which virtual single-spin flips to infeasible states generate a second-order interaction proportional to the CQA driver projected onto the feasible ground-state manifold, which is the leading term of the effective Hamiltonian of CQA. In the numerical simulations, the Jensen--Shannon divergence between the conditional ground-state distributions of penalty-based quantum annealing and CQA decreases approximately as the inverse square of the penalty-to-objective energy ratio, consistent with the perturbative analysis. This correspondence between the effective Hamiltonians extends to equal-weight fixed-magnetization constraints under the same perturbative conditions, providing a common mechanism for sampling bias in the two implementations.