---
abstract: 'Previous research on quantum annealing methods focused on effectively modeling systems of linear equations by utilizing quadratic unconstrained binary optimization (QUBO) formulations. These studies take part in enhancing quantum computing algorithms, which extract properties of quantum computers suitable for improving classical computational models. In this paper, we further develop the QUBO formulations of systems of linear equations by applying Sylvester's law of inertia, which explores matrix congruence of any real symmetric matrix to a diagonal matrix. We expect that the proposed algorithm can effectively implement higher dimensional systems of linear equations on a quantum computer. Further experimental verification of the proposed QUBO models as well as their comparisons to classical algorithms are also made.'
author:
- Sun Woo Park
- Kyungtaek Jun
title: 'On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations'
---

INTRODUCTION {#sec:intro}
============

Recent research on quantum computers focus on devising an effective and efficient algorithm which surpasses or complements previously studied algorithms. Among the newly proposed quantum algorithms, quantum annealing method focuses on devising an optimization problem which minimizes an energy level function induced from pre-existent classical models @RI14 [@MV16]. The problem of solving a system of linear equations, which is the focus of this paper, can be also reformulated as an energy minimization problem. In particular, quadratic unconstrained binary optimization (QUBO) formulations, proposed by Borle and Lomonaco, can be utilized to constructing a quadratic energy function for solving a system of linear equations @BL19. Quantum annealing processors effectively parallelize the procedure of solving the minimization problem by utilizing the base 2 representation of real numbers @MV16 [@BL19]. This has potential to greatly reduce computational complexity in solving higher dimensional systems of linear equations compared to previously studied methods. However, physical restraints of contemporary quantum computers may hinder such potential of QUBO formulations. These include partial connectivity of qubits and the limited number of implementable qubits on a quantum computer @BL19 [@JC21]. It is therefore a crucial question to ask what quantum algorithmic simplifications are required to surpass classical algorithms in solving a system of linear equations with large number of variables.

Park, Lee, Kim, Woo, and Jun proposed using matrix congruence to obtain a new simplified QUBO formulation for solving linear systems of equations @PLKWJ21. This congruence relation is known as "Sylvester's law of inertia", which proves congruence relation between diagonal and symmetric matrices, regardless of whether the given matrices are invertible or not @Ay62. We further examine the proposed methodology to show that Sylveter's law can significantly extend the implementable number of variables of a system of linear equations on a quantum computer. This feature is obtained from the fact that the proposed QUBO formulation substantially decreases the occurrences of required entanglements among utilized qubits, which reduces the required qubit connectivity of quantum computers. We construct and carefully examine examples to verify the effectiveness, efficiency, and potential of the proposed algorithm.

Method {#sec: method}
======

Sylvester's Law of Inertia {#subsec: background}
--------------------------

We recall how Sylvester's Law of Inertia simplifies the QUBO formulation of systems of linear equations @PLKWJ21. Let $A := (a_{i,j})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ be a real matrix, and $b := (b_i)_{i=1}^n \in \mathbb{R}^n$ a real column vector. In this section, we do not impose any restrictions on whether $A$ is an invertible matrix. We denote the vector of $n$ unknown variables as $x := (x_i)_{i=1}^n \in \mathbb{R}^n$. Suppose we have the system of linear equations given by $$\label{equation:linear_system}
    Ax = b.$$ The solution which minimizes the $l^2$-norm of the equation $$\label{equation:minimize_square}
    \| Ax - b \|^2 = x^T A^T A x - 2b^T A x + b b^T$$ solves (\[equation:linear\_system\]).

Using the $l^2$-norm, we define the energy level function: $$\label{equation:energy_function_defn}
    f(x) := x^T A^T A x - 2b^T A x.$$ Then the $l^2$-norm minimizing solution of is the solution which satisfies $$f(x) = -b b^T.$$

Recall that $A^T A$ is a positive semidefinite symmetric matrix over $\mathbb{R}$. Sylvester's law of inertia, which is stated below, implies that $A^T A$ can be transformed into a diagonal matrix $D \in \mathbb{R}^{n \times n}$ using matrix congruence relations.

\[Sylvester's Law of Inertia @S52\] Let $S \in \mathbb{R}^{n \times n}$ be any real symmetric matrix. Then there exists a diagonal matrix $D := (d_{i,j})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ and a non-singular real matrix $R:= (r_{i,j})_{i,j=1}^n \in \mathbb{R}^{n \times n}$ such that $$\label{equation:sylvester}
    D = R^T S R.$$ Furthermore, the number of non-zero diagonal entries of $D$ is equal to the rank of the matrix $S$.

Using (\[equation:sylvester\]), the equation (\[equation:minimize\_square\]) can be written as: $$\label{equation:sylvester_1}
    \| Ax - b \|^2 = (R^{-1} x)^T R^T A^T A R  (R^{-1} x) - 2b^T A R (R^{-1} x) + b b^T$$ Let $y \in \mathbb{R}^n$ be a new vector of $n$ unknown variables defined as $$y = R^{-1} x.$$ Note that $R^{-1}$ is a well-defined matrix because $R$ is non-singular. Using the new variable $y$, we can simplify (\[equation:sylvester\_1\]) as: $$\label{equation:sylvester_2}
    \|Ax - b\|^2 = y^T D y - 2 (b^T A R) y + b b^T.$$ The solution which optimizes the $l^2$-norm of (\[equation:sylvester\_2\]) gives the solution to the linear system (\[equation:linear\_system\]). $$\begin{aligned}
 \label{equation:sylvester_final}
    \|Ax - b\|^2 &= \sum_{i=1}^n d_{i,i} y_i^2 - 2 \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n  b_k a_{k,j} r_{j,i} y_i + \sum_{i=1}^n b_i^2\end{aligned}$$ The energy function from can be reformulated as $$\label{equation:energy_function_simplify}
    f(y) := \sum_{i=1}^n d_{i,i} y_i^2 - 2 \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n  b_k a_{k,j} r_{j,i} y_i.$$

QUBO models
-----------

Quantum annealing method can be used to approximate the $l^2$-norm minimizing solution of (\[equation:sylvester\_2\]) by utilizing a combination of qubits $q_{i,j} \in \{0,1\}$ @MV16 [@BL19; @JC21; @J21; @PLKWJ21]. In this subsection, we demonstrate that the proposed QUBO model greatly reduces the complexity of the energy function associated to system of linear equations, compared to that obtained from previously studied quantum annealing approaches.

The number of qubits required for implementing the QUBO model depends on the choice of the representations of variables. In this manuscript, we consider two types of representations, as proposed by O'Malley and Vesselinov @MV16, and Borle and Lomonaco @BL19.

We start with the base-2 representation of the column vector $y$ @MV16: $$\label{equation:QUBO_model_1}
    y_i \approx \sum_{l=-m}^m 2^l q_{i,l}^+ - \sum_{l=-m}^m 2^l q_{i,l}^-$$ The above formulation allows $y_i$ to take both positive and negative values. In fact, the set of qubits satisfy the condition that for any digits $-m \leq l_1, l_2 \leq m$, @J21 [@PLKWJ21] $$\label{equation:qubit_product}
    q_{i,l_1}^+ q_{i,l_2}^- = 0.$$

Under this choice of representation, we can approximate (\[equation:energy\_function\_simplify\]) as follows. The first term of (\[equation:energy\_function\_simplify\]) reduces to: $$\begin{aligned}
\begin{split}
    \sum_{i=1}^n d_{i,i} y_i^2 &\approx \sum_{i=1}^n d_{i,i} \left( \sum_{l=-m}^m 2^l q_{i,l}^+ - \sum_{l=-m}^m 2^l q_{i,l}^- \right)^2 \\
    &= \sum_{i=1}^n d_{i,i} \left( \left( \sum_{l=-m}^m 2^l q_{i,l}^+ \right)^2 + \left( \sum_{l=-m}^m 2^l q_{i,l}^- \right)^2\right) \\
    &= \sum_{i=1}^n d_{i,i} \left( \sum_{l=-m}^m 2^{2l} \left( \left(q_{i,l}^+ \right)^2 + \left( q_{i,l}^- \right)^2 \right)+ \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} \left( q_{i,l_1}^+ q_{i,l_2}^+ + q_{i,l_1}^- q_{i,l_2}^- \right) \right) \\
    &= \sum_{i=1}^n d_{i,i} \left( \sum_{l=-m}^m 2^{2l} \left( q_{i,l}^+ + q_{i,l}^- \right) + \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} \left( q_{i,l_1}^+ q_{i,l_2}^+ + q_{i,l_1}^- q_{i,l_2}^- \right) \right) \label{equation:QUBO_model_1_1}
\end{split}\end{aligned}$$

The second term of (\[equation:energy\_function\_simplify\]) reduces to: $$\begin{aligned}
 \label{equation:QUBO_model_1_2}
    2 \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n  b_k a_{k,j} r_{j,i} y_i &\approx \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=-m}^m 2^{l+1} b_k a_{k,j} r_{j,i} \left( q_{i,l}^+ - q_{i,l}^- \right).\end{aligned}$$ The associated QUBO model is the summation of (\[equation:QUBO\_model\_1\_1\]) and (\[equation:QUBO\_model\_1\_2\]), i.e. $$\begin{aligned}
    \begin{split}
        f(y) &:= \sum_{i=1}^n d_{i,i} \left( \sum_{l=-m}^m 2^{2l} \left( q_{i,l}^+ + q_{i,l}^- \right) + \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} \left( q_{i,l_1}^+ q_{i,l_2}^+ + q_{i,l_1}^- q_{i,l_2}^- \right) \right) \\
        &+ \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n \sum_{l=-m}^m 2^{l+1} b_k a_{k,j} r_{j,i} \left( q_{i,l}^+ - q_{i,l}^- \right)
    \end{split}\end{aligned}$$

