# Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large
condition numbers

Peniel Bertrand Tsemo  Centre for Quantum Engineering, Research and Education,
TCG CREST, Sector V, Salt Lake, Kolkata 700091, India  Akshaya Jayashankar
Centre for Quantum Engineering, Research and Education, TCG CREST, Sector V,
Salt Lake, Kolkata 700091, India  K. Sugisaki  Centre for Quantum Engineering,
Research and Education, TCG CREST, Sector V, Salt Lake, Kolkata 700091, India
Graduate School of Science and Technology, Keio University, 7-1 Shinkawasaki,
Saiwai-ku, Kawasaki, Kanagawa 212-0032, Japan  Quantum Computing Center, Keio
University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, Kanagawa 223-8522, Japan
Nishanth Baskaran  Department of Electrical and Computer Engineering, The
University of British Columbia, Vancouver, British Columbia V6T 1Z4, Canada
Sayan Chakraborty  Institute for Advancing Intelligence, TCG CREST, Sector V,
Salt Lake, Kolkata 700091, India  Academy of Scientific and Innovative
Research (AcSIR), Ghaziabad- 201002, India  V. S. Prasannaa
<EMAIL_ADDRESS>Centre for Quantum Engineering, Research and
Education, TCG CREST, Sector V, Salt Lake, Kolkata 700091, India  Academy of
Scientific and Innovative Research (AcSIR), Ghaziabad- 201002, India

###### Abstract

Although the Harrow-Hassidim-Lloyd (HHL) algorithm offers an exponential
speedup in system size for treating linear equations of the form
$A\vec{x}=\vec{b}$ on quantum computers when compared to their traditional
counterparts, it faces a challenge related to the condition number
($\mathcal{\kappa}$) scaling of the $A$ matrix. In this work, we address the
issue by introducing the post-selection-improved HHL (Psi-HHL) approach that
involves a simple yet effective modification of the HHL algorithm to extract a
feature of $\ket{x}$, and which leads to achieving optimal behaviour in
$\mathcal{\kappa}$ (linear scaling) for large condition number situations.
This has the important practical implication of having to use substantially
fewer shots relative to the traditional HHL algorithm. We carry out two sets
of simulations, where we go up to 26-qubit calculations, to demonstrate the
ability of Psi-HHL to handle situations involving large $\mathcal{\kappa}$
matrices via: (a) a set of toy matrices, for which we go up to size $64\times
64$ and $\mathcal{\kappa}$ values of up to $\approx$ 1 million, and (b) a
deep-dive into quantum chemistry, where we consider matrices up to size
$256\times 256$ that reach $\mathcal{\kappa}$ of about 466. The molecular
systems that we consider are Li2, RbH, and CsH. Although the feature of
$\ket{x}$ considered in our examples is an overlap between the input and
output states of the HHL algorithm, our approach is general and can be applied
in principle to any transition matrix element involving $\ket{x}$.

††preprint: APS/123-QED

###### Contents

  1. I Introduction
  2. II Theory and Methodology
    1. II.1 The HHL algorithm
    2. II.2 The Psi-HHL approach
      1. II.2.1 HHL1: Computing the wrong signal
      2. II.2.2 HHL2: Computing the mixed signal
      3. II.2.3 Psi-HHL: Subtracting signals
    3. II.3 Complexity aspects
  3. III Results and discussions
    1. III.1 Toy matrices: $4\times 4$ through $64\times 64$
    2. III.2 Quantum chemistry matrices
      1. III.2.1 The $A$ matrix dimension
      2. III.2.2 Condition number of the $A$ matrix
      3. III.2.3 HHL and Psi-HHL results
  4. IV Conclusion
  5. A1 Details on calculations involving toy matrices from size $4\times 4$ through $64\times 64$
  6. A2 Details on calculations involving quantum chemistry matrices
    1. A2.1 $A$ matrix and $\vec{b}$ vector generation
    2. A2.2 Orbital character analysis

##  I Introduction

The Harrow-Hassidim-Lloyd (HHL) algorithm was proposed to solve equations of
the form $A\vec{x}=\vec{b}$, where $A$ is a known and sparse $2^{N}\times
2^{N}$ matrix and $\vec{b}$ is a $2^{N}\times 1$ vector, on quantum computers
with a time complexity that is exponentially lower in system size than those
of the best known classical methods [1]. Further, via amplitude encoding,
$\vec{b}$, which is a $2^{N}\times 1$ vector, is encoded into a
log${}_{2}{2^{N}}$-qubit state (for brevity, we shall hereafter denote $2^{N}$
as $n$). Thus, when the HHL approach is applied to ‘killer applications’ of
quantum computing such as quantum chemistry, there is a natural exponential
suppression in qubit number relative to the other known approaches such as the
quantum phase estimation (QPE) and the variational quantum eigensolver (VQE)
algorithms [2], thus opening new avenues to apply HHL for calculating
properties of large molecules.

Despite possessing the aforementioned advantages, the HHL algorithm relies
upon the probability of successfully post-selecting $1$ on the HHL ancilla
qubit, that is, $P(1)$ [1]. It is known that there is a substantial decrease
in $P(1)$ with increase in the condition number of the problem matrix $A$,
which we shall denote by $\mathcal{\kappa}$. In other words, the fraction of
usable shots in the HHL algorithm becomes very low when large
$\mathcal{\kappa}$ input matrices are involved. Unfortunately, it is not
uncommon to encounter the issue while employing HHL for some interesting
problems (for example, see Ref. [3] for application of the algorithm to
hydrological systems), including quantum chemistry, which we shall discuss in
detail in our Results section. Several works in literature have addressed the
issue of handling large $\mathcal{\kappa}$ matrices either directly (where
$\mathcal{\kappa}$ of the $A$ matrix itself is altered via approaches such as
preconditioning) or indirectly [4, 5, 6, 7, 8, 3, 9]. For a thorough survey,
we direct the reader to Section 1.2 of Ref. [10].

In this work, we propose a new method to address the issue of handling $A$
matrices with large condition numbers, by introducing the post-selection-
improved HHL (Psi-HHL) algorithm, which relies upon the intuition of
extracting the correct signal by subtracting a wrong signal from a mixed
signal (that contains both the correct and wrong signals). A signal, in the
context of our work, refers to a scalar that is a feature of $\ket{x}$. For
the purposes of this work, we pick the overlap between the input and output
states of HHL, which in the case of molecules corresponds to their correlation
energies (up to some normalization constants), as our signal, although it is
to be noted that Psi-HHL itself is applicable to features as general as
transition matrix elements. The wrong signal is obtained by successfully post-
selecting outcome bit ‘0’ instead of ‘1’ (we call this approach HHL1). The
mixed signal is generated in an HHL quantum circuit by introducing an
appropriately chosen $2\times 2$ unitary just before measurement of the HHL
ancilla (we name this procedure HHL2). Figure 1 presents schematic diagrams
outlining the workings of the HHL and the Psi-HHL algorithms.

This simple modification involving execution of two HHL routines enables one
to carry out calculations for treating systems of linear equations involving
large-$\mathcal{\kappa}$ matrices without having to contend with a large
number of shots. In fact, we argue that the condition number scales linearly
with system size with our approach for large $\mathcal{\kappa}$ situations,
while still staying in the realm of a typical HHL computation. This compares
favourably with several other notable works in literature, including but not
limited to the original HHL work: $\mathcal{O}(\mathcal{\kappa}^{3})$ and
$\mathcal{O}(\mathcal{\kappa}^{2})$ without and with amplitude amplification
respectively [1],
$\mathcal{O}(\mathcal{\kappa}\mathrm{log}^{3}\mathcal{\kappa})$ with variable
time amplitude amplification [5], and works by Childs et al:
$\mathcal{O}(\mathcal{\kappa}\mathrm{polylog}(\mathcal{\kappa}))$ [11],
Wossnig et al: $\mathcal{O}(\mathcal{\kappa}^{2})$, and Costa et al’s discrete
quantum adiabatic approach based quantum linear solver algorithm [12]:
$\mathcal{O}(\mathcal{\kappa})$. In particular, the last approach also
achieves linear scaling in condition number, but we do so without invoking any
additional algorithmic machinery beyond the scope of the traditional HHL
algorithm. In order to provide a very qualitative perspective, we note that
for condition number of about 1 million,
$\mathcal{\kappa}^{3}:\mathcal{\kappa}^{2}:\mathcal{\kappa}\mathrm{log}^{3}\mathcal{\kappa}:\mathcal{\kappa}$
is $\sim 10^{18}:10^{12}:7.9\times 10^{9}:10^{6}$. For completeness, we add
that the best known classical approach, conjugate gradient, scales as
$\mathcal{O}(\sqrt{\mathcal{\kappa}})$ [13], but its scaling with respect to
system size is, of course, exponentially more expensive than that for HHL.

The paper is organized as follows: Section II presents the theory and
methodology involved in our work by introducing the Psi-HHL approach,
including a discussion on the complexity theoretic aspects (in
$\mathcal{\kappa}$) of Psi-HHL. Section III presents our results for Psi-HHL
applied to (a) suitably chosen sets of $4\times 4$, $8\times 8$, $16\times
16$, $32\times 32$, and $64\times 64$ toy matrices, as well as for (b)
molecular calculations ($64\times 64$ and $256\times 256$ $A$ matrix sizes) in
the linearized coupled cluster (LCC) HHL and Psi-HHL frameworks. We conclude
in Section IV.

Figure 1: (a) Schematic of the HHL algorithm, where 1 is post-selected and for
which $P(1)$ would be low for large $\mathcal{\kappa}$. $\ket{b}$ is the input
state register with $n_{b}$ qubits, while $n_{r}$ refers to the number of
clock register qubits. The Hong-Ou-Mandel (HOM) module is a controlled-SWAP
test without an additional ancilla qubit, and we use it to extract
$-\|\ket{b}_{\rm un}\|^{2}\ \|\ket{x}_{\rm un}\|\ \ |\langle b|x\rangle|$
(interpreted as the correlation energy, $E_{\mathrm{c}}^{\mathrm{HHL}}$, when
HHL is applied to molecular calculations), which is the feature of $\ket{x}$
that we are interested in. Sub-figure (b) provides a block-diagram description
of the HHL and the HOM modules. $QPE$ refers to the quantum phase estimation
while $CR(\theta)$ refers to the controlled-rotation module that inverts the
eigenvalues of $A$. The dashed cambered rectangle around the CNOT gate in the
HOM circuit module, and which is accompanied by $(i)$, indicates that the gate
is controlled on the ith qubit of the $\ket{b}$ register. Sub-figure (c)
consists of HHL1 in the top panel, where $P(0)$ is post-selected, and HHL2 in
the bottom panel, where the traditional HHL module is appended with an
additional mixing unitary, $R_{Y}(2\alpha)$, and where $P^{\prime}(1)$ is
post-selected. Psi-HHL relies on subtracting the final outcomes of HHL1 and
HHL2, and as the expression at the bottom of panel (c) indicates, we recover
the correlation energy via the procedure to within a simple factor. In our
notation, $E_{\mathrm{c}}^{\mathrm{HHL}}$ and $E_{\mathrm{c}}^{\mathrm{Psi-
HHL}}$ are the correlation energies obtained from HHL and Psi-HHL
respectively. Further, $a_{i},b_{i},c_{i},d_{i}\in\mathbb{R}$ are constants.

##  II Theory and Methodology

###  II.1 The HHL algorithm

We briefly sketch the relevant details of the HHL algorithm (we refer the
readers to Refs. [14, 15, 16, 17] for detailed descriptions of the algorithm)
in Figs. 1(a) and 1(b), where an amplitude-encoded input $\arrowvert
b\rangle=\sum_{i}b_{i}\arrowvert\nu_{i}\rangle$, such that
$\sum_{i}|b_{i}|^{2}=1$ where $\\{\arrowvert\nu_{i}\rangle\\}$ refers to the
eigenbasis of $A$, is fed into the HHL algorithm along with $n_{r}$ number of
clock register qubits and one HHL ancillary qubit. The HHL algorithm itself
involves QPE, followed by a non-trivial controlled-rotation module, and then a
QPE† module. At the end of the circuit, we have the following state vector,

$\displaystyle\sum_{i}b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}^{2}_{i}}}\ket{0}+\frac{C}{\tilde{\lambda}_{i}}\ket{1}\right)\otimes\ket{0^{n_{r}}}\otimes\ket{\nu_{i}}.$
(1)

In the above expression, $\\{\tilde{\lambda}_{i}\\}$ refers to the estimates
of the actual eigenvalues of $A$ ($1\geq\tilde{\lambda}_{i}\geq
1/\mathcal{\kappa}$) obtained via the QPE module of HHL. Typically, $C$ is
chosen to be the minimum eigenvalue of $A$, but it is worth noting that
incurring such a large classical overhead can always be circumvented via
approaches such as AdaptHHL [2]. When one post-selects the outcome ‘1’ on the
HHL ancilla qubit, one can think of it as choosing the ‘correct’ signal.

The solution vector $|x\rangle\propto A^{-1}|b\rangle$, and the input vector
$|b\rangle$ can be written as,

$|x\rangle=|x\rangle_{\rm un}/\||x\rangle_{\rm un}\|\ \mathrm{and}\
\ket{b}=\ket{b}_{\rm un}/\|\ket{b}_{\rm un}\|\ $ (2)

respectively, where subscript ‘$\mathrm{un}$’ refers to unnormalized states—
$|b\rangle_{\rm un}$ is the unnormalized input state after amplitude encoding
and $|x\rangle_{\rm
un}=\sum_{i}\frac{b_{i}C}{\tilde{\lambda}_{i}}|\nu_{i}\rangle$, with
$\sum_{i}|b_{i}|^{2}=1$. The probability of successfully post-selecting
outcome ‘$1$’ is given as $P(1)=\||x\rangle_{\rm un}\|^{2}$. Finally, when one
wants to predict a feature of the solution vector, say, the correlation energy
of a molecular system (proportional to the overlap between $\ket{x}$ and
$\ket{b}$), it can be done by appending an additional circuit (the Hong-Ou-
Mandel module [18]), abbreviated as HOM in Fig. 1(b) that inputs the output,
$\arrowvert x\rangle$, of the HHL algorithm and $\arrowvert b\rangle$, to
output the overlap between the two quantities. The correlation energy is then
calculated as

$\displaystyle E_{c}^{\rm HHL}$ $\displaystyle=$ $\displaystyle-\|\ket{b}_{\rm
un}\|^{2}\ \|\ket{x}_{\rm un}\|\ \ |\langle b|x\rangle|$ $\displaystyle=$
$\displaystyle-\|\ket{b}_{\rm{un}}\|^{2}\sum_{i}|b_{i}|^{2}\frac{C}{\tilde{\lambda}_{i}}.$

For the sake of simplicity, we set this quantity hereafter as the feature of
$\ket{x}$ that is of interest to us, for the rest of this work, although Psi-
HHL can be applied to more general features, such as transition matrix
elements involving $\ket{x}$. Therefore, even for non-quantum chemistry
examples that we shall later consider, we will use the term ‘correlation
energy’ to refer to the quantity from Eq. II.1. The number of trials needed to
successfully post-select outcome $`1$’ is $\mathcal{O}(\mathcal{\kappa}^{2})$.
Thus, in the event of large $\mathcal{\kappa}$, the success probability falls
quickly, making it practically difficult to carry computations using large
$\mathcal{\kappa}$ matrices. In this work, we demonstrate a new approach—
‘Psi-HHL’, towards handling large $\mathcal{\kappa}$ matrices by leveraging
the probability of successfully post-selecting the ‘wrong’ outcome $`0$’,
$P(0)$, in HHL.

###  II.2 The Psi-HHL approach

In this section, we discuss the two essential ingredients— HHL1 and HHL2,
which make up Psi-HHL as illustrated in Fig. 1(c). The HHL1 module depicts the
case where the ‘wrong’ signal is post-selected from the traditional HHL given
in Fig. 1(a) and Fig. 1(b). The HHL2 entails traditional HHL module appended
with a mixing $2\times 2$ unitary, given as $R_{Y}(2\alpha)$ and post-
selecting 1 from the mixed signal. The role of this unitary is to mix the
coefficients of $|0\rangle$ and $|1\rangle$ in the traditional HHL (see Eq.
1), thereby outputting a ‘mixed’ signal. The core idea behind Psi-HHL is to
subtract the correlation energies associated with HHL1 and HHL2 thus leaving
us with the correlation energy corresponding to the ‘correct’ signal. The gain
in taking this route is the efficiency that we achieve in the number of shots
expended. We summarize this in the following proposition:

######  Proposition.

Psi-HHL yields the same correlation energy as traditional HHL through two
implementations of HHL, but is more efficient in the number of shots than HHL,
especially when dealing with $A$ matrices with large condition numbers.

We expound on the first part of the proposition in the following paragraphs,
and the second in sub-section II.3.

####  II.2.1 HHL1: Computing the wrong signal

The first HHL module, HHL1, serves to post-select the ‘wrong’ signal of the
HHL ancilla qubit, that is, the state attached to $\ket{0}$ in Eq.1. We re-
write the state at the output of all the registers $|\psi_{\rm out}\rangle$
except the clock qubits register, as follows,

$\displaystyle|\psi_{\rm out}\rangle$ $\displaystyle=$
$\displaystyle\sum_{i}b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}^{2}_{i}}}\ket{0}\otimes\ket{\nu_{i}}+\frac{C}{\tilde{\lambda}_{i}}\ket{1}\otimes\ket{\nu_{i}}\right)$
(4) $\displaystyle=$
$\displaystyle(|0\rangle\otimes|x_{\mathrm{w}}\rangle+|1\rangle\otimes|x_{\mathrm{r}}\rangle).$

Note that here $|x_{\mathrm{w}}\rangle$ and $|x_{\mathrm{r}}\rangle$ are the
unnormalised vectors in the superposition. The subscripts $\rm w$ and $\rm r$
refer to ‘wrong’ and ‘correct’ respectively, where for the latter, we use $\rm
r$ since $\rm c$ is used already to denote ‘correlation’. The normalised
solution vector $|x_{0}\rangle$ which appears at the output register after
successfully post-selecting outcome ‘$0$’ is given by,

$\displaystyle\ket{x_{\rm 0}}$ $\displaystyle=$
$\displaystyle|x_{\mathrm{w}}\rangle/\||x_{\mathrm{w}}\rangle\|$ (5)
$\displaystyle=$
$\displaystyle\sum_{i}b_{i}\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\ket{\nu_{i}}/\||x_{\mathrm{w}}\rangle\|,$

where,

$\||x_{\rm
w}\rangle\|=\sqrt{P(0)}=\left(\sum_{i}\left|b_{i}\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\right|^{2}\right)^{1/2}.$
(6)

Here, $P(0)$ is the probability of successfully post-selecting outcome ‘0’.
The associated correlation energy is then given as,

$E_{\rm c}^{\rm w}=-\||b\rangle_{\rm un}\|^{2}\ \||x_{\rm w}\rangle\|\
|\langle b|x_{0}\rangle|.$ (7)

Here, $|b\rangle_{\rm un}$ is the unnormalized input vector after amplitude
encoding, and

$|\langle
b|x_{0}\rangle|=\sum_{i}|b_{i}|^{2}\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}.$
(8)

####  II.2.2 HHL2: Computing the mixed signal

The second HHL execution involves attaching the rotation gate $R_{Y}(2\alpha)$
on the HHL ancilla before the measurement as illustrated in the lower panel of
Fig. 1(c). This seemingly trivial addition to the algorithm introduces a new
degree of freedom via the angle $\alpha$, enabling one to boost the
probability of successful matrix inversion in the case of large
$\mathcal{\kappa}$. We recall that $R_{Y}(2\alpha)$ is a rotation about the
$Y$ axis on the Bloch sphere as given below

$R_{Y}(2\alpha)=\begin{pmatrix}\cos({\alpha})&-\sin({\alpha})\\\
\sin({\alpha})&\cos({\alpha})\end{pmatrix}.$ (9)

The state vector at the output of HHL2 module $|\psi^{\prime}_{\rm
out}\rangle$, ignoring the clock qubits register, after applying the unitary
in Eq. 9 is given below,

$\displaystyle|\psi^{\prime}_{\rm out}\rangle$ $\displaystyle=$
$\displaystyle\sum_{i}b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\cos({\alpha})-\frac{C}{\tilde{\lambda}_{i}}\sin({\alpha})\right)\ket{0}\otimes\ket{\nu_{i}}$
(10) $\displaystyle+$ $\displaystyle
b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\sin({\alpha})+\frac{C}{\tilde{\lambda}_{i}}\cos({\alpha})\right)\ket{1}\otimes\ket{\nu_{i}}$
$\displaystyle=$ $\displaystyle(|0\rangle\otimes|x_{\rm
m}\rangle+|1\rangle\otimes|x^{\prime}_{\rm m}\rangle).$

Note that in Eq. 10, $\ket{x_{\mathrm{m}}}$ and
$\ket{x^{\prime}_{\mathrm{m}}}$ are unnormalized vectors. The subscript ‘m’
denotes ‘mixed’, and while the unprimed vector accompanies $\ket{0}$, the
primed one accompanies $\ket{1}$. The solution vector at the output after
successfully post-selecting outcome ‘$1$’ is given below

$\displaystyle\ket{x^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{\ket{x^{\prime}_{\rm m}}}{\|\ket{x^{\prime}_{\rm m}}\|}$
$\displaystyle=$
$\displaystyle\sum_{i}b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\sin({\alpha})+\frac{C}{\tilde{\lambda}_{i}}\cos({\alpha})\right)\ket{\nu_{i}}/\|\ket{x^{\prime}_{\rm
m}}\|,$

where

$\displaystyle\|\ket{x^{\prime}_{\rm m}}\|$ $\displaystyle=$
$\displaystyle\sqrt{P^{\prime}(1)}$ (11) $\displaystyle=$
$\displaystyle\left(\sum_{i}\left|b_{i}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\sin({\alpha})+\frac{C}{\tilde{\lambda}_{i}}\cos({\alpha})\right)\right|^{2}\right)^{1/2}.$

Here, $P^{\prime}(1)$ is the probability of successfully obtaining outcome ‘1’
in HHL2. The correlation energy is then obtained as

$E_{\mathrm{c}}^{\rm m}=-\||b\rangle_{\rm un}\|^{2}\ \||x_{\rm
m}^{\prime}\rangle\|\ |\langle b|x^{\prime}\rangle|,$ (12)

where

$|\langle
b|x^{\prime}\rangle|=\sum_{i}|b_{i}|^{2}\left(\sqrt{1-\frac{C^{2}}{\tilde{\lambda}_{i}^{2}}}\sin(\alpha)+\frac{C}{\tilde{\lambda}_{i}}\cos(\alpha)\right).$
(13)

We choose $\alpha$ such that $\sin({\alpha})$ and $\cos({\alpha})$ are
positive and $P^{\prime}(1)\gg P^{\prime}(0)$. $P^{\prime}(0)$ refers to the
probability of post-selecting outcome ‘0’ in HHL2.

####  II.2.3 Psi-HHL: Subtracting signals

In order to prove this statement, we subtract Eq. 12 and Eq. 7, thus obtaining

$\displaystyle E_{c}^{\mathrm{Psi-HHL}}\mathrm{cot(\alpha)}$ $\displaystyle=$
$\displaystyle\frac{E_{\mathrm{c}}^{\mathrm{m}}}{\sin(\alpha)}-E_{\mathrm{c}}^{\mathrm{w}}$
(14) $\displaystyle=$ $\displaystyle-\|\ket{b}_{\rm
un}\|^{2}\sum_{i}|b_{i}|^{2}\frac{C}{\tilde{\lambda}_{i}}\rm cot(\alpha).$

By comparing the right hand sides of Eq. II.1 and Eq. 14, we see that the
expressions for $E_{\mathrm{c}}^{\rm HHL}$ and $E_{\mathrm{c}}^{\mathrm{Psi-
HHL}}$ differ only by a factor of $\rm cot(\alpha)$ as shown below.

$\displaystyle E_{\mathrm{c}}^{\mathrm{Psi-
HHL}}=\frac{\frac{E_{\mathrm{c}}^{\mathrm{m}}}{\rm
sin(\alpha)}-E_{\mathrm{c}}^{\mathrm{w}}}{\rm cot(\alpha)}=E_{\mathrm{c}}^{\rm
HHL}.$ (15)

Although theoretically, we obtain the same correlation energy from Psi-HHL, we
observe that this technique is superior to traditional HHL in the way it
handles large $\mathcal{\kappa}$ matrices, due to the optimal probability of
success that one achieves while post-selecting, as we explain in the
subsequent section. Therefore, $E_{c}^{\mathrm{Psi-HHL}}$ can predict the true
correlation energy, $E_{c}$, to a reasonable level of precision with fewer
shots even for values of $\mathcal{\kappa}$ where HHL procedure fails to do
so, which we illustrate in the Results section with examples. We find through
our examples that for up to fairly large values of $\mathcal{\kappa}$ that are
well beyond those that HHL can handle, Psi-HHL predicts the correlation energy
with fewer shots. It is also important to note that throughout the derivation
discussed above, we can replace $\ket{b}$ with $O\ket{y}$, where $O$ is a
suitably block-encoded observable [19], and $\ket{y}$ an arbitrary state that
can be an output of another algorithm, and our results from Psi-HHL still
hold. We also add that in problems where it is not immediately obvious a
priori that the condition number is large, one cannot determine whether to
employ HHL or Psi-HHL. However, this is not a problem as Psi-HHL intrinsically
involves the regular HHL procedure, and hence if $P(1)$ is significant, one
can choose not to opt for the Psi-HHL procedure.

###  II.3 Complexity aspects

We now demonstrate the complexity (in $\mathcal{\kappa}$) of the Psi-HHL
algorithm. Since for the purposes of deriving condition number behaviour at
the measurement-post-selection part of HHL, the distinction between the
estimated eigenvalues of $A$, that is, $\tilde{\lambda}_{i}$, and the actual
eigenvalues, $\lambda_{i}$, does not matter, we denote all estimated
eigenvalues in this section as simply $\lambda_{i}$ for the sake of
convenience.

In order to elaborate on the second part of our Proposition, we invoke the
probability with which one post selects the desired outcome successfully in
terms of $\kappa$.

a) Success probability of the post-selection process in HHL1: The probability
of successfully post-selecting the outcome ‘0’, $P(0)$, in HHL1 as given in
Eq. 6 can be expanded as [20]

$\displaystyle P(0)$ $\displaystyle=$
$\displaystyle\sum_{i}\left|b_{i}\sqrt{1-\frac{C^{2}}{{\lambda}_{i}^{2}}}\right|^{2}$
(16) $\displaystyle\approx$
$\displaystyle\|\sqrt{(\mathbb{I}-C^{2}A^{-2})}|b\rangle\|^{2},$

where $\mathbb{I}$ is the identity operator written in the eigenbasis of
operator $A$, constant $C=O(1/\mathcal{\kappa})$, where the condition number
$\mathcal{\kappa}$ is taken as $\lambda_{\rm max}/\lambda_{\rm min}$ and
$|b\rangle$ is the input to the HHL circuit. The set of values
$\bigg{\\{}\sqrt{1-\frac{C^{2}}{\lambda_{i}^{2}}}\bigg{\\}}$ are the
eigenvalues of the operator $\sqrt{\mathbb{I}-C^{2}A^{-2}}$, with the largest
eigenvalue being $\sqrt{1-\frac{C^{2}}{\lambda_{\rm max}^{2}}}$, and therefore

$\displaystyle P(0)$ $\displaystyle\leq$
$\displaystyle\|\sqrt{(\mathbb{I}-C^{2}A^{-2})}\|_{\rm
op}^{2}\||b\rangle\|^{2}$ $\displaystyle P(0)$ $\displaystyle\leq$
$\displaystyle 1-\frac{C^{2}}{\lambda_{\rm max}^{2}}$ (17) $\displaystyle\leq$
$\displaystyle 1-\frac{1}{\mathcal{\kappa}^{2}}.$

The first line uses the property of sub-multiplicativity of matrix norms, that
is, $\|AB\|\leq\|A\|\|B\|$. In Eq. II.3, we recall that we set $C=\lambda_{\rm
min}$, $\|.\|_{\rm op}$ is the operator norm, and $\||b\rangle\|=1$. Note that
the smallest eigenvalue of this operator is $\sqrt{1-\frac{C^{2}}{\lambda_{\rm
min}^{2}}}=0$, and corresponds to $P(0)=0$, which leads to expending a large
number of shots in HHL1. One could circumvent this issue by appropriately
choosing a scaled $C=\gamma\lambda_{\min}$, where $\gamma\in(0,1)$, leading to
$P(0)\geq 1-\gamma^{2}$. This idea has been illustrated via an example as
shown in Fig. 2, where we choose the scaling $\gamma=0.5$.

|
---|---
(a) | (b)
Figure 2: Figure showing probabilities of post-selecting various outcomes in
Psi-HHL. Sub-figures (a) and (b) show the behaviour of $P(0)$ and
$P^{\prime}(1)$ respectively with $\mathcal{\kappa}$, for $A$ being a $4\times
4$ diagonal matrix and with six different choices for the vector $\vec{b}$:
$P(0)_{\mathrm{vmin}}$ corresponds to the case where $\vec{b}$ is the
eigenvector associated with the minimum eigenvalue of $A$,
$P(0)_{\mathrm{vmax}}$ is the case where $\vec{b}$ is the eigenvector
associated with the maximum eigenvalue of $A$, $P(0)_{\lambda_{2}}$ and
$P(0)_{\lambda_{3}}$ correspond to the situations where $\vec{b}$ is the
eigenvector associated with two other eigenvalues of $A$,
$P(0)_{\mathrm{equal}}$ is the case where $\vec{b}$ is in equal superposition
of all eigenstates of $A$ and finally $P(0)_{\mathrm{unequal}}$ considers the
scenario where $\vec{b}$ is in an arbitrary superposition of eigenstates of
$A$. In the left-most figure of sub-figure (a), we choose the parameter $C$ as
$\lambda_{\mathrm{min}}$, that is, the minimum eigenvalue of $A$, whereas in
right-most figure of sub-figure (a), $C=0.5\lambda_{\mathrm{min}}$, that is,
$\gamma$ is set to 0.5. Figures (b) represent $P^{\prime}(1)$ where the
legend’s labels have a similar interpretation to those of $P(0)$. The HHL and
Psi-HHL calculations were done using 1 million shots, and $\alpha$ was set to
$60^{\circ}$ for Psi-HHL.

b) Success probability of the post-selection process in HHL2: A similar
expression for the probability of successful post-selection in HHL2,
$P^{\prime}(1)$, can be obtained by further expanding Eq. 11 as follows,

$\displaystyle P^{\prime}(1)$ $\displaystyle\approx$
$\displaystyle\rm\|[\sqrt{(\mathbb{I}-C^{2}A^{-2}})\mathrm{sin}(\alpha)$ (18)
$\displaystyle+$ $\displaystyle(CA^{-1})\mathrm{cos}(\alpha)]|b\rangle\|^{2}.$

The operator
$B\coloneq\sqrt{\mathbb{I}-C^{2}A^{-2}}\sin(\alpha)+(CA^{-1})\cos(\alpha)$ in
its eigenbasis $\\{|\nu_{i}\rangle\\}$ could be given in the diagonal form as

$\displaystyle\mathrm{diag}(\cdots,\sqrt{1-C^{2}/\lambda^{2}_{\mathrm{max}}}\sin(\alpha)+(C/\lambda_{\mathrm{max}})\cos(\alpha),\cdots,$
$\displaystyle\sqrt{1-C^{2}/\lambda^{2}_{\mathrm{min}}}\sin(\alpha)+(C/\lambda_{\mathrm{min}})\cos(\alpha),\cdots),$

where the entries that occur in the parentheses after ‘diag’ are the diagonal
elements of the matrix. Note that the largest and smallest eigenvalue of the
matrix given in Eq. II.3 depend on the choice of $\alpha$. When
$\alpha=\pi/2$, the component of that eigenvalue attached to $\sin(\alpha)$
remains, and we do not extract the desired solution. However, when $\alpha$ is
too small, say $0$, the component attached to $\cos(\alpha)$ remains and we
get the same complexity as the traditional HHL approach. Therefore, $\alpha$
is chosen to satisfy the following properties:

  * •

The success probability, $P^{\prime}(1)$ is large enough.

  * •

The solution component that matters to us does not vanish in the
superpositions that occur along the diagonal entries in Eq. II.3.

We demonstrate the case where $\alpha$ is close to $\pi/2$ and
$C=\lambda_{\min}$, in which case the operator in Eq. II.3 could be written in
the form where the largest eigenvalue is the first entry and the smallest
eigenvalue is the last entry, as given below,

