Constructing Driver Hamiltonians for Optimization Problems with Linear Constraints

Quantum annealing has been proposed as a heuristic method to exploit quantum mechanical effects in order to solve discrete optimization problems. Typically, these problems require optimizing a quadratic cost function subject to a set of linear constraints. The usual approach to treating these constraints consists of adding them to the cost function as penalty terms, thereby transforming the constrained optimization into an unconstrained one. This approach has some drawbacks, including an increase in the required resources (i.e., higher connectivity and increased dynamical range for the parameters that define the instance). In Ref.hen2016quantum , the authors introduced the idea of constrained quantum annealing (CQA), that uses specially tailored driver Hamiltonians for a specific set of constraints. These tailored Hamiltonians have several advantages, such as reducing the size of the search space of the problem and reducing the number of needed interactions to implement the annealing protocol. At the heart of the approach is the idea that a Hamiltonian which commutes with the operator embedding of the constraints and starts within the feasible space of configurations will remain in it throughout the evolution.

While Ref.hen2016quantum looked primarily at commuting with a single global constraint, the work in Ref.hen2016driver focused on finding driver Hamiltonians for several constraints. Under special conditions, the authors were able to construct appropriate driver Hamiltonians for several optimization problems of practical interest. In this paper, we ask and answer the general question of, given a set of arbitrary linear constraints, can we construct a driver Hamiltonian which will commute with the operator embedding of the constraints? Our main result is that this problem is NP-Complete – answering a question posited originally in Ref.hen2016driver . Along the way, we will derive a simple formula for describing the commutation relation and exploit it to understand many facets of CQA. These results can be naturally applied to the Quantum Alternating Operator Ansatz (QAOA) framework hadfield2017quantum, where one of the central tasks is to find mixer operators that connect feasible solutions of a constrained optimization problem. Since unitary operators are exponentials of Hermitian operators (for every unitary matrix $U$, there exists a Hermitian matrix $H$ such that $U=e^{iH}$) and therefore the existence of a unitary matrix with this commutative property necessitates the existence of the Hermitian matrix with the same commutative property (since $[e^{iH},\hat{C}]=\sum_{k=0}^{\infty}[\left(iH\right)^{k},\hat{C}]/k!$), our results directly translate into this setting as well.

The paper is organized as follows. In Section II we review the basic ideas behind constrained quantum annealing. In Section III, we derive a simple algebraic condition for the commutation relation of the driver Hamiltonian and the constraint operators. For many practical applications, Hamiltonians with bounded weight interaction (local) terms are often desired; in Section IV we show how brute forcing the simple algebraic condition from Section III to find driver Hamiltonians of bounded weight. In Section V, we introduce several variations of the problem ILP-QCOMMUTE, the problem of finding a Hermitian matrix that will commute with the constraint operators. We also reduce the EQUAL SUBSET SUM problem to the problem ILP-QCOMMUTE (and in Appendix A we show it for the special case of binary valued linear constraints). The EQUAL SUBSET SUM problem is known to be NP-Complete, thus proving our main result. We define a related complexity class, ILP-QCOMMUTE-k-LOCAL, about finding a Hermitian matrix that commutes with the constraints and has interaction terms up to $k$ weight. ILP-QCOMMUTE-k-LOCAL is in P by the approach detailed in Section IV. Other questions of interest, such as finding a driver Hamiltonian that has full reachability over a constrained space for a CQA protocol, will be addressed through our formulation in Section VI. We conclude with a discussion of the significance of our result and open problems related to what we have shown in this work.

In the quantum annealing (QA) framework, gradually decreasing quantum fluctuations are used to traverse the barriers of an energy landscape in the search of global minima to complicated cost functions kadowaki1998quantum ; farhi2000quantum . For an overview of these approaches, we refer the reader to Ref.albash2018adiabatic . Quantum annealing has gained traction for combinatorial optimization farhi2001quantum ; santoro2006optimization ; bian2016mapping ; hauke2020perspectives as a way to solve hard optimization problems faster and, more recently, for machine learning adachi2015application ; mott2017solving ; amin2018quantum ; biamonte2017quantum ; li2018quantum ; kumar2018quantum as a way to naturally sample desired probability distributions quickly. In the case of solving an optimization problem, the problem is encoded in the Hamiltonian $H_{p}$ such that the ground state is the optimum solution. Usually this is readily done by expressing the problem as an Ising model, a model for spin glassesbrush1967history ; sherrington1975solvable ; castellani2005spin ; troyer2005computational .

