$\rho_{3}={\mathcal{M}}_{q_{0},q_{1}}{\left(\rho_{2}\right)}$, and where the
qCCS-choice $\mathsf{D}{\left(q_{0},q_{1};x;x!a\mathsf{.}\mathsf{nil}\right)}$
is given by

$\displaystyle\mathsf{D}{\left(q_{0},q_{1};x;x!a\mathsf{.}\mathsf{nil}\right)}={}$
$\displaystyle\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{0}[q_{0},q_{1}]})\neq
0\mathsf{\ then\
}\mathcal{E}_{0}[q_{0},q_{1}]\mathsf{.}\left(\left(x!a\mathsf{.}\mathsf{nil}\right)\\{0/x\\}\right)\
+$ $\displaystyle\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{1}[q_{0},q_{1}]})\neq
0\mathsf{\ then\
}\mathcal{E}_{1}[q_{0},q_{1}]\mathsf{.}\left(\left(x!a\mathsf{.}\mathsf{nil}\right)\\{1/x\\}\right)\
+$ $\displaystyle\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{2}[q_{0},q_{1}]})\neq
0\mathsf{\ then\
}\mathcal{E}_{2}[q_{0},q_{1}]\mathsf{.}\left(\left(x!a\mathsf{.}\mathsf{nil}\right)\\{2/x\\}\right)\
+$ $\displaystyle\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{3}[q_{0},q_{1}]})\neq
0\mathsf{\ then\
}\mathcal{E}_{3}[q_{0},q_{1}]\mathsf{.}\left(\left(x!a\mathsf{.}\mathsf{nil}\right)\\{3/x\\}\right).$

To emulate the behaviour of $S$ we choose again the first branch within
$\mathsf{D}{\left(q_{0},q_{1};x;x!a\mathsf{.}\mathsf{nil}\right)}$.

$\displaystyle T^{*}$
$\displaystyle{\left\langle\left(0!a\mathsf{.}\mathsf{nil}\right)\parallel\llbracket\mathit{Bob}\left(q_{2},0,1,2,3\right)\rrbracket,\rho_{4}\right\rangle}$
$\displaystyle{\left\langle\mathsf{nil}\parallel\left(\mathcal{I}[q_{2}]\mathsf{.}\checkmark\right)\parallel\left(1?y\mathsf{.}\mathcal{X}[q_{2}]\mathsf{.}\checkmark\right)\parallel\left(2?y\mathsf{.}\mathcal{Z}[q_{2}]\mathsf{.}\checkmark\right)\parallel\left(3?y\mathsf{.}\mathcal{Y}[q_{2}]\mathsf{.}\checkmark\right),\rho_{4}\right\rangle}$
$\displaystyle{\left\langle\mathsf{nil}\parallel\checkmark\parallel\left(1?y\mathsf{.}\mathcal{X}[q_{2}]\mathsf{.}\checkmark\right)\parallel\left(2?y\mathsf{.}\mathcal{Z}[q_{2}]\mathsf{.}\checkmark\right)\parallel\left(3?y\mathsf{.}\mathcal{Y}[q_{2}]\mathsf{.}\checkmark\right),\rho_{4}\right\rangle},$

with $\rho_{4}={\mathcal{E}}_{0,q_{0},q_{1}}{\left(\rho_{3}\right)}$. ∎

##  6\. Separating Quantum Based Systems

Since super-operators are more expressive than unitary transformations, an
encoding from qCCS into CQP is more difficult.

Consider the following super-operator inspired by an operator for amplitude-
damping ${\mathcal{Q}}_{q}{\left(\rho\right)}=\begin{pmatrix}1&0\\\
0&\sqrt{1+p}\end{pmatrix}\rho\begin{pmatrix}1&0\\\
0&\sqrt{1+p}\end{pmatrix}-\begin{pmatrix}0&\sqrt{p}\\\
0&0\end{pmatrix}\rho\begin{pmatrix}0&0\\\ \sqrt{p}&0\end{pmatrix}$, where $p$
is a probability. With $p=1$ we obtain
${\mathcal{Q}}_{q}{\left(\rho\right)}=\begin{pmatrix}\rho_{00}-\rho_{11}&\sqrt{2}\rho_{01}\\\
\sqrt{2}\rho_{10}&2\rho_{11}\end{pmatrix}$ that sometimes behaves as identity,
i.e., ${\mathcal{Q}}_{q}{\left(|0\rangle\langle 0|\right)}=|0\rangle\langle
0|$, and sometimes changes the qubit, e.g.
${\mathcal{Q}}_{q}{\left(|1\rangle\langle 1|\right)}=\begin{pmatrix}-1&0\\\
0&2\end{pmatrix}$,
${\mathcal{Q}}_{q}{\left(|+\rangle\langle+|\right)}=\begin{pmatrix}0&\frac{\sqrt{2}}{2}\\\
\frac{\sqrt{2}}{2}&1\end{pmatrix}$, and
${\mathcal{Q}}_{q}{\left(|-\rangle\langle-|\right)}=\begin{pmatrix}0&-\frac{\sqrt{2}}{2}\\\
-\frac{\sqrt{2}}{2}&1\end{pmatrix}$. To observe this strange behaviour of
$\mathcal{Q}[q]$, we measure the resulting qubit using the qCCS-configuration

$\displaystyle\mathsf{S_{ce}}{\left(\rho\right)}$
$\displaystyle={\left\langle\mathcal{Q}[q]\mathsf{.}\mathsf{if\
}\mathsf{tr}({\mathcal{E}_{0}[q]})\neq 0\mathsf{\ then\
}\tau.\checkmark+\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{1}[q]})\neq 0\mathsf{\
then\ }\tau.\mathsf{nil},\rho\right\rangle}$

for the 1-qubit system $\rho=q$, where the choice allows to unguard success if
$0$ can be measured. We observe that $\mathsf{S_{ce}}{\left(|0\rangle\langle
0|\right)}$ must reach success, $\mathsf{S_{ce}}{\left(|1\rangle\langle
1|\right)}$ may but not must reach success, and
$\mathsf{S_{ce}}{\left(|+\rangle\langle+|\right)}$ as well as
$\mathsf{S_{ce}}{\left(|-\rangle\langle-|\right)}$ cannot reach success. ∎

An encoding from qCCS into CQP needs to emulate the behaviour of
$\mathcal{Q}[q]$. Since CQP does not allow for super-operators but only
unitary transformations and since there is no unitary transformation with the
same effect as $\mathcal{Q}[q]$, there is no good encoding from qCCS into CQP
(or CQP-). To prove this separation result we borrow a technical result from
[PNG13]. By success sensitiveness, a source term $S$ reaches success if and
only if its literal translation $\llbracket S\rrbracket$ reaches success. As a
consequence $S$ cannot reach success if and only if $\llbracket S\rrbracket$
cannot reach success. The next lemma shows that operational correspondence and
success sensitiveness also imply that $S$ must reach success, i.e., reaches
success in all finite traces, if and only if $\llbracket S\rrbracket$ must
reach success.

######  Lemma 11.

For all operationally corresponding and success sensitive encodings
$\llbracket\cdot\rrbracket$ w.r.t. some success respecting preorder $\preceq$
on the target and for all source configurations $S$, $S$ must reach success in
all finite traces iff $\llbracket S\rrbracket$ must reach success in all
finite traces.

######  Proof 6.1.

We consider both directions separately.

if $S$ must reach success then also $\llbracket S\rrbracket$:

Assume the opposite, i.e., there is an encoding that satisfies the criteria
operational soundness and success sensitiveness, $\preceq$ is success
respecting, and there is some source configuration $S$ such that for all
$S^{\prime}$ with $S\Longmapsto S^{\prime}$ we have
${S^{\prime}}{\Downarrow_{\checkmark}}$, i.e., $S$ must reach success in all
finite traces, but there is some target configuration $T$ such that
$\llbracket S\rrbracket\Longmapsto T$ and $T$ cannot reach success.

Since $\llbracket\cdot\rrbracket$ is operationally sound, $\llbracket
S\rrbracket\Longmapsto T$ implies that there exist some
$S^{\prime\prime},T^{\prime\prime}$ such that $S\Longmapsto S^{\prime\prime}$,
$T\Longmapsto T^{\prime\prime}$, and $\llbracket
S^{\prime\prime}\rrbracket\preceq T^{\prime\prime}$. Since $T$ cannot reach
success and $T\Longmapsto T^{\prime\prime}$, then $T^{\prime\prime}$ cannot
reach success. Since $\preceq$ respects success, $\llbracket
S^{\prime\prime}\rrbracket\preceq T^{\prime\prime}$ and that
$T^{\prime\prime}$ cannot reach success imply that $\llbracket
S^{\prime\prime}\rrbracket$ cannot reach success. Because
$\llbracket\cdot\rrbracket$ is success sensitive, then also $S^{\prime\prime}$
cannot reach success, which contradicts the assumption that $S$ must reach
success. We conclude that if $S$ must reach success in all finite traces then
$\llbracket S\rrbracket$ must reach success in all finite traces.

if $\llbracket S\rrbracket$ must reach success then also $S$:

Assume the opposite, i.e., there is an encoding that satisfies the criteria
operational completeness and success sensitiveness, $\preceq$ is success
respecting, and there is some source configuration $S$ such that for all $T$
with $\llbracket S\rrbracket\Longmapsto T$ we have
${T}{\Downarrow_{\checkmark}}$, i.e., $\llbracket S\rrbracket$ must reach
success in all finite traces, but there is some source configuration
$S^{\prime}$ such that $S\Longmapsto S^{\prime}$ and $S^{\prime}$ cannot reach
success.