$\displaystyle\mathrm{diag}(\cdots,\sqrt{1-1/\mathcal{\kappa}^{2}}\sin(\alpha)+(1/\mathcal{\kappa})\cos(\alpha),\cdots,\cos(\alpha)).$

Using once again the sub-multiplicativity of matrix norms in Eq. 18, we can
write

$\displaystyle P^{\prime}(1)$ $\displaystyle\leq$
$\displaystyle\rm\|[\sqrt{\mathbb{I}-C^{2}A^{-2}}\ sin(\alpha)$ (21)
$\displaystyle+$ $\displaystyle CA^{-1}\cos(\alpha)]\|^{2}_{\rm
op}\||b\rangle\|^{2},$

where $\|.\|_{\rm op}$ is the operator norm yielding the largest eigenvalue of
the operator, and $\||b\rangle\|=1$. Then $P^{\prime}(1)$ is bounded the
following way,

$\displaystyle\cos^{2}(\alpha)\leq P^{\prime}(1)$ $\displaystyle\leq$
$\displaystyle\rm\bigg{|}\bigg{[}\bigg{(}\sqrt{1-\frac{1}{\mathcal{\kappa}^{2}}}\bigg{)}sin(\alpha)+\frac{1}{\mathcal{\kappa}}cos(\alpha)\bigg{]}\bigg{|}^{2}$
(22) $\displaystyle=$
$\displaystyle\rm\bigg{(}1-\frac{1}{\mathcal{\kappa}^{2}}\bigg{)}\sin^{2}(\alpha)+\frac{1}{\mathcal{\kappa}^{2}}cos^{2}(\alpha)$
$\displaystyle+$ $\displaystyle
2\left(\sqrt{1-\frac{1}{\mathcal{\kappa}^{2}}}\right)\frac{1}{\mathcal{\kappa}}\sin(\alpha)cos(\alpha)$
$\displaystyle\approx$ $\displaystyle\rm
sin^{2}(\alpha)+\frac{1}{\mathcal{\kappa}}\
sin(2\alpha)+\frac{1}{\mathcal{\kappa}^{2}}\cos(2\alpha)$ $\displaystyle-$
$\displaystyle\frac{1}{\mathcal{\kappa}^{3}}\sin(\alpha)\cos(\alpha).$

In this bound, the left hand side is the square of the smallest eigenvalue of
the matrix given in Eq. II.3, while the right hand side is the square of the
largest eigenvalue of the matrix in Eq. II.3.

For the choice of $C=\gamma\lambda_{\min}$, where $\gamma\in(0,1)$, one can
push the lower bound for the choice of given $\alpha$. This implies that fewer
measurements are required to invert matrices with large condition numbers, as
compared to the traditional HHL technique illustrated in Fig. 1(a). We show
this in Fig. 2, where for a given $\alpha=60^{\circ}$, we obtain

$\displaystyle\rm\bigg{|}\bigg{[}\bigg{(}\sqrt{1-\frac{\gamma^{2}}{\mathcal{\kappa}^{2}}}\bigg{)}sin(\alpha)+\frac{\gamma}{\mathcal{\kappa}}cos(\alpha)\bigg{]}\bigg{|}^{2}$
$\displaystyle\leq$ $\displaystyle P^{\prime}(1)$ (23) $\displaystyle\leq$
$\displaystyle\bigg{|}\bigg{[}(\sqrt{1-{\gamma^{2}}})\mathrm{sin}(\alpha)$
$\displaystyle+$
$\displaystyle{\gamma}\mathrm{cos}(\alpha)\bigg{]}\bigg{|}^{2}.$

While the $A$ and $B$ matrices share the same basis $\\{\ket{\nu_{i}}\\}$, an
eigenstate of $B$ matrix that achieves the lower bound for $P^{\prime}(1)$ may
not often correspond to the largest/smallest eigenvalue of $A$ matrix, for a
given choice of angle $\alpha$.

Note that for an arbitrary input $|b\rangle$ which is a nontrivial
superposition of all the eigenvectors $\\{|\nu_{i}\rangle\\}$ of $A$, we have
the following condition,

$\displaystyle{P^{\prime}(1)}$ $\displaystyle=$
$\displaystyle\left(\sum_{i}\left|b_{i}\left(\sqrt{1-\frac{C^{2}}{{\lambda}_{i}^{2}}}\sin({\alpha})+\frac{C}{{\lambda}_{i}}\cos({\alpha})\right)\right|^{2}\right)$
(24) $\displaystyle=$ $\displaystyle\left(\sum_{i}\mid
b_{i}\mid^{2}{\lambda}_{i}^{\prime 2}\right).$

Here, $\\{\lambda_{i}^{\prime}\\}$ are the eigenvalues of the operator
$\rm\sqrt{\mathbb{I}-C^{2}A^{-2}}\ sin(\alpha)+CA^{-1}\cos(\alpha)$. Eq. 24 is
a convex combination of the square of eigenvalues, $\lambda_{i}^{\prime 2}$,
therefore, an arbitrary input $|b\rangle$ will yield a $P^{\prime}(1)$
satisfying the condition given in Eq. 22. We augment our findings with the
simulations in the subsequent Sec. III.

##  III Results and discussions

In this section, we consider two sets of examples to compare the performance
of Psi-HHL with that of HHL:

  * •

Toy $A$ matrices of sizes $4\times 4$, $8\times 8$, $16\times 16$, $32\times
32$, and $64\times 64$: For practical reasons associated with computational
resources, we do not choose matrices whose $\mathcal{\kappa}$ grows with the
$A$ matrix size. Instead, we generate a sequence of $A$ matrices with
systematically increasing condition numbers for every system size. For
example, for $4\times 4$ matrix size, we begin with a sparse and diagonally
dominant matrix (the latter is not a requirement but simplifies matters for
our illustrations) such that its smallest diagonal entry is $2^{-(n_{r}-1)}$
and the largest 1. Recall that $n_{r}$ is the number of QPE clock register
qubits. We generate the sequence by varying $n_{r}$ from 2 to 20. In such a
sequence, $\mathcal{\kappa}$ grows exponentially with $n_{r}$, thus enabling
us to reach the failure point of HHL rather rapidly and with existing
computational resources. We also note that changing the position of the
minimum diagonal element of $A$ along the diagonal does not affect our
analysis.

  * •

Quantum chemistry: Since quantum chemistry is one of the main applications of
interest with quantum computers, it is worth exploring this domain for our
analysis [2]. However, since we no longer are considering toy examples, we
begin by qualitatively assessing the applicability of HHL to the LCC problem
by:

    1. 1.

Checking how the $A$ matrices grow with system size (and along the way,
defining the system size), thereby providing a handle on the classical
hardness of the problem, and

    2. 2.

Checking how $\mathcal{\kappa}$ itself grows as a function of what we set to
be the system size. Only after this qualitative analysis do we move to our
main results for this problem domain.

  * •

We carry out the following analyses:

    1. 1.

For the toy matrices, we compare HHL and Psi-HHL, and demonstrate the ability
of the latter in predicting correlation energies across a range of condition
number values. As we shall explain later in this section, we find that since
$\mathcal{\kappa}$ grows slowly for the quantum chemistry case, it is not
computationally feasible to carry out the analysis. We quantify the quality of
our results for the correlation energies through percentage fraction
difference, abbreviated as PFD, given by
$\frac{E_{\mathrm{c}}-E_{\mathrm{c}}^{\mathrm{HHL}}}{E_{\mathrm{c}}}\times
100$ for HHL and $\frac{E_{\mathrm{c}}-E_{\mathrm{c}}^{\mathrm{Psi-
HHL}}}{E_{\mathrm{c}}}\times 100$ for Psi-HHL. We denote the correlation
energy obtained on a traditional computer by $E_{\mathrm{c}}$, whereas
$E_{\mathrm{c}}^{\mathrm{HHL}}$ and $E_{\mathrm{c}}^{\mathrm{Psi-HHL}}$ are
the values for the quantity obtained from HHL and Psi-HHL respectively.

    2. 2.

For both the toy matrices as well as the quantum chemistry matrices, we study
the PFDs of HHL and Psi-HHL approaches versus the number of shots.

|  |
---|---|---
(a) | (b) | (c)

|
---|---
(d) | (e)

Figure 3: Figure showing a comparison of the performance of HHL and Psi-HHL
approaches for toy matrices. Sub-figures whose top panels present the average
probabilities of HHL and Psi-HHL with varying values of $\mathcal{\kappa}$ for
different $A$ matrix sizes: $4\times 4$ (sub-figure (a)), $8\times 8$ (sub-
figure (b)), $16\times 16$ (sub-figure (c)), $32\times 32$ (sub-figure (d)),
and $64\times 64$ (sub-figure (e)). The bottom panel of each sub-figure
represents the average Percentage Fraction Differences (PFD) of the overlap,
$E_{c}$, calculated with HHL and Psi-HHL with respect to the classical value
versus $\mathcal{\kappa}$. Each data point results from 10 repeated runs of
$10^{6}$ shots each. Also, all the computations have been done with $A$ not
diagonal and $\vec{b}$ in unequal superposition, as described in the main
text. We also note here that the approximate equality is due to the fit
coefficients in the figure being rounded off to two decimal places.

###  III.1 Toy matrices: $4\times 4$ through $64\times 64$

We begin by discussing the details of our $A$ matrices and $\vec{b}$ vectors.
We pick our $4\times 4$ matrix to be non-diagonal, and is given by

$A=\begin{pmatrix}2^{-(n_{r}-1)}&0.00&0.00&0.00\\\ 0.00&0.75&0.10\times
10^{-3}&0.00\\\ 0.00&0.10\times 10^{-3}&0.50&0.00\\\
0.00&0.00&0.00&1.00\end{pmatrix},$

and $\vec{b}=\begin{pmatrix}0.10\\\ 0.01\\\ 0.20\\\ 1.00\end{pmatrix}$. The
sparsity, $s$, of $A$ is defined as the number of non-zero entries in the row
with the most number of non-zero elements and is set to 2. Our choices for the
other matrices, $8\times 8$ through $64\times 64$ can be found in Figure A1 of
the Appendix. We have set the following values for sparsity: 3 for $8\times
8$, 4 for $16\times 16$, 17 for $32\times 32$, and 7 for $64\times 64$
matrices. Throughout, we have ensured that the eigenvalues of the $A$ matrix
lies between $1/\mathcal{\kappa}$ and 1. We provide more examples for the
$4\times 4$ matrix size in Section A1 of the Appendix.

Figures 3(a) through 3(e) provides our findings for $4\times 4$ through the
$64\times 64$ examples considered. Each data point in the sub-figures is the
average result obtained over 10 repetitions, with each repetition involving 1
million shots. We pick $\alpha=60^{\circ}$ for the Psi-HHL calculations. The
corresponding data is given in Table A1 of the Appendix. Our results obtained
using other choices of angles, $70^{\circ}$ and $80^{\circ}$, are provided in
Tables A2 and A3 respectively. We now return to Figure 3, where each sub-
figure provides two sets of data: one which compares the probabilities,
$P(0)$, $P(1)$, $P^{\prime}(0)$, and $P^{\prime}(1)$, obtained by executing
HHL and Psi-HHL, and the other providing the PFDs for the two methods. We
choose condition numbers all the way till about 1 million. Figures A2 and A3
of the Appendix shows these results for $\alpha$ of $60^{\circ}$,
$70^{\circ}$, and $80^{\circ}$, with $10^{5}$ and $10^{6}$ shots respectively.
The figures show that our data fits for HHL align with the expected behaviour
of $P(1)\sim\mathcal{O}(\mathcal{\kappa}^{-2})$. We also find that
$P^{\prime}(1)$ scales as $\sim\mathcal{O}(1)$ for large condition numbers
(with the fit parameter $a=0.75$ matching with the Y-axis intercept for large
condition number values). For completeness, we verify that the fit
probabilities add to one (see Table A4 of the Appendix).

|
---|---
(a) | (b)
Figure 4: Figure showing a comparison of the spread in PFDs as well as the
average PFD (over 10 repetitions), obtained using HHL (sub-figure (a)) and
Psi-HHL (sub-figure (b)), against a range of three different numbers of shots
and for the case where $A$ is of size $4\times 4$, and for which
$\mathcal{\kappa}\approx 2^{12}=4096$.

We now comment on the PFDs. We immediately see that HHL fails at some value of
$\mathcal{\kappa}$ for the chosen number of shots (indicated by ‘nan’ values
in Tables A1, A2, and A3 of the Appendix). This is due to the fact that as
$P(1)$ becomes very small, the fraction of the total number of shots that
yield 1 upon measurement tend to very small values. Therefore, the number of
shots available for the HOM module become too small to give any reasonable
result beyond a certain value of $\mathcal{\kappa}$. The bottom panel of each
sub-figure of Figure 3 shows that the error bars, in which the upper and lower
points of the bars reflect the largest and the smallest PFD values obtained
using HHL, increases as the condition number increases, till it reaches a
critical value of $\mathcal{\kappa}$, beyond which HHL fails. In contrast, we
see that for Psi-HHL, even at $\mathcal{\kappa}\ \approx$ 1 million, the
length of the error bar is about 17 percent.

We now verify that HHL does not fail upon increasing the number of shots, but
the number requires to be about 1 billion in order to get a comparable range
of PFDs as Psi-HHL, while Psi-HHL only incurs 10 million shots, as Figure 4
shows. In particular, HHL gives a maximum PFD of 1.51 percent and a minimum of
$-2.98$ percent with a billion shots, whereas Psi-HHL gives a maximum and
minimum PFD of 2.33 and $-2.97$ percent respectively with only 10 million
shots.

We finally comment on our results from Figure 3 on the larger size matrices
($8\times 8$ through $64\times 64$), where for Psi-HHL, we consider
$\alpha=60^{\circ}$. Figures A4 through A7 provides the data for $70^{\circ}$
and $80^{\circ}$ cases, with Figure A4 also giving the information for
$10^{5}$ shots. We observe that broadly, the trends are similar to what we
find for the smaller $4\times 4$ cases. Figure A8 of the Appendix summarizes
the situations where HHL fails for all of the toy matrices considered, as a
heat map. We find that for 1 million shots, HHL starts returning ‘nan’ values
between $\mathcal{\kappa}$ of $2^{8}$ and $2^{10}$. In view of the
computational cost involved, we did not go all the way up to a condition
number of $2^{20}$ for matrices above $4\times 4$ size, and we stopped much
earlier for the $64\times 64$ case.

###  III.2 Quantum chemistry matrices

Quantum chemistry is regarded as one of the killer applications of quantum
computing [21]. Therefore, it is interesting to consider the performance of
Psi-HHL in this scenario. In particular, we consider quantum chemistry
problems via the LCC approach [2], for this purpose. Quantum chemistry on
quantum computers can involve different approaches to selecting systems of
interest depending on the application domain, including but not limited to
performing calculations on numerous candidate molecules of progressively
increasing size, picking one molecule and systematically improving the
precision in one’s calculations via suitable active space choices (as well as
better quality single particle bases, incorporating more physical effects in
the molecular non-relativistic Hamiltonian, etc), etc. For the purposes of
this work, since we only want to compare performance of the HHL and Psi-HHL
approaches, we opt for the substantially simpler second approach.

|  |
---|---|---
(a) | (b) | (c)
Figure 5: Figure showing a comparison of the performance of HHL and Psi-HHL
approaches for three representative molecules. PFDs of Li2 (sub-figure (a)),
RbH (sub-figure (b)), and CsH (sub-figure (c)) molecules versus number of
shots (denoted in the figure as ‘No. of shots’). The centre of each unfilled
circle represents the average PFD over a range of 5 repetitions. Each Li2
calculation involves evaluating a 21-qubit circuit, with the $A$ matrix size
being $64\times 64$, while for RbH, we evaluate a 25-qubit circuit involving
an $A$ matrix size of $256\times 256$. For CsH, we carry out 26-qubit
calculations where the $A$ matrix size is $256\times 256$. The zero PFD value
is marked with a horizontal line for ease of visualization.

####  III.2.1 The $A$ matrix dimension

Since we are now going beyond toy examples, we begin with some preliminary
qualitative remarks. We begin with the growth of the LCC $A_{mol}$ matrix. We
make a distinction between the dimension of the LCC matrix, $A_{mol}$, which
is $m\times m$, and the dimension of the associated $A$ matrix, $n\times n$,
where we recall that $n=2^{N}$. We go from $A_{mol}$ to $A$ via padding, which
we explain in Section A2 of the Appendix.

  * •

