Corresponding Author: Kyungtaek Jun,
Sun Woo Park: E-mail<EMAIL_ADDRESS>/<EMAIL_ADDRESS>
Kyungtaek Jun: E-mail<EMAIL_ADDRESS>
# On the application of Sylvester’s law of inertia to QUBO formulations for
systems of linear equations

Sun Woo Park  Department of Mathematics, University of Wisconsin-Madison, 480
Linconln Dr., Madison, WI 53706, USA / National Institute for Mathematical
Sciences, 463-1 Jeonmin-dong, Yuseong-gu, Daejon, 34047, Republic of Korea.
Kyungtaek Jun  Research Center, Innovation on Quantum and Computed Tomography,
Seoul, Republic of Korea

###### 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. In particular, the proposed algorithm hints the linear
correspondence between the number of unknown variables of a linear system and
the number of qubits supported on a quantum annealing device. Further
experimental verification of the proposed QUBO models as well as their
comparisons to classical algorithms are also made.

###### keywords:

Quantum Annealing, QUBO, Sylvester’s law of inertia, Systems of linear
equations

##  1 INTRODUCTION

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 [1, 2]. 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 [3]. Quantum annealing
processors effectively parallelize the procedure of solving the minimization
problem by utilizing the base 2 representation of real numbers [2, 3]. 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
[3, 4]. 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.

Recent research on such QUBO formulations focuses on utilizing matrix
congruence to obtain a new simplified model for solving linear systems of
equations [5]. This congruence relation is known as “Sylvester’s law of
inertia”, which guarantees the transformations of real symmetric matrices to
diagonal matrices, regardless of whether the given symmetric matrices are
invertible or not [6]. 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 expect that the proposed feasible optimization technique opens up numerous
possibilities to effectively and efficiently implement a wide range of systems
of linear equations on a quantum annealing device. One particular merit of the
proposed method, which we will primarily focus on this paper, is that
Sylvester’s law of inertia hints the linear correspondence between the number
of unknown variables of a linear system and the number of qubits supported on
a quantum annealing device. For instance, we conjecture that the upcoming
D-wave 7000Q quantum annealing device can process systems of linear equations
with $\frac{7}{2}$ times more unknown variables than those implementable on
the D-wave 2000Q quantum computer. Careful constructions and examinations of
some examples are provided for verification of the potential effectiveness,
efficiency, and extensiveness of the proposed algorithm.

##  2 Method

###  2.1 Sylvester’s Law of Inertia

We recall how Sylvester’s Law of Inertia simplifies the QUBO formulation of
systems of linear equations [5]. Let
$A=(a_{i,j})_{i,j=1}^{n}\in\mathbb{R}^{n\times n}$ be an invertible real
matrix, and $b=(b_{i})_{i=1}^{n}\in\mathbb{R}^{n}$ a real column vector. 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

$Ax=b.$ (1)

The solution which minimizes the $l^{2}$-norm of the equation

$\|Ax-b\|^{2}=x^{T}A^{T}Ax-2b^{T}Ax+bb^{T}$ (2)

solves (1).

Using the $l^{2}$-norm, we define the energy level function:

$f(x)=x^{T}A^{T}Ax-2b^{T}Ax.$ (3)

Then the $l^{2}$-norm minimizing solution of (2) is the solution
$x^{*}\in\mathbb{R}^{n}$ which satisfies

$f(x^{*})=-bb^{T}.$ (4)

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.

######  Theorem 2.1 (Sylvester’s Law of Inertia [7]).

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

$D=R^{T}SR.$ (5)

Furthermore, the number of non-zero diagonal entries of $D$ is equal to the
rank of the matrix $S$.

Using (5), the equation (2) can be written as:

$\|Ax-b\|^{2}=(R^{-1}x)^{T}R^{T}A^{T}AR(R^{-1}x)-2b^{T}AR(R^{-1}x)+bb^{T}$ (6)

Let $y\in\mathbb{R}^{n}$ be a new vector of $n$ unknown variables defined as

$y=R^{-1}x.$ (7)

Note that $R^{-1}$ is a well-defined matrix because $R$ is non-singular. Using
the new variable $y$, we can simplify (6) as:

$\|Ax-b\|^{2}=y^{T}Dy-2(b^{T}AR)y+bb^{T}.$ (8)