Once the problem Hamiltonian is described, the QA framework prescribes an evolution to the final Hamiltonian from some readily preparable Hamiltonian $H_{d}$ - usually through a linear interpolation of $H_{d}$ and $H_{p}$:

where there is a continuous smooth function $s(t)$ for $t\in[0,T]$ such that $s(0)=0$ and $s(T)=1$. If the process is varied slowly enough, the adiabatic theorem ensures that the wave function of the system will be close to the instantaneous ground state of the system for any $s$ and therefore any $t$. By the adiabatic theorem, if the total time $T$ that the system is evolved for is large compared to the inverse of the minimum gap squared, then the wavefunction of the system will be close to the ground state of $H_{p}$. For the purpose of our presentation here, we restrict our focus to the case of binary linear optimization problems, a heavily studied optimization class. Specifically, we can consider a set of linear constraints $\mathcal{C}=\{C_{1},\ldots,C_{m}\}$. Suppose that the solutions to the optimization problem are subject to constraints $C_{i}$ such that a solution state $x\in\{0,1\}^{n}$ satisfies $C_{i}(x)=\sum_{j}c_{ij}x_{i}=b_{i}$ for some $b_{i}$. Because $C_{i}$ is a simple linear function, we can associate a vector $\vec{c}_{i}$ with it such that $C_{i}(x)=\vec{c}_{i}\cdot\vec{x}$ where $\vec{c}_{i}\in\mathbb{Z}^{n}$. When referring to constraints throughout this paper, we are referring specifically to linear constraints, for which our main results are pertinent to.

Consider the problem to find Hamiltonian drivers that have, as their eigenvectors, support over the possible values that satisfy the given linear constraints. In the most general sense, we consider constraints of the form:

with a constraint value $b$ that corresponds to one of the energy levels of $\hat{C}$. Often problems of practical interest can be captured in the restricted case where $\vec{c}\in\{0,1\}^{n}$ or $\vec{c}\in\{-1,0,1\}^{n}$.

Consider the linear transformation $[M,\sigma^{z}]$ that maps any two by two matrix $M$ to a new two by two matrix $M^{\prime}$, by commuting the matrix with $\sigma^{z}$. This transformation has two obvious eigenmatrices - $\mathbbm{1}$ and $\sigma^{z}$ - that span the kernel of the transformation. One can easily verify that $\sigma^{+}$ ($\left\lvert\,0\,\right\rangle\left\langle\,1\,\right\rvert$) and $\sigma^{-}$ ($\left\lvert\,1\,\right\rangle\left\langle\,0\,\right\rvert$) are also eigenmatrices of this transformation, with eigenvalue $2$ and $-2$ respectively. Together these four eigenmatrices and their eigenvalues describe the spectrum decomposition of the transformation. We exploit this fact to find a simple algebraic formula for expressing the commutation of a general Hamiltonian with a linear constraint. It is easy to verify that for $H$ over $n$ qubits, if $\text{Tr}_{1,\ldots i-1,i+1,\ldots n}[H]=\sigma^{\pm}$, then $[H,\sigma_{i}^{z}]=\pm 2\,H$.

Given any complete basis for a single qubit system, we can extend that basis to define a basis over $n$ qubits. Doing this with the found eigenmatrices defines a basis $\{\mathbbm{1},\sigma^{z},\sigma^{+},\sigma^{-}\}^{\otimes n}$. Note as well that $\left(\alpha_{j}\sigma_{i}^{\pm}\right)^{\dagger}=\alpha_{j}^{\dagger}\sigma_{i}^{\mp}$ for $\alpha_{j}\in\mathbb{C}$. This suggests a simple representation in which a Hermitian matrix is defined by its nonzero terms over this basis. Then any Hermitian matrix can be written in the form:

where $\mathscr{Y}=\{\vec{y_{1}},\ldots,\vec{y_{r}}\}$ with $\vec{y}_{i}\in\{0,1\}^{n}$, $\mathscr{V}=\{\vec{v_{1}},\ldots,\vec{v_{r}}\}$ with $\vec{v}_{i}\in\{0,1\}^{n}$, and $\mathscr{W}=\{\vec{w_{1}},\ldots,\vec{w_{r}}\}$ with $\vec{w}_{i}\in\{0,1\}^{n}$ are such that the corresponding $\alpha_{i}\neq 0$. Here $\Delta(\mathscr{Y},\mathscr{V},\mathscr{W})=\{(\vec{y}_{i},\vec{v}_{i},\vec{w}_{i})|y_{i}\in\mathscr{Y},v_{i}\in\mathscr{V},w_{i}\in\mathscr{W}\}$, where $\Delta$ simply takes any indexed element sets and creates the set of the index-wise confederated tuples. A tuple $(\vec{y}_{i},\vec{v}_{i},\vec{w}_{i})$ specifies the indices in which we chose $\sigma^{z}$, $\sigma^{+}$, or $\sigma^{-}$ for each nonzero term. Once that choice is made, hermiticity demands the corresponding second term seen in Eq. 6 to be part of the Hamiltonian as well. However, there are restrictions on what vectors can be chosen. Specifically, $\vec{y}_{i}\cdot\vec{w}_{i}=0$ and $\vec{y}_{i}\cdot\vec{v}_{i}=0$, since choosing $\sigma^{z}$ and a $\sigma^{\pm}$ would actually mean selecting $\sigma^{\pm}$ with a new coefficient $-\alpha_{j}$ instead. Likewise, it should also be the case that $\vec{v}_{i}\cdot\vec{w}_{i}=0$ – otherwise the term would be equivalent to two terms with the same coefficient halved and one taking the term $\sigma^{z}$, the other taking the identity term. As such, this added constraints on $\Delta(\mathscr{Y},\mathscr{V},\mathscr{W})$ so that the representations are unique, which must be enforced before applying the theorem below because the uniqueness of the basis will be actively used. As an example, consider the driver Hamiltonian discussed in the previous section: $H_{d}=\sum_{i=1}^{n-1}(\sigma_{i}^{x}\sigma_{i+1}^{x}+\sigma_{i}^{y}\sigma_{i+1}^{y})=2\,\sum_{i=1}^{n-1}(\sigma_{i}^{+}\sigma_{i+1}^{-}+\sigma_{i}^{-}\sigma_{i+1}^{+})$. For this Hamiltonian, $\mathscr{Y}=\{\vec{0},\ldots,\vec{0}\},\mathscr{V}=\{\vec{e}_{1},\ldots,\vec{e}_{n-1}\},\mathscr{W}=\{\vec{e}_{2},\ldots,\vec{e}_{n}\}$ – where $\vec{e}_{i}$ refers to the standard basis vectors. While the notation is somewhat awkward, it becomes useful for expressing our first major result:

Consider the example discussed in Section II in the context of Theorem III.1. It is easy to see that $v_{1}=(1,0,0,0),w_{1}=(0,1,0,0),v_{2}=(0,1,0,0),w_{2}=(0,0,1,0),v_{3}=(0,0,1,0),w_{3}=(0,0,0,1)$ would satisfy Eq. 7, defining $H_{d}=\sum_{i=1}^{3}\sigma_{i}^{+}\sigma_{i+1}^{-}+\sigma_{i}^{-}\sigma_{i+1}^{+}$. Note that more vector pairs will also satisfy the condition, for example $v_{4}=(0,0,0,1)$ and $w_{4}=(1,0,0,0)$.

The algebraic condition of Theorem III.1 can be used as a starting point to understand several features of CQA. One of them is motivated by the fact that actual implementations of quantum annealing will likely impose a bound on the weight of the driver operators available. Hence, given a set of linear constraints, we could restrict our search for commuting drivers to those with bounded weight.

