Constrained QAOA Algorithm

Some optimization problems require finding the optimum subject to certain constraints on the variables.

For example, consider minimizing the objective function \({f}(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) in Ising variables \(z\). The constraint is “exactly 1 of \(z_0\), \(z_1\), \(z_2\) takes the value \(-1\).” Without any constraint, the function \({f}(z)\) attains its minimum value \({f}(z) = -5\) at \((z_0, z_1, z_2) = (-1, -1, 1)\). However, this solution violates the constraint. Under the constraint, the minimum is \({f}(z) = -3\) at \((z_0, z_1, z_2) = (1, -1, 1)\).

While many types of variable constraints exist, the kind illustrated above is widely used.

In the case of binary variables \(\{0,1\}\), the constraint that exactly N variable equals \(1\) is often called an N-HOT constraint. For more on N-HOT constraints, see Wikipedia: One-hot.

Note

Here, we also use the term N-HOT for a constraint on a sequence of Ising variables. It requires that exactly \(n\) of them take the value \(-1\).

The one_hot() function in the Amplify SDK is implemented as poly == 1. Therefore, to define a one-hot constraint with Ising variables, you need to express it as an equality constraint using the equal_to() function.

In the following, “constraint” refers to this type of condition.

When running QAOA, Amplify automatically detects optimization problems with N-HOT constraints. It then performs variable grouping according to the given constraints. This grouping reduces the search space and makes the optimization more efficient. Automatic detection can also be disabled. For details, see QAOA type.

N-HOT QAOA

This section explains how variable grouping based on given constraints enables finding optimal solutions.

Consider solving a constrained optimization problem with a solver that cannot handle constraints directly. A (relaxation) polynomial \({g}\) whose optimal solution satisfies the constraint is introduced along with a penalty coefficient \(\lambda\). The problem \({f}' = {f} + \lambda {g}\) is then solved to obtain the constrained optimum.

For example, consider minimizing the objective function \({f}(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) subject to the equality constraint “\(z_0 + z_1 + z_2 = 1\)”. One can set \({g}(z) = (z_0+z_1+z_2 - 1)^2\) and choose \(\lambda\) to obtain the desired solution. For details, see Penalty method.

In contrast, N-HOT QAOA uses a constraint-aware ansatz. This ansatz reduces the given problem to finding the minimum eigenvalue and eigenvector of the Hamiltonian. It searches only the parameter space that the constraints restrict. This approach is expected to be more efficient.

Suppose the optimization problem has \(k\) independent equality constraints (constraints whose variable sets do not overlap). Under these constraints, the variables \(z\) are partitioned into \(k+1\) groups: \(z = (z^{(1)},z^{(2)},\ldots,z^{(k)},{z})\), where \(z^{(1)}, \ldots, z^{(k)}\) are the groups corresponding to the independent equality constraints, and \({z}\) is the group of unconstrained variables.

The ansatz is defined so that independent quantum circuits act on each group: \(\ket{\psi(\boldsymbol{\theta})}=\ket{\psi_{\mathrm{group}, 1}(\boldsymbol{\theta}^{(1)})}\otimes\ket{\psi_{\mathrm{group}, 2}(\boldsymbol{\theta}^{(2)})}\otimes\cdots\ket{\psi_{\mathrm{group}, k}(\boldsymbol{\theta}^{(k)})}\otimes\ket{\psi_{\mathrm{ungroup}}(\boldsymbol{{\theta}})}\). For the unconstrained part \(\ket{\psi_{\mathrm{ungroup}}(\boldsymbol{{\theta}})}\), independent Pauli \(X\) rotation gates \(R_X(\theta)=\mathrm{e}^{i\frac{\theta}{2} X}\) are applied.

The circuit structure is outlined in the following diagram:

Group Ansatz Circuit

For each group \(i = 1,2,\ldots,k\), the ansatz circuit \(U(\boldsymbol{\theta}^{(i)})\) is constructed as follows:

In the circuit diagram, the 2-qubit gate \(A(\theta)\) is realized using a CNOT gate and a Pauli \(Y\) rotation gate \(R_Y(\theta) = \mathrm{e}^{-i\frac{\theta}{2} Y}\) as shown below:

The matrix representation of gate \(A(\theta)\) is:

\[\begin{split} A(\theta) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \sin\theta & \cos\theta & 0 \\ 0 & \cos\theta & -\sin\theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{split}\]

[1][2].

Examining the action of \(A(\theta)\) on the computational basis states, we obtain:

\[ \begin{align}\begin{aligned} A(\theta)\ket{00} &= \ket{00},\\A(\theta)\ket{01} &= \sin\theta\ket{01} +\cos\theta\ket{10},\\A(\theta)\ket{10} &= \cos\theta\ket{01} -\sin\theta\ket{10},\\A(\theta)\ket{11} &= \ket{11} \end{aligned}\end{align} \]

This shows that when the input is a computational basis state, the output preserves the number of “1”s present in the input.

Group Initial State

For each group \(i = 1,2,\ldots,k\), the initial state \(\ket{\psi_{\mathrm{init}, i}}\) is a quantum state. It has as many ‘1’s as the number of \(-1\)s required by the constraint.

Note

As noted in the QAOA theory, the single-qubit computational basis \(\{\ket{0}, \ket{1}\}\) consists of eigenvectors of the Pauli \(Z\) operator. Its eigenvalues correspond to Ising variables. Specifically:

\[\begin{split} \braket{0|Z|0} &= 1 \\ \braket{1|Z|1} &= -1 \end{split}\]

so \(\ket{0}\) corresponds to \(1\) and \(\ket{1}\) corresponds to \(-1\).

Recall that the qubit label “1” corresponds to the Ising value \(-1\). With that in mind, read the phrase “a quantum state with as many ‘1’s as the number of \(-1\)s required by the constraint”. That state is the quantum state that you obtain when you embed the constraint on the Ising variables into the qubits.

Let us give a more mathematical description. Let \(n_i\) be the number of qubits in group \(i\), and \(l_i\) be the number of \(-1\)s required by the constraint. Define the Hamming weight of a bit string \(x^n \in \{0,1\}^n\) as \(w(x^n)\) (the number of “1”s in the string). Then consider the subset of computational basis states \(\{\ket{x^{n_i}}: w(x^{n_i}) = l_i\}\). This is the set of computational basis states containing exactly \(l_i\) ones.

“A quantum state with as many ‘1’s as the number of \(-1\)s required by the constraint” refers to any superposition of the elements of this subset, that is, a state expressed using complex numbers \(c_{x^{n_i}}\) satisfying

\[ \sum_{x^{n_i}:w(x^{n_i}) = l_i} |c_{x^{n_i}}|^2 = 1 \]

as:

\[ \sum_{x^{n_i}:w(x^{n_i}) = l_i} c_{x^{n_i}}\ket{x^{n_i}} \]

In Amplify, the initial state is set to:

\[ \ket{\psi_{\mathrm{init}, i}} = \ket{\underbrace{1\dots1}_{l_i \text{ ones}}\underbrace{0\dots0}_{(n_i -l_i) \text{ zeros}}} \]

Why the Constraint is Preserved

Given the construction of the ansatz circuit \(U(\boldsymbol{\theta}^{(i)})\) and the initial state \(\ket{\psi_{\mathrm{init}, i}}\), the state obtained by applying \(U(\boldsymbol{\theta}^{(i)})\) to \(\ket{\psi_{\mathrm{init}, i}}\) also takes the form:

\[ U(\boldsymbol{\theta}^{(i)})\ket{\psi_{\mathrm{init}, i}} = \sum_{x^{n_i}:w(x^{n_i}) = l_i} c_{x^{n_i}}\ket{x^{n_i}} \]

Let us verify with an example. In the following, we write the gate \(A\) acting on qubits \(i\) and \(j\) as \(A_{(i,j)}\). Consider applying gate \(A(\theta_1)_{(1,2)}\) to the initial state \(\ket{\psi_{\mathrm{init}}} = \ket{100}\).

The result is:

\[ A(\theta_1)_{(1,2)}\ket{\psi_{\mathrm{init}}} = \cos\theta_1\ket{010} - \sin\theta_1\ket{100} \]

Applying gate \(A(\theta_2)_{(2,3)}\) to this state gives:

\[ A(\theta_2)_{(2,3)}A(\theta_1)_{(1,2)}\ket{\psi_{\mathrm{init}}} = \cos\theta_1\cos\theta_2\ket{001} - \cos\theta_1\sin\theta_2\ket{010} - \sin\theta_1\ket{100} \]

No matter how many times this operation is repeated, the output state always contains exactly one “1”. That is, it always remains “a quantum state with as many ‘1’s as the number of \(-1\)s required by the constraint.”

As shown above, the state \(U(\boldsymbol{\theta}^{(i)})\ket{\psi_{\mathrm{init}, i}}\) preserves the number of “1”s in the initial state. By using this ansatz state, it becomes possible to find the optimal solution while maintaining the constraint.

Example

Here we examine the circuit construction of constrained QAOA using a simple example.

Define the problem as \(f(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) and consider:

\[ \min_{z: z_0 + z_1 = 0} {f}(z) \]

For simplicity, we set the ansatz circuit depth (reps) to \(1\).

In this problem, variables \(z_0\) and \(z_1\) belong to the group constrained by \(z_0 + z_1 = 0\), while \(z_2\) is unconstrained.

This constraint requires exactly one of \(z_0\) and \(z_1\) to be \(-1\). Following the procedure described above, Amplify sets the initial state for \(z_0\) and \(z_1\) to \(\ket{10}\). It sets the initial state for \(z_2\) to \(\ket{0}\). The following diagram shows the resulting constrained QAOA circuit:

Indeed, consider the portion of the circuit involving \(z_0\) and \(z_1\). There the number of “1”s in the input state equals the number of “1”s in the output state.

As demonstrated above, the ansatz state \(\ket{\psi(\boldsymbol{\theta})}\) introduced on this page is restricted to states satisfying the \(k\) independent constraints. It is expected to be more efficient than the standard approach, which relaxes the constraints and searches.

---

[1]

B.T. Gard, L. Zhu, G.S. Barron et al. Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm. npj Quantum Inf 6, 10 (2020).

[2]

Y. Ibe, Y.O. Nakagawa, N. Earnest et al. Calculating transition amplitudes by variational quantum deflation. Phys. Rev. Research 4, 013173 (2022).