The solution which optimizes the $l^{2}$-norm of (8) gives the solution to the
linear system (1).

$\displaystyle\|Ax-b\|^{2}$
$\displaystyle=\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}$
(9)

The energy function from (3) can be reformulated as

$f(y)=y^{T}Dy-2b^{T}ARy=\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}.$
(10)

###  2.2 QUBO models

Quantum annealing method can be used to approximate the $l^{2}$-norm
minimizing solution of (8) by utilizing a combination of qubits
$q_{i,j}\in\\{0,1\\}$ [2, 3, 4, 8, 5]. 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 [2], and
Borle and Lomonaco [3].

We start with the base-2 representation of the column vector $y$ [2]:

$y_{i}\approx\sum_{l=-m}^{m}2^{l}q_{i,l}^{+}-\sum_{l=-m}^{m}2^{l}q_{i,l}^{-}$
(11)

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$, [8, 5]

$q_{i,l_{1}}^{+}q_{i,l_{2}}^{-}=0.$ (12)

Under this choice of representation, we can approximate (10) as follows. The
first term of (10) reduces to:

$\displaystyle\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)\end{split}$
(13)

The second term of (10) reduces to:

$\displaystyle
2\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}b_{k}a_{k,j}r_{j,i}y_{i}$
$\displaystyle\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).$
(14)

The associated QUBO model is the summation of (13) and (14), i.e.

$\displaystyle\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}$
(15)

Borle and Lomonaco’s approximation [3] of $y$, on the other hand, takes the
following form:

$y_{i}\simeq-2^{m+1}q_{i}^{-}+\sum_{l=-m}^{m}2^{l}q_{i,l}^{+}$ (16)

This approach leads to a new QUBO model which further reduces the number of
utilized qubits. The first term of (9) is approximated by:

$\displaystyle\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)\end{split}$
(17)

The second term of (9) simplifies to:

$\displaystyle
2\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}b_{k}a_{k,j}r_{j,i}y_{i}$
$\displaystyle\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)$
(18)

Under this approximation technique, the QUBO model can be summarized as the
summation of (17) and (18).

$\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}$
(19)

After the solution $y^{*}$ for the $l^{2}$-norm minimization problem is
obtained, we use the matrix $R$ to obtain the original solution to (1):

$x^{*}=Ry^{*}$ (20)

###  2.3 Example: System of invertible linear equations in 2 variables

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
(11). 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 previous work by
authors of this paper and their collaborators [5]. Suppose we have a linear
system $Ax=b$ given by [4, 5]:

$\begin{pmatrix}3&1\\\ -1&2\end{pmatrix}\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix}=\begin{pmatrix}-1\\\ 5\end{pmatrix}.$ (21)

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}$ (22)

We use base-2 digits to approximate $y=(y_{1},y_{2})^{T}=R^{-1}x$:

$y_{i}=\sum_{l=1}^{3}2^{l-1}q_{i,l}-\sum_{l=1}^{3}2^{l-1}q_{i,l+3}$ (23)

In accordance to (12), the set of qubits $\\{q_{i,l}\\}$ satisfy:

$\displaystyle\begin{cases}&q_{i,l_{1}}q_{i,l_{2}}=0\\\
&q_{i,j}^{2}=q_{i,j}\end{cases}$ (24)

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
(10) is given as

$\displaystyle
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},$
(25)

where the column vector $y\in\mathbb{R}^{n}$ which satisfies

$f(y)=-b^{T}b=-26$ (26)

solves the desired system of linear equations. Substituting (23) to (25) and
further reducing the terms using conditions on products of qubits from (12)
and (24), we obtain:

$\displaystyle\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}$
(27)

The above energy function gives rise to the $12\times 12$ matrix $\hat{Q}$,
defined as in (28).

${\small\hat{Q}=\setcounter{MaxMatrixCols}{12}\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},}$ (28)

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:

$f(y)=q_{y}^{T}\hat{Q}q_{y}=y^{T}Dy-2b^{T}ARy.$ (29)

We note that the equality holds under a set of conditions specified in (24).
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 (24) 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 (2) [4]. 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}^{\prime}$:

${\small\hat{Q}^{\prime}=\setcounter{MaxMatrixCols}{12}\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},}$
(30)

where $x^{T}\hat{Q}^{\prime}x=x^{T}A^{T}Ax-2b^{T}Ax$ up equivalence relation
$q_{i,j}^{2}=q_{i,j}$. Then, we have

$q_{x}^{T}\hat{Q}^{\prime}q_{x}=x^{T}A^{T}Ax-2b^{T}Ax$ (31)

The qubit entanglements required for representing $x_{i}$’s correspond to
upper triangular entries of the matrix $\hat{Q}^{\prime}$. The solution to the
quadratic equation $q_{x}^{T}\hat{Q}^{\prime}q_{x}=-26$ is the solution to the
linear system (21).

##  3 Implementation

This section verifies how Sylvester’s law of inertia significantly boosts both
effectiveness and extensiveness of QUBO formulations of systems of linear
equations on a quantum annealing device. For all experiments we use the D-Wave
2000Q quantum annealer to process the system of linear equations. We
approximate the unknown variables of a given system of linear equations using
O’Malley and Vesselinov’s technique [2] to effectively compare the proposed
QUBO formulation to previously studied models.

###  3.1 Effectiveness

As shown in previous research [5], we process the system of linear equations
in 2 variables from Section 2.3 on the D-Wave 2000Q quantum annealer. We
perform 3 trials of both QUBO models (29, 31) on the D-Wave system using
10,000 anneals to verify the strength of utilizing Sylvester’s theorem.

####  3.1.1 Vanilla model

The vanilla QUBO model (31) 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 (23).

$\displaystyle\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}$
(32)

The implementation results of the vanilla model is provided in Table 1. 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.

$q_{11}$ | $q_{12}$ | $q_{13}$ | $q_{14}$ | $q_{15}$ | $q_{16}$ | $q_{21}$ | $q_{22}$ | $q_{23}$ | $q_{24}$ | $q_{25}$ | $q_{26}$ | Energy | # Occurrences
---|---|---|---|---|---|---|---|---|---|---|---|---|---
Run 1 | Run 2 | Run 3
0 | 0 | 0 | 1 | 0 | 0 | All 6 combinations | -26.0 | 203 | 66 | 50
0 | 1 | 0 | 1 | 1 | 0 | All 6 combinations | -26.0 | 77 | 49 | 531
0 | 0 | 1 | 1 | 0 | 1 | All 6 combinations | -26.0 | 131 | 147 | 251
0 | 1 | 1 | 1 | 1 | 1 | All 6 combinations | -26.0 | 71 | 116 | 51
1 | 0 | 0 | 0 | 1 | 0 | All 6 combinations | -26.0 | 75 | 43 | 74
1 | 0 | 1 | 0 | 1 | 1 | All 6 combinations | -26.0 | 71 | 83 | 62
1 | 1 | 0 | 0 | 0 | 1 | All 6 combinations | -26.0 | 259 | 677 | 46
|  | Total | 887 | 1181 | 1065
Table 1: Number of occurrences which minimizes the energy function obtained
from (30) [5]. The list of all possible qubit combinations for $x_{2}=2$ is
omitted from the table.

####  3.1.2 Proposed model

Sylvester’s law of inertia transforms the solution of the linear system of
equations (21) to $(y_{1},y_{2})=(-2,5)$. The objective of the new simplified
QUBO model (29) is to obtain the unique combination of qubits
$y_{i}=q_{i1}+2q_{i2}+4q_{i3}-q_{i4}-2q_{i5}-4q_{i6}$:

$\displaystyle\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}$ (33)

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 2. 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.

$q_{11}$ | $q_{12}$ | $q_{13}$ | $q_{14}$ | $q_{15}$ | $q_{16}$ | $q_{21}$ | $q_{22}$ | $q_{23}$ | $q_{24}$ | $q_{25}$ | $q_{26}$ | Energy | Zero Terms | # Occurrences
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Run 1 | Run 2 | Run 3
0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | -26.0 | Yes | 1526 | 2495 | 2063
0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | -26.0 | No | 2103 | 4441 | 1727
Table 2: Number of occurrences which minimizes the energy function obtained
from (28) [5]. The column “Zero Terms” specifies whether the zero terms of the
characterizing matrix are explicitly implemented on the D-wave system.