The number of rows (or columns), $m$, of the $A_{mol}$ matrix, which we shall
hereafter think of as the system size, is the number of particle-hole
excitations that one considers for a calculation, which in turn is decided by
choice of single particle basis and active space size. We denote the number of
occupied orbitals as $n_{o}$ and virtuals by $n_{v}$. It is common to employ
the LCC approach by only considering single and double excitations (termed
LCCSD), in which case $A_{mol}$ matrix grows as $m\sim n_{o}^{2}n_{v}^{2}$ for
fixed values of $n_{o}$ and $n_{v}$. As we include more excitations
systematically, such as triples, quadruples, etc, while keeping the number of
orbitals fixed, we observe that the $A_{mol}$ matrix grows as $\sim
n_{o}^{\mathcal{E}}n_{v}^{\mathcal{E}}$, which is exponential. $\mathcal{E}$
refers to the excitation rank.

  * •

For a given excitation rank, $\mathcal{E}$, as we increase the number of
orbitals, the system size, $m$, grows further polynomially, for example, see
Figure A9 in the Appendix. For the purposes of this work, we restrict
ourselves to LCCSD approximation ($\mathcal{E}=2$), and study the size of
$A_{mol}$ with increase in number of unoccupied orbitals, $n_{v}$, in a
molecule, while keeping $n_{o}$ fixed at a reasonable number.

For our analyses, we do not attempt to consider a molecule in a given active
space size to study the variation of $m$ with choice of single particle basis,
and defer the study for a future work. We choose three examples: the light
Li2, the moderately heavy RbH, and the heavy CsH neutral diatomic molecules,
all in their equilibrium bond lengths (Li2: 5.06 Bohr, RbH: 4.4726 Bohr, and
CsH: 4.7135 Bohr) [22, 23]. The adjective ‘light’ and ‘heavy’ refer to the
atomic number of the heavier atom in a diatomic molecule. We pick the Sapporo
double zeta basis sets for RbH and CsH (Rb: Sapporo-DZP, Cs: Sapporo-
DKH3-DZP-2012, and H: Sapporo-DZP) [24], while for Li2, we choose the STO-6G
basis [25]. We employ the $C_{2v}$ point group symmetry for RbH and CsH
computations, while for the case of Li2, we pick the $D_{2h}$ symmetry. We fix
$n_{o}$ to 3, 13 , and 18 for Li2, RbH, and CsH respectively. The technical
details involved in the generation of $A$ matrix as well as the $\vec{b}$
vector are discussed in Section A2.A of the Appendix.

####  III.2.2 Condition number of the $A$ matrix

Although HHL offers an exponential advantage in terms of system size, it is
worth checking if for the LCCSD problem, the condition number itself scales
favourably with system size, $m$, for the systems that we considered. We point
out towards the end of Section A2.A of the Appendix that it is sufficient to
analyze $\mathcal{\kappa}$ versus $m$; this curve upper bounds
$\mathcal{\kappa}$ versus $n$. We increase the active space, and thus $m$, in
a systematic manner by carrying out an orbital character analysis, whose
details we explain in Section A2.B of the Appendix. Furthermore, for this
analysis, we only consider RbH and CsH, and not Li2 as the system is too small
(in the STO-6G basis) to carry out condition number versus system size
analysis. For RbH, we consider $n_{o}=13$ for our calculations, and vary the
number of virtuals from 1 to 21, which corresponds to $A_{mol}$ matrix size of
$40\times 40$ to $9065\times 9065$ respectively. For CsH, $n_{o}=18$ and
virtuals are varied from 1 to 16, while the $A_{mol}$ matrix size goes from
$67\times 67$ to $11058\times 11058$.

Our results shown in Figure A10 of the Appendix indicate that for RbH as well
as for CsH, as we go from $m$ of 40 to 9065 and 67 to 11059 respectively,
$\mathcal{\kappa}$ grows polylogarithmically (fourth and sixth order
respectively). This behaviour is also consistent with what one may expect from
chemistry intuition: we begin by referring the reader to Table A10 of the
Appendix, where we list the largest and smallest eigenvalues of the $A$ matrix
for each value of $m$, for both RbH and CsH. The data shows that the increase
in $\mathcal{\kappa}$ as we add virtual orbitals is driven by the decrease of
the lowest eigenvalue of the $A$ matrix. We note that every matrix element of
the $A$ matrix can be expressed as $\langle\Phi_{p}|H|\Phi_{q}\rangle$, where
$H$ is the Hamiltonian and $\ket{\Phi_{p}}$ and $\ket{\Phi_{q}}$ are the
excited determinants built from particle-hole excitations arising from the
Hartree-Fock configuration. The smallest eigenvalue of the sparse and
diagonally dominant $A$ matrix, which we saw as being important in determining
the growth of $\mathcal{\kappa}$, can be qualitatively thought of as
corresponding to the energy of the first excited state (assuming that the wave
function of the first excited state has small contribution from the HF
configuration). Thus, we expect that the decrease in the lowest eigenvalue of
$A$ saturates as we keep adding virtual orbitals, and eventually, the lowest
eigenvalue of the $A$ matrix will converge to a certain value. Thus, the
increase of $\mathcal{\kappa}$ saturates too, thus leading one to expect that
the condition number would vary as a polylogarithmic function of system size.
We add at this juncture that while considering only two molecules does not
allow any quantitative inference on the behaviour of condition number with
system size, it gives a qualitative indication that quantum chemistry using
HHL-LCCSD may a reasonable direction to consider. However, further analysis
would be required to assess what one would expect for $\mathcal{\kappa}(m)$ in
general for an HHL-LCC computation. We also note that we carried out a similar
analysis for sparsity, and found that it too grows polylogarithmically for RbH
and CsH (see Figure A11 of the Appendix).

####  III.2.3 HHL and Psi-HHL results

We now discuss our results for the performance of the HHL and Psi-HHL
algorithms for the molecules considered in this work.

We begin by conducting a study similar to the one shown in Figure 4 for the
toy matrices. It is not practical to carry out an analysis similar to that in
Figure 3, since unlike the toy matrices case, the condition number grows much
slower and the computations become too expensive too soon. For the purposes of
our analysis in Figure 4, we vary the number of shots and compare the
performance of HHL and Psi-HHL in predicting the PFD, as well as the range
across which the PFDs are spread, across 5 repetitions. For this analysis, we
consider Li2, RbH and CsH. The details are:

  1. 1.

Li2: 21-qubit circuit with an $A$ matrix size of $64\times 64$ (built out of
single and double excitations arising from 3 occupied and 8 virtual orbitals)
in the STO-6G basis, with $\mathcal{\kappa}=64.07$.

  2. 2.

RbH: 25-qubit circuit with an $A$ matrix size of $256\times 256$ (built out of
single and double excitations arising from 13 occupied and 3 virtual orbitals)
in the Sapporo double zeta basis, with $\mathcal{\kappa}=153.17$.

  3. 3.

CsH: 26-qubit calculations with an $A$ matrix size of $256\times 256$ (built
out of single and double excitations arising from 18 occupied and 2 virtual
orbitals) in the Sapporo double zeta basis, with $\mathcal{\kappa}=466.59$.
Although RbH and CsH have the same $A$ matrix size, the latter involves a
26-qubit calculation because we set an additional ancilla for CsH due to its
larger atomic number.

We note that for RbH, the same calculation would have incurred more qubits for
VQE-UCCSD (32-qubit circuit) and QPE-CASCI (with $n_{r}=8$, 40-qubit circuit)
computations, while we carry out a 25-qubit circuit evaluation in the case of
HHL-LCC. Similarly, for CsH, VQE-UCCSD: 40 qubits, QPE-CASCI: 48 qubits, and
HHL-LCC: 26 qubits.

Our results are presented in Figure 5, with the accompanying data given in
Table A11 of the Appendix. For Li2, the condition number is very small, and
hence we only study the performance of HHL and Psi-HHL between 500 and 10000
shots. The data indicates that for Li2, the Psi-HHL approach gives better
average PFDs, especially in the regime of fewer number of shots (500 and 1000
shots). In the same regime, the spread in PFDs is also lesser for Psi-HHL. For
the cases of RbH and CsH, as we increase the number of shots, the error bars
for both HHL and Psi-HHL are seen to become much smaller.

##  IV Conclusion

We propose the Psi-HHL algorithm to efficiently handle problems involving $A$
matrices with large condition numbers. The approach involves post-selecting 0
in HHL (the ‘wrong signal’), followed by post-selecting 1 from an HHL-like
circuit that contains an additional mixing $2\times 2$ unitary (the ‘mixed
signal’), and taking the difference between the wrong and the mixed signals to
extract the correct signal.

We present arguments to show that the complexity of Psi-HHL is optimal in
condition number for large $\mathcal{\kappa}$ regimes; the complexity of the
algorithm scales as $\mathcal{\kappa}$. This is an improvement over earlier
approaches in literature, such as HHL with amplitude amplification (scales
quadratically, and incurs several additional gates due to its iterative
nature) and HHL with variable time amplitude amplification (scales as
$\mathcal{\kappa}\mathrm{log}^{3}\mathcal{\kappa}$). It is also important to
note that while the optimal $\mathcal{\kappa}$ behaviour can be recovered
using a discrete quantum adiabatic approach based quantum linear solver
algorithm [12], we achieve the same result using Psi-HHL, which is a simple
modification to the HHL algorithm.

We apply our method to different toy matrices, where we systematically vary
the condition number all the way to about 1 million while keeping the number
of shots fixed to 1 million, and show that while HHL fails beyond a certain
value, Psi-HHL continues to predict good results. We also demonstrate the
performance of our proposed Psi-HHL approach for quantum chemistry examples,
where we once again find that Psi-HHL yields better quality results in much
fewer number of shots. En route, we also carry out a qualitative analysis to
check suitability of treating LCC equations using the HHL algorithm.

We anticipate that our work will pave the way for development of non-trivial
Psi-HHL variants that would allow it to be integrated as an algorithmic
primitive in larger algorithmic frameworks that use traditional HHL as a
subroutine.

###### Acknowledgements.

We acknowledge National Supercomputing Mission (NSM) for providing computing
resources of ‘PARAM Siddhi-AI’, under National PARAM Supercomputing Facility
(NPSF), C-DAC, Pune and supported by the Ministry of Electronics and
Information Technology (MeitY) and Department of Science and Technology (DST),
Government of India. VSP thanks Prof. Aram Harrow for a very fruitful
discussion on HHL as well as HHL-LCC. VSP and AJ thank Dr. Shibdas Roy for
nice discussions on complexity. VSP and PBT thank Prof. Debashis Mukherjee for
useful discussions on the quantum chemical sections of the work. KS
acknowledges support from Quantum Leap Fragship Program (Grant No.
JPMXS0120319794) from Ministry of Education, Culture, Sports, Science and
Technology (MEXT), Japan; Center of Innovations for Sustainable Quantum AI
(JPMJPF2221) from Japan Science and Technology Agency (JST), Japan; and
Grants-in-Aid for Scientific Research C (21K03407) and for Transformative
Research Area B (23H03819) from Japan Society for the Promotion of Sciences
(JSPS), Japan.

## References

  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
  * Baskaran  _et al._ [2023] N. Baskaran, A. S. Rawat, A. Jayashankar, D. Chakravarti, K. Sugisaki, S. Roy, S. B. Mandal, D. Mukherjee, and V. S. Prasannaa, Adapting the Harrow-Hassidim-Lloyd algorithm to quantum many-body theory, Phys. Rev. Research 5, 043113 (2023).
  * Golden  _et al._ [2022] J. Golden, D. J. O’Malley, and V. Hari, Quantum computing and preconditioners for hydrological linear systems, Sci. Rep. 12, 22285 (2022).
  * Brassard  _et al._ [2002] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Q. Comput. Q. Info., Samuel J. Lomonaco, Jr. (editor), AMS Contemporary Mathematics 305, 74 (2002).
  * Ambainis [2010] A. Ambainis, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations, arXiv:1010.4458 (2010).
  * Clader  _et al._ [2013] B. D. Clader, B. C. Jacobs, and C. R. Sprouse, Preconditioned quantum linear system algorithm, Phys. Rev. Lett. 250504, 110 (2013).
  * Shao and Xiang [2018] C. Shao and H. Xiang, Quantum circulant preconditioner for a linear system of equations, Phys. Rev. A 062321, 98 (2018).
  * Tong  _et al._ [2021] Y. Tong, D. An, N. Wiebe, and L. Lin, Fast inversion, preconditioned quantum linear system solvers, fast Green’s-function computation, and fast evaluation of matrix functions, Phys. Rev. A 032422, 104 (2021).
  * Babukhin [2023] D. V. Babukhin, Harrow-Hassidim-Lloyd algorithm without ancilla postselection, Phys. Rev. A 107, 042408 (2023).
  * Orsucci and Dunjko [2021] D. Orsucci and V. Dunjko, On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number, Quantum 5, 573 (2021).
  * Childs  _et al._ [2017] A. M. Childs, R. Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM Journal on Computing 46, 1920 (2017).
  * P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush and D. W. Berry [2022] P. C. S. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush and D. W. Berry, Optimal scaling quantum linear-systems solver via discrete adiabatic theorem, PRX Quantum 3, 040303 (2022).
  * Shewchuk [1994] J. R. Shewchuk, An introduction to the conjugate gradient method without the agonizing pain, Technical report, School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213 (1994).
  * Dervovic  _et al._ [2018] D. Dervovic, M. Herbster, P. Mountney, S. Severini, N. Usher, and L. Wossnig, Quantum linear systems algorithms: a primer, arXiv:1802.08227 (2018).
  * Morrell  _et al._ [2023] H. J. Morrell, A. Zaman, and H. Y. Wong, A step-by-step HHL algorithm walkthrough to enhance understanding of critical quantum computing concepts, IEEE Access 11, 77117 (2023), arXiv:2108.09004 [quant-ph] .
  * Liu  _et al._ [2022] X. Liu, H. Xie, Z. Liu, and C. Zhao, Survey on the improvement and application of hhl algorithm, J. Phys.: Conf. Ser. 2333, 012023 (2022).
  * Duana  _et al._ [2022] B. Duana, J. Yuana, C.-H. Yub, J. Huanga, and C.-Y. Hsie, A survey on HHL algorithm: From theory to application in quantum machine learning, Phys. Lett. A 384, 126595 (2022).
  * Garcia-Escartin and Chamorro-Posada [2013] J. C. Garcia-Escartin and P. Chamorro-Posada, Swap test and hong-ou-mandel effect are equivalent, Phys. Rev. A 87, 052330 (2013).
  * Alase  _et al._ [2022] A. Alase, R. R. Nerem, M. Bagherimehrab, P. Hoyer, and B. C. Sanders, Tight bound for estimating expectation values from a system of linear equations , Phys. Rev. Research 023237, 4 (2022).
  * Lin [2022] L. Lin, Lecture notes on quantum algorithms for scientific computation, arXiv:2201.08309 (2022).
  * Bourzac [2017] K. Bourzac, Chemistry is quantum computing’s killer app, C&EN 95, 27 (2017).
  * Geum  _et al._ [2001] N. Geum, G.-H. Jeung, A. Derevianko, R. Côté, and A. Dalgarno, Interaction potentials of LiH, NaH, KH, RbH, and CsH, J. Chem. Phys. 115, 5984 (2001).
  * Brooks  _et al._ [1963] R. A. Brooks, C. H. Anderson, and N. F. Ramsey, Rotational magnetic moments of diatomic alkalis, Phys. Rev. Lett. 10, 441 (1963).
  * Noro  _et al._ [2012] T. Noro, M. Sekiya, and T. Koga, Segmented contracted basis sets for atoms H through Xe: Sapporo-(DK)-nZP sets (n = D, T, Q), Theor. Chem. Acc. 131, 1124 (2012).
  * Pritchard  _et al._ [2019] B. P. Pritchard, D. Altarawy, B. Didier, T. D. Gibson, and T. L. Windus, A new basis set exchange: An open, up-to-date resource for the molecular sciences community, J. Chem. Inf. Model. 59(11), 4814 (2019).
  * Barca  _et al._ [2022] G. M. J. Barca _et al._ , Recent developments in the general atomic and molecular electronic structure system, J. Chem. Phys. 152, 154102 (2022).

## Appendix

##  Appendix A1 Details on calculations involving toy matrices from size
$4\times 4$ through $64\times 64$

|
---|---
(a) | (b)
|
(c) | (d)
Figure A1: Our choices for (a) $8\times 8$, (b) $16\times 16$, (c) $32\times
32$, and (d) $64\times 64$ toy matrices for comparing the performance of HHL
and the Psi-HHL algorithms. The cell with a star symbol denotes the matrix
element with the variable, $n_{r}$ (the number of clock register qubits from
the HHL circuit), which sets $\mathcal{\kappa}$.