Borle and Lomonaco's approximation @BL19 of $y$, on the other hand, takes the following form: $$\label{equation:QUBO_model_2}
    y_i \simeq -2^{m+1} q_i^- + \sum_{l=-m}^m 2^l q_{i,l}^+$$ This approach leads to a new QUBO model which further reduces the number of utilized qubits. The first term of (\[equation:sylvester\_final\]) is approximated by: $$\begin{aligned}
\begin{split}
    \sum_{i=1}^n d_{i,i} y_i^2 &\simeq \sum_{i=1}^n d_{i,i} \left( -2^{m+1} q_i^- + \sum_{l=-m}^m 2^l q_{i,l}^+ \right)^2 \\
    &= \sum_{i=1}^n d_{i,i} \left( 2^{2m+2} (q_i^-)^2 + \sum_{l=-m}^m \left( 2^{2l} (q_{i,l}^+)^2 - 2^{m+l+2} q_i^- q_{i,l}^+  \right) +  \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} q_{i,l_1}^+ q_{i,l_2}^+ \right) \\
    &= \sum_{i=1}^n d_{i,i} \left( 2^{2m+2} q_i^- + \sum_{l=-m}^m 2^{2l} q_{i,l}^+ - \sum_{l=-m}^m 2^{m+l+2} q_i^- q_{i,l}^+ + \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} q_{i,l_1}^+ q_{i,l_2}^+ \right) \label{equation:QUBO_model_2_1}
