Return to Answer

Edit: You seem interested in a provably optimal solution to an optimization problem (not "analytical" or "exact"). In that case, Simplex and its more advanced variants/implementations (Gurobi solver, CPLEX, Gecko optimization library, Google OR-Tools) should be used. Those algorithms can yield a provably optimal solution to the problem subject to some additional runtime execution constraints. There is no need to brute force all solutions.

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 like Rayleigh), which are not considered analytical.

Now, with this out of the way, let's look at the eigenvalues of $Q$ and their relation to $\min_x x^TQx$.

Eigenvalues of $Q$ are not related to solutions of the quadratic problem $\min_x x^TQx$. For example, consider a $2 \times 2$ diagonal $Q$ with entries $1$ and $-1$. The eigenvalues are $1$ and $-1$, but the minimum of $x^TQx$ is unbounded for $x$ unbounded. Another example, diagonal $Q$ with entries $1$ and $2$. The smallest eigenvalue is $1$, but the minimum is $0$ as $x_{\min}=(0,0)$.

Since you want $x \in \{0,1\}^n$, I don't think looking into eigenvalues of $Q$ is a good approach. It is best if you look at integer programming methods: stuff like Simplex algorithm with branch and bound method, cutting planes etc. By the way, Simplex combined with the branch and bound method can be done by hand for small problems. Alternatively, Simplex combined with cutting planes can also be done by hand for very small problems. The latter has the advantage that it can be graphed on paper. Maybe this is what you were asking for. See these notes for an introductory material.

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.

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 like Rayleigh), which are not considered analytical.

Now, with this out of the way, let's look at the eigenvalues of $Q$ and their relation to $\min_x x^TQx$.

Eigenvalues of $Q$ are not related to solutions of the quadratic problem $\min_x x^TQx$. For example, consider a $2 \times 2$ diagonal $Q$ with entries $1$ and $-1$. The eigenvalues are $1$ and $-1$, but the minimum of $x^TQx$ is unbounded for $x$ unbounded. Another example, diagonal $Q$ with entries $1$ and $2$. The smallest eigenvalue is $1$, but the minimum is $0$ as $x_{\min}=(0,0)$.

Since you want $x \in \{0,1\}^n$, I don't think looking into eigenvalues of $Q$ is a good approach. It is best if you look at integer programming methods: stuff like Simplex algorithm with branch and bound method, cutting planes etc. By the way, Simplex combined with the branch and bound method can be done by hand for small problems. Alternatively, Simplex combined with cutting planes can also be done by hand for very small problems. The latter has the advantage that it can be graphed on paper. Maybe this is what you were asking for. See these notes for an introductory material.

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 \times 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.

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, let's look at the eigenvalues of $Q$ and their relation to $\min_x x^TQx$.

Eigenvalues of $Q$ are not related to solutions of the quadratic problem $\min_x x^TQx$. For example, consider a $2 \times 2$ diagonal $Q$ with entries $1$ and $-1$. The eigenvalues are $1$ and $-1$, but the minimum of $x^TQx$ is unbounded for $x$ unbounded. Another example, diagonal $Q$ with entries $1$ and $2$. The smallest eigenvalue is $1$, but the minimum is $0$ as $x_{\min}=(0,0)$.

Since you want $x \in \{0,1\}^n$, I don't think looking into eigenvalues of $Q$ is a good approach. It is best if you look at integer programming methods: stuff like Simplex algorithm with branch and bound method, cutting planes etc. By the way, Simplex combined with the branch and bound method can be done by hand for small problems. Alternatively, Simplex combined with cutting planes can also be done by hand for very small problems. The latter has the advantage that it can be graphed on paper. Maybe this is what you were asking for.

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.

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 like Rayleigh), which are not considered analytical.

Now, with this out of the way, let's look at the eigenvalues of $Q$ and their relation to $\min_x x^TQx$.

Eigenvalues of $Q$ are not related to solutions of the quadratic problem $\min_x x^TQx$. For example, consider a $2 \times 2$ diagonal $Q$ with entries $1$ and $-1$. The eigenvalues are $1$ and $-1$, but the minimum of $x^TQx$ is unbounded for $x$ unbounded. Another example, diagonal $Q$ with entries $1$ and $2$. The smallest eigenvalue is $1$, but the minimum is $0$ as $x_{\min}=(0,0)$.

Since you want $x \in \{0,1\}^n$, I don't think looking into eigenvalues of $Q$ is a good approach. It is best if you look at integer programming methods: stuff like Simplex algorithm with branch and bound method, cutting planes etc. By the way, Simplex combined with the branch and bound method can be done by hand for small problems. Alternatively, Simplex combined with cutting planes can also be done by hand for very small problems. The latter has the advantage that it can be graphed on paper. Maybe this is what you were asking for. See these notes for an introductory material.

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.