Skip to main content
7 of 15
added 1 character in body
MonteNero
  • 3.3k
  • 7
  • 24

The short answer: QUBO problems are known to be NP-hard. So, there should be no analytical solution.

The long answer: You seem confused about solving quadratic problems, eigenvalues and the meaning of analytical solutions.

In mathematics, when we say to solve something analytically, we mean to write an explicit expression without doing any numerics.

Generally, it is not possible to compute eigenvalues analytically for matrices larger than 4 by 4. This well-known result stems from the Galois theory. Finding eigenvalues is equivalent to finding the roots of a matrix's characteristic polynomial, and we know that there is no algebraic (or analytical) solution for polynomials larger than the 4th degree.

This means that if we want to find the eigenvalues of a large matrix, we need to resort to iterative approaches (numerical methods), which are not considered analytical.

Now, with this out of the way. You also seem confused about how we formulate optimization problems for quantum algorithms versus classical optimization.

Eigenvalues of $Q$ are not related to solutions of the quadratic problem $\min_x x^TQx$. Even if we find eigenvalues of $Q$ and the associated eigenvectors numerically, it will not tell us anything about the actual solution $x_{\min}$, even if $x_{\min}$ is allowed to be a real-valued vector. That is, in general, $\lambda_{\min} \neq \min_{x}x^T Q x$ for $x \in \mathbb{R}^n$.

Only in quantum computing do we take quadratic problems and cast them into a problem of finding the lowest eigenvalue (energy) of a diagonal Hamiltonian. In this case, the smallest eigenvalue of the Hamiltonian $H$ corresponds to the smallest objective function value of the optimization problem $x^TQx$. But $Q$ is not a Hamiltonian, and its eigenvalues are unrelated to solutions; see quadratic programming. What we actually have is: $$\lambda_{\min}(H) = x_{\min}^T Q x_{\min}.$$

To expand on the above, for $n \times n$ matrix $Q$, the diagonal Hamiltonian $H$ that we formulate for quantum optimization is of dimension $2^n$. The diagonal entries are all possible values of $x^TQx$ for $x \in \{0,1\}^n$. That is, \begin{align} H = \begin{pmatrix} x_1^TQx_1 && 0 && \cdots && 0\\ 0 && x_2^T Q x_2 && \cdots && 0 \\ \vdots && \ddots && && \vdots \\ 0 && \cdots && 0 && x_{2^n}^TQx_{2^n} \end{pmatrix}. \end{align} Clearly, we never formulate $H$ explicitly as a matrix as it requires evaluation of $x^TQx$ for all $x$.

A few more remarks: If $Q$ has positive/negative eigenvalues, then $x^TQx$ is a convex/concave function for $x \in \mathbb{R}^n$. The solution to $\min$ ($\max$) is trivial. Otherwise, the optimization problem is non-convex. So, there is no hope for any analytical solutions.

Now, if $x$ is a binary string, the problem $x^TQx$ is not convex even if all eigenvalues are positive. This is because the domain of $x^TQx$ is the vertices of a hypercube, i.e., $x \in \{0,1\}^n$, which means that the domain is not convex. Again, there is no hope for an analytical solution.

MonteNero
  • 3.3k
  • 7
  • 24