Since $\llbracket\cdot\rrbracket$ is operationally complete, $S\Longmapsto
S^{\prime}$ implies that there exists some $T^{\prime}$ such that $\llbracket
S\rrbracket\Longmapsto T^{\prime}$ and $\llbracket S^{\prime}\rrbracket\preceq
T^{\prime}$. Because $\llbracket\cdot\rrbracket$ is success sensitive and
$S^{\prime}$ cannot reach success, then also $\llbracket S^{\prime}\rrbracket$
cannot reach success. Since $\preceq$ respects success, $\llbracket
S^{\prime}\rrbracket\preceq T^{\prime}$ and that $\llbracket
S^{\prime}\rrbracket$ cannot reach success imply that $T^{\prime}$ cannot
reach success. Since $T^{\prime}$ cannot reach success and $\llbracket
S\rrbracket\Longmapsto T^{\prime}$, this contradicts the assumption that
$\llbracket S\rrbracket$ must reach success. We conclude that if $\llbracket
S\rrbracket$ must reach success in all finite traces then $S$ must reach
success in all finite traces.

To prove the non-existence of an encoding from qCCS into CQP we use
$\mathcal{Q}[q]$ as a counterexample and show that it is not possible in CQP
to emulate the behaviour of $\mathcal{Q}[q]$ modulo compositionality,
operational correspondence, and success sensitiveness. More precisely, since
there is no unitary transformation with this behaviour and also measurement or
additional qubits do not help to emulate this behaviour on the state of the
qubit (see the proof of Theorem 12), there is no encoding from qCCS into CQP
that satisfies compositionality, operational correspondence, and success
sensitiveness. To capture the behaviour of $\mathcal{Q}[q]$, we use Example 6
as a counterexample. Note that we reason here about CQP instead of CQP-, since
even the full expressive power of CQP does not help to correctly emulate this
super-operator.

######  Theorem 12.

There is no encoding from qCCS into CQP that satisfies compositionality,
operational correspondence, and success sensitiveness.

######  Proof 6.2.

The proof is by contradiction, i.e., we assume that there is an encoding
$\llbracket\cdot\rrbracket$ from qCCS into CQP that satisfies
compositionality, operational correspondence, and success sensitiveness. In
qCCS we start with a configuration that contains a single qubit (represented
as a density matrix in $\rho$). The encoding translates this qCCS-
configuration into a CQP-configuration such that its state is captured in a
vector $\sigma$. The encoding may use the qubit inside $\rho$ directly for
$\sigma$, or it may measure this qubit and uses the information gained in this
measurement to construct $\sigma$. Remember that it is impossible to determine
the exact state of the qubit and hence the entries for the density matrix.
Using the original qubit directly results in a 1-qubit vector $\sigma$. From
measuring the original qubit we cannot gain more than one bit information such
that we again capture all the information in a 1-qubit vector $\sigma$. In
other words, we can assume that the encoding translates a 1-qubit density
matrix $\rho$ into a 1-qubit vector $\sigma$, because there is no more
information available to justify the use of more qubits in CQP, i.e., systems
with more qubits won’t provide more information.

By compositionality, then there is a CQP-context
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ such that

$\displaystyle\llbracket{\left\langle\mathsf{if\
}\mathsf{tr}({\mathcal{E}_{0}[q]})\neq 0\mathsf{\ then\
}\tau.\mathsf{nil}+\mathsf{if\ }\mathsf{tr}({\mathcal{E}_{1}[q]})\neq
0\mathsf{\ then\ }\tau.\checkmark,\rho\right\rangle}\rrbracket$
$\displaystyle={\left(\sigma;\phi_{\mathcal{M}};T_{\mathcal{M}}\right)}\text{
and}$ $\displaystyle\llbracket\mathsf{S_{ce}}{\left(\rho\right)}\rrbracket$
$\displaystyle={\left(\sigma;\phi_{1};\mathcal{C}_{\mathcal{Q}}\\!\left(T_{\mathcal{M}}\right)\right)},$

where $\sigma$ is the translation of $\rho$. Since the qCCS-configurations in
the source are parametric on $\rho$, the behaviour of the resulting CQP-
configurations depends on $\sigma$. By operational correspondence and success
sensitiveness, these contexts have to behave exactly as their respective
sources w.r.t. the reachability of success (including the reachability of
success in all finite traces as in Lemma 11). Since the behaviour of the
translations depends only on $\sigma$ as input, we can focus in the
translation of $\mathcal{Q}[q]$ on the quantum register $\sigma$ that
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ constructs from the input
$\rho$. In CQP as well as CQP- the only operators with direct influence on the
quantum register are unitary transformations, measurement, and the creation of
new qubits. Moreover, e.g. by communication or the probability distributions
after measurement CQP-configurations can introduce branching and thus provide
different results on different branches.

With the creation of new qubits the size of the vector is increased.
Intuitively, $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ gets as input
a 1-qubit vector and has to produce another 1-qubit vector as output, because
$T_{\mathcal{M}}$ and $\mathcal{C}_{\mathsf{H}}\\!\left([\cdot]\right)$
require a 1-qubit vector. Because of that, the creation of new qubits can only
contribute to $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ by allowing
to set a qubit to $|0\rangle$. Since this can also be done by measurement
followed by a bit-flip if 1 was measured, we do not need to consider the
creation of new qubits, i.e., this behaviour is subsumed by the other
operations.

Note that we consider 1-bit vectors. Measuring one qubit in CQP creates a
probability distribution with two cases that consist of their respective
probability, which can be zero, followed by the configuration in the
respective case. The overall evolution of closed systems—and CQP can express
only closed systems—can be described by a unitary transformation. Accordingly,
for the way in that $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$
manipulates the 1-qubit vector the only relevant effect of measurement is (1)
that it creates branches, (2) that some of these branches might have a zero-
probability w.r.t. particular inputs but not necessarily all inputs, and (3)
that the evolution of the 1-qubit vector in every of these branches is
described by a unitary transformation, at least if we consider as inputs only
the base values $|0\rangle\langle 0|,|1\rangle\langle
1|,|+\rangle\langle+|,|-\rangle\langle-|$.

There are two sources for branching: either branching results from the
probability distribution after measurement or from communication. Since the
matrix multiplication of two unitary transformations is again a unitary
transformation, sequences of unitary transformations can be abbreviated by a
single unitary transformation. Accordingly, if we consider a single branch in
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ from the beginning to the
end, the transformation on the 1-qubit vector can be abbreviated by a single
unitary transformation $\begin{pmatrix}\alpha&\beta\\\
\gamma&\delta\end{pmatrix}$.

Assume that all branches in $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$
result from communication, i.e.,
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ does not use measurement.
Then for every branch there is a unitary transformation
$\begin{pmatrix}\alpha&\beta\\\ \gamma&\delta\end{pmatrix}$ that emulates
$\mathcal{Q}[q]$ in this branch. Considering the behaviour of
$\mathsf{S_{ce}}{\left(|0\rangle\langle 0|\right)}$ it follows

$\displaystyle\begin{pmatrix}\alpha&\beta\\\
\gamma&\delta\end{pmatrix}\begin{pmatrix}1\\\
0\end{pmatrix}=\begin{pmatrix}1\\\ 0\end{pmatrix}\text{ and therefore
}\alpha=1\text{ and }\gamma=0$ (1)

for all branches, because $\begin{pmatrix}1\\\ 0\end{pmatrix}$ is the only
state such that $T_{\mathcal{M}}$ applied to this state always unguards
$\checkmark$ and $\mathsf{S_{ce}}{\left(|0\rangle\langle 0|\right)}$ must
reach success. With (1) and from the behaviour of
$\mathsf{S_{ce}}{\left(|+\rangle\langle+|\right)}$, we learn that

$\displaystyle\begin{pmatrix}\alpha&\beta\\\
\gamma&\delta\end{pmatrix}=\begin{pmatrix}1&\beta\\\
0&\delta\end{pmatrix}\dfrac{1}{\sqrt{2}}\begin{pmatrix}1\\\
1\end{pmatrix}=\begin{pmatrix}0\\\ 1\end{pmatrix}\text{ and therefore
}\beta=-1\text{ and }\delta=\sqrt{2}$ (2)

for all branches, because $\begin{pmatrix}0\\\ 1\end{pmatrix}$ is the only
state such that $T_{\mathcal{M}}$ applied to this state never unguards
$\checkmark$ and $\mathsf{S_{ce}}{\left(|+\rangle\langle+|\right)}$ cannot
reach success. Finally, with (1), (2),
$\mathsf{S_{ce2}}{\left(|-\rangle\langle-|\right)}$, and since there is no
measurement in $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$, we obtain

$\displaystyle\begin{pmatrix}\alpha&\beta\\\
\gamma&\delta\end{pmatrix}=\begin{pmatrix}1&-1\\\
0&\sqrt{2}\end{pmatrix}\dfrac{1}{\sqrt{2}}\begin{pmatrix}1\\\
-1\end{pmatrix}=\begin{pmatrix}\dfrac{2}{\sqrt{2}}\\\ -1\end{pmatrix}\text{
and therefore
}{\left(\left|\dfrac{2}{\sqrt{2}}\right|\right)}^{2}+{\left(\left|-1\right|\right)}^{2}\neq
1$ (3)

This is a contradiction. Therefore, our assumption that all branches in
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ result from communication
must be wrong, i.e., $\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$
measures the qubit such that there are two branches that depend on
probabilities.