In our Results section in the main text, we discussed the case of $A$ not
diagonal and the amplitude encoded state corresponding to $\vec{b}$ in an
unequal superposition. We also provide our $4\times 4$ through $64\times 64$
matrices that we considered in the main text in Figure A1.

We now provide additional data on two more choices for our $4\times 4$ $A$
matrices:

  1. 1.

$A$ is diagonal and the amplitude encoded state corresponding to $\vec{b}$ is
in an equal superposition. In particular,
$A=\begin{pmatrix}2^{-(n_{r}-1)}&0.00&0.00&0.00\\\ 0.00&0.75&0.00&0.00\\\
0.00&0.00&0.50&0.00\\\ 0.00&0.00&0.00&1.00\end{pmatrix}$,
$\vec{b}=\begin{pmatrix}1.00\\\ 1.00\\\ 1.00\\\ 1.00\end{pmatrix}$. The
sparsity, $s$, of $A$ is set to 1.

  2. 2.

$A$ is diagonal and the amplitude encoded state associated with $\vec{b}$ is
in an unequal superposition. In particular, $A$ is the same as in case 1 given
above, and $\vec{b}=\begin{pmatrix}0.10\\\ 0.01\\\ 0.20\\\ 1.00\end{pmatrix}$.

We also present these results for $\alpha$ set to 60, 70, and 80 degrees (the
main text only discussed the first case). Furthermore, while the main text
considers 1 million shots, we also perform the same analyses for $10^{5}$
shots. All of these results are presented in Figures A2 and A3 for the cases
considering $10^{5}$ and $10^{6}$ shots respectively. The accompanying data is
provided in Tables A1, A2, and A3, for 60, 70, and 80 degrees examples
respectively.

|  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$

|  |
---|---|---
(d) $\alpha=60^{\circ}$ | (e) $\alpha=70^{\circ}$ | (f) $\alpha=80^{\circ}$

|  |
---|---|---
(g) $\alpha=60^{\circ}$ | (h) $\alpha=70^{\circ}$ | (i) $\alpha=80^{\circ}$

Figure A2: Sub-figures presenting the average probabilities of HHL and Psi-HHL
with varying condition number $\mathcal{\kappa}$ of $A$, for $4\times 4$
matrices and using $10^{5}$ shots throughout. Sub-figures (a) through (c)
consider the case where $A$ is diagonal and $\vec{b}$ is in equal
superposition. Sub-figures (d) through (f) consider the case where $A$ is
diagonal and $\vec{b}$ is in unequal superposition, and Subfigures (g) through
(i) consider the case where $A$ is not diagonal and $\vec{b}$ is in unequal
superposition.

|  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$

|  |
---|---|---
(d) $\alpha=60^{\circ}$ | (e) $\alpha=70^{\circ}$ | (f) $\alpha=80^{\circ}$

|  |
---|---|---
(g) $\alpha=60^{\circ}$ | (h) $\alpha=70^{\circ}$ | (i) $\alpha=80^{\circ}$

Figure A3: Sub-figures presenting the average probabilities of HHL and Psi-HHL
with varying condition number $\mathcal{\kappa}$ of $A$, for $4\times 4$
matrices and using $10^{6}$ throughout. Sub-figures (a) through (c) consider
the case where $A$ is diagonal, and $\vec{b}$ is in equal superposition. Sub-
figures (d) through (f) consider the case where $A$ is diagonal and $\vec{b}$
is in unequal superposition, and Sub-figures (g) through (i) consider the case
where $A$ is not diagonal, and $\vec{b}$ is in unequal superposition. Table
A1: Table presenting the data for HHL and Psi-HHL algorithms (with
$\alpha=60^{\circ}$) for $4\times 4$ matrices, and in particular, for three
cases: $A$ diagonal and $\vec{b}$ in equal superposition (denoted in the table
as ‘$A$ diag, $\vec{b}$ equal’), $A$ diagonal and $\vec{b}$ not in equal
superposition (denoted in the table as ‘$A$ diag, $\vec{b}$ unequal’), and $A$
not diagonal and $\vec{b}$ in an unequal superposition (denoted in the table
as ‘$A$ not diag, $\vec{b}$ unequal’). The string ‘nan’ refers to situations
where we get the square root of a negative quantity for energy, which is
unphysical, and hence is not a valid result.

|  |  |  $A$ diag, $\vec{b}$ equal |  $A$ diag, $\vec{b}$ unequal |  $A$ not diag, $\vec{b}$ unequal
---|---|---|---|---|---
# shots | $\mathcal{\approx\mathcal{\kappa}}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1))$ | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$)
| $2^{2}$ | 8 | -0.44(0.65, 0.35) | -0.22(0.21, 0.79) | -1.01(0.92, 0.08) | -0.10(0.06, 0.94) | -0.87(0.92, 0.08) | -0.04(0.08, 0.92)
| $2^{3}$ | 9 | -0.55(0.72, 0.28) | -0.07(0.27, 0.73) | -5.82(0.97, 0.03) | -0.32(0.15, 0.85) | -5.72(0.97, 0.03) | 0.08(0.15, 0.85)
| $2^{4}$ | 10 | -0.81(0.74, 0.26) | 0.32(0.32, 0.68) | 14.39(0.99, 0.01) | -0.69(0.2, 0.80) | 17.20(0.99, 0.01) | 0.26(0.2, 0.80)
| $2^{5}$ | 11 | -0.17(0.75, 0.25) | -0.02(0.35, 0.65) | 3.96(0.99, 0.01) | 2.85(0.23, 0.77) | -0.12(0.99, 0.01) | 0.32(0.22, 0.78)
| $2^{6}$ | 12 | 0.30(0.75, 0.25) | 0.05(0.37, 0.63) | -6.73(0.99, 0.01) | 1.66(0.24, 0.76) | -6.73(0.99, 0.01) | -1.56(0.24, 0.76)
| $2^{7}$ | 13 | nan(0.75, 0.25) | -0.45(0.37, 0.63) | nan(0.99, 0.01) | 1.91(0.25, 0.75) | nan(0.99, 0.01) | -2.62(0.25, 0.75)
| $2^{8}$ | 14 | nan(0.75, 0.25) | -0.01(0.37, 0.63) | nan(0.99, 0.01) | -2.00(0.25, 0.75) | nan(0.99, 0.01) | -3.87(0.25, 0.75)
| $2^{9}$ | 15 | nan(0.75, 0.25) | -0.22(0.37, 0.63) | nan(0.99, 0.01) | -7.50(0.25, 0.75) | nan(0.99, 0.01) | 8.02(0.25, 0.75)
| $2^{10}$ | 16 | nan(0.75, 0.25) | -0.26(0.37, 0.63) | nan(0.99, 0.01) | -2.33(0.25, 0.75) | nan(0.99, 0.01) | -7.77(0.25, 0.75)
| $2^{11}$ | 17 | nan(0.75, 0.25) | 0.08(0.37, 0.63) | nan(0.99, 0.01) | 2.65(0.25, 0.75) | nan(0.99, 0.01) | -0.55(0.25, 0.75)
| $2^{12}$ | 18 | nan(0.75, 0.25) | 0.03(0.37, 0.63) | nan(0.99, 0.01) | 7.93(0.25, 0.75) | nan(0.99, 0.01) | -2.41(0.25, 0.75)
| $2^{13}$ | 19 | nan(0.75, 0.25) | 0.30(0.38, 0.62) | nan(0.99, 0.01) | 4.67(0.25, 0.75) | nan(0.99, 0.01) | 3.12(0.25, 0.75)
| $2^{14}$ | 20 | nan(0.75, 0.25) | 0.41(0.38, 0.62) | nan(0.99, 0.01) | 9.11(0.25, 0.75) | nan(0.99, 0.01) | -5.60(0.25, 0.75)
| $2^{15}$ | 21 | nan(0.75, 0.25) | 0.13(0.38, 0.62) | nan(0.99, 0.01) | 9.42(0.26,0.74) | nan(0.99, 0.01) | -1.11(0.25, 0.75)
| $2^{16}$ | 22 | nan(0.75, 0.25) | 0.54(0.38, 0.62) | nan(0.99, 0.01) | -0.25(0.25, 0.75) | nan(0.99, 0.01) | 2.43(0.25, 0.75)
| $2^{17}$ | 23 | nan(0.75, 0.25) | -0.03(0.38, 0.62) | nan(0.99, 0.01) | -0.40(0.26, 0.74) | nan(0.99, 0.01) | -7.87(0.25, 0.75)
| $2^{18}$ | 24 | nan(0.75, 0.25) | 0.26(0.37, 0.63) | nan(0.99, 0.01) | -8.56(0.26, 0.74) | nan(0.99, 0.01) | 9.69(0.26, 0.74)
| $2^{19}$ | 25 | nan(0.75, 0.25) | 0.19(0.37, 0.63) | nan(0.99, 0.01) | 6.91(0.26, 0.74) | nan(0.99, 0.01) | 1.06(0.25, 0.75)
$10^{5}$ | $2^{20}$ | 26 | nan(0.75, 0.25) | -0.58(0.37, 0.63) | nan(0.99, 0.01) | 0.30(0.25, 0.75) | nan(0.99, 0.01) | 6.15(0.25, 0.75)
| $2^{2}$ | 8 | -0.57(0.65, 0.35) | 0.00(0.21, 0.79) | -0.87(0.92, 0.08) | 0.03(0.08, 0.92) | -0.88(0.92, 0.08) | 0.04(0.08, 0.92)
| $2^{3}$ | 9 | -0.61(0.72, 0.28) | -0.14(0.27, 0.73) | -5.82(0.97, 0.03) | -0.04(0.15, 0.85) | -5.82(0.97, 0.03) | 0.00(0.15, 0.85)
| $2^{4}$ | 10 | -0.63(0.74, 0.26) | -0.04(0.31, 0.69) | 14.66(0.99, 0.01) | 0.11(0.20, 0.8) | 14.95(0.99, 0.01) | -0.15(0.20, 0.80)
| $2^{5}$ | 11 | 0.27(0.75, 0.25) | -0.06(0.34, 0.66) | 1.84(0.99, 0.01) | 0.16(0.22, 0.78) | 0.61(0.99, 0.01) | 0.44(0.22, 0.78)
| $2^{6}$ | 12 | 0.04(0.75, 0.25) | 0.00(0.36, 0.64) | -0.72(0.99, 0.01) | 0.01(0.24, 0.76) | 1.68(0.99, 0.01) | -0.70(0.24, 0.76)
| $2^{7}$ | 13 | -0.07(0.75, 0.25) | 0.20(0.37, 0.63) | 1.35(0.99, 0.01) | -1.56(0.25, 0.75) | -4.87(0.99, 0.01) | -0.11(0.25, 0.75)
| $2^{8}$ | 14 | -0.13(0.75, 0.25) | -0.02(0.37, 0.63) | 0.09(0.99, 0.01) | -0.04(0.25, 0.75) | -4.04(0.99, 0.01) | -1.15(0.25, 0.75)
| $2^{9}$ | 15 | 0.05(0.75, 0.25) | 0.06(0.37, 0.63) | -2.82(0.99, 0.01) | 2.82(0.25, 0.75) | nan(0.99, 0.01) | 2.26(0.25, 0.75)
| $2^{10}$ | 16 | 0.04(0.75, 0.25) | -0.04(0.37, 0.63) | nan(0.99, 0.01) | -0.12(0.25, 0.75) | nan(0.99, 0.01) | -0.59(0.25, 0.75)
| $2^{11}$ | 17 | 0.19(0.75, 0.25) | -0.05(0.37, 0.63) | nan(0.99, 0.01) | -1.49(0.25, 0.75) | nan(0.99, 0.01) | 1.41(0.25, 0.75)
| $2^{12}$ | 18 | 0.08(0.75, 0.25) | -0.20(0.37, 0.63) | nan(0.99, 0.01) | 0.11(0.25, 0.75) | nan(0.99, 0.01) | 1.26(0.25, 0.75)
| $2^{13}$ | 19 | 0.12(0.75, 0.25) | 0.01(0.37, 0.63) | nan(0.99, 0.01) | 0.13(0.25, 0.75) | nan(0.99, 0.01) | -3.37(0.25, 0.75)
| $2^{14}$ | 20 | -0.03(0.75, 0.25) | -0.00(0.37, 0.63) | nan(0.99, 0.01) | -4.52(0.25, 0.75) | nan(0.99, 0.01) | 1.47(0.25, 0.75)
| $2^{15}$ | 21 | 0.05(0.75, 0.25) | -0.05(0.37, 0.63) | nan(0.99, 0.01) | -0.70(0.25, 0.75) | nan(0.99, 0.01) | -0.79(0.25, 0.75)
| $2^{16}$ | 22 | 0.10(0.75, 0.25) | 0.12(0.38, 0.63) | nan(0.99, 0.01) | 1.57(0.25, 0.75) | nan(0.99, 0.01) | 0.84(0.25, 0.75)
| $2^{17}$ | 23 | -0.03(0.75, 0.25) | -0.15(0.38, 0.63) | nan(0.99, 0.01) | -0.40(0.25, 0.75) | nan(0.99, 0.01) | 0.05(0.25, 0.75)
| $2^{18}$ | 24 | 0.11(0.25, 0.75) | 0.00(0.37, 0.63) | nan(0.99, 0.01) | -1.22(0.25, 0.75) | nan(0.99, 0.01) | -3.58(0.25, 0.75)
| $2^{19}$ | 25 | 0.08(0.75, 0.25) | -0.03(0.37, 0.63) | nan(0.99, 0.01) | 0.78(0.25, 0.75) | nan(0.99, 0.01) | 1.41(0.25, 0.75)
$10^{6}$ | $2^{20}$ | 26 | 0.16(0.75, 0.25) | -0.19(0.37, 0.63) | nan(0.99, 0.01) | -1.52(0.25, 0.75) | nan(0.99, 0.01) | 0.01(0.25, 0.75)

Table A2: Table providing the data for HHL and Psi-HHL algorithms (with
$\alpha=70^{\circ}$) for $4\times 4$ matrices. The notations are the same as
those used in Table A1.