###  3.2 Extensiveness

We shall now empirically assess the comparative extensiveness of the proposed
QUBO model (10) to that of the vanilla QUBO model (3) in processing a system
of linear equations. Consider the following $4$ systems of linear equations in
$2,3,4,$ and $5$ variables:

$\begin{pmatrix}3&1\\\ -1&2\end{pmatrix}\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix}=\begin{pmatrix}-1\\\ 5\end{pmatrix}$ (34)

$\begin{pmatrix}5&0&1\\\ -1&2&1\\\ 3&2&3\end{pmatrix}\begin{pmatrix}x_{1}\\\
x_{2}\\\ x_{3}\end{pmatrix}=\begin{pmatrix}-65\\\ -15\\\ -80\end{pmatrix}$
(35)

$\begin{pmatrix}5&0&1&3\\\ -1&2&1&4\\\ 3&2&3&5\\\
6&29&30&-14\end{pmatrix}\begin{pmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\
x_{4}\end{pmatrix}=\begin{pmatrix}-65\\\ -15\\\ -80\\\ -1\end{pmatrix}$ (36)

$\begin{pmatrix}5&0&1&3&8\\\ -1&2&1&4&5\\\ 3&2&3&5&26\\\ 6&29&30&-14&-1\\\
5&3&4&-2&65\end{pmatrix}\begin{pmatrix}x_{1}\\\ x_{2}\\\ x_{3}\\\ x_{4}\\\
x_{5}\end{pmatrix}=\begin{pmatrix}-65\\\ -15\\\ -80\\\ -1\\\ 47\end{pmatrix}$
(37)

We determine the extensiveness of both QUBO models (3, 10) by verifying
whether the D-wave quantum annealer using $1,000$ anneals compiles the given
system of linear equations (34, 35, 36, 37) with predetermined number of
base-2 digits representing the unknown variables. For example, a system of
linear equation in $2$ variables where each variable is approximated with $20$
base-2 digits requires the QUBO model to utilize $20\times 2=40$ qubits on the
D-wave quantum annealer. Exemplary compilations of these systems of linear
equations can be found in the following github repository:
https://github.com/ktfriends/Quantum_Computing/tree/main/Sylvester_Theorem

####  3.2.1 Vanilla model

As shown in Table 3, the D-wave quantum annealer compiles the vanilla QUBO
model (3) which utilizes at most $64$ qubits. We omitted the experimental
results obtained for QUBO models utilizing more than $80$ qubits, for all
these attempts failed to compile on the D-wave quantum annealer.

Linear system | # variables | # base-2 digits | # utilized qubits | Compile
---|---|---|---|---
(34) | 2 | 20 | 40 | $\circ$
(35) | 3 | 20 | 60 | $\circ$
(36) | 4 | 20 | 80 | $\times$
(34) | 2 | 6 | 12 | $\circ$
(34) | 2 | 32 | 64 | $\circ$
(34) | 2 | 34 | 68 | $\times$
Table 3: Number of qubits implementable on a D-wave 2000Q quantum annealer
using the vanilla QUBO model (3). Experimental results suggest that the
vanilla QUBO model can utilize at most $64$ qubits.

####  3.2.2 Proposed model

Experimental results suggest that the D-wave quantum annealer compiles the
proposed QUBO model (10) utilizing at most $132$ qubits, as demonstrated in
Table 4.

Linear system | # variables | # base-2 digits | # utilized qubits | Compile
---|---|---|---|---
(34) | 2 | 20 | 40 | $\circ$
(35) | 3 | 20 | 60 | $\circ$
(36) | 4 | 20 | 80 | $\circ$
(37) | 5 | 20 | 100 | $\circ$
(34) | 2 | 6 | 12 | $\circ$
(34) | 2 | 60 | 120 | $\circ$
(34) | 2 | 66 | 132 | $\circ$
(34) | 2 | 68 | 136 | $\times$
(34) | 2 | 70 | 140 | $\times$
(34) | 2 | 80 | 160 | $\times$
(34) | 2 | 100 | 200 | $\times$
Table 4: Number of qubits implementable on a D-wave 2000Q quantum annealer
using the proposed QUBO model (10). Experimental results suggest that the
proposed QUBO model can utilize at most $132$ qubits.

##  4 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:

  * •

Effectiveness: Guarantees enhanced and cost-efficient performance with the
simplified QUBO model

  * •

Extensiveness: Extends implementable QUBO model with reduced qubit
connectivity

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. We expect
that the proposed model effectively enhances efficiency, accuracy, and
extensiveness of previously studied QUBO models for solving a system of linear
equations on a quantum annealing device.

###  4.1 Effectiveness and the simplified characterization matrix

As demonstrated in Section 3.1, both implementations of the proposed QUBO
model (29) clearly surpasses the vanilla QUBO model (31) [5]. 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
5.

# Trial | Vanilla QUBO model | New QUBO model | New QUBO model
---|---|---|---
(Table 1) |  (Table 2, row 1) |  (Table 2, row 2)
Run 1 | 887 | 1526 | 2103
Run 2 | 1181 | 2495 | 4441
Run 3 | 1065 | 2063 | 1727
Average # Occurrences | 1044 | 2028 | 2758
Average Probability | 10.44% | 20.28 % | 27.58 %
Table 5: A summary of the average number of occurrences that minimize the
energy level function from Section 3.1 for all three models [5].

The new QUBO model minimizes the energy function which formulates (21) 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 (11). 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 (31), satisfies the following inequality:

$\\#\text{non-zero entries of }Q_{vanilla}\leq\frac{2mn(2mn+1)}{2}=mn(2mn+1).$
(38)

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 (29),
satisfies

$\\#\text{non-zero entries of }Q_{new}\leq 2n\times\frac{m(m+1)}{2}=mn(m+1).$
(39)

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}.$ (40)