If there is one branch with non-zero probability for all the inputs that
result from the translations of $|0\rangle\langle
0|,|+\rangle\langle+|,|-\rangle\langle-|$, then we derive again the
contradiction in (3). Considering $|0\rangle$ and $|+\rangle$, we observe that
these two values are classic values w.r.t. orthogonal bases. Note that when
measuring such values (regardless of which basis we measure against), we
cannot avoid that one of the resulting branches has non-zero probability for
both inputs. Hence, to avoid the contradiction in (3), the measurement in
$\mathcal{C}_{\mathcal{Q}}\\!\left([\cdot]\right)$ has to ensure that there is
no branch with non-zero probability for the inputs that correspond to the
translations of $|+\rangle\langle+|$ and $|-\rangle\langle-|$. We cannot avoid
that there is a branch with non-zero probability for inputs that correspond to
the translations of $|+\rangle\langle+|$ and $|0\rangle\langle 0|$ or
$|-\rangle\langle-|$ and $|0\rangle\langle 0|$. Let us consider the case of a
branch with non-zero probability for the inputs that result from the
translations of $|+\rangle\langle+|$ and $|0\rangle\langle 0|$ and let the
unitary transformation in this case be $\begin{pmatrix}\alpha_{+}&\beta_{+}\\\
\gamma_{+}&\delta_{+}\end{pmatrix}$. By repeating the above argumentation for
(1) we obtain

$\displaystyle\begin{pmatrix}\alpha_{+}&\beta_{+}\\\
\gamma_{+}&\delta_{+}\end{pmatrix}\begin{pmatrix}1\\\
0\end{pmatrix}=\begin{pmatrix}1\\\ 0\end{pmatrix}\text{ and therefore
}\alpha_{+}=1\text{ and }\gamma_{+}=0.$ (4)

Similarly, we repeat the argumentation of (2) and obtain

$\displaystyle\begin{pmatrix}\alpha_{+}&\beta_{+}\\\
\gamma_{+}&\delta_{+}\end{pmatrix}=\begin{pmatrix}1&\beta_{+}\\\
0&\delta_{+}\end{pmatrix}\dfrac{1}{\sqrt{2}}\begin{pmatrix}1\\\
1\end{pmatrix}=\begin{pmatrix}0\\\ 1\end{pmatrix}\text{ and therefore
}\beta_{+}=-1\text{ and }\delta_{+}=\sqrt{2}.$ (5)

Since there is only a singe qubit, only the first measurement (of this qubit)
will result in branches such for different inputs we get zero as well as non-
zero probabilities. In every branch after the first measurement, every
consecutive measurement is not depending on the input any more but only on the
value measured in the first measurement. Because of that, for the input that
results from the translation of $|1\rangle\langle 1|$ the branch we consider,
i.e., the branch with the unitary transformation
$\begin{pmatrix}\alpha_{+}&\beta_{+}\\\ \gamma_{+}&\delta_{+}\end{pmatrix}$,
has a non-zero probability. With (4), (5), and
$\mathsf{S_{ce2}}{\left(|1\rangle\langle 1|\right)}$, we conclude

$\displaystyle\begin{pmatrix}\alpha_{+}&\beta_{+}\\\
\gamma_{+}&\delta_{+}\end{pmatrix}=\begin{pmatrix}1&-1\\\
0&\sqrt{2}\end{pmatrix}\begin{pmatrix}0\\\ 1\end{pmatrix}=\begin{pmatrix}-1\\\
\sqrt{2}\end{pmatrix}\text{ and therefore
}{\left(\left|-1\right|\right)}^{2}+{\left(\left|\sqrt{2}\right|\right)}^{2}\neq
1$

This is again a contradiction. Accordingly, our original assumption, i.e.,
that there is an encoding $\llbracket\cdot\rrbracket$ from qCCS into CQP that
satisfies compositionality, operational correspondence, and success
sensitiveness is wrong: there is no such encoding.

##  7\. Quality Criteria for Quantum Based Systems

Sections 5 and 6 show that the quality criteria of Gorla in [Gor10] can be
applied to quantum based systems and are still meaningful in this setting.
They might, however, not be exhaustive, i.e., there might be aspects of
quantum based systems that are relevant but not sufficiently covered by this
set of criteria. To obtain these criteria, Gorla studied a large number of
encodings, i.e., this set of criteria was built upon the experience of many
researchers and years of work. Accordingly, we do not expect to answer the
question ’what are good quality criteria for quantum based systems’ now, but
rather want to start the discussion.

A closer look at the criteria in Section 4 reveals a first candidate for an
additional quality criterion. Name invariance ensures that encodings cannot
cheat by treating names differently. It requires that good encodings preserve
substitutions to some extend. CQP and qCCS model the dynamics of quantum
registers in fundamentally different ways, but both languages address qubits
by qubit names. It seems natural to extend name invariance to also cover qubit
names.

As in [Gor10], we let our definition of qubit invariance depend on a renaming
policy $\varphi$, where this renaming policy is for qubit names. The renaming
policy translates qubit names of the source to tuples of qubit names in the
target, i.e., $\varphi:\mathcal{V}\to\mathcal{V}^{n}$, where we require that
$\varphi(q)\cap\varphi(q^{\prime})=\emptyset$ whenever $q\neq q^{\prime}$.

The new criterion _qubit invariance_ , then requires that encodings preserve
and reflect substitutions on qubits modulo the renaming policy on qubits.

[Qubit Invariance] The encoding $\llbracket\cdot\rrbracket$ is _qubit
invariant_ if, for every $S\in\mathfrak{C}_{\mathsf{S}}$ and every
substitution $\gamma$ on qubit names, it holds that $\llbracket
S\gamma\rrbracket=\llbracket S\rrbracket\gamma^{\prime}$, where
$\varphi(\gamma(q))=\gamma^{\prime}(\varphi(q))$ for every $q\in\mathcal{V}$.

In [Gor10], name invariance allows the slightly weaker condition $\llbracket
S\gamma\rrbracket\preceq\llbracket S\rrbracket\gamma^{\prime}$ for non-
injective substitutions. In contrast, substitutions on qubits always have to
be injective such that they cannot violate the no-cloning principle. Since
$\llbracket\cdot\rrbracket$ translates qubit names to themselves and
introduces no other qubit names, it satisfies qubit invariance for $\varphi$
being the identity and $\gamma^{\prime}=\gamma$. The corresponding proof is
given above in Lemma 5.

Note that the qubits discussed so far are so-called _logical qubits_ , i.e.,
they are abstractions of the physical qubits. To implement a single _logical
qubit_ as of today several _physical qubits_ are necessary. These additional
physical qubits are used to ensure stability and fault-tolerance in the
implementation of logical qubits. Since the number of necessary physical
qubits can be much larger than the number of logical qubits, already a small
increase in the number of logical qubits might seriously limit the
practicability of a system. Accordingly, one may require that encodings
preserve the number of logical qubits.

[Size of Quantum Registers] An encoding $\llbracket\cdot\rrbracket$ _preserves
the size of quantum registers_ , if for all $S\in\mathfrak{C}_{\mathsf{S}}$,
the number of qubits in $\llbracket S\rrbracket$ is not greater than in $S$.

Again, the encoding $\llbracket\cdot\rrbracket$ in Definition 5 satisfies this
criterion, which can be verified easily by inspection of the encoding
function.

######  Lemma 13.

The encoding $\llbracket\cdot\rrbracket$ preserves the size of quantum
registers, i.e., for all $S\in\mathfrak{C}_{\mathsf{S}}$, the number of qubits
in $\llbracket S\rrbracket$ is not greater than in $S$.

######  Proof 7.1.

By Definition 5, the number of qubits in $\llbracket S\rrbracket$ is the same
as the number of qubits in $S$. Moreover, $\llbracket\cdot\rrbracket$ does not
introduce new qubits in any of its cases except as the encoding of the
creation of a new qubit in the source. Because of that, also the derivatives
of source term translations have the same number of qubits as their respective
source term equivalents. Thus, $\llbracket\cdot\rrbracket$ preserves the size
of quantum registers.

Similarly to success sensitiveness, requiring the preservation of the size of
quantum registers on literal encodings is not enough. To ensure that all
reachable target terms preserve the size of quantum registers, we again link
this criterion with the target term relation $\preceq$. More precisely, we
require that $\preceq$ is sensible to the size of quantum registers, i.e.,
$T_{1}\preceq T_{2}$ implies that the quantum registers in $T_{1}$ and $T_{2}$
have the same size. The correspondence simulation $\preceq$ that we used as
target relation for the encoding $\llbracket\cdot\rrbracket$ is not sensible
to the size of quantum registers, but we can easily turn it into such a
relation. Therefore, we simply add the condition that $|\rho|=|\sigma|$
whenever ${\left\langle P,\rho\right\rangle}\mathcal{R}{\left\langle
Q,\sigma\right\rangle}$ to Definition 4. Fortunately, all of the already shown
results remain valid for the altered version of $\preceq$.

In contrast to CQP-, the semantics of qCCS yields a non-probabilistic
transition system, where probabilities are captured in the density matrices.
The encoding $\llbracket\cdot\rrbracket$ translates probability distributions
into non-deterministic choices. Thereby, branches with zero probability are
correctly eliminated, but all remaining branches are treated similarly and
their probabilities are forgotten. To check also the probabilities of
branches, we can strengthen operational correspondence to a labelled variant,
where labels capture the probability of a step. The challenge here is to
create a meaningful criterion that correctly accumulates the probabilities in
sequences of steps as e.g. a single source term step might be translated into
a sequence of target term steps, but the product of the probabilities
contained in the sequence has to be equal to the probability of the single
source term step. We leave the derivation of a suitable probabilistic version
of operational correspondence to future work.