Consider a set $\mathcal{C}=\{C_{1},\ldots,C_{m}\}$ of linear constraints on $n$ variables, and let $C^{M}$ be the $m\times n$ matrix with coefficients $c_{ij}$ (recall $C_{i}(x)=\sum_{j}c_{ij}x_{j}$). Then, Theorem III.1 tells us that there is a non-diagonal driver commuting with all the constraints, if and only if, the linear system $C^{M}\,\vec{u}=\vec{0}$, where $\vec{u}=\vec{v}-\vec{w}\in\{-1,0,1\}^{n}$. Furthermore, we can see that the number of components of $\vec{u}$ that are non-zero is a lower bound for the weight of such a driver (the weight could be higher if we allow $\sigma^{z}$ operators acting on the variables associated with the vanishing components of $\vec{u}$). This leads to a simpler analysis of the case of bounded weight drivers.

Assume that we are only allowed weight $k$ drivers, and we further impose the condition that they are constructed from $k$ 1-qubit operators that act non trivially in the computational basis (in our case, it means these are chosen from $\{\sigma^{+},\sigma^{-}\}$). Then, the number of such operators is $2^{k-1}\binom{n}{k}$. For fixed $k$, this is polynomial in $n$, and so it is tractable to check all the possible vectors $\vec{u}$ to find which ones satisfy the condition $C^{M}\,\vec{u}=0$. From those that do, we can construct the corresponding weight $k$ driver that will commute with all the constraints, by assigning $\sigma^{+}$ to qubit $i$ if $u_{i}=1$, and $\sigma^{-}$ if $u_{i}=-1$. This is a simple but very useful result in practice: brute force searching for solutions to the condition from Theorem III.1 finds all possible driver Hamiltonians that commute with the embedded constraint operators up to a certain weight in time polynomial on the system size.

2-local means that $\vec{u}$ in the condition $C^{M}\,\vec{u}=0$ has only 2 non zero components, and we can take these to be $(1,1)$ or $(1,-1)$, since the other two possibilities would produce the corresponding Hermitian conjugates. Since multiplying a matrix by a column vector results in a linear combination of the columns of the matrix, with the coefficients given by the vector components, the condition $C^{M}\,\vec{u}=0$ will state that $C^{M}$ has two columns that are the same (if the non zero components of $\vec{u}$ are $(1,-1)$), or are opposites (if they are $(1,1)$). To any distinct pair of columns that satisfy one of these conditions we can associate a distinct weight-2 driver that commutes with the constraints, so the maximum number of such possible weight-2 drivers is $\binom{n}{2}$.

Having found a simple algebraic condition for expressing the commutation relationship of any Hermitian matrix with a linear constraint, we wish to exploit that fact here to find what the general complexity of knowing the existence of such a Hermitian matrix is. We consider the following problem:

Solving this problem would be useful for constructing Hamiltonian drivers for quantum annealing. We can also define 0-1-LP-QCOMMUTE as the binary version, where $c_{ij}\in\{0,1\}$, and also {-1,0,1}-LP-QCOMMUTE, where $c_{ij}\in\{-1,0,1\}$, the type of coefficients used when representing problems like 1-in-3 3-SAT as an ILP. One of the central results of this paper is that these problems are NP-Completecook1971complexity karp1975computational , which can be shown by reducing them to the EQUAL SUBSET SUM problemkarp1972reducibility . This reduction is simple and straightforward for ILP-QCOMMUTE, and we discuss it in this section to give a sense of the connection between the two problems. However, this proof is not enough to imply that 0-1-LP-QCOMMUTE and {-1,0,1}-LP-QCOMMUTE are also NP-Complete, since they could both very well be easier subclasses of ILP-QCOMMUTE. That is not the case, but the proof for 0-1-LP-QCOMMUTE is more involved (and rather tedious) and thus is presented in the Appendix A.

The EQUAL SUBSET SUM problem is known to be NP-Completewoeginger1992equal . We map an instance of the EQUAL SUBSET SUM problem to the ILP-QCOMMUTE problem; the former defined over a set $S=\{s_{1},s_{2},\ldots,s_{n}\}$, with $s_{i}\in\mathbb{Z}^{+}$. Consider the constraint operator defined by $\hat{C}=\sum_{i=1}^{n}s_{i}\sigma_{i}^{z}$, and the vector $\vec{s}=(s_{1},\ldots,s_{n})$. Suppose we can find vectors $\vec{v},\vec{w}$ with binary components, such that $\vec{s}\cdot\left(\vec{v}-\vec{w}\right)=0$ (the algebraic condition derived in Theorem III.1). Then the indices corresponding to the nonzero components of $\vec{v}$ and $\vec{w}$ can be used to identify the sets $A$ and $B$ (respectively) in the EQUAL SUBSET SUM problem.