|  |  |  $A$ diag, $\vec{b}$ equal |  $A$ diag, $\vec{b}$ unequal |  $A$ not diag, $\vec{b}$ unequal
---|---|---|---|---|---
# shots | $\mathcal{\approx\mathcal{\kappa}}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$)
| $2^{2}$ | 8 | -0.04(0.65, 0.35) | -0.24(0.23, 0.77) | -1.01(0.92, 0.08) | -0.18(0.02, 0.98) | -0.87(0.92, 0.08) | 0.58(0.02, 0.98)
| $2^{3}$ | 9 | -0.55(0.72, 0.28) | -0.28(0.25, 0.75) | -5.82(0.97, 0.03) | -0.50(0.06, 0.94) | -5.72(0.97, 0.03) | -0.41(0.06, 0.94)
| $2^{4}$ | 10 | -0.81(0.74, 0.26) | 0.51(0.27, 0.73) | 14.39(0.99, 0.01) | 0.33(0.12, 0.88) | 17.20(0.99, 0.01) | 0.44(0.09, 0.91)
| $2^{5}$ | 11 | -0.17(0.75, 0.25) | 0.05(0.29, 0.71) | 3.96(0.99, 0.01) | -0.17(0.1, 0.90) | -0.12(0.99, 0.01) | 1.17(0.10, 0.90)
| $2^{6}$ | 12 | 0.30(0.75, 0.25) | 0.54(0.30, 0.70) | nan(0.99, 0.01) | -1.16( 0.12, 0.88) | -6.73(0.99, 0.01) | 0.99(0.11, 0.89)
| $2^{7}$ | 13 | nan(0.75, 0.25) | 0.74(0.30,0.70) | nan(0.99, 0.01) | 0.30(0.12, 0.88) | nan(0.99, 0.01) | 2.20(0.02, 0.88)
| $2^{8}$ | 14 | nan(0.75, 0.25) | 0.40(0.30, 0.69) | nan(0.99, 0.01) | -7.03(0.12, 0.88) | nan(0.99, 0.01) | 3.54(0.02, 0.88)
| $2^{9}$ | 15 | nan(0.75, 0.25) | -0.31(0.31, 0.69) | nan(0.99, 0.01) | 2.88(0.12, 0.88) | nan(0.99, 0.01) | 1.96(0.02, 0.88)
| $2^{10}$ | 16 | nan(0.75, 0.25) | 0.02(0.31, 0.69) | nan(0.99, 0.01) | 5.28(0.12, 0.88) | nan(0.99, 0.01) | 4.93(0.02, 0.88)
| $2^{11}$ | 17 | nan(0.75, 0.25) | -0.30(0.31, 0.69) | nan(0.99, 0.01) | 2.52(0.12, 0.88) | nan(0.99, 0.01) | -2.36(0.02, 0.88)
| $2^{12}$ | 18 | nan(0.75, 0.25) | 0.48(0.31, 0.69) | nan(0.99, 0.01) | -3.50(0.12, 0.88) | nan(0.99, 0.01) | 0.81(0.02, 0.88)
| $2^{13}$ | 19 | nan(0.75, 0.25) | 0.38(0.31, 0.69) | nan(0.99, 0.01) | -9.08(0.12, 0.88) | nan(0.99, 0.01) | -2.22(0.02, 0.88)
| $2^{14}$ | 20 | nan(0.75, 0.25) | 0.15(0.31, 0.69) | nan(0.99, 0.01) | -0.46(0.12, 0.88) | nan(0.99, 0.01) | 0.33(0.02, 0.88)
| $2^{15}$ | 21 | nan(0.75, 0.25) | 1.26(0.31, 0.69) | nan(0.99, 0.01) | 3.66(0.12, 0.88) | nan(0.99, 0.01) | 6.98(0.02, 0.88)
| $2^{16}$ | 22 | nan(0.75, 0.25) | -0.34(0.31, 0.69) | nan(0.99, 0.01) | 5.62(0.12, 0.88) | nan(0.99, 0.01) | -17.07(0.02, 0.88)
| $2^{17}$ | 23 | nan(0.75, 0.25) | 1.31(0.31, 0.69) | nan(0.99, 0.01) | 5.56(0.12, 0.88) | nan(0.99, 0.01) | 2.02(0.02, 0.88)
| $2^{18}$ | 24 | nan(0.75, 0.25) | 0.00(0.69, 0.31) | nan(0.99, 0.01) | 0.00(0.12, 0.88) | nan(0.99, 0.01) | 18.88(0.13, 0.87)
| $2^{19}$ | 25 | nan(0.75, 0.25) | 0.33(0.31, 0.69) | nan(0.99, 0.01) | 0.33(0.12, 0.88) | nan(0.99, 0.01) | 6.42( 0.12, 0.88)
$10^{5}$ | $2^{20}$ | 26 | nan(0.75, 0.25) | -0.27(0.31, 0.69) | nan(0.99, 0.01) | -6.81(0.12, 0.88) | nan(0.99, 0.01) | 6.75(0.12, 0.88)
| $2^{2}$ | 8 | -0.57(0.64, 0.36) | -0.01(0.23, 0.77) | -0.87(0.92, 0.08) | -0.02(0.02, 0.98) | -0.88(0.92, 0.08) | -0.01(0.02, 0.98)
| $2^{3}$ | 9 | -0.61(0.72, 0.28) | -0.16(0.22, 0.76) | -5.82(0.97, 0.03) | 0.04(0.06,0.94) | -5.82(0.97, 0.03) | 0.00(0.06, 0.94)
| $2^{4}$ | 10 | -0.63(0.74, 0.26) | -0.05(0.27, 0.73) | 14.66(0.99, 0.01) | -0.26(0.09, 0.91) | 14.95(0.99, 0.01) | -0.27(0.09, 0.91)
| $2^{5}$ | 11 | 0.27(0.75, 0.25) | -0.08(0.29, 0.71) | 1.84(0.99, 0.01) | -0.26(0.10, 0.90) | 0.61(0.99, 0.01) | 0.50(0.11, 0.89)
| $2^{6}$ | 12 | 0.04(0.75, 0.25) | 0.02(0.3, 0.70) | -0.72(0.99, 0.01) | 1.32(0.11, 0.89) | 1.68(0.99, 0.01) | -0.27(0.12, 0.88)
| $2^{7}$ | 13 | -0.07(0.75, 0.25) | -0.07(0.31, 0.69) | 1.35(0.99, 0.01) | -0.24(0.12, 0.88) | -4.87(0.99, 0.01) | 0.40(0.12, 0.88)
| $2^{8}$ | 14 | -0.13(0.75, 0.25) | 0.12(0.31, 0.69) | 0.09(0.99, 0.01) | 0.43(0.12, 0.88) | -4.04(0.99, 0.01) | 1.91(0.12, 0.88)
| $2^{9}$ | 15 | 0.05(0.75, 0.25) | 0.19(0.31, 0.69) | -2.82(0.99, 0.01) | -1.81(0.12, 0.88) | nan(0.99, 0.01) | 1.12(0.12, 0.88)
| $2^{10}$ | 16 | -0.04(0.75, 0.25) | -0.26(0.31, 0.69) | nan(0.99, 0.01) | 1.19(0.12, 0.88) | nan(0.99, 0.01) | -2.59(0.12, 0.88)
| $2^{11}$ | 17 | 0.18(0.75, 0.25) | 0.04(0.31, 0.69) | nan(0.99, 0.01) | -1.68(0.12, 0.88) | nan(0.99, 0.01) | -0.85(0.12, 0.88)
| $2^{12}$ | 18 | 0.07(0.75, 0.25) | -0.44(0.31, 0.69) | nan(0.99, 0.01) | 2.36(0.12, 0.88) | nan(0.99, 0.01) | -5.96(0.12, 0.88)
| $2^{13}$ | 19 | 0.12(0.75, 0.25) | 0.15(0.31, 0.69) | nan(0.99, 0.01) | 5.19(0.12, 0.88) | nan(0.99, 0.01) | 1.52(0.12, 0.88)
| $2^{14}$ | 20 | -0.04(0.75, 0.25) | 0.25(0.31, 0.69) | nan(0.99, 0.01) | 2.50(0.12, 0.88) | nan(0.99, 0.01) | -1.89(0.12, 0.88)
| $2^{15}$ | 21 | 0.06(0.75, 0.25) | -0.33(0.31, 0.69) | nan(0.99, 0.01) | 0.41(0.12, 0.88) | nan(0.99, 0.01) | -3.65(0.12, 0.88)
| $2^{16}$ | 22 | 0.10(0.75, 0.25) | -0.01(0.31, 0.69) | nan(0.99, 0.01) | -3.09(0.12, 0.88) | nan(0.99, 0.01) | -1.88(0.12, 0.88)
| $2^{17}$ | 23 | -0.03(0.75, 0.25) | -0.07(0.31, 0.69) | nan(0.99, 0.01) | 2.54(0.12, 0.88) | nan(0.99, 0.01) | -0.92(0.12, 0.88)
| $2^{18}$ | 24 | 0.11(0.75, 0.25) | 0.07(0.31, 0.69) | nan(0.99, 0.01) | -0.47(0.88, 0.12) | nan(0.99, 0.01) | -0.46(0.88, 0.12)
| $2^{19}$ | 25 | -0.08(0.75, 0.25) | 0.09(0.31, 0.69) | nan(0.99, 0.01) | 1.81(0.12, 0.88) | nan(0.99, 0.01) | -0.89(0.12, 0.88)
$10^{6}$ | $2^{20}$ | 26 | 0.16(0.75, 0.25) | -0.02(0.31, 0.69) | nan(0.99, 0.01) | -2.00(0.12, 0.88) | nan(0.99, 0.01) | 3.65(0.12, 0.88)

Table A3: Table providing the data for HHL and Psi-HHL algorithms (with
$\alpha=80^{\circ}$) for $4\times 4$ matrices. The notations are the same as
those used in Tables A1 and A2.

|  |  |  $A$ diag, $\vec{b}$ equal |  $A$ diag, $\vec{b}$ unequal |  $A$ not diag, $\vec{b}$ unequal
---|---|---|---|---|---
# shots | $\mathcal{\approx\mathcal{\kappa}}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$)
| $2^{2}$ | 8 | -0.44(0.65, 0.35) | 0.43(0.21, 0.79) | -1.01(0.92, 0.08) | 0.06(0.01, 0.99) | -0.87(0.92, 0.08) | 0.31(0.02, 0.98)
| $2^{3}$ | 9 | -0.55(0.72, 0.28) | 0.29(0.27, 0.73) | -5.82(0.97, 0.03) | -0.59(0.02, 0.98) | -5.72(0.97, 0.03) | -0.92(0.02, 0.98)
| $2^{4}$ | 10 | -0.81(0.74, 0.26) | 2.47(0.32, 0.68) | 14.39(0.99, 0.01) | 2.59(0.02, 0.98) | 17.20(0.99, 0.01) | 1.55(0.02, 0.98)
| $2^{5}$ | 11 | -0.17(0.75, 0.25) | 0.67(0.35, 0.65) | 3.96(0.99, 0.01) | 1.63(0.03, 0.97) | -0.12(0.99, 0.01) | 1.89(0.03, 0.97)
| $2^{6}$ | 12 | 0.30(0.75, 0.25) | -0.17(0.36, 0.64) | -6.73(0.99, 0.01) | 5.34(0.04, 0.96) | -6.73(0.99, 0.01) | -4.59(0.03, 0.97)
| $2^{7}$ | 13 | nan(0.75, 0.25) | -0.30(0.37, 0.63) | nan(0.99, 0.01) | 0.55(0.04, 0.96) | nan(0.99, 0.01) | 0.37(0.04, 0.96)
| $2^{8}$ | 14 | nan(0.75, 0.25) | -2.17(0.37, 0.63) | nan(0.99, 0.01) | 6.89(0.04, 0.96) | nan(0.99, 0.01) | 0.46(0.04, 0.96)
| $2^{9}$ | 15 | nan(0.75, 0.25) | 0.04(0.37, 0.63) | nan(0.99, 0.01) | -2.64(0.04, 0.96) | nan(0.99, 0.01) | 4.65(0.04, 0.96)
| $2^{10}$ | 16 | nan(0.75, 0.25) | 1.01(0.37, 0.63) | nan(0.99, 0.01) | 3.21(0.04, 0.96) | nan(0.99, 0.01) | -4.06(0.04, 0.96)
| $2^{11}$ | 17 | nan(0.75, 0.25) | -0.20(0.37, 0.63) | nan(0.99, 0.01) | -5.46(0.04, 0.96) | nan(0.99, 0.01) | -0.93(0.04, 0.96)
| $2^{12}$ | 18 | nan(0.75, 0.25) | -0.55(0.37, 0.63) | nan(0.99, 0.01) | -4.80(0.04, 0.96) | nan(0.99, 0.01) | 9.42(0.04, 0.96)
| $2^{13}$ | 19 | nan(0.75, 0.25) | -0.17(0.37, 0.63) | nan(0.99, 0.01) | 2.18(0.04, 0.96) | nan(0.99, 0.01) | 7.83(0.04, 0.96)
| $2^{14}$ | 20 | nan(0.75, 0.25) | 0.56(0.37, 0.63) | nan(0.99, 0.01) | 5.32(0.04, 0.96) | nan(0.99, 0.01) | -0.86(0.04, 0.96)
| $2^{15}$ | 21 | nan(0.75, 0.25) | -0.11(0.37, 0.63) | nan(0.99, 0.01) | 5.89(0.04, 0.96) | nan(0.99, 0.01) | 3.92(0.04, 0.96)
| $2^{16}$ | 22 | nan(0.75, 0.25) | 0.24(0.37, 0.63) | nan(0.99, 0.01) | -12.26(0.04, 0.96) | nan(0.99, 0.01) | 9.60(0.04, 0.96)
| $2^{17}$ | 23 | nan(0.75, 0.25) | -0.94(0.37, 0.63) | nan(0.99, 0.01) | -2.94(0.04, 0.96) | nan(0.99, 0.01) | -5.61(0.04, 0.96)
| $2^{18}$ | 24 | nan(0.75, 0.25) | -1.64(0.26, 0.74) | nan(0.99, 0.01) | -0.60(0.04, 0.96) | nan(0.99, 0.01) | 5.92(0.04, 0.96)
| $2^{19}$ | 25 | nan(0.75, 0.25) | 1.47(0.27, 0.73) | nan(0.99, 0.01) | -0.60(0.04, 0.96) | nan(0.99, 0.01) | -4.92(0.04, 0.96)
$10^{5}$ | $2^{20}$ | 26 | nan(0.75, 0.25) | -1.70(0.26, 0.74) | nan(0.99, 0.01) | -17.20(0.04, 0.96) | nan(0.99, 0.01) | 5.03(0.04, 0.96)
| $2^{2}$ | 8 | -0.57(0.64, 0.36) | -0.13(0.28, 0.72) | -0.87(0.92, 0.08) | 0.00(0.02, 0.98) | -0.88(0.92, 0.08) | 0.03(0.02, 0.98)
| $2^{3}$ | 9 | -0.61(0.72, 0.28) | 0.14(0.24, 0.76) | -5.82(0.97, 0.03) | -0.19(0.01, 0.99) | -5.82(0.97, 0.03) | -0.06(0.01, 0.99)
| $2^{4}$ | 10 | -0.63(0.74, 0.26) | -0.03(0.25, 0.75) | 14.66(0.99, 0.01) | -0.22(0.02, 0.98) | 14.95(0.99, 0.01) | -0.02(0.02, 0.98)
| $2^{5}$ | 11 | 0.27(0.75, 0.25) | 0.64(0.26, 0.74) | 1.84(0.99, 0.01) | 0.03(0.03, 0.97) | 0.61(0.99, 0.01) | 1.11(0.03, 0.97)
| $2^{6}$ | 12 | 0.04(0.75, 0.25) | -0.05(0.26, 0.74) | -0.72(0.99, 0.01) | 1.21(0.04, 0.96) | 1.68(0.99, 0.01) | 0.68(0.03, 0.97)
| $2^{7}$ | 13 | -0.07(0.75, 0.25) | 0.17(0.26, 0.74) | 1.35(0.99, 0.01) | -1.22(0.04, 0.96) | -4.87(0.99, 0.01) | 0.24(0.03, 0.97)
| $2^{8}$ | 14 | -0.13(0.75, 0.25) | -0.17(0.26, 0.74) | 0.09(0.99, 0.01) | -3.19(0.04, 0.96) | -4.04(0.99, 0.01) | 0.32(0.04, 0.96)
| $2^{9}$ | 15 | 0.05(0.75, 0.25) | -0.50(0.26, 0.74) | 2.82(0.99, 0.01) | -2.13(0.04, 0.96) | nan(0.99, 0.01) | -2.48(0.04, 0.96)
| $2^{10}$ | 16 | -0.03(0.75, 0.25) | -0.30(0.26, 0.74) | nan(0.99, 0.01) | -0.59(0.04, 0.96) | nan(0.99, 0.01) | -0.24(0.04, 0.96)
| $2^{11}$ | 17 | 0.18(0.75, 0.25) | 0.47(0.26, 0.74) | nan(0.99, 0.01) | -2.93(0.04, 0.96) | nan(0.99, 0.01) | 0.05(0.04, 0.96)
| $2^{12}$ | 18 | 0.07(0.75, 0.25) | 0.40(0.26, 0.74) | nan(0.99, 0.01) | 0.62(0.04, 0.96) | nan(0.99, 0.01) | -2.73(0.04, 0.96)
| $2^{13}$ | 19 | 0.11(0.75, 0.25) | 0.14(0.26, 0.74) | nan(0.99, 0.01) | 0.12(0.04, 0.96) | nan(0.99, 0.01) | 6.03(0.04, 0.96)
| $2^{14}$ | 20 | -0.03(0.75, 0.25) | 0.62(0.26, 0.74) | nan(0.99, 0.01) | 2.52(0.04, 0.96) | nan(0.99, 0.01) | 0.28(0.04, 0.96)
| $2^{15}$ | 21 | 0.05(0.75, 0.25) | -0.34(0.26, 0.74) | nan(0.99, 0.01) | 1.03(0.04, 0.96) | nan(0.99, 0.01) | -6.30(0.04, 0.96)
| $2^{16}$ | 22 | 0.10(0.75, 0.25) | -0.59(0.26, 0.74) | nan(0.99, 0.01) | -3.21(0.04, 0.96) | nan(0.99, 0.01) | -2.40(0.04, 0.96)
| $2^{17}$ | 23 | -0.03(0.75, 0.25) | 0.49(0.26, 0.74) | nan(0.99, 0.01) | 0.45(0.04, 0.96) | nan(0.99, 0.01) | 2.72(0.04, 0.96)
| $2^{18}$ | 24 | 0.11(0.75, 0.25) | 0.14(0.27, 0.73) | nan(0.99, 0.01) | -2.46(0.04, 0.96) | nan(0.99, 0.01) | -1.52(0.04, 0.96)
| $2^{19}$ | 25 | 0.08(0.75, 0.25) | 0.01(0.27, 0.73) | nan(0.99, 0.01) | -1.95(0.04, 0.96) | nan(0.99, 0.01) | -0.72(0.04, 0.96)
$10^{6}$ | $2^{20}$ | 26 | 0.16(0.75, 0.25) | -0.33(0.27, 0.73) | nan(0.99, 0.01) | -2.07(0.04, 0.96) | nan(0.99, 0.01) | -2.46(0.04, 0.96)