Another important aspect is in how far the quality criteria capture the
fundamental principles of quantum based systems such as the _no-cloning
principle_ : By the laws of quantum mechanics, it is not possible to exactly
copy a qubit. Technically, such a copying would require some form of
interaction with the qubit and this interaction would destroy its
superposition, i.e., alter its state. Interestingly, the criteria of Gorla are
even strong enough to observe a violation of this principle in the encoding
from CQP- into qCCS, i.e., if we allow CQP- to violate this principle but
require that qCCS respects it, then we obtain a negative result. Therefore, we
remove the type system from CQP-. Without this type system, we can use the
same qubit at different locations, violating the no-cloning principle. As an
example, consider $S={\left(\sigma;\phi;c\mathsf{!}[q]\mathsf{.}\mathbf{0}\mid
c\mathsf{!}[q]\mathsf{.}\mathbf{0}\right)}$. Then the encoding
$\llbracket\cdot\rrbracket$ in Definition 5 is not valid any more, because
$\llbracket S\rrbracket={\left\langle{\left(c!q\mathsf{.}\mathsf{nil}\parallel
c!q\mathsf{.}\mathsf{nil}\right)}\setminus\phi,\rho\right\rangle}$ violates
condition Cond2. Using $S$ as counterexample, it should be possible to show
that there exists no encoding that satisfies compositionality, operational
correspondence, and success sensitiveness.

Of course, even if we succeed with this proof, this does not imply that the
criteria are strong enough to sufficiently capture the no-cloning principle.
Indeed, the other direction is more interesting, i.e., criteria that rule out
encodings such that the source language respects the no-cloning principle but
not all literal translations or their derivatives respect it. We believe that
capturing the no-cloning principle and the other fundamental principles of
quantum based systems is an interesting research challenge.

##  8\. Conclusions

We proved that CQP- can be encoded by qCCS w.r.t. the quality criteria
compositionality, name invariance, operational correspondence, divergence
reflection, and success sensitiveness. Additionally, this encoding satisfies
two new, quantum specific criteria: it is invariant to qubit names and
preserves the size of quantum registers. We think that these new criteria are
relevant for translations between quantum based systems.

The encoding proves that the way in that qCCS treats qubits—using density
matrices and super-operators—can emulate the way in that CQP- treats qubits.
The other direction is more difficult. We showed that there exists no encoding
from qCCS into CQP that satisfies compositionality, operational
correspondence, and success sensitiveness.

The results themselves may not necessarily be very surprising. The unitary
transformations used in CQP-/CQP are a subset of the super-operators used in
qCCS and also density matrices can express more than the vectors used in
CQP-/CQP. What our case study proves is that the quality criteria that were
originally designed for classical systems are still meaningful in this quantum
based setting. They may, however, not be exhaustive. Accordingly, in Section 7
we start the discussion on quality criteria for this new setting of quantum
based systems. The first two candidate criteria that we propose, namely qubit
invariance and preservation of quantum register sizes, are relevant, but
rather basic. Since the semantics of quantum based systems is often
probabilistic, a variant of operational correspondence that requires the
preservation and reflection of probabilities in the respective traces might be
meaningful. Such a criterion would rule out the encoding
$\llbracket\cdot\rrbracket$ presented above. More difficult and thus also more
interesting are criteria that capture the fundamental principles of quantum
based systems such as the no-cloning principle. Hereby, we pose the task of
identifying such criteria as research challenge.

As, to the best of our knowledge, there are no well-accepted probabilistic
versions of operational correspondence. As a first step we will study
probabilistic versions of operational correspondence and the nature of the
relation between source and target they imply.

## References

  * [BBC+93] Charles H. Bennett, Gilles Brassard, Claude Crépeau, RichardJozsa, Asher Peres, and William K. Wootters.  Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels.  Physical Review Letters, 70:1895–1899, 1993.  doi:10.1103/PhysRevLett.70.1895.
  * [BNP20] Benjamin Bisping, Uwe Nestmann, and Kirstin Peters.  Coupled similarity: the first 32 years.  Acta Informatica, 57(3–5):439–463, 2020.  doi:10.1007/s00236-019-00356-4.
  * [dRMT+04] H. de Riedmatten, I. Marcikic, W. Tittel, H. Zbinden, D. Collins, and N. Gisin.  Long Distance Quantum Teleportation in a Quantum Relay Configuration.  Physical Review Letters, 92:047904, 2004.  doi:10.1103/PhysRevLett.92.047904.
  * [FDY12] Yuan Feng, Runyao Duan, and Mingsheng Ying.  Bisimulation for Quantum Processes.  ACM Transactions on Programming Languages and Systems, 34(4), 2012\.  doi:10.1145/2400676.2400680.
  * [Gay06] Simon J. Gay.  Quantum programming languages: survey and bibliography.  Mathematical Structures of Computer Science, 16(4):581–600, 2006\.  doi:10.1017/S0960129506005378.
  * [GN05] Simon J. Gay and Rajagopal Nagarajan.  Communicating quantum processes.  In Proceedings of SIGPLAN-SIGACT (ACM), pages 145–157, 2005.  doi:10.1145/1040305.1040318.
  * [Gor10] Daniele Gorla.  Towards a Unified Approach to Encodability and Separation Results for Process Calculi.  Information and Computation, 208(9):1031–1053, 2010.  doi:10.1016/j.ic.2010.05.002.
  * [Gru08] Jozef Gruska.  Quantum Computing.  In Wiley Encyclopedia of Computer Science and Engineering. John Wiley & Sons, Inc., 2008.  doi:10.1002/9780470050118.ecse720.
  * [JL04] Philippe Jorrand and Marie Lalire.  Toward a Quantum Process Algebra.  In Proceedings of CF, pages 111–119, 2004.  doi:10.1145/977091.977108.
  * [KPY16] Dimitrios Kouzapas, Jorge A. Pérez, and Nobuko Yoshida.  On the Relative Expressiveness of Higher-Order Session Processes.  In Proceedings of ESOP, volume 9632 of LNCS, pages 446–475, 2016.  doi:10.1007/978-3-662-49498-1_18.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information (10th Anniversary edition).  Cambridge University Press, 2010.
  * [Pet19] Kirstin Peters.  Comparing Process Calculi Using Encodings.  In Proceedings of EXPRESS/SOS, volume 300 of EPCTS, pages 19–38, 2019.  doi:10.4204/EPTCS.300.2.
  * [Plo04] Gordon D. Plotkin.  A structural approach to operational semantics.  Logic and Algebraic Programming, 60-61:17–139, 2004.
  * [PNG13] Kirstin Peters, Uwe Nestmann, and Ursula Goltz.  On Distributability in Process Calculi.  In Proceedings of ESOP, volume 7792 of LNCS, pages 310–329, 2013.  doi:10.1007/978-3-642-37036-6_18.
  * [PvG15] Kirstin Peters and Rob van Glabbeek.  Analysing and Comparing Encodability Criteria.  In Proceedings of EXPRESS/SOS, volume 190 of EPTCS, pages 46–60, 2015.  doi:10.4204/EPTCS.190.4.
  * [RP00] Eleanor Gilbert Rieffel and Wolfgang Polak.  An introduction to quantum computing for non-physicists.  ACM Computing Surveys, 32(3):300–335, 2000.  doi:10.1145/367701.367709.
  * [SPD22a] Anna Schmitt, Kirstin Peters, and Yuxin Deng.  Encodability Criteria for Quantum Based Systems.  In Proceedings of Forte, volume 13273 of LNCS, pages 151–169. Springer, 2022.  doi:10.1007/978-3-031-08679-3_10.
  * [SPD22b] Anna Schmitt, Kirstin Peters, and Yuxin Deng.  Encodability Criteria for Quantum Based Systems (Technical Report).  Technical report, 2022.  doi:10.48550/ARXIV.2204.06068.
  * [YFDJ09] Mingsheng Ying, Yuan Feng, Runyao Duan, and Zheng-Feng Ji.  An algebra of quantum processes.  ACM Transactions on Computational Logic, 10(3):1–36, 2009.  doi:10.1145/1507244.1507249.


# An Improved Method for Quantum Matrix Multiplication

Nhat A. Nghiem<EMAIL_ADDRESS>Department of Physics and
Astronomy, State University of New York at Stony Brook, Stony Brook, NY
11794-3800, USA  Tzu-Chieh Wei  Department of Physics and Astronomy, State
University of New York at Stony Brook, Stony Brook, NY 11794-3800, USA  C. N.
Yang Institute for Theoretical Physics, State University of New York at Stony
Brook, Stony Brook, NY 11794-3840, USA

###### Abstract

Following the celebrated quantum algorithm for solving linear equations (so-
called HHL algorithm), Childs, Kothari and Somma [SIAM Journal on Computing,
46: 1920, (2017)] provided an approach to solve a linear system of equations
with exponentially improved dependence on precision. In this note, we aim to
complement such a result for applying a matrix to some quantum state, based
upon their Chebyshev polynomial approach. A few examples that motivate this
application are included and we further discuss an application of this
improved matrix application algorithm explicitly with an efficient quantum
procedure.

##  I Main Procedure

Quantum algorithm for solving linear systems, so-called HHL, was originally
introduced in Ref.harrow2009quantum , in which the authors aimed to find
solution to the following equations: $A\cdot x=B$, where $A$ is $N\times N$
matrix that is s-sparse ($s\ll N$), and $B$ is an $N\times 1$ unit vector. In
the ideal case, $x$ could be written down explicitly as $x=A^{-1}\cdot B$.
Hence, the ability to invert the matrix $A$ yields the solution directly.
Given access to entries of $A$, and a procedure to prepare the vector $B$ (or
more precisely, $\ket{B}$), the outcome of HHL algorithm is a unit vector
(i.e., quantum state) proportional to the actual solution:
$\ket{x}={x}/{||x||}$ where $||x||$ is the length ($l_{2}$-norm) of the
solution. Let $\kappa$ be conditional number of $A$ (which is the ratio
between the largest and smallest singular values). The running time of the HHL
algorithm is $poly(log(N),\kappa,s,\frac{1}{\epsilon})$, where $\epsilon$ is
the error tolerance.

