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\), subject to the constraint “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 to refer to the constraint that exactly \(n\) variables in a sequence of Ising variables take the value \(-1\).

Note that 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 and performs variable grouping according to the given constraints, reducing the search space for more efficient optimization. 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.

When 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\), and the problem \({f}' = {f} + \lambda {g}\) is solved to obtain the constrained optimum.

For example, to minimize 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 an appropriate \(\lambda\) to obtain the desired solution. For details, see Penalty method.

In contrast, N-HOT QAOA uses a constraint-aware ansatz, reducing the given optimization problem to “finding the minimum eigenvalue and eigenvector of the Hamiltonian within the parameter space restricted by the constraints.” 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 set to “a quantum state with 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, and 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\).

Keeping in mind that the qubit label “1” corresponds to the Ising value \(-1\), the phrase “a quantum state with as many ‘1’s as the number of \(-1\)s required by the constraint” can be interpreted as the quantum state obtained by embedding 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), and 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 elements from this subset, i.e., 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}\) and the initial state for \(z_2\) to \(\ket{0}\), resulting in the following constrained QAOA circuit diagram:

Indeed, in the portion of the circuit involving \(z_0\) and \(z_1\), 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, and is expected to find solutions more efficiently compared to the standard approach of relaxing constraints and searching.

---

[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).