Suppose there is a solution $H$ to ILP-QCOMMUTE. From Theorem III.1, it follows that $\vec{c}_{i}\cdot\left(\vec{v}-\vec{w}\right)=0$ for the vector $\vec{c}$ associated with constraint $C$ and any nonzero term in the basis $\{\mathbbm{1},\sigma^{z},\sigma^{+},\sigma^{-}\}^{\otimes n}$ with a term $\sigma^{\pm}$ on at least one qubit will be enough to define a new $H^{\prime}$ that will be associated with a solution to EQUAL SUBSET SUM. At least one such element exists for $H$ because $H$ has at least one off-diagonal term in the spin-z basis. We can associate any off-diagonal term of H with $\vec{y},\vec{v},\vec{w}$ such that $H^{\prime}=\alpha\bigotimes_{i=1}^{n}\left(\sigma^{z}\right)^{y_{i}}\left(\sigma^{+}\right)^{v_{i}}\left(\sigma^{-}\right)^{w_{i}}+\alpha^{\dagger}\bigotimes_{i=1}^{n}\left(\sigma^{z}\right)^{y_{i}}\left(\sigma^{+}\right)^{w_{i}}\left(\sigma^{-}\right)^{v_{i}}$ is a matrix with only that off-diagonal term and its complex conjugate for some $\alpha$ and $\vec{v}\neq\vec{0},\vec{w}\neq\vec{0}$. Then for a specific off-diagonal term, every non-zero entry in $\vec{v}$ between $1$ and $n$, call it $i$, picks an integer $s_{i}\in S$ for the set $A$, and $\vec{w}$ does likewise for the set $B$, providing a solution to the corresponding instance of EQUAL SUBSET SUM since $\vec{s}\cdot(\vec{v}-\vec{w})=\left(\sum_{s_{i}\in A}s_{i}\right)-\left(\sum_{s_{i}\in B}s_{i}\right)=0$. Suppose there is a solution $A,B$ to EQUAL SUBSET SUM, then define $\vec{v}$ such that $v_{i}=1$ ($w_{i}=1$) if and only if $s_{i}$ is in $A$ ($B$). Then $H=\bigotimes_{i=1}^{n}\left(\sigma^{+}\right)^{v_{i}}\left(\sigma^{-}\right)^{w_{i}}+\bigotimes_{i=1}^{n}\left(\sigma^{+}\right)^{w_{i}}\left(\sigma^{-}\right)^{v_{i}}$ is a solution to ILP-QCOMMUTE since $\left(\sum_{s_{i}\in A}s_{i}\right)+\left(\sum_{s_{i}\in B}s_{i}\right)=\vec{s}\cdot\left(\vec{v}-\vec{w}\right)=0$. Hence, we have the following result.

Given this result, we can show NP-Completeness by noting that we can check for an off-diagonal term in the spin-z basis in polynomial time. Let $H$ be a proposed solution to the ILP-QCOMMUTE such that there exists nonequivalent indices $i,j$ such that entry $h_{ij}\neq 0$. Checking that $H$ commutes with the constraints is polynomial time. For $k\in\{1,\ldots,n\}$, check if $\text{Tr}_{k}\left(H\sigma_{k}^{+}\right)\neq 0$ or $\text{Tr}_{k}\left(H\sigma_{k}^{-}\right)\neq 0$. $H$ has at least one element $h_{ij}$ that is off-diagonal in the spin-z basis if and only if there exists $k$ such that at least one of these terms is nonzero. Since the partial trace of tensor products is the trace over a specific tensor component, this can be done quickly.

While we have shown that this problem is NP-Hard, we note that for any specific instance of the problem, the practical runtime can still be tractable and therefore a useful avenue for even the hardest instances of optimization problems.Also take note that since every unitary operator is the exponential of a corresponding Hermitian operator, knowing the existence of a unitary operator that commutes with the constraint operators is paramount to knowing a Hermitian matrix exists with the same property. As such, our result immediately translates to the QAOA setting where one wishes to construct unitary operators that will commute with the embedded linear constraint operators.