\end{split}\end{aligned}$$ The second term of (\[equation:sylvester\_final\]) simplifies to: $$\begin{aligned}
\label{equation:QUBO_model_2_2}
    2 \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n  b_k a_{k,j} r_{j,i} y_i &\approx \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n b_k a_{k,j} r_{j,i} \left( -2^{m+2} q_i^- + \sum_{l=-m}^m 2^{l+1} q_{i,l}^+ \right)\end{aligned}$$ Under this approximation technique, the QUBO model can be summarized as the summation of (\[equation:QUBO\_model\_2\_1\]) and (\[equation:QUBO\_model\_2\_2\]). $$\begin{split}
    f(y) &:= \sum_{i=1}^n d_{i,i} \left( 2^{2m+2} q_i^- + \sum_{l=-m}^m 2^{2l} q_{i,l}^+ - \sum_{l=-m}^m 2^{m+l+2} q_i^- q_{i,l}^+ + \sum_{l_1 < l_2} 2^{l_1 + l_2 + 1} q_{i,l_1}^+ q_{i,l_2}^+ \right) \\
    &+ \sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n b_k a_{k,j} r_{j,i} \left( -2^{m+2} q_i^- + \sum_{l=-m}^m 2^{l+1} q_{i,l}^+ \right)
\end{split}$$

After the solution $\hat{y}$ for the $l^2$-norm minimization problem is obtained, we use the matrix $R$ to obtain the original solution to (\[equation:linear\_system\]): $$\hat{x} = R \hat{y}.$$