The error dependence $\mathcal{O}(1/\epsilon)$ is a result of the quantum
phase estimation (QPE) subroutine used in HHL algorithm. This dependence has
been significantly improved in childs2017quantum  to scale as
$\mathcal{O}(poly(log(1/\epsilon)))$. As mentioned in childs2017quantum , due
to the finite-bit precision required to achieve an error $\epsilon$
eventually, the QPE subroutine in harrow2009quantum  limits a better scaling
of error dependence. Instead, the authors of childs2017quantum  outlined two
approaches based on Fourier and Chebyshev series decomposition. These two
methods are implemented differently, but they share the same striking
property: their truncations at relatively low orders
($\sim\mathcal{O}(poly(log(1/\epsilon))$) guarantee an approximation error
$\epsilon$ of the given function, i.e., ${1}/{x}$, for the matrix inversion.
These series decompositions are then integrated into quantum algorithms thanks
to a procedure to apply a linear combination of unitary operators. Details can
be found in childs2017quantum , and, in particular, see their Lemma 6 and
Lemma 7.

As we have mentioned previously, the key to solve the linear equation is to
invert a given matrix $A$, i.e., to implement the action of $A^{-1}$. While
the application of the quantum matrix inversion method still continues to be
explored, for example, Ref. clader2013preconditioned  provides a concrete case
that benefits its quantum advantage, many problems instead require the ability
to apply the matrix multiplication itself, so as to implement the
multiplication of $A$ itself. In wiebe2012quantum , the authors consider the
problem of data fitting in the quantum setting. Aside from inverting a matrix,
their algorithm requires the ability to prepare a state that is proportional
to $F\ket{B}$, where $F$ is some sparse matrix of a given size and $\ket{B}$
is some given unit vector. Another example is the quantum power method
executed by consecutive application of a given matrix to some input state
nghiem2022quantum , combined with Hadamard test to obtain the largest
eigenvalue of a given matrix.

As worked out in wiebe2012quantum , multiplication of a matrix is an adaptive
version of HHL algorithm harrow2009quantum . After the QPE step, one simply
performs controlled-rotation on the ancilla with the multiplied eigenvalues
(instead of dividing them) to achieve the goal of multiplication (see
harrow2009quantum ; wiebe2012quantum  for details). Since it is just a slight
modification of the HHL algorithm, the QPE subroutine is still employed and
hence, the running time still scales as $\mathcal{O}(1/\epsilon)$. It is very
natural to ask if such an error scaling could be improved to
$\mathcal{O}(poly(log(1/\epsilon)))$, as for the matrix inversion case. The
answer is affirmative, and it is surprisingly simple to achieve this, as we
explain below.

We now discuss the Chebyshev series approach in childs2017quantum . The two
main ingredients of this approach are: (1) approximating a function (in the
matrix inversion case, it is 1/$x$) by a linear combination of Chebyshev
polynomials, and (2) implementing each Chebyshev polynomial by a quantum walk
berry2015hamiltonian . In childs2017quantum , all these ingredients are
discussed comprehensively, and hence we would not repeat the details here.
Instead, we recapitulate a key result from there. For completeness, a brief
review of key ingredients from childs2017quantum  is provided in Appendix A.

###### Lemma 1

childs2017quantum  Let A be a symmetric, $N\times N$, s-sparse matrix with
eigenvalues in the range $[\frac{1}{\kappa},1]$. Define $U_{n}(A)$ as
following:

$\displaystyle
U_{n}(A)\ket{0^{m}}\ket{\phi}=\ket{0^{m}}T_{n}(A/s)\ket{\phi}+\ket{\Phi_{\perp}}$

where $m=log(2N)+1$, $\ket{\Phi_{\perp}}$ is a (unnormalized) state that is
orthogonal to $\ket{0^{m}}T_{n}(A/s)\ket{\phi}$:
$\ket{0^{m}}\bra{0^{m}}\otimes\mathbb{I}\ket{\Phi_{\perp}}=0$, and $T_{n}$ is
the $n$-th Chebyshev polynomial of the first kind. Given coherent access to
entries of A, then $U_{n}$ could be implemented up to error $\epsilon$ in time

$\displaystyle\mathcal{O}\big{(}n(logN+log^{2.5}(\kappa sn/\epsilon))\big{)}.$

using $\mathcal{O}(n)$ queries to entries of A.

Recall that in the above Lemma, by coherent access to entries of matrix $A$,
we mean that there exists a procedure $P_{A}$ that returns the entries of $A$
given entries index, i.e:

$\displaystyle
P_{A}\ket{i}\ket{j}\ket{\bf{0}}\rightarrow\ket{i}\ket{j}\ket{a_{ij}}$ (1)

where the third register holds the encoded values of corresponding entries
$a_{ij}$. We emphasize that this is a very standard assumption in the context
of Hamiltonian simulation berry2007efficient ; berry2012black ;
berry2015hamiltonian . In harrow2009quantum , the assumption is slightlly
modified as they assume entries of given matrix is row-computable, i.e, they
can be computed on demand.

We remind that Chebyshev polynomials of the first kind can be obtained from
the recurrence relation as follows.

$\displaystyle T_{0}(x)$ $\displaystyle=1,$ $\displaystyle T_{1}(x)$
$\displaystyle=x,$ $\displaystyle T_{n+1}(x)$
$\displaystyle=2xT_{n}(x)-T_{n-1}(x).$

Whereas in the matrix inversion case, we need to approximate 1/$x$ by a
Chebyshev series with complicated coefficients childs2017quantum , in the
matrix multiplication case, it is simply that $T_{1}(x)=x$. This means that we
only need to implement $U_{1}(A)$ in order to successfully multiply a given
state $\ket{\phi}$ by a matrix. In other words, the representation of function
$x$ as a Chebyshev series is exact and extremely short. It further means that
no approximation error is induced. The only source of error comes from the
implementation of $T_{1}(A)$, which is done by using quantum walk. Now we
state our main result.

######  Theorem 1 (Matrix Multiplication)

Let $\ket{B}$ be some quantum state of dimension $N\times 1$, and $U_{B}$
denotes the unitary circuit that prepares $\ket{B}$. Let A be a symmetric
matrix of size $N\times N$, s-sparse and have a conditional number $\kappa$.
Given cohrent access to matrix A, then there exists a quantum procedure that
prepares the following state

$\displaystyle\ket{\phi}=\frac{A\ket{B}}{||A\ket{B}||}$

in time

$\mathcal{O}\big{(}poly(logN,log(\kappa),s,log(\frac{1}{\epsilon}))\big{)}.$

The proof is straightforward. We first apply $I^{m}\otimes U_{B}$ to
$\ket{0}^{m}\otimes\ket{0}^{logN}$ to obtain $\ket{0}^{m}\ket{B}$ (the tensor
product sign is omitted here) and then apply the result of Lemma 1 with $n$ =
1 to obtain the following state

$\displaystyle
U(A)\ket{0}^{m}\ket{B}=\ket{0}^{m}\frac{A}{s}\ket{B}+\ket{\Phi_{\perp}},$ (2)

where we have used the fact that $T_{1}(A)=A$. Now we measure the first $m$
qubits, post-select on obtaining $\ket{0}^{m}$ to obtain the desired state
$\ket{\phi}$. The measurement succeeds with a probability
$||A\ket{B}||^{2}/s^{2}$ which can be improved to near unity by quantum
amplitude amplification brassard2002quantum , at the cost of inflicting the
circuit depth by a factor $\mathcal{O}(||A\ket{B}||/s)$. The total running
time is thus $\mathcal{O}(T_{U}s/||A\ket{B}||)$, where $T_{U}$ is the time
required to implement $U_{1}(A)$. By plugging in $T_{U}$ the expression from
Lemma 1, we obtain the final running time as stated. Note that we have
absorbed the length of solution $||A\ket{B}||$ into the running time.

Before we head into some applications, we make a quick comparison between our
improved matrix multiplication algorithm versus previously known method for
multiplying matrix, which occurs in the context of data fitting
wiebe2012quantum . For completeness, the statement of the matrix
multiplication problem is, for a given state $\ket{b}$, we need to prepare the
state $A\ket{b}/|A\ket{b}|$ where $|.|$ refers to the norm. In their work
wiebe2012quantum , the authors essentially adapt HHL algorithm
harrow2009quantum  to implement matrix multiplication by simply adjusting the
phase rotation step, which produces the desired state in time

$\displaystyle\mathcal{O}]\Big{(}\log(N)s\kappa^{2}/\epsilon\Big{)}$

Meanwhile, as we pointed out in Thm 1, the desired state could be produced in
time that scales polylogarithmically to most of parameters, except sparsity
$s$. It demonstrates the quite surprising power of the Chebyshev approach that
was first employed in childs2017quantum . Furthermore, in this approach, only
a single query to entries of $A$ is being used.

##  II Applications

In this section, we highlight some interesting applications of the above
simple procedure for matrix multiplication. We will soon appreciate a very
remarkable efficiency that the above method yields.

###  II.1 Accelerating Eigenvalues Finding

As we have mentioned from the beginning, one of the problem that motivates
this work is quantum power method nghiem2022quantum . More specifically, a
similar technique as in harrow2009quantum ; wiebe2012quantum  was used to
consecutively ‘apply’ a given matrix $A$ to some initial state $\ket{x_{0}}$.
By ‘apply’, we mean the unitary $U_{A}$ that acts as following:

$\displaystyle
U_{A}\ket{0}\ket{x_{0}}=\ket{0}A\ket{x_{0}}+\ket{1}\ket{Garbage},$ (3)

where $\ket{Garbage}$ is some unimportant state (not properly normalized).
Combining such a procedure with the Hadamard test, the largest eigenvalue of
$A$ can be estimated. As mentioned in Theorem 1 of nghiem2022quantum , the
running time of the quantum power method is

$\displaystyle\mathcal{O}\Big{(}\frac{\sqrt{n}\log(n)s\kappa^{2}}{\epsilon^{4}}\Big{)},$
(4)