Table A4: Summary of the fitted probabilities of HHL and Psi-HHL for the 4x4 case $A$ not diagonal and $\vec{b}$ in an unequal superposition of states, $\alpha=60^{\circ},70^{\circ},80^{\circ}$ and the number of shots is fixed to $10^{6}$. $\alpha$ | $\approx\mathcal{\kappa}$ | $P_{\text{Fit}}(0)$ | $P_{\text{Fit}}(1)$ | $P_{\text{Fit}}(0)+P_{\text{Fit}(1)}$ | $P^{\prime}_{\text{Fit}}(0)$ | $P^{\prime}_{\text{Fit}}(1)$ | $P^{\prime}_{\text{Fit}}(0)+P^{\prime}_{\text{Fit}}(1)$
---|---|---|---|---|---|---|---
$60^{\circ}$ | 4 | 0.92 | 0.08 | 1.00 | 0.07 | 0.93 | 1.00
32 | 0.99 | 0.01 | 1.00 | 0.22 | 0.78 | 1.00
64 | 0.99 | 0.01 | 1.00 | 0.24 | 0.76 | 1.00
1024 | 0.99 | 0.01 | 1.00 | 0.25 | 0.75 | 1.00
2048 | 0.99 | 0.01 | 1.00 | 0.25 | 0.75 | 1.00
$70^{\circ}$ | 4 | 0.92 | 0.08 | 1.00 | 0.01 | 0.99 | 1.00
32 | 0.99 | 0.01 | 1.00 | 0.10 | 0.90 | 1.00
128 | 0.99 | 0.01 | 1.00 | 0.11 | 0.89 | 1.00
1024 | 0.99 | 0.01 | 1.00 | 0.12 | 0.88 | 1.00
2048 | 0.99 | 0.01 | 1.00 | 0.12 | 0.88 | 1.00
$80^{\circ}$ | 4 | 0.92 | 0.08 | 1.00 | 0.02 | 0.98 | 1.00
32 | 0.99 | 0.01 | 1.00 | 0.03 | 0.97 | 1.00
128 | 0.99 | 0.01 | 1.00 | 0.04 | 0.96 | 1.00
1024 | 0.99 | 0.01 | 1.00 | 0.04 | 0.96 | 1.00
2048 | 0.99 | 0.01 | 1.00 | 0.04 | 0.96 | 1.00

|  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$

|  |
---|---|---
(d) $\alpha=60^{\circ}$ | (e) $\alpha=70^{\circ}$ | (f) $\alpha=80^{\circ}$