For instance, when $n=2$ and $m=3$, there are at most $78$ non-zero entries in
$Q_{vanilla}=\hat{Q}^{\prime}$ from (30). However, there are at most $24$ non-
zero entries in $Q_{new}=\hat{Q}$ from (30), the number of which is less than
a third of 78.

###  4.2 Extensiveness and reduced qubit connectivity

The strength of the proposed QUBO model can be also found from its
extensiveness in compiling a wide variety of systems of linear equations.
Further implementations of linear systems on D-wave quantum annealer, as
demonstrated in Section 3.2, clearly show that the proposed model allows
compilations of higher dimensional systems of linear equations that previous
models were not able to achieve. In fact, experimental verification suggests
that the proposed model doubles the utilizable number of qubits compared to
other QUBO formulations.

Such expansions in a range of implementable system of equations originates
from substantial reduction in the connectivity of qubits required to perform
the QUBO model on 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}^{\prime}$ from (30) and (28). For now, let’s assume
that all qubit quadratic terms appearing in the energy function (29) let the
corresponding pair of qubits to be simultaneously entangled. The matrix
$\hat{Q}^{\prime}$ from the vanilla QUBO model (30), requires simultaneous
couplings of all pairs of 12 qubits, as shown in the graph on the left of
Figure 1 (We note that the graphs are drawn in a similar fashion to those
appearing on a previous work by Zbinden et al. [11]).

123456789101112123456789101112

Figure 1: A graph of connectivity of $12$ qubits required to simultaneously
process the characterizing matrix $\hat{Q}^{\prime}$ of the vanilla QUBO model
(left) and $\hat{Q}$ of the proposed QUBO model (right). The QUBO model
formulates a system of linear equations in $2$ variables where each variable
is approximated by $6$ base-2 digits. Note that $3$ out of the $6$ qubits are
used to represent positive digits, whereas the other $3$ are used to represent
negative digits.

On the other hand, our proposed model is characterized by the matrix $\hat{Q}$
from (28), 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 the graph on the
right of Figure 1 is far simpler than the one required for implementing the
vanilla QUBO model. The stark difference between the connectivity of qubits
required for two QUBO formulations becomes clearly noticeable for system of
linear equations utilizing $40$ qubits, see Figure 2 for instance.

1234567891011121314151617181920212223242526272829303132333435363738394012345678910111213141516171819202122232425262728293031323334353637383940