where $n$ is the dimension of $A$, $s$ is the sparsity of $A$, $\kappa$ is the
conditional number of $A$, $k$ is the number of iterations, and $\epsilon$ is
the error tolerance (the additive approximation to the true largest
eigenvalue).

While the speedup with respect to $n$ is remarkable, we shall see that the
improved matrix application 1 can improve the scaling on $\kappa$ and
$\epsilon$. The crucial step in such a quantum power method is the HHL-like
procedure, where the eigenvalues of $A$ are extracted via quantum phase
estimation, followed by rotation of ancilla controlled by the phase register.
As can be seen from Theorem 1, matrix multiplication can be done very
efficiently with the Chebyshev method childs2017quantum . The dependence on
dimension $n$ and conditional number $\kappa$ and even tolerance error
$\epsilon$ are all polylogarithmic. With such an improvement in performing
matrix multiplication, we establish the following faster routine for quantum
power method:

###### Theorem 2

Given coherent access to a Hermitian matrix A, its largest eigenvalue could be
estimate to additive accuracy $\epsilon$ with running time

$\displaystyle\mathcal{O}\Big{(}(log(n)+log^{2.5}(\frac{\kappa
s}{\epsilon}))\frac{s\kappa\sqrt{n}}{\epsilon^{3}}\Big{)}.$ (5)

For simplicity purpose, if we neglect the contribution of logarithmic terms
(compared to the polynomial terms), then we the faster QPW method has the same
scaling on dimension $n$ and sparsity $s$, almost quadratically better
dependence on $\kappa$ and a minor improvement on error $\epsilon$.

###  II.2 Estimating Trace of a Matrix

We remark that the adaptive method in wiebe2012quantum  has the same running
time as the original HHL harrow2009quantum , which is quadratic in $\kappa$
and polynomial in sparsity $s$. In our aforementioned result, the dependence
on $\kappa$ and $s$ are polylogarithmic, which is thus highly efficient. It
demonstrates the surprising utility of the Chebyshev series method introduced
in childs2017quantum . As we have mentioned three examples above that rely on
matrix multiplication, we foresee that matrix multiplication will be employed
in other algorithms. The polylogarithmic dependence on all factors highlights
that even if it is being used as a subroutine in a larger algorithm, the cost
induced would be very modest. To exploit further the surprising efficiency of
the above method, we now provide an alternative solution to the trace
estimation problem of some given matrix. This problem has occured in
rebentrost2014quantum , as estimating trace of kernel matrix is a necessary
step of building (quantum) support vector machine. Additionally, this problem
is also finds its application the DQC-1 model of quantum computation
knill1998power ; shor2008estimating , which can, e.g., efficiently estimate
the values of Jones polynomials. We shall see that, in a similar fashion to
the Chebyshev method childs2017quantum , our method to estimate trace of a
matrix would not make use of Hamiltonian subroutine, e.g., as in
rebentrost2014quantum .

The full statement of trace estimation problem is straightforward as it seems.
Suppose we are given access, for example, to an efficient procedure that
computes entries of some Hermitian matrix $A$ with the conditional number
$\kappa$ and sparsity $s$, and the goal is to estimate $\operatorname{Tr}(A)$.
Without loss of generalization, assume that dim($A$) = $N$ is a power of 2,
i.e, $N=2^{n}$ where $n$ is some positive integer. Classically this problem is
very simple, as we only need to perform the summation of diagonal entries. Now
we sketch our new quantum solution that employs matrix multiplication as a
subroutine.

Similar to childs2017quantum ; harrow2009quantum , we assume that entries
$a_{ij}$ of $A$ is accessible via a procedure denoted as $P_{A}$. What we do
next is to ‘relocate’ those diagonal entries of $A$ to the first column by
performing the following trick. Remind that the operation of $P_{A}$ is done
as follows:

$P_{A}\ket{i}\ket{j}\ket{00..00}=\ket{i}\ket{j}\ket{a_{ij}}.$

where the number of $0$ on the third register on the left hand side of the
above equation is the necessary number of bits required to store the
corresponding entries. We note that the diagonal entries are $\\{a_{ii}\\}$
and entries on the first column are $\\{a_{i0}\\}$. Before we use $P_{A}$ to
query the index, we add CNOT layers, denoted as C. Such CNOT layers C acts on
the diagonal index as:

$\ket{i}\ket{i}\rightarrow\ket{i}\ket{0},$

and

$\ket{i}\ket{0}\rightarrow\ket{i}\ket{i}.$

Then reverse the CNOT layers to return the old index. We obtain the following:

$\displaystyle
P_{A}^{\prime}\ket{i}\ket{i}=C^{\dagger}P_{A}C\ket{i}\ket{i}=\ket{i}\ket{i}\ket{a_{i0}},$
(6)

and

$\displaystyle P_{A}^{\prime}\ket{i}\ket{0}=\ket{i}\ket{i}\ket{a_{ii}}.$ (7)

Effectively, the modified blackbox $P_{A}^{\prime}$ would ‘return’ the new
matrix that has entries in a different order compared to $A$. However, the
first column of, say, $A^{\prime}$ is exactly the diagonal entries of $A$. We
remark that what we describe above is just a simple way to relocate the
entries of given matrix $A$. Basically, one can opt to relocate, or permute
entries of $A$ in different ways, as long as the first column of the new
matrix is the diagonal of $A$.

Now we are ready to describe our main algorithm. We note the following simple
matrix multiplication identity:

$\displaystyle\begin{bmatrix}m_{00}&m_{01}&\cdots&m_{0,n-1}\\\
m_{10}&m_{11}&\cdots&m_{1,n-1}\\\ \vdots&\\\
m_{n-1,0}&m_{n-1,1}&\cdots&m_{n-1,n-1}.\end{bmatrix}\times\begin{bmatrix}1\\\
0\\\ \vdots\\\ 0\end{bmatrix}=\begin{bmatrix}m_{00}\\\ m_{10}\\\ \vdots\\\
m_{n-1,0}\end{bmatrix}.$

It means that if we simply apply the matrix $A^{\prime}$ to the first basis
state $\ket{0^{n}}$ and it results in a vector $u$ with entries from the first
column of $A^{\prime}$, which are exactly diagonal entries of $A$. Let $v$ be
an $N\times 1$ vector with all entries 1 (up to an overall normalization) then
it is obvious that

$\displaystyle\braket{v,u}=\sum_{i=0}^{N-1}a_{ii}=\operatorname{Tr}(A).$ (8)

The corresponding normalized quantum state $\ket{v}=\frac{1}{\sqrt{N}}v$ can
simply be prepared using Hadamard gates, i.e., $H^{n}\ket{0^{n}}$, with
$N=2^{n}$. Therefore, in order to estimate $\operatorname{Tr}(A)$, we can
employ the SWAP test algorithm nielsen2002quantum  with the following two
input states:

$\bullet$ The first state is (see Lemma 1 for definition of $U(A^{\prime})$
and $m=log(2N)+1)$

$\displaystyle\ket{\Phi_{1}}=U(A^{\prime})\ket{0}^{m}\ket{0^{n}}=\ket{0}^{m}\frac{A^{\prime}}{s}\ket{0^{n}}+\ket{\text{Garbage}},$
(9)

where we note that $\ket{\text{Garbage}}$ satisfies
$\ket{0^{m}}\bra{0^{m}}\otimes I\ket{\text{Garbage}}=0$; and $s$ is the
sparsity of matrix A.

$\bullet$ The second state is

$\displaystyle\ket{\Phi_{2}}=\ket{0}^{m}\ket{v}.$ (10)

Their inner product $\braket{\Phi_{1},\Phi_{2}}$ is
$\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}a_{ii}=\operatorname{Tr}(A)/(s\sqrt{N})$.
We remark that $\operatorname{Tr}(A)$ could be complex. Therefore, the real
and complex part of $\operatorname{Tr}(A)$ can simply be estimated to an
accuracy $\delta$, respectively, by running the Hadamard test circuit
$\mathcal{O}(1/\delta^{2})$ times. The whole process, including applying
matrix $A^{\prime}$ and estimating $\operatorname{Tr}(A)$, is highly efficient
with respect to key parameters, which are dimension $N$, conditional number
$\kappa$ and sparsity $s$. As we have seen that the matrix multiplication has
running time that is polylogarithmically in all factors, i.e., $N$, $\kappa$,
and $s$, therefore, the above trace estimation procedure can be applied to
dense matrices with high conditional numbers. The running time of above
quantum algorithm is

$\displaystyle\mathcal{O}\big{(}(logN+log^{2.5}(\kappa
s/\epsilon))/\delta^{2}\big{)}.$ (11)

We have noted that this problem can be done easily using classical algorithm.
We just simply need to query the matrix to get the diangonal entries and
perform the summation, which can be done in logarithmic time using parallel
algorithm. Therefore, classical computer can perform better in regards of time
complexity. However, classical algorithm requires as much as N queries to
matrix A in order to obtain diagonal entries. Meanwhile, in order to perform
matrix multiplication, $\mathcal{O}(1)$ queries to matrix A is sufficient
childs2017quantum . We remark that the above quantum running time is highly
efficient w.r.t all parameters $N,\kappa,s$, as long as when $\kappa$ and $s$
grows polynomially as a function of $N$. For completeness, we restate the
above quantum algorithm in the following theorem with the condition that the
matrix $A$ is not too ill-conditioned.

###### Theorem 3

Given coherent access to some Hermitian matrix A, then its trace can be
estimated to additive accuracy $\delta$ in time

$\displaystyle\mathcal{O}\big{(}poly\log(N)/\epsilon^{2}\big{)}.$

where the highest order of $polylog(N)$ is about 2.5

Another solution to the trace estimation problem which does not require
relocation of entries is clearly possible. We first apply $H^{\log N}\otimes
I^{\log N}$ to $\ket{0}^{\log N}\ket{0}^{\log N}$, following by a CNOT layer
composed of $\log N$ CNOT gates, to obtain the following state:

$\displaystyle\ket{\phi}=\frac{1}{\sqrt{N}}\sum_{i=1}^{N}\ket{i}\ket{i}.$ (12)

We now use Lemma 1 to perform the following unitary $U_{1}(A)\otimes I^{\log
N}$ to the above state. We end up having:

$\displaystyle\ket{\phi_{1}}=\frac{1}{\sqrt{N}}\sum_{i=1}^{N}\Big{(}\ket{0^{m}}(A/s)\ket{i}+\ket{Garbage}_{i}\Big{)}\ket{i},$
(13)

where $\ket{Garbage}_{i}$ is the redundant state that is orthogonal to
$\ket{0}^{m}A\ket{i}$ for all $i$. We remark that $A\ket{i}$ is the $i$-th
column of $A$. The diagonal entries of $A$ are now ‘encoded’ in the state
$A\ket{i}\ket{i}$. We now prepare the following state (we have mentioned a
procedure previously):

$\displaystyle\ket{\phi_{2}}=\frac{1}{\sqrt{N}}\ket{0^{m}}\sum_{i=1}^{N}\ket{i}\ket{i}.$
(14)

The inner product of the above two states is

$\displaystyle\braket{\phi_{2}}{\phi_{1}}=\frac{1}{N}\sum_{i=1}^{N}\bra{i}\bra{i}A\ket{i}\ket{i}=\frac{1}{sN}\operatorname{Tr}(A).$
(15)

By using Hadamard test, we can estimate the real and complex part of
$\operatorname{Tr}(A)$, or more precisely, of $\operatorname{Tr}(A)/(sN)$.

###  II.3 Estimating Trace of Product of Two Matrices

In the above method, we use the simple trick to relocate those diagonal
entries of given matrix $A$. However, that trick is not convenient to use when
dealing with the problem of estimating $\operatorname{Tr}(A\cdot B)$ where $A$
and $B$ are two matrices of size $N\times N$ (we assume the same condition on
the bound of their spectrum, as well as Hermitian property as in the previous
section). Before diving into the quantum algorithm, we quickly review the
computation of trace. Let $C=A\cdot B$, then

$\displaystyle\operatorname{Tr}(C)=\sum_{i}\sum_{j}a_{ij}b_{ji},$ (16)

where $a_{ij}$ (respectively $b_{ij})$ refers to entries of $A$ (and
respectively $B$). Since A and B are generally complex,
$\operatorname{Tr}(AB)$ could be complex. We note that the term

$\displaystyle\sum_{j}a_{ij}b_{ji}$ (17)

is exactly the inner product between $i$-th row of $A$ and $i$-th column of
$B$. However, as we have assumed $A$ to be Hermitian, we know $i$-th row of
$A$ is the same is $i$-th column of $A$ up to a complex conjugation. Our
quantum algorithm begins with the following state $\ket{0^{n}}$. Applying a
layer of Hadamard gates $H^{n}$, we obtain

$\displaystyle\ket{\phi_{0}}=\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i},$ (18)

where $\\{\ket{i}\\}_{i=0}^{N-1}$ are computational basis states, and we then
append another register initialized in $\ket{0}^{m}\ket{0}^{n}$ (where
$m=log(2N)+1$), followed by applying layers of CNOT using $\\{\ket{i}\\}$ as
the control bits and $\ket{0}^{n}$ as the target qubits. We arrive at the
state

$\displaystyle\ket{\phi_{1}}=\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i}\ket{0}^{m}\ket{i}.$
(19)

The reason why we need $\ket{0}^{m}$ is to perform matrix application
subsequently (see Lemma 1). Now we perform the matrix application of $B$ to
the second register, with the aim of obtaining $B\ket{i}$ for all $\ket{i}$,
and we obtain

$\displaystyle\ket{\phi_{2}}=\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i}\Big{(}\ket{0}^{m}\frac{B}{s_{B}}\ket{i}+\ket{G_{i}}\Big{)},$
(20)

where $\ket{G_{i}}$ is abbreviation to garbage state as a result of matrix
application to $\ket{i}$. Again, we emphasize that this state is unimportant.

Now we make a simple observation: since $\ket{i}$ is the $i$-th basis state,
the entries of $B\ket{i}$ is exactly the $i$-th column of $B$, denoted as
$B^{i}$. Now we follow the same three steps as above, but instead of applying
matrix $B$ at the end, we apply matrix $A^{\dagger}$ (it is easy to see that
local access to $A$ yields local access to $A^{\dagger}$ as it is just a
matter of transpose plus complex conjugation). We thus obtain the following
state

$\displaystyle\ket{\Phi_{2}}=\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i}\Big{(}\ket{0}^{m}\frac{A^{\dagger}}{s_{A}}\ket{i}+\ket{G^{\prime}_{i}}\Big{)}.$
(21)

where $s_{A},s_{B}$ is the sparsity of A and B respectively. It is
straightforward to see that $A^{\dagger}\ket{i}$ is the $i$-th column of
$A^{\dagger}$, which is the $i$-th row of $A$ due to its Hermitian property. A
further important observation is that, the inner product of the above two
states is proportional to

$\displaystyle\Big{(}\sum_{j=0}^{N-1}\bra{j}\bra{j}A\Big{)}\cdot\Big{(}\sum_{i=0}^{N-1}\ket{i}B\ket{i}\Big{)}=\operatorname{Tr}(AB).$
(22)

So now the goal is to evaluate the above summation, using $\ket{\phi_{2}}$ and
$\ket{\Phi_{2}}$. At first, a simple solution is to measuring those two states
separately and post-selecting on $\ket{0}^{m}$, and we will be left with a
(normalized) state corresponding to $\sum\ket{i}A\ket{i}$. The renormalization
factor can be revealed via measurement process. We then plug those post-
selected state to the Hadamard test circuit. However, this method will induces
further cost. We now aim to incorporate such measuring/post-selecting step so
as to save some computational time. Typically, in the Hadamard test, one
measures the first qubit of the circuit and based on measurement probability
to estimate the real/complex part of inner product (more precisely of given
two states. Here, we put extra measurements on those $m$ registers of both
states $\ket{\phi_{2}}$ and $\ket{\Phi_{2}}$. By post-selecting the
measurement outcome to be $\ket{0}$ on the first register, and $\ket{0}^{m}$
on both registers of $\ket{\phi_{2}}$ and $\ket{\Phi_{2}}$ and estimate the
probability outcome, we then can estimate the following quantities that
correspond to real and imaginary part of $\operatorname{Tr}(AB)$,
respectively:

$\displaystyle\frac{\Re(\operatorname{Tr}(AB))}{Ns_{A}s_{B}}\text{ and
}\frac{\mathcal{I}(\operatorname{Tr}(AB))}{Ns_{A}s_{B}}$ (23)

to accuracy $\delta$ using $\mathcal{O}(1/\delta^{2})$ repetitions. Hence,
$|\operatorname{Tr}(AB)|$ could also be estimated. We state the following
theorem.

###### Theorem 4

Given access to entries of two matrix $A$ and $B$, the trace of $AB$ could be
estiamted to additive accuracy $\delta$ in time

$\displaystyle\mathcal{O}\Big{(}poly(\log N,\log\kappa),1/\delta^{2}\Big{)}$
(24)

In order to compute $\operatorname{Tr}(AB)$, matrix multiplication needs to be
done before summing over the diagonal entries. There are many classical
algorithms for matrix multiplication, but none are known for achieving such
task within polylogarithmic time. Therefore, the quantum algorithm outlined
above yields exponential speedup with respect to dimension N of given matrix.

###  II.4 Estimating Frobenius Norm

Given a Hermitian matrix $A$ of size $N\times N$, its Frobenius norm is
computed as:

$\displaystyle|A|_{F}=\sqrt{\sum_{i=1}^{N}\lambda_{i}^{2}},$ (25)

where $\\{\lambda_{i}\\}$ are eigenvalues of $A$ (note that since $A$ is
Hermitian then all eigenvalues are real). Revealing the full spectrum of $A$
is apparently a daunting task. However, by definition, we have:

$\displaystyle|A|_{F}=\sqrt{\operatorname{Tr}(A^{\dagger}A)}.$ (26)

Hence, as straightforward as it seems, the square of Frobenius norm is a
direct result of previous section, since we are able to apply the matrix $A$
and $A^{\dagger}$. The running time is similar to equation (23).

As an alternative solution, now we describe how to compute such Frobenius norm
with matrix application technique combined with quantum phase estimation. We
first prepare the completely mixed state:

$\displaystyle\rho_{I}=\frac{1}{N}\sum_{i=0}^{N-1}\ket{i}\bra{i},$ (27)

which can be prepared simply by applying $H^{n}$ to $\ket{0}^{n}$ ($n=log(N)$)
to obtain

$\displaystyle\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i},$ (28)

Then apply the CNOT layers to obtain:

$\displaystyle\frac{1}{\sqrt{N}}\sum_{i=0}^{N-1}\ket{i}\ket{i}.$ (29)

Tracing out the second register we would obtain the desired mixed state
$\rho_{I}$. The algorithm now proceeds simply with the application of Lemma 1
with mixed state input $\ket{0}^{m}\bra{0}^{m}\otimes\rho_{I}$ instead of pure
state. The output of such application is then:

$\displaystyle\ket{0}^{m}\bra{0}^{m}(A/s_{A})\rho_{I}(A^{\dagger}/s_{A})+\rho_{garbage},$
(30)

where $\rho_{garbage}$ is the part that is orthogonal to
$\ket{0}^{m}\bra{0}^{m}$ under trace. Now we perform measurement on the first
m register and post-select on $\ket{0}^{m}$. The probability of such
measurement is