Figure A4: Sub-figures presenting the average probabilities of HHL and Psi-HHL with varying condition number $\mathcal{\kappa}$ of $A$, for $8\times 8$ matrices using $10^{5}$ shots ((a) through (c)) and using $10^{6}$ ((d) through (f)) |  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$
Figure A5: Sub-figures presenting the average probabilities of HHL and Psi-HHL with varying condition number $\mathcal{\kappa}$ of $A$, for $16\times 16$ matrices and using $10^{6}$ shots throughout. |  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$
Figure A6: Data for $32\times 32$ matrices. Note that we have again reproduced here the sub-figure (a) with 1 million shots (which are already present in the main text). |  |
---|---|---
(a) $\alpha=60^{\circ}$ | (b) $\alpha=70^{\circ}$ | (c) $\alpha=80^{\circ}$
Figure A7: Data for $64\times 64$ matrices. Note that we have again reproduced here the sub-figure (a) with 1 million shots (which are already present in the main text). Figure A8: Figure showing average (over 10 repetitions) values of percentage fraction difference (PFD) of HHL and Psi-HHL, as the condition number grows from $2^{2}$ to $2^{20}$, for fixed $A$ matrix sizes going from $4\times 4$ to $64\times 64$. Only the case where $\alpha=60^{\circ}$, $A$ not diagonal, $\vec{b}$ in an unequal superposition, and number of shots =$10^{6}$ is considered. The blue cells indicate cases where HHL gives outputs, and red denotes cases where HHL fails. The white cells denote those cases for which we did not carry a calculation, due to computational cost.  Table A5: Table providing the data for HHL and Psi-HHL algorithms (with $\alpha=60^{\circ}$, $70^{\circ}$, $80^{\circ}$) for $8\times 8$ matrices.  |  |  | HHL | Psi-HHL |  |
---|---|---|---|---|---|---
|  |  |  | $\alpha=60^{\circ}$ | $\alpha=70^{\circ}$ | $\alpha=80^{\circ}$ |  |
# shots | $\approx\mathcal{\kappa}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) |  |
| $2^{2}$ | 10 | -6.75(0.82, 0.18) | 4.90(0.07, 0.93) | 5.99(0.05, 0.95) | 6.97(0.10, 0.90) |  |
| $2^{3}$ | 11 | -4.69(0.95, 0.05) | -3.11(0.11, 0.89) | -2.93(0.03, 0.97) | -2.93(0.01, 0.99) |  |
| $2^{4}$ | 12 | -9.27(0.98, 0.02) | -2.75(0.18, 0.82) | -2.48(0.07, 0.93) | 2.54(0.02, 0.98) |  |
| $2^{5}$ | 13 | 1.87(0.99, 0.01) | 1.60(0.21, 0.79) | -0.90(0.10, 0.90) | -0.09(0.02, 0.98) |  |
| $2^{6}$ | 14 | 0.12(0.99, 0.01) | -1.20(0.23, 0.77) | -1.21(0.11, 0.89) | -4.35(0.03, 0.97) |  |
| $2^{7}$ | 15 | 0.09(0.99, 0.01) | -1.96(0.24, 0.76) | -3.83(0.12, 0.88) | 0.40(0.03, 0.97) |  |
| $2^{8}$ | 16 | nan(0.99, 0.01) | -0.33(0.25, 0.75) | -1.74(0.12, 0.88) | -4.53(0.03, 0.97) |  |
| $2^{9}$ | 17 | nan(0.99, 0.01) | -13.83(0.25, 0.75) | -3.82(0.12, 0.88) | 10.35(0.04, 0.96) |  |
| $2^{10}$ | 18 | nan(0.99, 0.01) | -1.66(0.25, 0.75) | 0.94(0.12, 0.88) | -7.44(0.04, 0.96) |  |
| $2^{11}$ | 19 | nan(0.99, 0.01) | -0.82(0.25, 0.75) | 4.90(0.12, 0.88) | 3.13(0.04, 0.96) |  |
| $2^{12}$ | 20 | nan(0.99, 0.01) | -0.91(0.25, 0.75) | -7.52(0.12, 0.88) | 10.89(0.04, 0.96) |  |
| $2^{13}$ | 21 | nan(0.99, 0.01) | 2.62(0.25, 0.75) | 8.41(0.12, 0.88) | -0.26(0.04, 0.96) |  |
| $2^{14}$ | 22 | nan(0.99, 0.01) | -3.20(0.25, 0.75) | 7.12(0.12, 0.88) | 8.53(0.04, 0.96) |  |
| $2^{15}$ | 23 | nan(0.99, 0.01) | 5.74(0.25, 0.75) | -7.34(0.12, 0.88) | -7.60(0.04, 0.96) |  |
| $2^{16}$ | 24 | nan(0.99, 0.01) | -5.89(0.25, 0.75) | -4.65(0.12, 0.88) | -13.89(0.04, 0.96) |  |
| $2^{17}$ | 25 | nan(0.99, 0.01) | -6.58(0.25, 0.75) | -10.10(0.12, 0.88) | 2.78(0.04, 0.96) |  |
$10^{5}$ | $2^{18}$ | 26 | nan(0.99, 0.01) | 1.03(0.25, 0.75) | -3.87(0.12, 0.88) | 4.50(0.04, 0.96) |  |
| $2^{2}$ | 10 | -6.40(0.82, 0.18) | 5.23(0.10, 0.99) | 6.13(0.05, 0.95) | 7.15(0.10, 0.90) |  |
| $2^{3}$ | 11 | -4.69(0.95, 0.05) | -3.14(0.10, 0.90) | -3.02(0.03, 0.97) | -2.83(0.01, 0.99) |  |
| $2^{4}$ | 12 | -8.84(0.98, 0.02) | -2.60(0.18, 0.82) | -2.58(0.07, 0.93) | -2.71(0.02, 0.98) |  |
| $2^{5}$ | 13 | 2.03(0.99, 0.01) | 0.04(0.21, 0.79) | 0.03(0.09, 0.91) | -0.04(0.02, 0.98) |  |
| $2^{6}$ | 14 | -8.55(0.99, 0.01) | -1.49(0.23, 0.77) | -0.73(0.11, 0.89) | -1.09(0.03, 0.97) |  |
| $2^{7}$ | 15 | -4.68(0.99, 0.01) | -2.18(0.24, 0.76) | 1.16(0.12, 0.88) | 0.36(0.03, 0.97) |  |
| $2^{8}$ | 16 | -0.39(0.99, 0.01) | 1.51(0.25, 0.75) | -1.35(0.12, 0.88) | -1.61(0.04, 0.96) |  |
| $2^{9}$ | 17 | -10.48(0.99, 0.01) | 2.19(0.25, 0.75) | 1.34(0.12, 0.88) | -1.99(0.04, 0.96) |  |
| $2^{10}$ | 18 | -29.14(0.99, 0.01) | 0.08(0.25, 0.75) | -3.98(0.12, 0.88) | 0.33(0.04, 0.96) |  |
| $2^{11}$ | 19 | nan(0.99, 0.01) | 1.51(0.25, 0.75) | -4.00(0.12, 0.88) | -1.72(0.04, 0.96) |  |
| $2^{12}$ | 20 | nan(0.99, 0.01) | 1.34(0.25, 0.75) | 0.28(0.12, 0.88) | 0.00(0.04, 0.96) |  |
| $2^{13}$ | 21 | nan(0.99, 0.01) | -2.83(0.25, 0.75) | 1.03(0.12, 0.88) | 1.99(0.04, 0.96) |  |
| $2^{14}$ | 22 | nan(0.99, 0.01) | 3.20(0.25, 0.75) | -4.70(0.12, 0.88) | 1.75(0.04, 0.96) |  |
| $2^{15}$ | 23 | nan(0.99, 0.01) | -0.19(0.25, 0.75) | -4.56(0.12, 0.88) | -0.58(0.04, 0.96) |  |
| $2^{16}$ | 24 | nan(0.99, 0.01) | 0.97(0.25, 0.75) | 0.14(0.12, 0.88) | -0.11(0.04, 0.96) |  |
| $2^{17}$ | 25 | nan(0.99, 0.01) | 0.62(0.25, 0.75) | 3.21(0.12, 0.88) | 3.19(0.04, 0.96) |  |
$10^{6}$ | $2^{18}$ | 26 | nan(0.99, 0.01) | -0.56(0.25, 0.75) | -5.17(0.12, 0.88) | 2.30(0.04, 0.96) |  |
Table A6: Table providing the data for HHL and Psi-HHL algorithms (with $\alpha=60^{\circ}$, $70^{\circ}$, $80^{\circ}$) for $16\times 16$ matrices.  |  |  | HHL | Psi-HHL |  |
---|---|---|---|---|---|---
|  |  |  | $60^{\circ}$ | $70^{\circ}$ | $80^{\circ}$ |  |
# shots | $\approx\kappa$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) |  |
| $2^{2}$ | 12 | -5.90(0.83,0.17) | 3.60(0.06, 0.94) | 4.29(0.04,0.96) | 5.11(0.08,0.92) |  |
| $2^{3}$ | 13 | -9.09(0.95,0.05) | -3.42(0.11,0.89) | -3.26(0.03,0.97) | 3.19(0.01,0.99) |  |
| $2^{4}$ | 14 | -15.82(0.98,0.02) | -2.09(0.18, 0.82) | -2.17(0.07,0.93) | -1.76(0.01,0.99) |  |
| $2^{5}$ | 15 | -8.45(0.99,0.01) | -0.75(0.21, 0.79) | -0.53(0.10,0.91) | 0.92(0.02,0.98) |  |
| $2^{6}$ | 16 | -25.62(0.99,0.01) | 0.10(0.23, 0.77) | 0.60(0.11,0.89) | -0.06(0.03,0.97) |  |
| $2^{7}$ | 17 | -24.21(0.99,0.01) | -1.22(0.24, 0.76) | -1.18(0.11,0.89,) | -2.15(0.03,0.97) |  |
| $2^{8}$ | 18 | 2.25(0.99,0.01) | -1.30(0.25, 0.75) | 0.47(0.12, 0.88) | 2.68(0.03,0.97) |  |
| $2^{9}$ | 19 | nan(0.99,0.01) | -0.85(0.25, 0.75) | 3.64(0.12,0.88) | -0.04(0.04,0.97) |  |
| $2^{10}$ | 20 | nan(0.99,0.01) | 1.75(0.25, 0.75) | -0.11(0.12,0.88) | -5.97(0.04,0.96) |  |
| $2^{11}$ | 21 | nan(0.99,0.01) | -2.02(0.25, 0.75) | -2.59(0.12,0.88) | 3.26(0.04,0.96) |  |
| $2^{12}$ | 22 | nan(0.99,0.01) | -2.75(0.25, 0.75) | -4.15(0.12,0.88) | -7.93(0.04,0.96) |  |
| $2^{13}$ | 23 | nan(0.99,0.01) | -4.07(0.25, 0.75) | 0.29(0.12,0.88) | 1.88(0.04,0.96) |  |
| $2^{14}$ | 24 | nan(0.99,0.01) | -3.97(0.25, 0.75) | -0.83(0.12,0.88) | 1.30(0.04,0.96) |  |
| $2^{15}$ | 25 | nan(0.99,0.01) | 7.01(0.25, 0.75) | -1.46(0.12,0.88) | 2.07(0.04,0.96) |  |
$10^{6}$ | $2^{16}$ | 26 | nan(0.99,0.01) | -1.31(0.25, 0.75) | -5.10(0.12,0.88) | -11.71(0.04,0.96) |  |
Table A7: Table providing the data for HHL and Psi-HHL algorithms (with $\alpha=60^{\circ}$, $70^{\circ}$, $80^{\circ}$) for $32\times 32$ matrices.  |  |  | HHL | Psi-HHL |  |
---|---|---|---|---|---|---
|  |  |  | $60^{\circ}$ | $70^{\circ}$ | $80^{\circ}$ |  |
# shots | $\approx\mathcal{\kappa}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) |  |
| $2^{2}$ | 14 | -0.38(0.17, 0.83) | 1.73(0.06, 0.94) | 1.72(0.04, 0.96) | 1.68(0.08,0.92) |  |
| $2^{3}$ | 15 | -2.44(0.05, 0.95) | -0.37(0.12, 0.88) | -0.25(0.04, 0.96) | -0.32(0.01,0.99) |  |
| $2^{4}$ | 16 | -9.53(0.02, 0.98) | -1.73(0.18, 0.82) | -1.71(0.07, 0.93) | -1.75(0.01,0.99 |  |
| $2^{5}$ | 17 | -3.12(0.01, 0.99) | -0.71(0.21, 0.79) | -1.30(0.09, 0.91) | -0.64(0.02, 0.98) |  |
| $2^{6}$ | 18 | -18.33(0.01,0.99) | 0.29(0.23, 0.97) | -1.13(0.11, 0.89) | 0.52(0.03, 0.97) |  |
| $2^{7}$ | 19 | -15.11(0.01, 0.99) | -0.52(0.24, 0.76) | -1.25(0.11,0.89) | -1.00(0.03, 0.97 |  |
| $2^{8}$ | 20 | -13.01(0.01, 0.99) | -0.90(0.25, 0.75) | -0.03(0.12, 0.88) | -0.25(0.03, 0.97 |  |
| $2^{9}$ | 21 | -11.12(0.01, 0.99) | -0.15(0.25, 0.75) | 1.12(0.12, 0.88) | -1.40(0.04, 0.96) |  |
| $2^{10}$ | 22 | nan(0.01, 0.99) | -0.44(0.25, 0.75) | 2.37(0.12, 0.88) | 6.12(0.04, 0.96) |  |
| $2^{11}$ | 23 | nan(0.01, 0.99) | 4.36(0.25, 0.75) | 1.54(0.12, 0.88) | -0.60(0.04, 0.96) |  |
| $2^{12}$ | 24 | nan(0.01, 0.99) | 0.72(0.25, 0.75) | 0.23(0.12, 0.88) | -1.07(0.04, 0.96) |  |
| $2^{13}$ | 25 | nan(0.01, 0.99) | -2.31(0.25, 0.75) | -1.56(0.12, 0.88) | 1.31(0.04, 0.96) |  |
$10^{6}$ | $2^{14}$ | 26 | nan(0.01, 0.99) | 0.82(0.25, 0.75) | 4.95(0.12, 0.88) | 1.70(0.04, 0.96) |  |
Table A8: Table providing the data for HHL and Psi-HHL algorithms (with $\alpha=60^{\circ}$, $70^{\circ}$, $80^{\circ}$) for $64\times 64$ matrices.  |  |  | HHL | Psi-HHL |  |
---|---|---|---|---|---|---
|  |  |  | $60^{\circ}$ | $70^{\circ}$ | $80^{\circ}$ |  |
# shots | $\approx\mathcal{\kappa}$ | # qubits | PFD($P(0),P(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) | PFD($P^{\prime}(0),P^{\prime}(1)$) |  |
| $2^{2}$ | 16 | -3.13(0.82, 0.17) | 0.01(0.12, 0.88) | 0.21(0.10, 0.91) | 0.82(0.10, 0.90) |  |
| $2^{3}$ | 17 | -2.26(0.94, 0.05) | -1.06(0.012, 0.88) | -0.95(0.04, 0.96) | -1.01(0.02, 0.98) |  |
| $2^{4}$ | 18 | -14.67(0.98, 0.02) | -1.82(0.17, 0.83) | 1.47(0.03, 0.97) | -1.56(0.02,0.98) |  |
| $2^{5}$ | 19 | -2.16(0.99, 0.01) | -1.27(0.21, 0.79) | -1.57(0.10, 0.91) | -0.86(0.02,0.98) |  |
| $2^{6}$ | 20 | -1.28(1.00, 0.00) | -0.55(0.23, 0.77) | -1.26(0.10, 0.90) | -1.06(0.02, 0.98) |  |
| $2^{7}$ | 21 | -6.18(1.00, 0.00) | 0.16(0.24, 0.76) | -0.10(0.11, 0.89) | -0.10(0.03, 0.97) |  |
| $2^{8}$ | 22 | nan(1.00, 0.00) | -0.86(0.25,0.75) | -0.45(0.11, 0.89) | 0.18(0.03, 0.97) |  |
| $2^{9}$ | 23 | nan(1.00, 0.00) | -0.40(0.25, 0.75) | 0.05(0.12, 0.88) | -2.46(0.03, 0.97) |  |
$10^{6}$ | $2^{10}$ | 24 | nan(1.00, 0.00) | 1.47(0.25, 0.75) | 1.47(0.12, 0.88) | 2.09(0.03, 0.97) |  |

##  Appendix A2 Details on calculations involving quantum chemistry matrices

###  A2.1 $A$ matrix and $\vec{b}$ vector generation

We begin by explaining the procedure for generating the $A$ matrix of size
$n$. We use the configuration state function-based Graphical Unitary Group
Approach-Configuration Interaction Singles and Doubles (GUGA-CISD) method
available in the GAMESS program [26] to construct the Hamiltonian for a given
molecule in a specified single particle basis. GUGA-CI ensures that the
Hamiltonian is constructed in an orthogonal basis; hence, it is Hermitian.
Also, because it is a spin-adapted CI method, it avoids spin contamination of
the wave function, thereby giving accurate results. We remove the first row
and the first column of the GUGA-CISD Hamiltonian matrix and subtract the
diagonal entries of the resulting matrix with the energy obtained from Møller-
Plesset theory to second order in perturbation (also called MP2 in
literature). The latter step is carried out for the purpose of normal
ordering, which in turn ensures that HHL would output the correlation part of
the ground state energy directly instead of the total ground state energy
(which can be written as a sum of the Hartree-Fock (HF) energy and the
correlation energy, with the latter being much lesser than the former). This
is desirable when one executes HHL-LCC calculations on NISQ era quantum
hardware, as the error in the total ground state energy can be much greater
than the correlation energy itself. We also note that unlike the traditional
approach where the HF energy is subtracted from the diagonal entries, we take
away the MP2 energy, in order to make sure that $A$ is positive definite. In a
sense, subtracting MP2 energy could be thought of as a level shift over and
beyond subtracting the HF energy.

We now focus our attention on the elements of the $A$ matrix. The size of an
$A$ matrix, $m$, generated from a quantum chemical calculation, which we can
denote as $A_{mol}$, is not necessarily of the dimension $n\times n$. In such
cases, we embed the $A_{mol}$ matrix of dimension ${m\times m}$ as a diagonal
block in a larger matrix of dimension $n\times n$, with the other diagonal
block being an identity matrix of size $(n-m)\times(n-m)$, denoted as
$\mathcal{I}$. In such a case, we solve a system of linear equations given by

$\displaystyle A=\begin{bmatrix}A_{mol}&0\\\
0&\mathcal{I}\end{bmatrix}\begin{bmatrix}\vec{b}\\\
0\end{bmatrix}=\begin{bmatrix}\vec{x}\\\ 0\end{bmatrix}.$ (A25)

This approach ensures that the eigenvalues of $A_{mol}$ remain unaffected, as
long as its maximum eigenvalue is $\approx$ 1\. We choose our matrices
carefully so that this condition is satisfied. In the event that the maximum
diagonal entry of $A$ is less than 1, it is recommended to pad with the
largest (or the smallest) diagonal entry of $A$ so that the number of shots
expended is reduced. As an example, we picked a $3\times 3$ sparse matrix such
that the largest diagonal entry is 0.70: $\begin{pmatrix}0.25&0.10&0.00\\\
0.10&0.45&0.20\\\ 0.00&0.20&0.70\end{pmatrix}$, and considered two cases:
padding with 1 and with 0.70. We found that kappa is larger in the latter
(5.16) than in the former (4.21).

Since for the problems we consider, $\mathcal{\kappa}$ increases with system
size monotonically, and further, going from an unpadded to a padded matrix
always right shifts a data point, it is sufficient to carry out
$\mathcal{\kappa}$ versus $m$ analysis for the unpadded case, as it upper
bounds the complexity of the padded scenario of $\mathcal{\kappa}$ versus $n$.

---
(a)
(b)
(c)
Figure A9: Sub-figure (a) shows the increase in system size with number of
virtuals, $n_{v}$, for RbH and CsH molecules in the LCCSD approximation, while
the sub-figures (b) and (c) show that the $A$ matrix increases as
$n_{o}^{2}n_{v}^{2}$ for both cases, as one would expect.

###  A2.2 Orbital character analysis

We now explain the procedure that we adopted for selecting orbitals, based on
orbital character. We begin with RbH, and then proceed to explain our
procedure for CsH (with accompanying data provided in Table A9).

We fix the number of core orbitals to 13. We now describe the method adopted
in choosing virtual molecular orbitals (MOs). Instead of taking the approach
of ordering the virtual MOs by energy in ascending order and then imposing an
energy cut-off to define our active space, we pick those MOs that are
dominated by important atomic orbitals (AOs). We select the important AOs, and
for the purposes of this work, we pick those AOs in the order of the principal
quantum numbers. For example, in the case of RbH, we can decide the important
AOs from the set that arise from our choice of basis, namely the Sapporo
double zeta basis: $5s$ through $7p$. For the purposes of our analysis on
condition number versus system size, we pick all the AOs that the basis allows
in order to obtain more data points for fitting (details given in Table A9).
We now move to some specifics for RbH: for the smallest system size considered
(1 virtual MO), we pick the first virtual from our sorted MO list, which is
the MO dominated by the Rb $5s-5p_{z}$ hybrid, and thus our active space that
is built out of 13 occupied MOs and 1 virtual one has a system size, $m$, of
$40\times 40$, and subsequently upon padding, an $A$ matrix size, $n$, of
$64\times 64$. For the next system size, we add the next MO in the sorted
list, which is dominated by Rb $5p_{y}$, leading to a $119\times 119$ matrix,
which, after padding, becomes a matrix of size $128\times 128$. We continue to
construct $A$ matrices in this fashion until we reach $m=9065$, for which
$\mathcal{\kappa}$ is about 348.

For the case of CsH molecule, we fix the number of occupied orbitals to 18
while progressively increasing the number of valence orbitals. The order in
which we add virtual MOs as well as each such virtual MO’s details are
mentioned in Table A9.

|
---|---
(a) | (b)
Figure A10: Plots showing the increase in $\mathcal{\kappa}$ with $A_{mol}$ matrix size, denoted as $m$, for the RbH molecule (sub-figure (a)) and the CsH molecule (sub-figures (b)) in the Sapporo double zeta basis set. The system size is determined by increase in number of virtuals.  |
---|---
(a) | (b)
Figure A11: Plots showing the increase in sparsity, s, with $A$ matrix size, $m$, for the RbH (sub-figure (a)) and the CsH (sub-figure (b)) molecules in the Sapporo double zeta basis set. The system size is determined by increase in number of virtuals.  Table A9: Table providing the data for condition number ($\mathcal{\kappa}$) of the $n\times n$ $A$ matrix versus system size ($n$), for RbH and CsH molecules, where we vary the virtual orbitals to increase $n$. In the table, $n_{o}$ the number of active spin orbitals, and $n_{v}$ the number of unoccupied spin orbitals. The first row of the column, ‘MO character’, gives information on the atomic orbitals that contribute dominantly to the considered virtual molecular orbital for $m=40$ case, whereas the second row gives the same information about the second virtual added to the active space for $m=119$ case, and so on. The last column specifies the corresponding newly added virtual’s energy in units of Hartree.  Molecule | $m$ | $\mathcal{\kappa}(n_{o},n_{v})$ | MO character | Virtual orbital energy (in Hartree)
---|---|---|---|---
RbH | 40 | 152.23 (13, 1) | Rb $5s-5p_{z}$ hybrid | -0.02
119 | 152.91 (13, 2) | Rb $5p_{y}$ | 0.04
228 | 153.18 (13, 3) | Rb $5p_{x}$ | 0.04
407 | 157.92 (13, 4) | Rb $5s-5p_{z}$ hybrid | 0.08
889 | 192.30 (13, 6) | Rb $4d_{x^{2}-y^{2}}$, Rb $4d_{xy}$ | 0.57, 0.57
1863 | 195.79 (13, 9) | Rb $4d_{xz}$, Rb $4d_{yz}$, Rb $4d_{z^{2}}$ | 0.57, 0.57
3866 | 228.12 (13, 13) | Rb $6s$, Rb $6p_{x}$, Rb $6p_{y}$, Rb $6p_{z}$ | 0.57, 0.06, 0.42, 0.42
4518 | 235.94 (13, 14) | Rb $7s$ | 0.44
5225 | 312.02 (13, 15) | H $2s$ | 0.83
5896 | 336.53 (13, 16) | H $2p_{y}$ | 0.87
6595 | 338.98 (13, 17) | H $2p_{x}$ | 1.69
7441 | 345.62 (13, 18) | H $2p_{z}$ | 1.69
| 8238 | 346.55 (13, 19) | Rb $7p_{y}$ | 1.71
| 9065 | 347.49 (13, 21) | Rb $7p_{x}$, Rb $7p_{z}$ | 2.12, 2.14
CsH | 67 | 465.89 (18, 1) | Cs $6p_{x}$ | 0.42
210 | 466.59 (18, 2) | Cs $6p_{y}$ | 0.42
417 | 467.08 (18, 3) | Cs $6p_{z}$ | 0.48
744 | 487.04 (18, 4) | Cs $6s$ | 1.49
1171 | 541.58 (18, 5) | Cs $8s$ | 0.01
1698 | 546.70 (18, 6) | Cs $7p_{y}$ | 0.05
2175 | 551.19(18, 7) | Cs $7p_{x}$ | 0.05
2802 | 573.09(18, 8) | Cs $7s$ | 0.08
3493 | 593.31(18, 9) | Cs $5d_{y^{2}}$ | 0.38
4344 | 640.22 (18, 10) | Cs $5d_{xy}$ | 0.38
5215 | 646.10 (18, 11) | Cs $5d_{xz}$ | 0.39
6150 | 652.10 (18, 12) | Cs $5d_{yz}$ | 0.39
7261 | 714.59 (18, 13) | Cs $5d_{z^{2}}$ | 0.39
8473 | 956.37 (18, 14) | H $2s$ | 0.93
9784 | 974.45 (18, 15) | H $2p_{x}$ | 1.70
11058 | 1003.49 (18, 16) | H $2p_{y}$ | 1.70
Table A10: Table providing the minimum and maximum eigenvalues of the matrix $A_{mol}$, denoted in the table as $\lambda_{\mathrm{min}}^{\mathrm{A_{mol}}}$ and $\lambda_{\mathrm{max}}^{\mathrm{A_{mol}}}$, for RbH and CsH systems. The energies are in units of milli-Hartree.  Molecule | $m$ | $\lambda_{\mathrm{min}}^{\mathrm{A_{mol}}}$ | $\lambda_{\mathrm{max}}^{\mathrm{A_{mol}}}$ |
---|---|---|---|---
RbH | 40 | 135.31 | 20599.95 |
119 | 135.18 | 20670.59 |
228 | 135.04 | 20685.98 |
407 | 131.94 | 20837.37 |
889 | 109.40 | 21038.25 |
1863 | 107.55 | 21058.36 |
3866 | 92.36 | 21071.00 |
4518 | 90.25 | 21294.40 |
5225 | 72.72 | 22690.04 |
5896 | 72.32 | 24341.29 |
6595 | 71.93 | 24386.59 |
7441 | 71.46 | 24701.91 |
8238 | 71.27 | 24702.28 |
| 9065 | 71.09 | 24702.65 |
CsH | 67 | 128.09 | 59680.83 |
210 | 127.99 | 59722.33 |
417 | 127.90 | 59737.34 |
744 | 122.88 | 59847.85 |
1171 | 110.54 | 59867.65 |
1698 | 109.50 | 59867.64 |
2175 | 108.61 | 59867.63 |
2803 | 104.46 | 59867.67 |
3493 | 100.89 | 59867.69 |
4345 | 93.60 | 59916.79 |
5215 | 92.75 | 59929.31 |
6150 | 91.91 | 59939.41 |
7262 | 83.88 | 59948.78 |
8473 | 64.56 | 61759.13 |
9784 | 63.38 | 61761.97 |
11058 | 63.22 | 63448.99 |
Table A11: Average PFDs and Range of PFDs of HHL and Psi-HHL for Li2, RbH and
CsH molecules resp. in STO-6G, Sapporo-DZP and Sapporo-DKH3-DZP-2012 basis
sets. The PFDs are calculated over a range of 5 repetitions.

| Li2 | RbH | CsH
---|---|---|---
# shots | HHL(PFD, Range) | Psi-HHL(PFD, Range) | HHL(PFD, Range) | Psi-HHL(Range) | HHL(PFD, Range) | Psi-HHL(PFD, Range)
$5\times 10^{2}$ | (-7.68, 40.22) | (-2.79, 29.58) |  |  |  |
$10^{3}$ | (-4.08, 19.80) | (-1.46, 8.34) | (1.15, 30.41) | (2.51, 25.93) | (-3.76, 55.34) | (0.49, 23.56)
$5\times 10^{3}$ | (-2.94, 8.89) | (-2.11, 7.57) |  |  |  |
$10^{4}$ | (-0.58, 6.00) | (1.07, 4.47) | (3.64, 25.05) | (-0.42, 6.18) | (-11.83, 9.82) | (2.24, 4.22)
$5\times 10^{4}$ |  |  | (3.29, 16.90) | (1.92, 3.14) | (-12.38, 2.04) | (1.63, 4.77)
$10^{5}$ |  |  | (5.77, 4.03) | (0.60, 1.79) | (-11.74, 2.49) | (-0.06, 2.29)
$5\times 10^{5}$ |  |  | (5.29, 0.76) | (0.99, 0.71) | (-10.49, 2.29) | (0.38, 1.77)
$10^{6}$ |  |  | (5.46, 0.72) | (1.07, 0.56) | (-10.92, 2.01) | (0.56, 1.05)