Figure 2: A graph of connectivity of $40$ qubits required to simultaneously
process the characterizing matrix of the vanilla QUBO model (left) and that of
the proposed QUBO model (right). The QUBO model formulates a system of linear
equations in $2$ variables where each variable is approximated by $20$ base-2
digits. Note that $10$ out of the $20$ qubits are used to represent positive
digits, whereas the other $10$ are used to represent negative digits.

In general, suppose that we want to solve a system of $n$ linear equations
with $n$ variables. We further assume that we use $m$ positive digits and $m$
negative 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.

QUBO model | Qubit Connectivity
---|---
Vanilla | Fully connected network of $2mn$ qubits
Proposed |  $2n$ sets of fully connected network of $m$ qubits
Table 6: 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

The underlying topology of connectivity of qubits on the D-wave 2000Q quantum
annealer is a key factor that determines the upper bound on the number of
qubits the given QUBO formulation can execute. The D-wave 2000Q quantum
annealer uses the Chimera topology $C_{16,16,4}$ to model the connectivity of
$2048$ qubits [12, 14]. Given a positive number $m$, the space $C_{m,m,4}$,
comprised of $4m^{2}$ qubits, is an interconnected $m\times m$ grid of
bipartite graphs $K_{4,4}$. There exists a natural embedding of the complete
graph with $4m$ nodes $K_{4m}$ inside $C_{m,m,4}$ as a graph minor,
corresponding to a triangle on the $m\times m$ grid consisting of $4m$ chains
of length $m+1$ [12, 13]. As for the topology $C_{16,16,4}$, the space has a
naturally embedded complete graph $K_{64}$ inside $C_{16,16,4}$ as a graph
minor.

$K_{64}\hookrightarrow C_{16,16,4}$ (41)

Observant readers may have already noticed that the number of nodes of the
complete graph that can be embedded in $C_{16,16,4}$ is precisely the
empirical maximum number of qubits the vanilla QUBO model can process. As
Figure 1 and 2 illustrate, the vanilla QUBO model utilizing $N$ qubits can be
represented as a complete graph with $N$ nodes $K_{N}$. There doesn’t exist a
natural embedding of complete graphs with number of nodes exceeding $64$ into
the Chimera topology $C_{16,16,4}$. Thus, the D-wave quantum annealer can
process the previously studied QUBO models which utilizes up to $64$ qubits.

Meanwhile, the proposed model significantly bounds the connectivity of qubits
regardless of the number of variables used in the system of linear equations.
As previously assumed, suppose the proposed model formulates a linear system
in $n$ variables, with each variable represented by $m$ base-2 positive digits
and $m$ base-2 negative digits. As shown in Figure 1 and 2, the model can be
represented as a union of $4$ complete graphs with $m$ nodes $K_{m}$.
Experimental results suggest that the D-wave 2000Q quantum annealer succeeds
in embedding $4$ copies of complete graphs with $33$ nodes $K_{33}$ into the
space $C_{16,16,4}$ (Note that $K_{33}$ can be embedded into $C_{16,16,4}$
because $K_{64}$, which includes $K_{33}$, can be). This gives an explanation
of why the proposed model can process $33\times 4=132$ qubits instead of the
$64$ qubits the previously studied QUBO models can process.

$\bigsqcup_{i=1}^{4}K_{33}\hookrightarrow C_{16,16,4}$ (42)

Even better, the proposed model establishes a linear relation between the
implementable dimension of the system of linear equations on the quantum
annealer and the number of qubits on the quantum annealing device. This
achievement is made possible because the connectivity of qubits is solely
determined from the number of base-2 digits used to represent each variable,
regardless of the number of unknown variables used in the system of linear
equations. For example, given a positive number $m>0$, suppose the quantum
annealing device supports the connectivity of $2048m^{2}$ qubits using the
Chimera topology $C_{16m,16m,4}$. Previously researched QUBO models can
process the QUBO model which utilizes $64m$ qubits [12, 13]. In particular,
the vanilla QUBO model establishes a square-root relation between the number
of qubits on the quantum annealer and the number of qubits executed by the
QUBO model.

$\text{\\# implementable qubits (vanilla QUBO)}\leq\sqrt{2\times(\text{\\#
qubits on }C_{16m,16m,4})}$ (43)

On the other hand, the new QUBO model can process $132m^{2}$ qubits using the
same topology. This is because the topology $C_{16m,16m,4}$ contains $m^{2}$
copies of $C_{16,16,4}$, each space of which can process $132$ qubits using
the proposed model. Thus, we obtain:

$\text{\\# implementable qubits (proposed
QUBO)}\leq\frac{33}{512}\times(\text{\\# qubits on }C_{16m,16m,4}).$ (44)

Prospective quantum annealing devices are expected to support more number of
qubits by enlarging the dimensions of planar grids of the Chimera topology. In
other words, one shall expect linear growth in the number of variables of
systems of linear equations implementable on quantum annealing devices, as
shown in (44). For example, the D-wave 7000Q quantum annealer aims to enact
qubit connections on Zephyr topology $Z_{m}$, obtained as a quotient space of
the Chimera topology $C_{2m+1,2m+1,8}$ [14]. We conjecture that the number of
implementable unknown variables supported by the D-wave 7000Q quantum annealer
will be $\frac{7}{2}$ times more than that supported by the D-wave 2000Q
quantum annealer.

###  4.3 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 $mn^{2}$. Evaluating (14) 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}$ (45)

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}.$ (46)

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 $mn^{3}$. [3, 8].

###  4.4 Limitations and relation to classical algorithms

A 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^{\prime}$ where $Q\in\mathbb{R}^{n\times n}$ is a real
orthogonal matrix, and $R^{\prime}\in\mathbb{R}^{n\times n}$ is an upper
triangular matrix. This yields the following equation:

$(R^{\prime-1})^{T}A^{T}AR^{\prime-1}=(AR^{\prime-1})^{T}(AR^{\prime-1})=Q^{T}Q=I.$
(47)

The diagonal matrix $D$ can be then chosen to be the identity matrix, and $R$
the matrix $R^{\prime-1}$.

One limitation of the proposed method is the potential difficulty in computing
the matrices $D$ and $R$ for any given real matrix $A$. Assuming that both $D$
and $R$ are obtained, however, the QUBO model can effectively parallelize the
computational process of obtaining solutions to systems of linear equations.

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 [9] and synthesis of quantum circuits [10].
These methods are expected to achieve polynomial speedup in computing an
orthogonal basis of a vector space in comparison to previously researched
classical algorithms. Thus, with prospective effective quantum implementations
of Sylvester’s law of inertia, we shall expect to achieve an accurate,
efficient, and feasible quantum algorithm for solving systems of linear
equations with large number of variables.

## Declaration of Interests

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

## Contributions

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.

## References

  * [1] S.B. Rønnow, T. and Isakov, S., ”Evidence for quantum annealing with more than one hundred qubits,” _Nat. Phys_ 10, 218-224 (2014).
  * [2] 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)
  * [3] 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).
  * [4] 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).
  * [5] 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).
  * [6] Ayres, F., ”Theory and problems of matrices,” _Schaum’s Outline Series_ 115-124 (1962).
  * [7] 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).
  * [8] Jun, K. ”QUBO formulations for system of linear equations” _arXiv preprint arXiv:2106.10819_ (2021).
  * [9] Ma, G., Li, H., and Zhao, J. ”Quantum QR decomposition in the computational basis,” _Quantum Information Processing_ 19(8), 1–16 (2020)
  * [10] de Brugière, T. G., Baboulin, M., Valiron, B., and Allouche, C. ”Quantum circuits synthesis using Householder transformations,” _Computer Physics Communications_ 248, 107001 (2020).
  * [11] Zbinden, S., B’́artschi, A., Djidjev, H., and Eidenbenz, S. ”Embedding algorithms for quantum annealers with Chimera and Pegasus connection topologies,” _International Conference on High Performance Computing_ 187–206 (2020)
  * [12] Boothby, K., King, A.D., and Roy, A. ”Fast clique minor generation in Chimera qubit connectivity graphs,” _Quantum Information Processing_ 15, 495–508 (2016).
  * [13] Choi, V. ”Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design,” _Quantum Information Processing_ 10 (3), 343–353 (2011).
  * [14] Boothby, K., King, A.D., and Raymond, J. ”Zephyr Topology of D-Wave Quantum Processors” _Technical report available at https://www.dwavesys.com/media/fawfas04/14-1056a-a_zephyr_topology_of_d-wave_quantum_processors.pdf_ 1–18 (2021).