$\operatorname{Tr}(A\rho_{I}A^{\dagger})/s_{A}^{2}=\frac{\sum_{i=1}^{N}\lambda_{i}^{2}}{Ns_{A}^{2}}$

Due to the fact that the maximally mixed state Eqn. (27) is diagonal in the
space spanned by eigenvectors of $A$ (with coefficient $1/N$). In such basis,
$A$ is diagonal (with entries $\\{\lambda_{i}\\}$ on the diagonal). Hence,
simple algebraic multiplication yields the above probability. In order to
estimate such probability to accuracy $\delta$, $\mathcal{O}(1/\delta^{2})$
repetitions are sufficient. Since the preparation of mixed state $\rho_{I}$ is
highly efficient, taking almost a single step, hence we have the following
result:

###### Theorem 5

Given access to matrix $A$, its Frrobenius norm $|A|_{F}$ could be estimated
to additive accuracy $\delta$ in time:

$\displaystyle\mathcal{O}\Big{(}poly(\log N,\log\kappa),1/\delta^{2}\Big{)}.$
(31)

##  III Discussion and Conclusion

Motivated by some recent progress in quantum algorithms, such as
childs2017quantum ; harrow2009quantum ; nghiem2022quantum ; wiebe2012quantum ,
we point out a simple way to apply the techniques developed in
childs2017quantum  to a broader context. The running time of such matrix
application techniques is surprisingly efficient. Aside from significantly
accelerating the data fitting algorithm of Ref. wiebe2012quantum  with our
approach, in particularly, we provide a new way to deal with trace estimation
problem, which might be applied to the DQC-1 algorithm knill1998power ;
shor2007estimating. Given that a huge amount of problems in engineering and
physics require the ability to manipulate matrices, including performing their
multiplication, we suspect that the simple method outlined in this work can
find many applications. To leverage the result regarding estimating the trace
of a matrix or product of two matrices as we describe above, we would like to
mention the so-called Frechet distance problem, which aims to measure the
difference between probability distributions. Suppose two multivariate
Gaussian distributions with means $\mu_{X}$ and $\mu_{Y}$ and covariance
matrices $C_{X}$ and $C_{Y}$ are given, the Frechet distance between these
distributions is defined as

$d^{2}=|\mu_{X}-\mu_{Y}|^{2}+\operatorname{Tr}\Big{(}C_{X}+C_{Y}-2\sqrt{C_{X}C_{Y}}\Big{)}.$

While the estimation of $\operatorname{Tr}(C_{X})$ and
$\operatorname{Tr}(C_{Y})$ are straightforward, the last term
$\operatorname{Tr}(\sqrt{C_{X}C_{Y}})$ is a bit more tricky as our above
method requires further local access to $\sqrt{C_{X}}$ and $\sqrt{C_{y}}$. If,
instead of $A$ and $B$, we have oracular access to their square root, then the
solution is clear as we just need to apply our above algorithm. We would not
discuss in greater detail about such oracle construction here as it is not the
main scope of our work. A more interesting question is raised here, that
whether or not we can estimate $\operatorname{Tr}(\sqrt{AB})$ given local
access to $A$ and $B$ only? In principle, it could be done by using a general
singular value decomposition (in this case if $A$ and $B$ are Hermitian, then
it would be eigenvalues), adopting HHL technique harrow2009quantum . However,
HHL algorithm employs quantum phase estimation as a subroutine and hence,
would likely to incur $\mathcal{O}(1/\epsilon)$ time ahead, meanwhile our goal
for this particular problem, which is also the goal of the paper, is to reduce
such running time to polylogarithmically on the error-tolerance. We leave such
a problem for future work.

## Acknowledgements

This work was supported in part by the U. S. Department of Energy, Office of
Science, National Quantum Information Science Research Centers, Co-design
Center for Quantum Advantage (C2QA) under contract number DE-SC0012704. We
also acknowledge the support from a Seed Grant from Stony Brook University’s
Office of the Vice President for Research.

## Declarations

On behalf of all authors, the corresponding author states that there is no
conflict of interest.

## Data Availability Statement

There is no data generated in this work.

## References

  * (1) Aram W Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical review letters, 103(15):150502, 2009.
  * (2) Andrew M Childs, Robin Kothari, and Rolando D Somma.  Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.  SIAM Journal on Computing, 46(6):1920–1950, 2017.
  * (3) B David Clader, Bryan C Jacobs, and Chad R Sprouse.  Preconditioned quantum linear system algorithm.  Physical review letters, 110(25):250504, 2013.
  * (4) Nathan Wiebe, Daniel Braun, and Seth Lloyd.  Quantum algorithm for data fitting.  Physical review letters, 109(5):050505, 2012.
  * (5) Nhat A Nghiem and Tzu-Chieh Wei.  Quantum algorithm for estimating eigenvalue.  arXiv preprint arXiv:2211.06179, 2022.
  * (6) Dominic W Berry, Andrew M Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th annual symposium on foundations of computer science, pages 792–809. IEEE, 2015.
  * (7) Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders.  Efficient quantum algorithms for simulating sparse hamiltonians.  Communications in Mathematical Physics, 270(2):359–371, 2007.
  * (8) Dominic W Berry and Andrew M Childs.  Black-box hamiltonian simulation and unitary implementation.  Quantum Information and Computation, 12:29–62, 2009.
  * (9) Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  Contemporary Mathematics, 305:53–74, 2002.
  * (10) Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  Physical review letters, 113(13):130503, 2014.
  * (11) E. Knill and R. Laflamme.  Power of one bit of quantum information.  Phys. Rev. Lett., 81:5672–5675, Dec 1998.
  * (12) Peter W. Shor and Stephen P. Jordan.  Estimating jones polynomials is a complete problem for one clean qubit.  8(8):681–714, 2008.
  * (13) Michael A Nielsen and Isaac Chuang.  Quantum computation and quantum information, 2002.

##  Appendix A Review of Chebyshev Approach

Here we make a review of Chebyshev approach that was employed in [2], which is
essentially built upon quantum walk technique [8, 6]. What we will describe
below is more or less a summary of Section 4 in Ref. [2], the result of which
was used in our main text.

Let $A$ be a $d$-sparse ($s$ was used in the main text) $N\times N$ Hermitian
matrix and a procedure, or black-box that could query the entries of $A$.
Define the following state on the Hilbert space
$\mathcal{C}^{2N}\otimes\mathcal{C}^{2N}$:

$\displaystyle\ket{\psi_{j}}=\ket{j}\otimes\frac{1}{\sqrt{d}}\sum_{k\in[N];A_{ij}\neq
0}\Big{(}\sqrt{A_{ij}^{*}}\ket{k}+\sqrt{1-|A_{ij}|}\ket{k+N}\Big{)}$ (32)

We also define the following isometry $T$ from $\mathcal{C}^{N}$ to
$\mathcal{C}^{2N}\otimes\mathcal{C}^{2N}$:

$\displaystyle T=\sum_{j\in[N]}\ket{\psi_{j}}\bra{j}.$ (33)

We note that $T$ is not unitary, and, therefore, what we would need is a
unitary version of $T$, which is $U_{T}$ acting as following:

$\displaystyle U_{T}\ket{0^{m}}\ket{\phi}=T\ket{\phi},$ (34)

for some $\ket{\phi}\in\mathcal{C}^{N}$ and $m=log(2N)+1$.

The so-called walk operator is defined as:

$\displaystyle W=S(2TT^{\dagger}-I),$ (35)

where $S$ is the SWAP operator on the space
$\mathcal{C}^{2N}\otimes\mathcal{C}^{2N}$, i.e., $S\ket{j,k}=\ket{k,j}$. The
implementation of $W$ (and $U_{T}$) was explicitly described in Lemma 10 of
Ref. [6]. We now summarize the structural property of $W$ that makes it highly
beneficial for many quantum algorithms, including the improved quantum linear
solver [2], and quantum simulation [6].

Let $\ket{\lambda}$ and $\lambda$ be eigenvector and eigenvalue of $A/d$ (note
that the scaling by $d$ doesn’t have further systematic problem, as the
spectrum remains the same, only eigenvalues got scaled by a factor). Within
the subspace spanned by $T\ket{\lambda}$ and $ST\ket{\lambda}$, $W$ admits the
following block form:

$\displaystyle\begin{bmatrix}\lambda&-\sqrt{1-\lambda^{2}}\\\
\sqrt{1-\lambda^{2}}&\lambda\end{bmatrix}.$ (36)

The proof can be found in Lemma 15 of [2]. The above form of $W$ possess the
following remarkable property (Lemma 16 of [2]),

$\displaystyle
W^{n}=\begin{bmatrix}T_{n}(\lambda)&-\sqrt{1-\lambda^{2}}U_{n-1}(\lambda)\\\
\sqrt{1-\lambda^{2}}U_{n-1}(\lambda)&T_{n}(\lambda)\end{bmatrix},$ (37)

where $T_{n}$ is the $n$-th Chebyshev polynomial of the first kind, and
$U_{n}$ is the $n$-th Chebyshev polynomial of the second kind. The
construction of $W_{n}$ is simply product of $n$ times application of $W$.
Therefore, we can construct the unitary $U=U_{T}^{\dagger}W^{n}U_{T}$ that
acts on $\ket{0^{m}}\ket{\phi}$ as follows,

$\displaystyle
U\ket{0^{m}}\ket{\phi}=\ket{0^{m}}T_{n}(A)\ket{\phi}+\ket{\Phi_{\perp}},$ (38)

where $\ket{\Phi_{\perp}}$ is orthogonal to $\ket{0^{m}}T_{n}(A)\ket{\phi}$.
As we have remarked in the main text, the 1st Chebyshev polynomial of the
first kind $T_{1}(x)=x$ is sufficient for matrix multiplication purpose, which
requires a single execution of $W$.