How to solve quadratic programming problems with continuous variables by using quantum algorithms?

Question

I need to solve a quadratic programming problems with continuous variables, which is defined below: \begin{eqnarray} &&\min \, x^T \Sigma \, x - \mu^T x \nonumber\\ &&\mbox{subject to}: \sum_{i=1}^n x_i = 1 \nonumber\\ &&\quad\,\,\, \quad \quad \quad 0 \le x_i \le 1,\quad i=1,\dots,n \nonumber \end{eqnarray} where we use the following notation:

• $x$ is the $n$-dimensional vector of continuous decision variables,
• $\Sigma \in \mathbb{R}^{n\times n }$ is a constant matrix,
• $\mu \in \mathbb{R}^{n }$ is a constant vector.

The requirement is that I need to solve it with quantum algorithms. For solving QUBO problems, I could use QAOA. But for solving quadratic programming problems with only continuous variables, I don't know which quantum algorithm I could use. Or maybe this problem could be converted to a QUBO problem and then handled by QAOA. I'm not sure.

Could anyone help me?

Answer 1

You can replace continuous variable $x$ with its binary representation $$ x = \sum_{i=0}^{n-1} 2^i y_i + \sum_{j=1}^m 2^{-j} y_j, $$ where $y_i \in \{0;1\}$ are binary variables. The first sum is integer part of $x$ and the second one is its decimal part. Numbers $n$ and $m$ express the accuracy of integer and decimal parts, respectively. Under this setting, the continuous variable problem is switched to QUBO.

However, as you can see, each continuous variable is replaced by $n+m$ binary variables which greatly increases number of variables in QUBO, particularly in case if high accuracy is required.

Another drawback of this approach is ignoring sign of $x$. You can multiply both sums by $2s-1$ where $s$ is a binary variable representing sign. However, in such case your QUBO is changed to HUBO (H = higher order) as you will have terms like $s_1x_1s_2x_2$ comming from part $x^T\Sigma x$. It seems that your problem is concerning portfolio optimization, so you can ignore signs under assumption that short positions are forbidden to prevent changing QUBO to HUBO.

Note that under current state of development this modification prevents you from employing QAOA algorithm as gate-based quantum computers do not have enough qubits (only toy models can be deployed). However, you can think about using D-Wave annealer.

Answer 2

How about reformulating your problem as QUBO by including the constraint into the objective function and treating $x_i$ as binary and then doing some post-processing with measured samples. The constraint of your problem allows to exploits some tricks.

The state $| \psi \rangle$ representing an optimized QAOA circuit will have the following form \begin{align} | \psi \rangle = a_0 |0 \rangle + \cdots +a_{2^n-1} | 2^{n}-1 \rangle. \end{align} Given that the circuit is optimized, it is expected that the state $|k \rangle$ has a probability $|a_k|^2$ near zero for any $k \notin \{1, 2, 4,...,2^{n-1}\}$. This is because for $k \notin \{1, 2, 4,...,2^{n-1}\}$ we get states like $|3 \rangle = |0 \cdots011\rangle$ or $|5 \rangle = |0 \cdots101\rangle$. Such states violate the constraint and introduce penalty. Since QAOA tries to minimize the expected energy it will try to decrease the probability $|a_k|^2$ of such infeasible states. Therefore, the most probable states are $|k\rangle$ for $k \in \{1, 2, 4,...,2^{n-1}\}$. Or in other words, states that have only single bit on e.g. $|1\rangle = |0\cdots01\rangle$ or $|2\rangle = |0\cdots10\rangle$.

Next, you can make $m$ measurements of the circuit to obtain samples. For simplicity, suppose that your problem has 3 variables. Then you sample set will contain many binary strings of the form $001, 010, 100$. These are all feasible solutions. Of course there will be infeasible strings too. But you can ignore them.

Finally, select all the feasible strings and for each bit compute the frequency of 1. This will give the estimate of the probability distribution given by $|\psi\rangle$ for each feasible solution. For example, suppose you sampled 5 bit strings $100, 100, 100, 010, 001$ then the frequency vector for each bit is $(3/5, 1/5, 1/5)$. This is the approximation of probabilities given by $| \psi \rangle$ that only includes feasible solutions. And we always get $x_1 + x_2 + x_3 = 1$.

In the other post it was suggested to use a binary expansion for $x_i$ so that it could model float numbers with limited precision. While it is something that people usually do, such an approach will make your problem extremely hard in comparison to the original problem. First, with each variable $y_k$ you double the search space (and increase the number of qubits). Second, the energy landscape becomes really rugged. Basically, you turn an "easy" problem into a really hard one.