Example: System of invertible linear equations in 2 variables {#sec:example_1}
-------------------------------------------------------------

Throughout the upcoming sections, we represent the variables of the linear system of equations using base-2 digits as given by O'Malley and Vesselinov (\[equation:QUBO\_model\_1\]). We also assume that $A$, from the equation $Ax = b$, is an invertible matrix.

We illustrate with an example to demonstrate the significance of applying Sylvester's law of inertia. This section closely follows the work of Park, Lee, Kim, Woo, and Jun @PLKWJ21. Suppose we have a linear system $Ax = b$ given by @JC21 [@PLKWJ21]: $$\label{equation:sample_example}
    \begin{pmatrix}
    3 & 1 \\
    -1 & 2
    \end{pmatrix}
    \begin{pmatrix}
    x_1 \\
    x_2
    \end{pmatrix}
    =
    \begin{pmatrix}
    -1 \\
    5
    \end{pmatrix}.$$ The symmetric matrix $A^T A$ can be diagonalized to matrix $D$ using the invertible matrix $R$. $$D = \begin{pmatrix}
    \frac{8}{5} & 0 \\ 0 & \frac{98}{125}
    \end{pmatrix}, \; \; 
    R = \begin{pmatrix}
    \frac{2}{5} & -\frac{1}{25} \\
    0 & \frac{2}{5}
    \end{pmatrix}$$ We use base-2 digits to approximate $y = (y_1, y_2)^T = R^{-1}x$: $$\label{equation:example_QAOA}
    y_i = \sum_{l=1}^3 2^{l-1} q_{i,l} - \sum_{l=1}^3 2^{l-1} q_{i,l+3}$$ In accordance to (\[equation:qubit\_product\]), the set of qubits $\{q_{i,l}\}$ satisfy: $$\begin{aligned}
 \label{equation:equivalence_relation}
\begin{cases}
    & q_{i,l_1} q_{i,l_2}= 0 \\
    & q_{i,j}^2 = q_{i,j}
\end{cases}\end{aligned}$$ where $i \in \{1,2\}$ denotes the components of the variable $y$, $j \in \{1,2,\cdots,6\}$ the digits used in the base 2 representation of $y_i$, $1 \leq l_1 \leq 3$ the positive digits, and $4 \leq l_2 \leq 6$ the negative digits.

For a 2-dimensional system of linear equations, the energy level function from (\[equation:energy\_function\_simplify\]) is given as $$\begin{aligned}
 \label{equation:sylvester_final_1}
    f(y) := \sum_{i=1}^2 d_{i,i} y_i^2 - 2 \sum_{i=1}^2 \sum_{j=1}^2 \sum_{k=1}^2 b_k a_{k,j} r_{j,i} y_i,\end{aligned}$$ where the column vector $y \in \mathbb{R}^n$ which satisfies $$f(y) = -b^T b = -26$$ solves the desired system of linear equations. Substituting (\[equation:example\_QAOA\]) to (\[equation:sylvester\_final\_1\]) and further reducing the terms using conditions on products of qubits from (\[equation:qubit\_product\]) and (\[equation:equivalence\_relation\]), we obtain: $$\begin{aligned}
\begin{split}
    f(y) = &8q_{11} + \frac{32}{5}q_{11}q_{12} + \frac{64}{5}q_{11}q_{13} + \frac{96}{5}q_{12} + \frac{128}{5}q_{12}q_{13} + \frac{256}{5}q_{13} - \frac{24}{5}q_{14} + \frac{32}{5}q_{14}q_{15} + \frac{64}{5}q_{14}q_{16} - \frac{32}{5}q_{15} \\
    &+  \frac{128}{5}q_{15}q_{16} - \frac{882}{125}q_{21} + \frac{392}{125}q_{21}q_{22} - \frac{1568}{125}q_{22} + \frac{784}{125}q_{21}q_{23} + \frac{1568}{125}q_{22}q_{23} - \frac{2352}{125}q_{23} + \frac{1078}{125}q_{24} \\
    &+ \frac{392}{125}q_{24}q_{25} + \frac{2352}{125}q_{25} + \frac{784}{125}q_{24}q_{26} + \frac{1568}{125}q_{25}q_{26} + \frac{5488}{125}q_{26}.
\end{split}\end{aligned}$$ The above energy function gives rise to the $12 \times 12$ matrix $\hat{Q}$, defined as in (\[equation:Qhat\_y\]). $$\label{equation:Qhat_y}
{\small
    \hat{Q} :=
    \begin{pmatrix}
    8 & 6.4 & 12.8  & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 19.2  & 25.6  & 0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 0  & 51.2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 0  & 0  & -4.8 & 6.4 & 12.8 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & -6.4 & 25.6 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & 0  &  0 & -7.056 & 3.136 & 6.272 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & -12.544 & 12.544 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & -18.816 & 0 & 0 & 0 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 8.624 & 3.136 & 6.272 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 0 & 18.816 & 12.544 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 0 & 0 & 43.904 \\
    \end{pmatrix},
}$$ The qubits utilized in the QUBO model are given by the column vector $q_y := [q_{11}, q_{12}, \cdots q_{26}]^T$, which approximates the unknown variables $y = (y_1, y_2)^T$ using base-2 digits. The cost function $f(y)$ can be reformulated in terms of $q_y$ as: $$\label{equation:new_qubo_model}
    f(y) = q_y^T \hat{Q} q_y = y^T D y - 2 b^T A R y.$$ We note that the equality holds under a set of conditions specified in (\[equation:equivalence\_relation\]). Entanglements among pairs of qubits required for approximating $y_i$'s are represented as non-zero entries in the matrix $\hat{Q}$. Finding the vector of utilized qubits $q_y$ which satisfies $q_y^T \hat{Q} q_y = -26$ solves the given linear system.

We clearly observe that Sylvester's law of inertia and a number of conditions on qubit entanglements (\[equation:equivalence\_relation\]) forces a substantial portion of upper triangular matrix entries of $\hat{Q}$ to be equal to zero. This is unfortunately not the case for base-2 digit approximations of the variable $x$ from (\[equation:minimize\_square\]) @JC21. As before, we use $q_x := [q_{11},q_{12},\cdots,q_{26}]^T$ to represent the set of qubits utilized for approximating the variable $x = (x_1, x_2)^T$ using base-2 digits. The energy function formulating the system of lienar equations gives rise to the characterizing matrix $\hat{Q}'$: $$\label{equation:Qhat_prime_y}
{\small
    \hat{Q}' :=
    \begin{pmatrix}
    26 & 40 & 80  & -20  & -40 & -80 & 2 & 4 & 8 & -2 & -4 & -8 \\
    0  & 72  & 160  & -40  & -80 & -160 & 4 & 8 & 16 & -4 & -8 & -16 \\
    0  & 0  & 224 & -80 & -160 & -320 & 8 & 16 & 32 & -8 & -16 & -32 \\
    0  & 0  & 0  & -6 & 40 & 80 & -2 & -4 & -8 & 2 & 4 & 8 \\
    0  & 0  & 0  & 0  & 8 & 160 & -4 & -8 & -16 & 4 & 8 & 16 \\
    0  & 0  & 0  & 0  & 0  &  96 & -8 & -16 & -32 & 8 & 16 & 32 \\
    0  & 0  & 0  & 0  & 0  &  0 & -13 & 20 & 40 & -10 & -20 & -40 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & -16 & 80 & -20 & -40 & -80 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 8 & -40 & -80 & -160 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 23 & 20 & 40 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 0 & 56 & 80 \\
    0  & 0  & 0  & 0  & 0  &  0 & 0 & 0 & 0 & 0 & 0 & 152 \\
    \end{pmatrix},
}$$ where $x^T \hat{Q}' x = x^T A^T A x - 2 b^T A x$ up equivalence relation $q_{i,j}^2 = q_{i,j}$. Then, we have $$\label{equation:vanilla_qubo_model}
    q_x^T \hat{Q}' q_x = x^T A^T A x - 2 b^T A x$$ The qubit entanglements required for representing $x_i$'s correspond to upper triangular entries of the matrix $\hat{Q}'$. The solution to the quadratic equation $q_x^T \hat{Q}' q_x = -26$ is the solution to the linear system (\[equation:sample\_example\]).

Implementation
==============

As shown in the work of Park, Lee, Kim, Woo, and Jun, we process the system of linear equations from Section \[sec:example\_1\] on the D-Wave 2000Q quantum annealer @PLKWJ21. We perform 3 trials of both QUBO models (\[equation:new\_qubo\_model\], \[equation:vanilla\_qubo\_model\]) on the D-Wave system using 10,000 anneals to verify the strength of utilizing Sylvester's theorem.

Vanilla model
-------------

The vanilla QUBO model (\[equation:vanilla\_qubo\_model\]) computes all possible combinations of qubits $q_x$ for $(x_1, x_2) = (-1, 2)$, which are solutions obtained from the 2-dimensional linear system without using Sylvester's law of inertia. There are 7 qubit combinations for $x_1 = -1$, and 6 qubit combinations for $x_2 = 2$ under the base-2 representation from (\[equation:example\_QAOA\]). $$\begin{aligned}
 \label{equation:qubits_all_combinations}
    \begin{split}
        (q_{11}, q_{12}, q_{13}, q_{14}, q_{15}, q_{16}) \in \{ &(0,0,0,1,0,0),(0,1,0,1,1,0), \\ 
        &(0,0,1,1,0,1),(0,1,1,1,1,1), \\
        &(1,0,0,0,1,0),(1,0,1,0,1,1), \\
        &(1,1,0,0,0,1) \} \\
        (q_{21},q_{22},q_{23},q_{24},q_{25},q_{26}) \in \{ &(0,0,1,0,1,0),(0,1,0,0,0,0),\\
        &(0,1,1,0,0,1),(1,0,1,1,1,0),\\
        &(1,1,0,1,0,0),(1,1,1,1,0,1) \}
    \end{split}\end{aligned}$$ The implementation results of the vanilla model is provided in Table \[tab:original\_QUBO\]. We abbreviate the set of all possible qubit combinations of $x_2 = 2$. Each row lists the number of anneals which achieves the given combination of qubits and minimizes the energy function. The vanilla model minimizes the energy function 887, 1181, and 1065 times out of 10,000 anneals.

<span>c|c|c|c|c|c||c|c|c|c|c|c||c||c|c|c</span> & & & & & & & & & & & & &\
& & & & & & & & & & & & & Run 1 & Run 2 & Run 3\
0 & 0 & 0 & 1 & 0 & 0 & & -26.0 & 203 & 66 & 50\
0 & 1 & 0 & 1 & 1 & 0 & & -26.0 & 77 & 49 & 531\
0 & 0 & 1 & 1 & 0 & 1 & & -26.0 & 131 & 147 & 251\
0 & 1 & 1 & 1 & 1 & 1 & & -26.0 & 71 & 116 & 51\
1 & 0 & 0 & 0 & 1 & 0 & & -26.0 & 75 & 43 & 74\
1 & 0 & 1 & 0 & 1 & 1 & & -26.0 & 71 & 83 & 62\
1 & 1 & 0 & 0 & 0 & 1 & & -26.0 & 259 & 677 & 46\
& & Total & 887 & 1181 & 1065\

Proposed model
--------------

Sylvester's law of inertia transforms the solution of the linear system of equations (\[equation:sample\_example\]) to $(y_1, y_2) = (-2,5)$. The objective of the new simplified QUBO model (\[equation:new\_qubo\_model\]) is to obtain the unique combination of qubits $y_i = q_{i1} + 2q_{i2} + 4q_{i3} - q_{i4} - 2q_{i5} - 4q_{i6}$: $$\begin{aligned}
    \begin{split}
        (q_{11}, q_{12}, q_{13}, q_{14}, q_{15}, q_{16}) &= (0, 0, 0, 0, 1, 0) \\
        (q_{21}, q_{22}, q_{23}, q_{24}, q_{25}, q_{26}) &= (1, 0, 1, 0, 0, 0) 
    \end{split}\end{aligned}$$ Specifying the zero terms of the matrix characterizing the system of linear equations may affect the performance of the quantum algorithm on the D-wave computer. To verify this, the proposed model can be executed in two ways. One way is to explicitly code the zero terms appearing on the upper triangular region of the characterizing matrix $\hat{Q}$ to the D-wave system; the other way is to omit them. We display the number of occurrences of the desired qubits in Table \[tab:new\_QUBO\_with\_0\]. The former minimizes the energy function 1526, 2495, and 2063 times out of 10,000 anneals. On the other hand, the latter obtains the lowest energy level for 2103, 4441, and 1727 anneals out of 10,000 anneals.

Discussion
==========

To examine whether the proposed model is effective for processing high dimensional systems of linear equations, the experimental results should verify the following key criteria:

-   Simplifies the characterizing matrix of the QUBO model

-   Requires significantly reduced qubit connectivity of quantum computers

-   Guarantees enhanced and cost-efficient performance

In this section, we carefully examine and assess how the implementation results from the previous section achieve all three criteria for extending the number of implementable variables of systems of linear equations.

Implementation results
----------------------

Both implementations of the proposed QUBO model (\[equation:new\_qubo\_model\]) clearly surpasses the vanilla QUBO model (\[equation:vanilla\_qubo\_model\]) @PLKWJ21. A list of average number of occurrences and the average probability of obtaining the lowest energy levels obtained from all three experiments is provided in Table \[tab:Results Comparison\].

\[hbt!\]

The new QUBO model minimizes the energy function which formulates (\[equation:sample\_example\]) with average probability ranging between $20.28 \%$ and $27.58\%$. These values are at least twice to that obtained from the vanilla QUBO model, which is $10.44 \%$. Among the two implementations of the new QUBO model, omitting the zero entries from the code significantly improves the accuracy of the algorithm.

The block diagonalization of the matrix $Q$ characterizing the QUBO model is a key contributor to the outperformance of the new QUBO model. Suppose we want to obtain a solution of a system of $n$ linear equations with $n$ variables. We further assume that we use $2m$ digits to represent the variables using base-2 digits (\[equation:QUBO\_model\_1\]). The matrix $Q$ characterizing the QUBO model of the systems of linear equations is a $2mn \times 2mn$-matrix.

The number of non-zero entries of $Q_{vanilla}$ characterizing the vanilla QUBO model, as in (\[equation:vanilla\_qubo\_model\]), satisfies the following inequality: $$\# \text{non-zero entries of } Q_{vanilla} \leq \frac{2mn(2mn+1)}{2} = mn(2mn+1).$$ Sylvester's law of inertia allows $Q_{vanilla}$ to be decomposed into $2n$ block matrices of dimension $m \times m$, all of which are upper triangular.The number of non-zero entries of the newly obtained matrix $Q_{new}$, as in (\[equation:new\_qubo\_model\]), satisfies $$\# \text{non-zero entries of } Q_{new} \leq 2n \times \frac{m(m+1)}{2} = mn(m+1).$$ Therefore, assuming that both matrices $Q_{vanilla}$ and $Q_{new}$ have maximal numbers of non-zero entries, Sylvester's law of inertia significantly reduces the number of non-zero entries by at least a factor of $\frac{1}{2n-1}$, and at most a factor of $\frac{1}{2n}$: $$\frac{1}{2n} \leq \frac{\# \text{non-zero entries of } Q_{new}}{\# \text{non-zero entries of } Q_{vanilla}} = \frac{m+1}{2mn+1} \leq \frac{1}{2n-1}.$$ For instance, when $n=2$ and $m=3$, there are at most $78$ non-zero entries in $Q_{vanilla} = \hat{Q}'$ from (\[equation:Qhat\_prime\_y\]). However, there are at most $24$ non-zero entries in $Q_{new} = \hat{Q}$ from (\[equation:Qhat\_prime\_y\]), the number of which is less than a third of 78.

Qubit Connectivity
------------------

The proposed methodology also substantially reduces the required qubit connectivity of quantum computers. The key philosophy behind the proposed methodology is to transform a dense matrix characterizing the systems of linear equations to a sparse matrix using matrix congruence relations. This allows room for implementing a wider range of systems of linear equations on a quantum computer without substantially increasing the number of utilized qubits.

We demonstrate the aformentioned advantage with the characterizing matrices $\hat{Q}$ and $\hat{Q}'$ from (\[equation:Qhat\_prime\_y\]) and (\[equation:Qhat\_y\]). For now, let's assume that all qubit quadratic terms appearing in the energy function (\[equation:new\_qubo\_model\]) let the corresponding pair of qubits to be simultaneously entangled. The matrix $\hat{Q}'$ from the vanilla QUBO model (\[equation:Qhat\_prime\_y\]), requires simultaneous couplings of all pairs of 12 qubits, as shown in the Figure \[graph:qubit\_connectivity\_vanilla\].

On the other hand, our proposed model is characterized by the matrix $\hat{Q}$ from (\[equation:Qhat\_y\]), which can be decomposed into 4 blocks of $3 \times 3$ upper triangular matrices. This implies that any two qubits which process different blocks of matrices do not have to be entangled. Therefore, we require that 3 out of 12 qubits have to be interconnected on the quantum computer. For example, the following diagram of qubit connections is sufficient to simultaneously process the matrix $\hat{Q}$. We see that only a set of three qubits ($\{1,2,3\}, \{4,5,6\}, \{7,8,9\}, \{10,11,12\}$) are fully connected. The diagram of qubit connections displayed in Figure \[graph:qubit\_connectivity\_new\] is far simpler than the one required for implementing the vanilla QUBO model.

In general, suppose that we want to solve a system of $n$ linear equations with $n$ variables. We further assume that we use $2m$ digits and fractional digits to approximate unknown variables using base 2 digits. The matrix $Q_{vanilla}$ characterizing the vanilla QUBO model is a $2mn \times 2mn$ upper triangular matrix. Therefore, a quantum computer would require a fully connected network of $2mn$ qubits to simultaneously process $Q_{vanilla}$. On the other hand, the matrix $Q_{new}$ characterizing the proposed QUBO model can be decomposed into $2n$ upper triangular block matrices of dimension $m \times m$. This implies that a quantum computer would only require $2n$ sets of fully connected network of $2m$ qubits to simultaneously process $Q_{vanilla}$. In other words, our proposed method can reformulate the QUBO model in accordance to the given qubit connectivity of commercial quantum computers. This could enhance efficiency, accuracy, and extensity of the QUBO model for solving a system of linear equations on a quantum computer.

   QUBO model                   Qubit Connectivity
  ------------ -----------------------------------------------------
    Vanilla           Fully connected network of $2mn$ qubits
    Proposed    $2n$ sets of fully connected network of $2m$ qubits

  : A table summarizing the required qubit connectivity for simulatenously processing the characterizing matrix of the QUBO model for a system of linear equations with $n$ variables<span data-label="tab:qubit_connectivity"></span>

Complexity
----------

Given the two matrices $D$ and $R$ associated to $A^T A$ from Sylvester's law of inertia, our proposed method ensures that the computational complexity of solving the QUBO model is in the order of $m n^2$. Evaluating (\[equation:QUBO\_model\_1\_2\]) dominates the computational burden of utilizing our proposed method. Because $b \in \mathbb{R}^n$ is a column vector of dimension $n$, $$\# \text{ calculations for computing } \sum_{i,j,k=1}^n b_k a_{k,j} r_{j,i} \left( q_{i,l}^+ - q_{i,l}^- \right) \leq 4n^2$$ In light of the observation that the range of $l$ is between $-m$ and $m$, $$\# \text{ calculations for computing (\ref{equation:QUBO_model_1_2})} \leq 4(2m+1)n^2.$$ Our model hence provides polynomial speedup in solving the QUBO model in comparison to previously studied quantum annealing methods, whose computational complexities are in the order of $m n^3$. @BL19 [@J21].

Relation to classical QR decomposition methods
----------------------------------------------

One central question which is left unexplored in this manuscript is determining the computational complexity of obtaining the two matrices $D$ and $R$ from Sylvester's law of inertia. Suppose that $A$ is a non-singular matrix. Then the two matrices can be obtained from the $QR$ decomposition of $A$. Indeed, we may factorize $A = QR'$ where $Q \in \mathbb{R}^{n \times n}$ is a real orthogonal matrix, and $R' \in \mathbb{R}^{n \times n}$ is an upper triangular matrix. This yields the following equation: $$(R'^{-1})^T A^T A R'^{-1} = (AR'^{-1})^T (AR'^{-1}) = Q^T Q = I.$$ The diagonal matrix $D$ can be then chosen to be the identity matrix, and $R$ the matrix $R'^{-1}$.

Note that Sylvester's law of inertia does not necessitate the use of $QR$ factorization of $A$. One only needs to guarantee that the column vectors of the real matrix $AR \in \mathbb{R}^{n \times n}$, whose norms are the diagonal entries of $D$, are mutually orthogonal. In other words, comparative advantages that quantum algorithms possess to classical computational methods can prove to be effective in enhancing the cost efficiency of solving systems of linear equations on a quantum computer. For example, parallel computations of solutions of linear systems can be executed, which is not yet achievable on classical implementations such as QR decomposition using householder transformations. Meanwhile, QR decomposition methods can be implemented in a cost-efficient manner by utilizing intrinsic properties of quantum algorithms, including computational bases @MLZ20 and synthesis of quantum circuits @BBVA20. Thus, with effective quantum implementations of Sylvester's law of inertia, we expect to achieve an accurate, efficient, and feasible quantum algorithm for solving systems of linear equations with large number of variables.

Declaration of Interests {#declaration-of-interests .unnumbered}
========================

The authors have no competing interests which may have influenced the work shown in this manuscript.

Contributions {#contributions .unnumbered}
=============

S.W.P. conceived and designed the theoretical experiments, and the theoretical solutions. K.J. obtained the experimental results in a quantum annealer D-wave 2000. All authors wrote the paper.

S.B. R<span>ø</span>nnow, T. and Isakov, S., "Evidence for quantum annealing with more than one hundred qubits," *Nat. Phys* **10**, 218-224 (2014). O'Malley, D. and Vesselinov, V. V., "Toq. jl: A high-level programming language for d-wave machines based on julia," *2016 IEEE High Performance Extreme Computing Conference (HPEC)* 1-7. (2016) Borle, A. and Lomonaco, S. J., "Analyzing the quantum annealing approach for solving linear least squares problems," *International Workshop on Algorithms and Computation*, 289-301 (2019). Jun, K., Conley, R., Huang, Y., Lim, H., and Yu, K., "Solving linear systems by quadratic unconstrained binary optimization on D-Wave quantum annealing device," *Quantum Information Science, Sensing, and Computation XIII* **11726** 117260C (2021). Park, S. W., Lee, H. J., Kim, B. C., Woo, Y., and Jun, K. "On the application of Sylvester's law of inertia to QUBO formulations for systems of linear equations," *Accepted to the Proceedings of the 12th International Conference on ICT Convergence*, 1363–1367 (2021). Ayres, F., "Theory and problems of matrices," *Schaum's Outline Series* 115-124 (1962). Sylvester, J. J., "XIX. A demonstration of the theorem that every homogeneous quadratic polynomial is reducible by real orthogonal substitutions to the form of a sum of positive and negative squares," *The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science* **4** (23) 138–142 (1852). Jun, K. "QUBO formulations for system of linear equations" *arXiv preprint arXiv:2106.10819* (2021). Ma, G., Li, H., and Zhao, J. "Quantum QR decomposition in the computational basis," *Quantum Information Processing* **19**(8), 1–16 (2020) de Brugi<span>è</span>re, T. G., Baboulin, M., Valiron, B., and Allouche, C. "Quantum circuits synthesis using Householder transformations," *Computer Physics Communications* **248**, 107001 (2020).

{'source': 'arXiv_out/2111'}