In the previous section, we proved that finding a Hermitian matrix which commutes with a collection of linear spin-z constraints is NP-Complete. The related question becomes finding a Hermitian matrix which commutes with the constraints, but also connects the feasibility space. Note that two states $\left\lvert\,p\,\right\rangle,\left\lvert\,q\,\right\rangle$ are connected if they are in the same commutation subspace of $H$, that is $\left\langle\,p\,\right\rvert H^{r}\left\lvert\,q\,\right\rangle\neq 0$ for some $r\in\mathbb{Z}^{+}$. As such, for any pair of solutions $i,j$ in the feasibility space, their associated vectors in the computational basis $\left\lvert\,i\,\right\rangle,\left\lvert\,j\,\right\rangle$ should be in the same commutation subspace. In general, when finding a driver Hamiltonian for an anneal that should solve an optimization task, we wish to find a driver that satisfies this condition so that we can ensure that it will be able to reach the entire feasibility space, since commuting with the constraints alone is not enough to ensure this will happen. Consider the graph partitioning example discussed in Section II and Section V, clearly $\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+}$ commutes with the constraint, but fails to connect the entire feasible space. For example, the state $\left\lvert\,0011\,\right\rangle$ is disconnected from $\left\lvert\,1100\,\right\rangle$ under this driver Hamiltonian. While it succeeds not to mix solution states to nonsolution states, it does not mix all solution states with each other. We introduce the problem ILP-QCOMMUTE-NONTRIVIAL which asks to find a driver term that not only commutes with the constraints, but acts nontrivially on the feasible space, so that the action of the driver is such that there exists one solution state which the driver maps to another solution state in the feasible space. If we think about the solution states as vertices in a graph, then transitions induced by driver terms are the edges (and a driver term can induce more than one such edge). Then the problem ILP-QCOMMUTE-NONTRIVIAL asks that the driver term found induces at least one edge in the graph of feasible solutions. For the graph partitioning example discussed above, the term we discussed is clearly a solution to the problem ILP-QCOMMUTE-NONTRIVIAL since it connects $\left\lvert\,1010\,\right\rangle$ to $\left\lvert\,0110\,\right\rangle$, both of which are in the feasible space for this example. Let $P_{i}^{b_{i}}$ be the projection operator corresponding to the energy eigenvalue $b_{i}$ for the constraint operator $\hat{C}_{i}$. Then this formally defines the problem ILP-QCOMMUTE-NONTRIVIAL:

The main difference is that while ILP-QCOMMUTE required nontrivial off-diagonal terms in the spin-z basis, ILP-QCOMMUTE-NONTRIVIAL specifically requires these to be nontrivial in the constraint space of interest, which in general is a non-polynomial problem to verify (i.e. knowing a Hamiltonian has or fails to have an eigenvector for a specific energy level would allow one to know if a Hamiltonian has a solution to hard problems). We show that this problem is at least NP-Hard by reducing a problem closely related to EQUAL SUBSET SUM to ILP-QCOMMUTE-NONTRIVIAL. We begin with the famous NP-Complete SUBSET SUM problem:

While SUBSET SUM asks about the existence of a single solution, we are interested in at least two solutions, defining the problem:

We show that like SUBSET SUM (over positive integerscormen2009introduction ), 2-OR-MORE SUBSET SUM is also NP-Hard:

2-OR-MORE SUBSET SUM is closely related to EQUAL SUBSET SUM because both ask about the existence of two subsets with equal sums, but 2-OR-MORE SUBSET SUM adds the further constraint that these two subsets should have a specific sum. We show that ILP-QCOMMUTE-NONTRIVIAL is NP-Hard through a reduction to 2-OR-MORE SUBSET SUM. Note again that ILP-QCOMMUTE-NONTRIVIAL is not verifiable in polynomial time kitaev2002classical kempe20033 kempe2006complexity and so this reduction is only for the decision version of the problem 2-OR-MORE SUBSET SUM.

