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.
We present a very general construction for quantum annealing protocols to solve Combinational Circuit Fault Diagnosis problems that restricts the evolution to the space of valid diagnoses. This is accomplished by using special local drivers that induce a transition graph on the space of feasible configurations that is regular and instance independent for each given circuit topology. Analysis of small instances shows that the energy gap has a generic form, and that the minimum gap occurs in the last third of the evolution. We used these features to construct an improved annealing schedule and benchmarked its performance through closed system simulations. We found that degeneracy can help the performance of quantum annealing, especially for instances with a higher number of faults in their minimum fault diagnosis. This contrasts with the performance of classical approaches based on brute force search that are used in industry for large scale circuits.
The quantum alternating operator ansatz (QAOA) and constrained quantum annealing (CQA) restrict the evolution of a quantum system to remain in a constrained space, often with a dimension much smaller than the whole Hilbert space. A natural question when using quantum annealing or a QAOA protocol to solve an optimization problem is to select an initial state for the wavefunction and what operators to use to evolve it into a solution state. In this work, we construct several ansatzes tailored to solve the combinational circuit fault diagnostic (CCFD) problem in different subspaces related to the structure of the problem, including superpolynomially smaller subspaces than the whole Hilbert space. We introduce a family of dense and highly connected circuits that include small instances but can be scaled to larger sizes as a useful collection of circuits for comparing different quantum algorithms. We compare the different ansätzes on instances randomly generated from this family under different parameter selection methods. The results support that ansätzes more closely tailored to exploiting the structure of the underlying optimization problems can have better performance than more generic ansätzes.
We present a very general construction for quantum annealing protocols to solve Combinational Circuit Fault Diagnosis (CCFD) problems that restricts the evolution to the space of valid diagnoses. This is accomplished by using special local drivers that induce a transition graph on the space of feasible configurations that is regular and instance independent for each given circuit topology. Analysis of small instances shows that the energy gap has a generic form, and that the minimum gap occurs in the last third of the evolution. We used these features to construct an improved annealing schedule and benchmarked its performance through closed system simulations. We found that degeneracy can help the performance of quantum annealing, especially for instances with a higher number of faults in their minimum fault diagnosis. This contrasts with the performance of classical approaches based on brute force search that are used in industry for large scale circuits.
19 June 2026 in ACM Transactions on Quantum Computing
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 worse-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.