In practical applications, we are often able to quickly find some driver terms that commute with the constraints, but then need to know whether they are sufficient to connect the entire feasible space. This raises the following question: given $k$ driver terms (individual basis terms) that commute with the constraints, does some linear combination of them with nonzero coefficients connect the entire feasibility space? In other words, given that we have found $k$ driver terms that commute with the constraints, can we guarantee that some linear combination of them will have the whole feasible subspace as its smallest invariant subspace? Note that not every driver term that does commute with a subspace is necessary to solve this problem. For example, in the case of the constraint $\hat{C}=\sum_{i}^{n}\sigma_{i}^{z}$, it suffices to use the driver terms $\sigma_{i}^{+}\sigma_{i+1}^{-}+\sigma_{i}^{-}\sigma_{i+1}^{+}$ for $i\in[n-1]$. Any linear combination with nonzero coefficients, $H_{d}=\sum_{i}^{n-1}\lambda_{i}\left(\sigma_{i}^{+}\sigma_{i+1}^{-}+\sigma_{i}^{-}\sigma_{i+1}^{+}\right)$, then is a valid Hamiltonian driver to connect the feasible space. Then an extra term, like $\sigma_{1}^{+}\sigma_{3}^{-}+\sigma_{1}^{-}\sigma_{3}^{+}$ is unnecessary, because if $\left\lvert\,\phi\,\right\rangle$ is in the constrained subspace, it follows that $(\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+})\left\lvert\,\phi\,\right\rangle$, $(\sigma_{2}^{+}\sigma_{3}^{-}+\sigma_{2}^{-}\sigma_{3}^{+})\left\lvert\,\phi\,\right\rangle$, $(\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+})(\sigma_{2}^{+}\sigma_{3}^{-}+\sigma_{2}^{-}\sigma_{3}^{+})\left\lvert\,\phi\,\right\rangle$, and $(\sigma_{2}^{+}\sigma_{3}^{-}+\sigma_{2}^{-}\sigma_{3}^{+})(\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+})\left\lvert\,\phi\,\right\rangle$ are as well. Note that $(\sigma_{1}^{+}\sigma_{3}^{-}+\sigma_{1}^{-}\sigma_{3}^{+})=(\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+})(\sigma_{2}^{+}\sigma_{3}^{-}+\sigma_{2}^{-}\sigma_{3}^{+})+(\sigma_{2}^{+}\sigma_{3}^{-}+\sigma_{2}^{-}\sigma_{3}^{+})(\sigma_{1}^{+}\sigma_{2}^{-}+\sigma_{1}^{-}\sigma_{2}^{+})$. If a Hermitian matrix $M$ can be decomposed into a linear combination of products of operators chosen from the set of driver terms $\{\hat{G}_{k}\}$, and $\left\lvert\,\phi\,\right\rangle$ is a state in the constrained space, then for any state $\left\lvert\,\psi\,\right\rangle$ such that $\left\langle\,\psi\,\right\rvert M\left\lvert\,\phi\,\right\rangle\neq 0$ (i.e., any state reachable from $\left\lvert\,\phi\,\right\rangle$ through the action of $M$), is also reachable through the action of the driver terms in $\{\hat{G}_{k}\}$ for the state $\left\lvert\,\psi\,\right\rangle$.

The set of Hamiltonians that commute with a given set of constraints form an algebra (known as the commutant of the set of constraints). Each one of the driver terms we are considering can be seen as a generator of this commutant algebra. This leads us to define the problem ILP-QIRREDUCIBLECOMMUTE-GIVEN-k formally:

As such, ILP-QIRREDUCIBLECOMMUTE-GIVEN-k asks if a given set of driver terms is able to connect the entire feasible space of a set of constraints with the given constraint values. We show that this problem is also NP-Hard by reducing ILP-QCOMMUTE-NONTRIVIAL to ILP-QIRREDUCIBLECOMMUTE-GIVEN-k. We do so by finding a mapping for any instance of ILP-QCOMMUTE-NONTRIVIAL to an instance of ILP-QIRREDUCIBLECOMMUTE-GIVEN-k. Consider such an instance with constraints $\{C_{1},\ldots,C_{m}\}$ and constraint values $\{b_{1},\ldots,b_{m}\}$. Find an integer $a_{1}$ such that $\|\vec{c_{i}}\|_{1}<a_{1}$ for $i\in[m]$. Then expand the space $\{x_{1},\ldots,x_{n}\}$ by appending $x_{n+1},x_{n+2}$. Make the constraints $F_{i}(x)=C_{i}(x_{1},\ldots,x_{n})+a_{1}(x_{n+1}+x_{n+2})$ with constraint values $b_{i}+a_{1}$. Then we can easily find a driver term $\hat{G}_{1}=\sigma_{n+1}^{+}\sigma_{n+2}^{-}+\sigma_{n+1}^{-}\sigma_{n+2}^{+}$ (over the basis $\{\mathbbm{1},\sigma^{+},\sigma^{-},\sigma^{z}\}$) such that $[\hat{G}_{1},\hat{F_{i}}]=0$ for $i\in[m]$. Since the constraint values are $b_{i}+a_{1}$, then the only way to satisfy the constraints is if $(x_{n+1},x_{n+2})\in\{(1,0),(0,1)\}$, since $\sum_{i=1}^{n}c_{i}x_{i}\leq\|c_{i}\|_{1}<a_{1}$ by design.

We have thus altered the constraints such that the feasibility space of the original problem is now doubled in size by the addition of the two variables $x_{n+1}$ and $x_{n+2}$, if the original feasibility space was non-empty. The important structure we note here is that the feasibility subspace of the new constraints is the tensor product of the feasibility subspace of the original constraints, with the subspace generated by the states $\left\lvert\,10\,\right\rangle$ and $\left\lvert\,01\,\right\rangle$ over qubits $x_{n+1},x_{n+2}$. It should also be easy to recognize then that the only nontrivial action induced by the driver terms we choose over $x_{n+1},x_{n+2}$ is precisely the action of $\hat{G}_{1}$.

We can apply the same procedure recursively, adding ancillas $\{x_{n+1},\ldots,x_{n+2k}\}$ and generating $k$ driver terms, such that $a_{i}>\|\vec{c}_{i}\|_{1}+\sum_{j=1}^{i-1}a_{j}$ and $\hat{G}_{i}=(\sigma_{n+2\,i-1}^{+}\sigma_{n+2\,i}^{-}+\sigma_{n+2\,i-1}^{-}\sigma_{n+2\,i}^{+})$, $1\leq i\leq k$. By this construction, when restricted to the ancilla variables, the feasible subspace is spanned by the vectors $\{\bigotimes_{i=1}^{k}|i_{1}i_{2}\rangle,i_{1}+i_{2}=1\}$. Given any element in this subspace, the action of the $\hat{G}_{i}$ driver terms is sufficient to guarantee that any other element of this subspace can also be generated. To proceed with the reduction, we then give the constraints $\{F_{1},\ldots,F_{m}\}$ with constraint values $\{b_{1}+\sum_{i=1}^{k}a_{i},\ldots,b_{m}+\sum_{i=1}^{k}a_{i}\}$ respectively and the drivers $\{\hat{G}_{1},\ldots,\hat{G}_{k}\}$ to our ILP-QIRREDUCIBLECOMMUTE-GIVEN-k solver oracle. Since our $k$ driver terms are all over the added qubits $x_{n+1}$ to $x_{n+2\,k}$, it should be clear that these driver terms say nothing about the feasibility space of the original problem over qubits $x_{1}$ to $x_{n}$. Suppose we are told that our $k$ drivers are sufficient, i.e., they can generate the whole feasible subspace by acting on any one element of that subspace. Then clearly there are no driver terms for the original ILP-QCOMMUTE-NONTRIVIAL decision problem, since none of the $k$ driver terms operate over qubits associated with variables $x_{1}$ to $x_{n}$. Likewise if we are told our $k$ drivers are not sufficient, then clearly there must be at least one nontrivial driver for the original problem, since the drivers are enough to generate all elements of the feasible subspace when restricted to the ancillas. Note that this solves ILP-QCOMMUTE-NONTRIVIAL without giving us a token to verify it. Because this is the most general unstructured version of the problem, is it possible that a different complexity result can be found for a more structured questioning of the same problem. We note that the problem can also have a stronger complexity result, such as a relationship to a higher class in the polynomial hierarchymeyer1972equivalence ; stockmeyer1976polynomial ; garey1979computers , like #Pvaliant1979complexity , to which it has some natural analogues.