* [RV17] Oded Regev and Aravindan Vijayaraghavan.  On learning mixtures of well-separated gaussians.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 85–96. IEEE, 2017.
  * [SK01] Arora Sanjeev and Ravi Kannan.  Learning mixtures of arbitrary gaussians.  In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 247–257, 2001.
  * [SZB21] Min Jae Song, Ilias Zadik, and Joan Bruna.  On the cryptographic hardness of learning single periodic neurons.  In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 29602–29615. Curran Associates, Inc., 2021.
  * [Tie22] Stefan Tiegel.  Hardness of agnostically learning halfspaces from worst-case lattice problems.  arXiv preprint arXiv:2207.14030, 2022.
  * [TTM+85] D.M. Titterington, P.S.D.M. Titterington, S.A.F. M, A.F.M. Smith, U.E. Makov, and John Wiley & Sons.  Statistical Analysis of Finite Mixture Distributions.  Applied section. Wiley, 1985.
  * [VW02] Santosh Vempala and Grant Wang.  A spectral algorithm for learning mixtures of distributions.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 113–122. IEEE, 2002.

##  Appendix A Alternate Reduction from LWE to CLWE

In this section, we propose an alternate reduction from LWE to CLWE than that
of Corollary 5. We note that we reduce to _search_ CLWE, and not decisional
CLWE. Here is a brief outline to the steps of this reduction:

  1. 1.

First, we start with the standard search version of LWE (dimension $n$, mod
$q$, and noise $D_{\mathbb{Z},\sigma}$).

  2. 2.

Then, we reduce to the (search) “Hermite normal form” of LWE, where the secret
is drawn from the _error distribution_ instead of uniform over
$\mathbb{Z}_{q}^{n}$ (with a small additive blowup in the number of samples),
following [ACPS09, MR09] (and the more refined analysis by [BLP+13]).

  3. 3.

Since the secrets are now short, we know there is some (small)
$r\approx\sigma\sqrt{n}$ for which non-negligibly often, secrets will have
$\ell_{2}$ norm _exactly_ $r$. The reduction in this step is the trivial
reduction, but crucially uses the fact that this is a _search_ reduction.

  4. 4.

Since the secrets now have fixed (and small) norm, we use Theorem 6 to reduce
to CLWE, slightly modified to be a search reduction (as opposed to a decision
reduction).

Explicitly, we have the following theorem.

######  Theorem 9 (Alternate Reduction from LWE to CLWE).

Suppose there exists no algorithm running in time
$T+\mathsf{poly}(n,m,\log(\lambda),\log(q))$ that outputs $\mathbf{s}$ with
probability $\epsilon$ when given $(A,\mathbf{s}^{\top}A+\mathbf{e}\pmod{q})$,
where $A\sim U(\mathbb{Z}_{q}^{n\times m})$, $\mathbf{s}\sim
U(\mathbb{Z}_{q}^{n})$, and $\mathbf{e}\sim D_{\mathbb{Z}^{m},\sigma}$.
Suppose $q\leq 2^{2^{O(n)}}$ and $\sigma\geq 2\sqrt{\ln(n)}$. Then, there is
no $T$-time algorithm outputting $\mathbf{s}^{\prime}$ with probability at
least $(\epsilon+2^{-n})\cdot 2\sigma^{2}n+\mathsf{negl}(\lambda)$ when given
$(A^{\prime},\gamma\cdot(\mathbf{s}^{\prime})^{\top}A^{\prime}+\mathbf{e}\pmod{1})$,
where $A^{\prime}\sim(D_{1})^{n\times m^{\prime}}$,
$\mathbf{s}^{\prime}\sim\frac{1}{r}\mathcal{S}$, $\mathbf{e}\sim
D_{\beta}^{m^{\prime}}$, where $\mathcal{S}$ is the set of all vectors in
$\mathbb{Z}^{n}$ with norm exactly $r$, for some $r=O(\sigma\sqrt{n})$, and
where

$\displaystyle m^{\prime}$ $\displaystyle=m+O(n),$ $\displaystyle\gamma$
$\displaystyle=O\left(\sigma\sqrt{n}\cdot\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)}\right),$
$\displaystyle\beta$
$\displaystyle=O\left(\frac{\sigma\sqrt{n}\cdot\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)}}{q}\right).$

Note that one can reduce to secret distribution $\mathbf{s}^{\prime}\sim
U(S^{n-1})$ if desired, by using (a search version of) Lemma 19.

###### Proof.

First, we invoke Lemma 2 of [ACPS09] to turn the secret distribution from
$\mathbb{Z}_{q}^{n}$ into $D_{\mathbb{Z}^{n},\sigma}$. The only loss in
parameters we get is the number of samples, which becomes
$m^{\prime}=m+O(n)+O(\log\log q)$, as $O(n)+O(\log\log q)$ samples suffice to
efficiently find $n$ linearly independent vectors over $\mathbb{Z}_{q}$, with
probability of failure at most $2^{-n}$. (See Claim 2.13 of the full version
of [BLP+13].) Since $q\leq 2^{2^{O(n)}}$, $O(\log\log q)$ can be absorbed into
$O(n)$, making $m^{\prime}=m+O(n)$. This means there is no solver for
$\mathbf{s}$ with probability at least $\epsilon+2^{-n}$ for this “normal
form” of LWE (i.e. with $\mathbf{s}\sim D_{\mathbb{Z}^{n},\sigma}$).

Now, we observe that there exists some $r\leq\sigma\sqrt{n}$ such that non-
negligibly often, secrets $\mathbf{s}\sim D_{\mathbb{Z}^{n},\sigma}$ will have
$\ell_{2}$ norm exactly $r$. To see this, we use the proof of Lemma 4.4 in
[MR07] (ultimately based on Lemma 1.5 of [Ban93]) to see that the probability
that $\lVert\mathbf{s}\rVert\geq\sigma\sqrt{n}$ is at most $2^{-n}$ for
$\mathbf{s}\sim D_{\mathbb{Z}^{n},\sigma}$. Conditioned on
$\lVert\mathbf{s}\rVert\leq\sigma\sqrt{n}$, since $\lVert\mathbf{s}\rVert^{2}$
is a non-negative integer, we know it must take on at most $\sigma^{2}\cdot
n+1$ different values. Let $\mathcal{S}_{r}$ be the set of all vectors in
$\mathbb{Z}^{n}$ with $\ell_{2}$ norm exactly $r\in\mathbb{R}$. What we have
just shown is that there exists some $r\leq\sigma\sqrt{n}$ such that
$\Pr_{\mathbf{s}\sim
D_{\mathbb{Z}^{n},\sigma}}[\mathbf{s}\in\mathcal{S}_{r}]\geq(1-2^{-n})/(\sigma^{2}\cdot
n+1)\geq 1/(2\sigma^{2}n)$. From here on out, we now fix $r$ to be such an
$r$. Moreover, it is easy to see that $r\geq\sigma$, as the only way for the
norm to be below $\sigma$ is if all coordinates of the discrete Gaussian have
magnitude at most $\sigma$, which happens with exponentially small probability
in $n$.

Therefore, if we have some solver with success probability
$(\epsilon+2^{-n})\cdot 2\sigma^{2}n$ for LWE with
$\mathbf{s}\sim\mathcal{S}$, then that same solver has success probability at
least $\epsilon+2^{-n}$ for LWE with $\mathbf{s}\sim
D_{\mathbb{Z}^{n},\sigma}$. Therefore, we now know there is no solver for
$\mathsf{LWE}$ with secret distribution $\mathcal{S}$ with success probability
$(\epsilon+2^{-n})\cdot 2\sigma^{2}n$.

Before invoking Theorem 6, we simply increase the width of the noise, as the
requirement on the width of the noise is large for the reduction to go
through. Specifically, we set
$\sigma^{\prime}=3r\sqrt{\ln(m^{\prime})+\ln(n)+\omega(\log\lambda)}\geq\sigma$,
where the inequality comes from the fact that $r\geq\sigma$. We can achieve
this reduction by simply adding noise.

Now, we directly invoke Theorem 6, as our requirement on $\sigma^{\prime}$ is
now satisfied. While the reduction is formally a decisional reduction, the
proof also works in the search setting. In fact, throughout the reduction, the
secret remains the same, up to scaling by $r$. This implies there is no solver
with success probability at least $(\epsilon+2^{-n})\cdot
2\sigma^{2}n+\mathsf{negl}(\lambda)$, for parameters

$\displaystyle\gamma$
$\displaystyle=r\cdot\sqrt{\ln(m^{\prime})+\ln(n)+\omega(\log\lambda)}\leq
O\left(\sigma\sqrt{n}\cdot\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)}\right),$
$\displaystyle\beta$
$\displaystyle=O\left(\frac{\sqrt{(\sigma^{\prime})^{2}+r^{2}(\ln(m^{\prime})+\ln(n)+\omega(\log\lambda)}}{q}\right)=O\left(\frac{\sigma\sqrt{n}\cdot\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)}}{q}\right).$

∎

##  Appendix B Low-Sample Algorithm for Sparse $\mathsf{hCLWE}$

######  Theorem 10.

Let $m=5k\log_{2}(n)/\log_{2}(1/(\beta\sqrt{k}))$. Suppose $\gamma\geq
2\sqrt{k(\ln n+\ln m)}$ and $\log_{2}(1/(\beta\sqrt{k}))=\omega(\log\log m)$.
Then, there is a $O\left(m\cdot\mathsf{poly}(n)\cdot
2^{k}\binom{n}{k}\right)$-time algorithm using $m$ samples that learns the
parameters for GMM when restricted to ($m$ sample) mixtures $D_{1}^{n\times
m}$ and
$\mathsf{hCLWE}^{(g)}(m,D_{1}^{n},\frac{1}{\sqrt{k}}\mathcal{S}_{n,k},\gamma,\beta)$
for any fixed $g\geq C\cdot\gamma\cdot\sqrt{\log m}$ for some universal
constant $C$. That is, we view all the parameters as fixed, and the algorithm
either learns the correct secret
$\mathbf{s}\sim\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$ (and thus the
corresponding $\mathsf{hCLWE}^{(g)}$ distribution), or knows that the
distribution is $D_{1}^{n}$, with success probability at least $9/10$ in both
cases.

######  Remark 4.

This theorem can be generalized for other settings of $\beta,\gamma$, but we
state it this way because it suffices for our purposes. It also works for the
setting of non-truncated hCLWE.

######  Remark 5.

While the runtime of this algorithm is similar to the algorithm solving hCLWE
given in Theorem 7.5 of [BRST21] as applied in a black-box way, the sample
complexity needed here is $\ll k\log_{2}(n)$, as opposed to roughly
$2^{O(\gamma^{2})}=n^{\Omega(k)}$.

Input: Sampling oracle to distribution $\mathcal{D}$.

Output: $\mathbf{s}$ to indicate $\mathcal{D}=\mathsf{hCLWE}^{(g)}$ with
secret $\mathbf{s}$, and $0$ for $\mathcal{D}=D_{1}^{n}$.

Draw $m$ samples $\mathbf{a}_{1},\ldots,\mathbf{a}_{m}\sim\mathcal{D}$.

for  _$\mathbf{s}\in\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$_ do

Compute
$f_{\mathbf{s}}(\mathbf{a}_{i})=\langle\mathbf{a}_{i},\mathbf{s}\rangle\mod\gamma/(\sqrt{k}\cdot\gamma^{\prime
2})$ for all $i\in[m]$.

if
_$f_{\mathbf{s}}(\mathbf{a}_{i})\in[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]$
for all $i\in[m]$_ then

return _$\mathbf{s}$_.

return _$0$_.

Algorithm 1 Low Sample algorithm for $\mathsf{hCLWE}^{(g)}$

###### Proof.

Let $t:=|\mathcal{S}_{n,k}|=\binom{n}{k}\cdot 2^{k}$ denote the number of
$k$-sparse $\\{-1,0,+1\\}$-secrets. For the sake of this proof, we take the
representatives of $\mathbb{T}_{q}$ to be in the interval $[-q/2,q/2)$.
Further, let $\gamma^{\prime}=\sqrt{\gamma^{2}+\beta^{2}}$ and
$\mathbf{a}\in\mathbb{R}^{n}$ and
$\mathbf{s}\in\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$. We define
$f_{\mathbf{s}}:\mathbb{R}^{n}\to\mathbb{T}_{\gamma/(\sqrt{k}\cdot\gamma^{\prime
2})}$ by

$\displaystyle
f_{\mathbf{s}}(\mathbf{a}):=\langle\mathbf{a},\mathbf{s}\rangle\mod\gamma/(\sqrt{k}\cdot\gamma^{\prime
2}).$

We use the main idea in the proof of Claim 5.3 in [BRST21] to give an
algorithm that finds the correct secret $\mathbf{s}$, if it exists, or report
that none exists if the distribution is $D_{1}^{n}$. Given $m$ samples
$\mathbf{a}_{1},\ldots,\mathbf{a}_{m}$ from an unknown distribution
$\mathcal{D}$, we compute $f_{\mathbf{s}}(\mathbf{a}_{i})$ for all possible
secret directions $\mathbf{s}\in\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$ and for
all samples $i\in[m]$. This takes time $O(m\cdot t\cdot\mathsf{poly}(n))$,
where we allow $\mathsf{poly}(n)$ time to take numbers mod
$\gamma/(\sqrt{k}\gamma^{\prime 2})$. If there is some $\mathbf{s}$ such that
$f_{\mathbf{s}}(\mathbf{a}_{i})$ is small for all samples $i\in[m]$, then we
output $\mathbf{s}$, and otherwise we guess $\mathcal{D}=D^{m}_{1}$.

Now, suppose that the input distribution is
$\mathcal{D}=\mathsf{hCLWE}^{(g)}(m,D_{1}^{n},\frac{1}{\sqrt{k}}\mathcal{S}_{n,k},\gamma,\beta)$.
Let $\mathbf{s}^{*}$ be the randomly sampled but fixed secret direction. Then
for all the $m$ samples $\mathbf{a}_{i}$, we have that
$\langle\mathbf{s}^{*},\mathbf{a}_{i}\rangle\pmod{\gamma/(\gamma^{\prime 2})}$
is distributed as $D_{\beta/\gamma^{\prime}}\mod\gamma/\gamma^{\prime 2}$.
This can be seen from Equation 2. (As an aside, note that by Claim 5.3 of
[BRST21] this holds even when the input distribution is not truncated, that
is,
$\mathcal{D}=\mathsf{hCLWE}(m,D_{1}^{n},\frac{1}{\sqrt{k}}\mathcal{S}_{n,k},\gamma,\beta)$.)
Now, supposing for simplicity that $k$ is a perfect square, we can take this
mod $\gamma/(\sqrt{k}\cdot\gamma^{\prime 2})$ to get that
$f_{\mathbf{s}^{*}}(\mathbf{a}_{i})$ is distributed as
$D_{\beta/\gamma^{\prime}}\mod\gamma/(\sqrt{k}\cdot\gamma^{\prime 2})$. (In
case $k$ is not a perfect square, we can take
$\gamma/\left(\left\lceil\sqrt{k}\right\rceil\cdot\gamma^{\prime 2}\right)$ as
the modulus instead.)

For a parameter $\delta>0$ specified later, let $a=\sqrt{\ln(1/\delta)}$. By a
standard Chernoff bound, the probability mass of $D_{\beta/\gamma^{\prime}}$
that is outside the interval
$[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]$ is at most $\delta$. Taking
a union bound over the $m$ samples $\mathbf{a}_{i}$,

$\Pr\left[\exists i\in[m]\text{ s.t.
}f_{\mathbf{s}^{*}}(\mathbf{a}_{i})\notin[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]\right]\leq
m\delta=\frac{1}{100},$ (3)

when setting $\delta=1/(100m)$.

We still have to argue that for this $\mathcal{D}$ that no other
$\mathbf{s}\neq\mathbf{s}^{*}$ passes the test. To see this, fix some
$\mathbf{s}\neq\mathbf{s}^{*}$. Let
$\mathbf{z}=\mathbf{s}-\mathbf{s}^{*}\in\frac{1}{\sqrt{k}}\cdot\\{-2,-1,0,1,2\\}^{n}$.
Since $\mathbf{s}\in\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$ and
$\mathbf{s}\neq\mathbf{s}^{*}$, it follows that
$\lVert\mathbf{z}\rVert\geq\sqrt{2}/\sqrt{k}$. We have

$\langle\mathbf{a}_{i},\mathbf{s}\rangle=\langle\mathbf{a}_{i},\mathbf{s}^{*}+\mathbf{z}\rangle=\langle\mathbf{a}_{i},\mathbf{s}^{*}\rangle+\langle\mathbf{a}_{i},\mathbf{z}\rangle.$
(4)

On its own, for fixed $\mathbf{z}$, $\langle\mathbf{a}_{i},\mathbf{z}\rangle$
is distributed according to $D_{\lVert\mathbf{z}\rVert}$, which is from a
discrete Gaussian wider than $D_{1/\sqrt{k}}$. By Lemma 4 (and the union bound
over $m$ samples), it follows that the distribution of
$(\langle\mathbf{a}_{i},\mathbf{z}\rangle\pmod{\gamma/(\sqrt{k}\cdot\gamma^{\prime
2})})_{i\in[m]}$ is $m\cdot\exp(-\gamma^{\prime 4}/\gamma^{2})/2$-close to
$U(\mathbb{T}_{\gamma/(\sqrt{k}\cdot\gamma^{\prime 2})})^{m}$. Therefore,

$\displaystyle\Pr_{\mathbf{a}_{i}}\left[\left(f_{\mathbf{z}}(\mathbf{a}_{i})\right)_{i\in[m]}\in[-2a\beta/\gamma^{\prime},2a\beta/\gamma^{\prime}]^{m}\right]$
$\displaystyle\leq\Delta\left(D_{1}^{m}\mod\gamma/(\sqrt{k}\gamma^{\prime
2}),U\left(\mathbb{T}_{\gamma/(\sqrt{k}\gamma^{\prime
2})}\right)^{m}\right)+\left(4a\beta\sqrt{k}\cdot\frac{\gamma^{\prime}}{\gamma}\right)^{m}$
$\displaystyle\leq
m\exp(-\gamma^{2})/2+\left(4a\beta\sqrt{k}\cdot\frac{\gamma^{\prime}}{\gamma}\right)^{m}$
$\displaystyle\leq m\exp(-\gamma^{2})/2+\left(8a\beta\sqrt{k}\right)^{m}.$

Since this was for a particular secret $\mathbf{s}\neq\mathbf{s}^{*}$, we can
union bound over all $\mathbf{s}\neq\mathbf{s}^{*}$ to see that

$\Pr_{\mathbf{a}_{i}}\left[\exists\mathbf{s}\neq\mathbf{s}^{*}\text{ s.t.
}\left(f_{\mathbf{z}}(\mathbf{a}_{i})\right)_{i\in[m]}\in[-2a\beta/\gamma^{\prime},2a\beta/\gamma^{\prime}]^{m}\right]\leq
t\cdot m\exp(-\gamma^{2})/2+t\cdot\left(8\cdot a\beta\sqrt{k}\right)^{m}.$ (5)

Note that if
$f_{\mathbf{z}}(\mathbf{a}_{i})\notin[-2a\beta/\gamma^{\prime},2a\beta/\gamma^{\prime}]$
and
$f_{\mathbf{s}^{*}}(\mathbf{a}_{i})\in[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]$,
then by equation (4), it follows that
$f_{\mathbf{s}}(\mathbf{a}_{i})\notin[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]$.
Thus, equations (3) and (5) fully characterize the “bad” events, as if both
events do not happen, then $\mathbf{s}^{*}$ passes the test, and no other
$\mathbf{s}\neq\mathbf{s}^{*}$ passes the test. Therefore, if samples are from
the hCLWE distribution, then the probability of failure is at most

$\frac{1}{100}+t\cdot
m\exp(-\gamma^{2})/2+t\cdot\left(8a\beta\sqrt{k}\right)^{m}.$

We first analyze the middle term. Since $\gamma\geq 2\sqrt{k(\ln n+\ln m)}$,
we have

$t\cdot m\cdot\exp(-\gamma^{2})/2\leq\frac{2^{k}\cdot n^{k}\cdot m}{2\cdot
m^{4k}\cdot n^{4k}}<\frac{1}{100}$

for large enough $m$ and $k$. For the last term, we have

$\displaystyle
t\cdot\left(8a\beta\sqrt{k}\right)^{m}=t\cdot\left(8\cdot\ln(100m)\cdot\beta\sqrt{k}\right)^{m}$
$\displaystyle=t\cdot\left(2^{3+\log_{2}(\ln(100m))-\log_{2}(1/(\beta\sqrt{k}))}\right)^{m}$
$\displaystyle\leq t\cdot 2^{-(m/2)\cdot\log_{2}(1/(\beta\sqrt{k}))}$
$\displaystyle\leq 2^{k+k\log_{2}(n)-(m/2)\cdot\log_{2}(1/(\beta\sqrt{k}))}$
$\displaystyle\leq 2^{-k\log_{2}(n)}$ $\displaystyle\leq\frac{1}{100}$

for sufficiently large $k,n$, where we have used our hypothesis on
$\log_{2}(1/(\beta\sqrt{k}))$ and choice of $m$. Thus, for the hCLWE
distribution, we output the correct secret $\mathbf{s}^{*}$ with probability
at least $19/20$.

Now, suppose we are given samples from $D_{1}^{n}$. For any fixed
$\mathbf{s}\in\frac{1}{\sqrt{k}}\mathcal{S}_{n,k}$, we have
$\langle\mathbf{a}_{i},\mathbf{s}\rangle\sim D_{1}$, independently of
$\mathbf{s}$. By Lemma 4 and Lemma 2,

$\displaystyle\Delta(D_{1}^{m}\mod\gamma/(\sqrt{k}\cdot\gamma^{\prime
2}),\mathbb{T}_{\gamma/(\sqrt{k}\cdot\gamma^{\prime 2})}^{m})\leq
m\exp(-\gamma^{\prime 4}k/\gamma^{2})/2\leq m\exp(-\gamma^{2})/2.$

Therefore, by a simpler analysis than the one above, we have

$\Pr_{\mathbf{a}_{i}}\left[\exists\mathbf{s}\in\mathcal{S}_{n,k}\text{ s.t.
}\left(f_{\mathbf{s}}(\mathbf{a}_{i})\right)_{i\in[m]}\in[-a\beta/\gamma^{\prime},a\beta/\gamma^{\prime}]^{m}\right]\leq
t\cdot m\exp(-\gamma^{2})/2+t\cdot\left(8\cdot a\beta\sqrt{k}\right)^{m},$ (6)

which we have previously bounded above by $2/100$. This completes the proof,
as we will output 0 (to indicate $\mathcal{D}=D_{1}^{n}$) with probability at
least $19/20$ in this case. ∎

Now, we combine Theorem 10 and Corollary 8 to get the following tightness for
the mixtures of Gaussians we consider.

######  Corollary 10.

Following the notation of Corollary 8, there is an algorithm solving for the
parameters for GMM, when restricted to $D_{1}^{n}$ and hCLWE, using
$m=O(\ell)=O\left((\log n)^{1/\delta}\right)$ samples and time
$2^{O\left((\log n)^{1/\delta}\log\log n\right)}$.

###### Proof.

We apply Theorem 10. If we trace $\beta$ in the proof of Corollary 8, we see
that

$\beta\sqrt{k}=O\left(\frac{\sigma
k}{q}\right)=O\left(\frac{\sqrt{\ell}\cdot\ell}{\ell^{2}}\right)=O\left(\ell^{-1/2}\right).$

Therefore, $\log(1/(\beta\sqrt{k}))=\Omega(\log\ell)$, which implies

$m=\frac{5k\log_{2}(n)}{\log_{2}(1/\beta\sqrt{k})}=O\left(\frac{\ell^{1-\delta}\cdot\log(\ell)\cdot\ell^{\delta}}{\log(\ell)}\right)=O(\ell)=O((\log
n)^{1/\delta}),$

and thus that $\log(1/(\beta\sqrt{k}))=\omega(\log\log m)$. For the runtime,
observe that

$\displaystyle m\cdot\mathsf{poly}(n)\cdot 2^{k}\binom{n}{k}\leq m\cdot
n^{O(k)}\leq m\cdot 2^{O(\log(n)\ell^{1-\delta}\log(\ell))}$
$\displaystyle\leq\mathsf{poly}(\log n)\cdot 2^{O(\log(n)^{1/\delta}\log\log
n)}$ $\displaystyle=2^{O(\log(n)^{1/\delta}\log\log n)},$

as desired. ∎

##  Appendix C Reduction from CLWE to LWE

Here, we show a reversed version of Theorem 6, i.e. a reduction from discrete-
secret CLWE to fixed-norm LWE. Note that this gives a reduction only from
discrete-secret CLWE to LWE, and not CLWE with secrets $\mathbf{s}\sim
U(S^{n-1})$ to LWE.

######  Theorem 11 (CLWE to LWE).

Let $r\in\mathbb{R}_{\geq 1}$, and let $\mathcal{S}$ be an arbitrary
distribution over $\mathbb{Z}^{n}$ where all elements in the support of
$\mathcal{S}$ have $\ell_{2}$ norm $r$. Then, for

$\displaystyle\gamma$
$\displaystyle=r\cdot\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)},\text{ and}$
$\displaystyle\sigma$ $\displaystyle=O(\beta\cdot q),$

if there is no $T+\mathsf{poly}(n,m,\log(q),\log(\lambda))$ time distinguisher
between $\mathsf{CLWE}(m,D_{1}^{n},\frac{1}{r}\cdot\mathcal{S},\gamma,\beta)$
and $D_{1}^{n\times m}\times U(\mathbb{T}^{m})$ with advantage at least
$\epsilon-\mathsf{negl}(\lambda)$, then there is no $T$-time distinguisher
between $\mathsf{LWE}(m,\mathbb{Z}_{q}^{n},\mathcal{S},D_{\sigma})$ and
$U(\mathbb{Z}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$ with advantage
$\epsilon$, as long as $\beta\cdot q\geq
3r\sqrt{\ln(m)+\ln(n)+\omega(\log\lambda)}$.

Note that we reduce to a continuous-error version of LWE. Using standard
techniques (see Theorem 3.1 of [Pei10]), this can be reduced to discrete
Gaussian errors. Similarly, the final LWE distribution can be made to have
secrets $U(\mathbb{Z}_{q}^{n})$ by a standard random self-reduction. Lastly,
the proof of Theorem 11 preserves the secret vector up to scaling, so it also
is a reduction between the search versions of the problems.

With this reduction from discrete-secret CLWE to LWE, we get a search-to-
decision reduction for discrete-secret CLWE. This can be obtained immediately
by combining (the search version of) Theorem 11, standard search-to-decision
reductions for $\mathsf{LWE}$ (see [Pei09, ACPS09, MM11, MP12, BLP+13]), and
Theorem 5 (or Theorem 6 if the $\mathsf{LWE}$ search-to-decision reduction
preserves the norm of the secret). We leave open the question of whether there
is a more direct search-to-decision reduction for $\mathsf{CLWE}$.

The steps of this proof are essentially just versions of Lemma 18 and Lemma 16
but in the reverse directions. We give these “reversed” lemmas below.

######  Lemma 21 (Reverse of Lemma 18).

Let $n,m,q\in\mathbb{N},\sigma,r,\gamma\in\mathbb{R}$. Let $\mathcal{S}$ be a
distribution over $\mathbb{Z}^{n}$ where all elements in the support have
fixed norm $r$. Suppose there is no
$T+\mathsf{poly}(n,m,\log(\lambda),\log(q))$ time distinguisher between the
distributions
$\mathsf{CLWE}(m,D_{1}^{n},\frac{1}{r}\cdot\mathcal{S},\gamma,\beta)$ and
$D_{1}^{n\times m}\times U(\mathbb{T}_{1}^{m})$. Then, there is no $T$-time
distinguisher between the distributions
$\mathsf{LWE}(m,\mathbb{T}_{q}^{n},\mathcal{S},D_{\sigma})$ and
$U(\mathbb{T}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$, with an additive
advantage loss of $\mathsf{negl}(\lambda)$, where

$\displaystyle\gamma$ $\displaystyle=r\cdot\sqrt{\ln n+\ln
m+\omega(\log\lambda)},$ $\displaystyle\sigma$ $\displaystyle=\beta\cdot q.$

###### Proof.

Suppose we have one sample $(\mathbf{a},b)$, from either
$\mathsf{CLWE}(m,D_{1}^{n},\frac{1}{r}\cdot\mathcal{S},\gamma,\beta)$ or
$D_{1}^{n\times m}\times U(\mathbb{T}_{1}^{m})$. Now, consider the sample
$(\mathbf{a}\cdot\tau\cdot q\pmod{q},b\cdot q\pmod{q})$, where
$\tau=\sqrt{\ln(n)+\ln(m)+\omega(\log\lambda)}$ and $\gamma=r\cdot\tau$. Let
$\mathbf{s}\sim\frac{1}{r}\cdot S$ be the CLWE secret, and let
$\mathbf{a}^{\prime}=\mathbf{a}\cdot\tau\cdot q$, let $e^{\prime}=e\cdot q$,
and let $\mathbf{s}^{\prime}=r\cdot\mathbf{s}\in\mathbb{Z}^{n}$. If
$(\mathbf{a},b)$ is from the CLWE distribution, then we have (taking all
components mod $q$)

$\displaystyle(\mathbf{a}\cdot\tau\cdot q,b\cdot q)$
$\displaystyle=(\mathbf{a}^{\prime},(\gamma\cdot\langle\mathbf{s},\mathbf{a}\rangle+e)\cdot
q)$
$\displaystyle=(\mathbf{a}^{\prime},\gamma\cdot\langle\mathbf{s},q\cdot\mathbf{a}\rangle+e^{\prime})$
$\displaystyle=(\mathbf{a}^{\prime},\frac{\gamma}{r\cdot\tau}\cdot\langle
r\cdot\mathbf{s},\tau\cdot q\cdot\mathbf{a}\rangle+e^{\prime})$
$\displaystyle=(\mathbf{a}^{\prime},\langle r\cdot\mathbf{s},\tau\cdot
q\cdot\mathbf{a}\rangle+e^{\prime})$
$\displaystyle=(\mathbf{a}^{\prime},\langle\mathbf{s}^{\prime},\mathbf{a}^{\prime}\rangle+e^{\prime})$
$\displaystyle=(\mathbf{a}^{\prime},\langle\mathbf{s}^{\prime},\mathbf{a}^{\prime}\pmod{q}\rangle+e^{\prime}).$

Note that $\mathbf{s}^{\prime}=\mathbf{s}\cdot r\sim\mathcal{S}$ and
$e^{\prime}=e\cdot q\sim D_{\beta\cdot q}$, so $\mathbf{s}^{\prime}$ and
$\mathbf{e}^{\prime}$ have the right distribution. Lastly,
$\mathbf{a}^{\prime}=\tau\cdot q\cdot\mathbf{a}\sim D_{\tau\cdot q}^{n}$, so
by Lemma 4, $\mathbf{a}^{\prime}\pmod{q}$ is $\mathsf{negl}(\lambda)/m$-close
to $\mathbb{T}_{q}^{n}$ as long as
$q\cdot\tau\geq\eta_{\mathsf{negl}(\lambda)/m}(q\cdot\mathbb{Z}^{n})$, which
holds by Lemma 2 by construction of $\tau$. Thus, taking the triangle
inequality over all $m$ samples, the resulting distribution is
$\mathsf{negl}(\lambda)$-close to
$\mathsf{LWE}(m,\mathbb{T}_{q}^{n},\mathcal{S},D_{\sigma})$ where
$\sigma=\beta\cdot q$.

Lastly, if $(\mathbf{a},b)$ is from the null distribution, then clearly
$b\cdot q\sim\mathbb{T}_{q}$, and by the same argument as above,
$\mathbf{a}^{\prime}\pmod{q}$ is $\mathsf{negl}(\lambda)/m$-close to
$\mathbb{T}_{q}^{n}$, which by the triangle inequality, implies the resulting
distribution is $\mathsf{negl}(\lambda)$-close to $U(\mathbb{T}_{q}^{n\times
m}\times\mathbb{T}_{q}^{m})$, as desired. ∎

######  Lemma 22 (Reverse of Lemma 16).

Let $n,m,q\in\mathbb{N}$, $\sigma\in\mathbb{R}$. Let $\mathcal{S}$ be a
distribution over $\mathbb{Z}^{n}$ where all elements in the support have
fixed norm $r$, and suppose that

$\sigma\geq 3r\sqrt{\ln n+\ln m+\omega(\log\lambda)}.$

Suppose there is no $T+\mathsf{poly}(m,n,\log(\lambda),\log(q))$-time
distinguisher between the distributions
$\mathsf{LWE}(m,\mathbb{T}_{q}^{n},\mathcal{S},D_{\sigma})$ and
$U(\mathbb{T}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$. Then, there is no
$T$-time distinguisher between the distributions
$\mathsf{LWE}(m,\mathbb{Z}_{q}^{n},\mathcal{S},D_{\sigma^{\prime}})$ and
$U(\mathbb{Z}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$ with an additive
$\mathsf{negl}(\lambda)$ advantage loss, where we set

$\sigma^{\prime}=\sqrt{\sigma^{2}+9r^{2}(\ln n+\ln
m+\omega(\log\lambda))}=O(\sigma).$

###### Proof.

Suppose we are given a sample $(\mathbf{a},b)$ from either
$\mathsf{LWE}(m,\mathbb{T}_{q}^{n},\mathcal{S},D_{\sigma})$ or
$U(\mathbb{T}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$. Let
$\mathbf{a}^{\prime}\sim D_{\mathbb{Z}^{n}-\mathbf{a},\tau}$, where
$\tau=\sqrt{\ln(n)+\ln(m)+\omega(\log\lambda)}$. Let
$\mathbf{a}^{\prime\prime}=\mathbf{a}+\mathbf{a}^{\prime}\pmod{q}$, and
observe that
$\mathbf{a}^{\prime\prime}=\mathbf{a}+\mathbf{a}^{\prime}\pmod{q}\in\mathbb{Z}_{q}^{n}$,
as $\mathbf{a}^{\prime}$ is supported on $\mathbb{Z}^{n}-\mathbf{a}$. Now,
consider the sample $(\mathbf{a}^{\prime\prime},b)$. Let
$\mathbf{s}\sim\mathcal{S}$ be the LWE secret. If this is from the LWE
distribution, we have

$\displaystyle(\mathbf{a}^{\prime\prime},b)$
$\displaystyle=(\mathbf{a}^{\prime\prime},\langle\mathbf{s},\mathbf{a}\rangle+e)$
$\displaystyle=(\mathbf{a}^{\prime\prime},\langle\mathbf{s},\mathbf{a}^{\prime\prime}-\mathbf{a}^{\prime}\rangle+e)$
$\displaystyle=(\mathbf{a}^{\prime\prime},\langle\mathbf{s},\mathbf{a}^{\prime\prime}\rangle-\langle\mathbf{s},\mathbf{a}^{\prime}\rangle+e)$
$\displaystyle=(\mathbf{a}^{\prime\prime},\langle\mathbf{s},\mathbf{a}^{\prime\prime}\rangle+e^{\prime}),$

where we define $e^{\prime}=e-\langle\mathbf{s},\mathbf{a}^{\prime}\rangle$.
First, let’s analyze the distribution of $e^{\prime}$. By applying Lemma 3,
since $\mathbf{s}$ has norm $r$, we know that $e^{\prime}$ is
$\mathsf{negl}(\lambda)/m$ close to $D_{\sigma^{\prime}}$ where

$\sigma^{\prime}=\sqrt{\sigma^{2}+r^{2}\tau^{2}}=\sqrt{\sigma^{2}+r^{2}(\ln(n)+\ln(m)+\omega(\log\lambda)},$

as long as

$\eta_{\mathsf{negl}(\lambda)/m}(\mathbb{Z}^{n})\leq\frac{1}{\sqrt{1/\tau^{2}+(r/\sigma)^{2}}},$

which holds if
$\tau,\sigma/r\geq\sqrt{2}\cdot\eta_{\mathsf{negl}(\lambda)/m}(\mathbb{Z}^{n})$,
which it does by Lemma 2 and construction of $\tau$ and our condition on
$\sigma$. Therefore, by the triangle inequality over all $m$ samples, the
errors look $\mathsf{negl}(\lambda)$-close to $D_{\sigma^{\prime}}$.

Now, we consider the distribution of
$\mathbf{a}^{\prime\prime}=\mathbf{a}+\mathbf{a}^{\prime}\pmod{q}\in\mathbb{Z}_{q}^{n}$.
Note that the lattice $\mathbb{Z}^{n}+\mathbf{a}$ depends only on
$\mathbf{a}\pmod{1}$, so given $\mathbb{Z}^{n}+\mathbf{a}$, the conditional
distribution on $\mathbf{a}$ is $U(\mathbb{Z}_{q}^{n}+(\mathbf{a}\pmod{1}))$.
Therefore, by a one-time pad argument, the distribution of
$\mathbf{a}+\mathbf{a}^{\prime}$ is exactly $U(\mathbb{Z}_{q}^{n})$, even
conditioned on $\mathbf{a}^{\prime}$. Therefore,
$(\mathbf{a}^{\prime\prime},\langle\mathbf{s},\mathbf{a}^{\prime\prime}\rangle+e^{\prime})$
looks $\mathsf{negl}(\lambda)/m$-close to a sample from
$\mathsf{LWE}(m,\mathbb{Z}_{q}^{n},\mathcal{S},D_{\sigma^{\prime}})$, which by
the triangle inequality over $m$ samples, makes the resulting distribution
$\mathsf{negl}(\lambda)$-close to
$\mathsf{LWE}(m,\mathbb{Z}_{q}^{n},\mathcal{S},D_{\sigma^{\prime}})$.

Lastly, suppose $(\mathbf{a},b)$ is from the null distribution. Then by (a
simpler version of) the above argument, the distribution of
$\mathbf{a}^{\prime\prime}$ is given by $\mathbf{a}^{\prime\prime}\sim
U(\mathbb{Z}_{q}^{n})$, making $(\mathbf{a},b)\sim
U(\mathbb{Z}_{q}^{n}\times\mathbb{T}_{q})$, as desired. ∎

Now we are ready to prove Theorem 11.

###### Proof of Theorem 11.

Suppose there is no $T+\mathsf{poly}(n,m,\log(q),\log(\lambda))$ time
distinguisher between
$\mathsf{CLWE}(m,D_{1}^{n},\frac{1}{r}\cdot\mathcal{S},\gamma,\beta)$ and
$D_{1}^{n\times m}\times U(\mathbb{T}^{m})$ with advantage at least
$\epsilon-\mathsf{negl}(\lambda)$. Then, by Lemma 21, there is no
distinguisher between
$\mathsf{LWE}(m,\mathbb{T}_{q}^{n},\mathcal{S},D_{\sigma})$ and
$U(\mathbb{T}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$, where
$\gamma=r\sqrt{\ln(n)+\ln(m)+\omega(\log\lambda)}$ and $\sigma=\beta\cdot q$.
Then, by Lemma 22, there is no $T$-time distinguisher between
$\mathsf{LWE}(m,\mathbb{Z}_{q}^{n},\mathcal{S},D_{\sigma^{\prime}})$ and
$U(\mathbb{Z}_{q}^{n\times m}\times\mathbb{T}_{q}^{m})$ with advantage
$\epsilon$, where $\sigma^{\prime}=O(\sigma)$, as long as $\sigma=\beta\cdot
q\geq 3r\sqrt{\ln n+\ln m+\omega(\log\lambda)}$. ∎


# Two dimensional LiMgAs; a novel Topological Quantum Catalyst for Hydrogen
Evolution Reaction

Raghottam M. Sattigeri  Prafulla K. Jha<EMAIL_ADDRESS>Department of
Physics, Faculty of Science, The Maharaja Sayajirao University of Baroda,
Vadodara-390002, Gujarat, India  Piotr Śpiewak  Materials Design Division,
Faculty of Materials Science and Engineering, Warsaw University of Technology,
141 Wołoska Str., 02-507 Warsaw, Poland  Krzysztof J. Kurzydłowski  Faculty of
Mechanical Engineering, Białystok University of Technology, 45C Wiejska Str.,
15-351, Białystok, Poland

###### Abstract

Quantum materials such as Topological Insulators (TI) have been promising due
to diverse applications of their robust surface/edge states in the bulk (3D)
and two-dimensional (2D) regime. Such conducting surface states in 3D systems,
host "electron bath" which are known to facilitate catalysis. However, the
analogous effects in 2D scenarios wherein, conducting helical edge states
giving rise to Fermionic accumulation has been scarcely addressed. Using
density functional theory based first-principles calculations, we demonstrate
that, the conducting edge states in 2D TI such as LiMgAs can be exploited to
facilitate excellent catalytic response towards Hydrogen evolution reactions.
The Gibbs free energy in such cases was found to be as low as $-$0.02 eV which
is quite superior as compared to other materials reported in literature. The
concept presented herein can be extended to other well known 2D TI and used to
realise novel topological quantum catalysts for ultra-high performance and
efficient catalytic applications.

2D Topological Insulators, Topological Catalyst, DFT

Figure 1:  (a,b) The unit cells of 2D LiMgAs indicating the structural
parameters such as, lattice constant (a) and the angle between atoms at, 0%
stress and 10% biaxial compressive stress. The correspinding monolayer
thickness (h) is 1.60 Å and 1.95 Å respectively. (c) The hexagonal BZ of 2D
LiMgAs superimposed with the orthorhombic BZ of LiMgAs obtained by using the
rotation transformation matrix (R) and presented in (d). (e-h) Energy versus
time and temperature versus time plots of the AIMD simulations of 2D LiMgAs
under, pristine conditions (0% strain) and at 10% compressive stress for 2
picoseconds (3000 femtoseconds) with thermostat set at 300 K.

With increase in global energy demands, realising efficient and clean energy
generation has attained great importance over the past few decades.Obama
(2017); Seh  _et al._ (2017); Ding  _et al._ (2019) To this effect, generation
of energy using Hydrogen-rich resources has proven to be effective with
prominant use of Platinum group metals such as, Pt, Ru, Rh, Ir and Pd as a
catalysts towards Hydrogen evolution reaction (HER).Zeng and Li (2015)
However, the major issue is, the cost, rarity and short lifetime of electrodes
associated with the Platinum group metals. This motivated search for other
cost-effective and abundant alternatives. Till date, combination of metals
(such as, Pt, Pd, Ir, Ru, Au, Ni), binary metal alloys, 3d transition metal
hydroxides, phosphides, carbides and transition metal chalcogenides, nitrides,
borides, oxides and sulphides have been proposed as cost-effective
alternatives.Zeng and Li (2015); Strmcnik  _et al._ (2016) However, their
efficiency and performance are governed by the pH of surrounding media (with
qualitative and quantitative differences in acidic and alkaline
media).Strmcnik  _et al._ (2016)

The major factor affecting the catalytic activity, efficiency and performance
of such materials is surface states which arise from; [111] surfaces of noble
metals and dangling bonds on semi-conductor surface significantly affecting
the physio-chemical processes occuring on the surfaces.Chen  _et al._ (2011)
This is due to the spatial proximity and orbital natures across the Fermi
level. Such states are quite sensitive and not robust against; minor local
deviations/variations (due to impurities and defects), surface deterioration
(owing to redox reactions and corresponding degradation) altering the atomic
termination and crystal orientations.Chen  _et al._ (2011) Apart from these
factors as proposed by Gerischer and Parson,Sabatier (1920); Gerischer (1958);
Parsons (1958); Quaino  _et al._ (2014) the requirement arising from the
Sabatier’s principle pertaining to the Gibb’s free energy ($\Delta$G) i.e.,
thermoneutral condition with $\Delta$G $=$ 0 (yeilding optimal exchange
current densities) is another major challenge. Realising materials which are
capable of efficiently addressing the said physio-chemical problems has been
the most challengning task from materials design point of view.

With this background, topological quantum materials (such as, topological
insulators (TI), topological (Dirac, Weyl, nodal line) semimetals (TSM))
appear to be the most promising materials which can address the problems with
existig catalysts.Xie  _et al._ (2022) The character which makes them stand
out from existing catalysts is, conducting surface/edge states and Fermi arcs
(which are relatively robust against mild impurities (magnetic/non-magnetic),
surface oxidations and degradations) ensuring relatively longer life-times of
catalysts and exchange of high mobility electrons facilitating HER.Xie  _et
al._ (2022) This approach was first proposed in 2011 wherein, CO and O2
adsorptions over gold-covered TI Bi2Se3 surface were investigated; with
emphasis on the persistance of surface states as long as the bulk gap is
retained owing to the time-reversal symmetry.Chen  _et al._ (2011) It was
expected that, such design strategy would establish alternatives to
conventional d-band theory of heterogeneous catalysis. However, ever since
then, the interest in exploring topological quantum catalysts (TCat) made up
of TI and TSM had almost quenched until, recently; when the field was revived
with new perspectives for exploraing heterogenous catalysts based on, TSM,
Chiral crystals, Full/Half-Heusler alloys and Perovskite manganites.Li and
Felser (2020)

TSM might be promising TCat but, in some scenarios such as, Dirac and Weyl
semimetals, the weak electrostatic screening strength gives rise to lower
carrier densities around the Fermi level making them less reliable.Wang  _et
al._ (2017a) This motivatd us to revisit and investigate heterogenous
catalysis in two dimensional (2D) TI which are known to host high carrier
mobilities, high carrier densities across Fermi level and robust charge
accumulations along the edges. In this letter we report excellent catalytic
properties of 2D TI LiMgAs investigated using Density Functional Theory (DFT).
This system has been previously investigated by us for its TI nature which can
be dimensionally engineered from the [111] crystal plane of bulk Half-Heusler
(HH) compound LiMgAs.Sattigeri and Jha (2021) Here, we explore two types of
edge sites, (a) along the [100] plane and (b) along the [010] plane of 2D TI
LiMgAs. We find that, the catalytic activity and performance is persistent
along the edges and gets enhanced when spin-orbit coupling (SOC) is included.
With this effort, we believe that, dimensionally engineered 2D TI from
different planes of the HH compounds can be explored as candidate TCat. This
approach has potential of discovering large number of materials since, several
HH compounds have been predicted and realised experimentally till date owing
to the permutations and combinations of the s$-$ and p$-$ block elements which
typically make up HH compounds.Graf, Felser, and Parkin (2011); Casper  _et
al._ (2012); Yan and de Visser (2014); Felser  _et al._ (2015) TCat would thus
translate as an alternative to the conventional d$-$band theory and single
atom catalysis for varied applications.

We performed Density Functional Theory based first-principles calculations
using Quantum ESPRESSO.Giannozzi  _et al._ (2009) For calculations without
SOC, we use scalar-relativistic and norm-conserving Martins-Troullier
pseudopotentials and for calculations with SOC, we use fully-relativistic
Projector Augemented Wave (PAW) pseudopotentials. The generalized gradient
approximation was implemented with Perdew-Burke-Ernzerhof type of exchange-
correlation functional.Perdew, Burke, and Ernzerhof (1996); Blöchl (1994) We
used the hexagonal unit cell from the previous work and transformed it into
orthorhombic unit cell using the rotation matrix (R) which transforms the
hexagonal basis vector into orthorhombic basis vector (as evident from Fig.
1). This orthorhombic unit cell was then transformed into nanoribbons (with
ribbon width N = 15 to avoid edge-edge interactions) which are periodic along,
(a) [100] and (b) [010] crystal directions with zig-zag and planar like edges
respectively (presented in Fig. 2(c,d)). The corresponding uniform momentum
Monkhorst-Pack grid (k-mesh) for brillouin zone (BZ) sampling was set to be 1
$\times$ 6 $\times$ 1 and 6 $\times$ 1 $\times$ 1 respectively.Monkhorst and
Pack (1976) A vacuum of 25 Å along the [001] direction and 17 Å along the
aperiodic directions in the nanoribbon configurations was imposed to avoid
interactions due to periodic images. We also performed the calculations with 3
$\times$ 3 $\times$ 1 supercell of 2D LiMgAs (with 25 Å vacuum along the [001]
crystal direction) with k-mesh for BZ sampling as 6 $\times$ 6 $\times$ 1\.
The optimized kinetic energy cutoff used in all the calculations was set to 60
Ry and the systems were relaxed with force convergence criteria of $<$ 10-6
a.u. Throughout the calculations, Grimme correlations were incorporated to
address the van der Waals effects.Grimme (2006) From the perspective of
stability and room temperature viability, we performed ab initio molecular
dynamics simulations (AIMD) for 3 picoseconds (3000 femtoseconds) with
thermostat set at 300 K. We calculate the slab band structures using
WannierTools wherein the tight-binding Hamiltonian generated by Wannier90 is
implemented.Wu  _et al._ (2018); Mostofi  _et al._ (2008)

Figure 2:  (a) Electronic band structure with SOC at 0% and 10% biaxial
compressive stress alongside the charge densities of bands I, II and III. (b)
Slab band structure indicating the semi-metallic edge sites. (c,d) Zig-zag
(periodic along [010] crystal direction) and Planar (periodic along [100]
crystal direction) terminations of the nanoribbons (alongwith lattice
parameters) and their corresponding edge Fermionic accumulations.

The work presented in this letter builds up on 2D TI LiMgAs which is designed
dimensionally and exhibits non-trivial topology engineered by application of
biaxial stress. Under pristine conditions (without any pressure), 2D LiMgAs is
characterised by a structure similar to 1T-MoS2 with, As atoms forming a
hexagonal lattice occupying the octahedral coordinations between two layers of
hexagonal-closed-packed structures made up of Li and Mg (as presented in Fig.
1(a)). Such arragnement is governed by the P$\overline{3}$m1 space group and
the octahedral belongs to the D3d tetragonal symmetry.Jayabal  _et al._ (2018)
At around 10% biaxial compressive stress the structural intigrity is retained
(as evident from Fig. 1(b)) however, the system undergoes a quantum
topological phase transition from a trivial insulator to a non-trivial TI. We
assess the stability and viability of these systems at room temperature (300
K) by performing AIMD calculations. As evident from Fig. 1(e) the pristine
structure of LiMgAs (at 0% stress) thermalises and is stable throughout the
simulation. However, the system at 10% biaxial compressive stress has large
fluctuations in energy (as evident from Fig. 1(g)) initially but, after 1.5
picoseconds (highlighted by blue line in Fig. 1(g)) of simulations, the system
thermalises; attaining structural stability which is evident from small energy
fluctuations thereafter. The corresponding thermostat variations in both the
cases are also presented in Fig. 1(f,h).

Figure 3:  HER mechanism involving the primary Volmer reaction and the
secondary reactions (Volmer-Heyrovsky and Volmer-Tafel) along the edge sites
of, (a) Zig-zag and (b) Planar terminations of the LiMgAs nanoribbon.

We briefly discuss the topological properties of 2D LiMgAs. Figure 2(a)
presents the electronic band structure of 2D LiMgAs at 0% and 10% biaxial
compressive stress under the SOC regime. Apart from the s$-$, p$-$ orbital
inversion mechanism which has been previously discussed, we observe exchange
of charge densities across the Fermi level. This exchange is clearly evident
from the charge densities of bands I, II and III at 0% and 10% biaxial
compressive stress which reafirms the non-trivial topological phase
transitions. At 0% stress, the band gap of the system under SOC is 1.49 eV
whereas, upon quantum phase transition (at 10% stress) it turns out to be 0.16
eV which indicates that 2D LiMgAs exhibits a non-trivial large-gap which is
superior to several materials.Zhao and Wang (2020) This implies that, the edge
states would be robust even at room temperature. Also due to, high velocity of
Fermions, 2D LiMgAs crops up as an interesting candidate for catalytic
applications. Figure 2(b) exhibits the slab band structure calculated using
the tight-binding Hamiltonian model. It is clear that, the edge sites host a
non-trivial semi-metallic character while the band structure hosts a SOC
induced gap at 10% biaxial compressive stress.

With the help of rotation matrix (R) we transform the hexagonal unit cell into
an orthorhombic unit cell at 10% biaxial compressive stress (as presented in
Fig. 1(b,d)). Using this orthorhombic phase, we design two nanoribbon
configurations with, (a) zig-zag and (b) planar like edge terminations (by
exploiting the periodicity along [100] and [010] crystal direction). The
nanoribbon configurations presented in Fig. 2(c,d) have formation energies Ef
($=$ E${}_{\textit{LiMgAs}}-$ E${}_{\textit{Li}}-$ E${}_{\textit{Mg}}-$
E${}_{\textit{As}}$, where E${}_{\textit{LiMgAs}}$ is the energy of entire
system and E${}_{\textit{X}}$ with X $=$ Li, Mg, As; is the energy of
constituent elements) $-$2.03 eV/atom and $-$2.90 eV/atom respectively. These
energies are relatively lower as compared to their 2D counterpart which has
formation energy $-$1.70 eV/atom, indicating towards stability and high
probability of formation of nanoribbon configurations. It is also evident from
these configurations (presented in Fig. 2(c,d)) that, the edge sites have
robust Fermionic accumulations owing to the non-trivial topology. These
charactertic properties of 2D TI LiMgAs indicate that, it can potentially host
TCat along the edge sites as compared to the basal sites.

In order to confirm the superior activity along the edge sites as compared to
the basal sites in heterogenous catalysis such as HER and to affirm TCat, we
begin our calculations on a 3 $\times$ 3 $\times$ 1 supercell of the hexagonal
2D TI LiMgAs which exposes the basal sites for HER. We begin our
investigations with the primary Volmer reaction on different sites such as,
top (of Li, Mg, As) and bridge sites (such as, Li-Mg, Mg-As, Li-As). Governed
by Sabatier’s principle, the interaction of Hydrogen (H) atom during the
primary reaction should be optimal (i.e., the atom should interact neither
strongly nor weakly with the catalytic surface). This implies that during the
primary reaction (under neutral pH and reduction potential U $=$ 0), the
parameters such as, adsorption energy ($\Delta$E${}_{H}^{ads}=$
E${}_{LiMgAs+H}-$ E${}_{LiMgAs}-\frac{1}{2}$E${}_{H_{2}}$) where, ELiMgAs+H is
the total energy of H adsorbed LiMgAs, E${}_{\textit{LiMgAs}}$ is the total
energy of LiMgAs and E${}_{H_{2}}$ is the total energy of H2 molecule) and
Gibbs free energy ($\Delta$G${}_{H}=\Delta$E${}_{H}^{ads}+\Delta_{ZPE}-$
T$\Delta$S where, $\Delta_{ZPE}$ is the change in the zero-point energy of
adsorbed and gaseous state of H and $\Delta$S is the corresponding change in
the entropy and T is room temperature) should ideally be 0.24 eV and 0 eV
respectively.Lee, Jun, and Lee (2017) However, in our case, during the primary
reaction, the As site was found to be the most active site amongst all the
basal sites with adsorption and Gibbs free energy without SOC (with SOC) as
$-$2.38 eV ($-$2.46 eV) and $-$2.14 eV ($-$2.22 eV) respectively (see
Supplementary Information (SI), Tab. 1 for other sites). This implies that the
basal site strongly interacts with the adsorbed H indicating that the basal
sites wont be ideal catalysts.

In sharp contrast to the interactions at basal sites, the edge sites exhibit
excellent activity during the primary reaction due to robust Fermionic
accumulations. The different reaction mechanisms investigated herein are
presented in Fig. 3(a,b) for both zig-zag and planar termination
configurations of nanoribbons. The sites investigated for HER were, top (Li,
Mg, As) and bridge sites (Li-As, Mg-As). During primary reaction, the most
active sites in the zig-zag and planar configurations without SOC (with SOC)
are, As (As and Li-As) and As (As, Li) respectively. The most ideal adsorption
and Gibbs free energy in the zig-zag configuration (under SOC) was found to
be, $-$0.264 eV and $-$0.024 eV at As top site and, $-$0.26 eV and $-$0.02 eV
at Li-As bridge site respectively (see SI, Tab. 2, for other sites).
Similarly, for planar configuration the most ideal adsorption and Gibbs free
energy (under SOC) was found to be, $-$0.213 eV and 0.026 eV at Li top site
and, $-$0.212 eV and 0.027 eV at As top site respectively (see SI, Tab. 4, for
other sites). To further assure and associate the origin of such excellent
catalytic activity to the topological edge states, we performed calculations
for primary reaction at the mid site of nanoribbons, specifically, on top of
those sites which exhibit minimum Gibbs free energy under SOC (along the
edges). We found that, in both the configurations i.e., zig-zag and planar,
the interaction was of repelling nature with adsorption energy 0.118 eV and
0.679 eV respectively, while the corresponding Gibbs free energy were, 0.358
eV and 0.919 eV respectively. This firmly established the fact that, the
superior catalytic behaviour indeed originates from the topologically robust
edge sites.

We now proceed with the secondary reaction mechanisms which are Volmer-
Heyrovsky (the H adsorbed in primary reaction interacts with a H+ ion and
evolves into H2) and Volmer-Tafel (the H adsorbed in primary reaction
interacts with a neighbouring H and evolves into H2) along the optimal sites
in both the zig-zag and planar configurations of the nanoribbons as presented
in Fig. 3(a(i,ii), b(i,ii)) respectively. The adsorption and Gibbs free energy
fomalism for Volmer-Heyrovsky intermediate reaction is slightly modified and
given by, $\Delta$E${}_{H^{*}}^{ads}(n)(=(\frac{1}{n}$ E${}_{LiMgAs+nH^{*}}-$
E${}_{LiMgAs}-$ $\frac{n}{2}$E${}_{H_{2}}$) and
$\Delta$G${}_{H^{*}}(n)(=\Delta$E${}_{H^{*}}^{ads}(n)+\Delta_{ZPE}-$
T$\Delta$S) respectively with n $=$ 2 and terms having their usual
meaning.Lee, Jun, and Lee (2017) For Volmer-Tafel intermediate reactions, we
follow the modified formalism proposed by Lee et.al.Lee, Jun, and Lee (2017)

Figure 4:  Volcano plot generated here is based on our recomputations using,
exchange current densities (for rate constant k${}_{0}=$ 1 s-1 site-1,
according to Nørskov’s assumptions)Nørskov  _et al._ (2005) and Gibbs free
energy data from literature for various materials (see SI, Tab. 6 for
details).Seh  _et al._ (2017); Wang  _et al._ (2017b); Qu  _et al._ (2021);
Zhao  _et al._ (2020); Liu  _et al._ (2022); Hinnemann  _et al._ (2005); Li
_et al._ (2018); He  _et al._ (2019); Kong  _et al._ (2021); Yang  _et al._
(2021); Ekspong, Gracia-Espino, and Wagberg (2020); Yang  _et al._ (2020);
Wang  _et al._ (2021); Nørskov  _et al._ (2005) It is evident that, LiMgAs
outperforms other topological materials placing it closer to the Sabatiers
optimum (highlighted in yellow).

We find that, the zig-zag configuration facilitates both the secondary
reactions Volmer-Heyrovsky and, Volmer-Tafel (as evident from Fig. 3(a(i,ii)))
based on the adsorption and Gibbs free energy which are, $-$0.201 eV and 0.03
eV and, $-$0.296 eV and $-$0.05 eV respectively. Based on the Gibbs free
energy, it is evident that, the Volmer-Heyrovsky and Volmer-Tafel mechanisms
are exothermic and endothermic in nature respectively. However, the planar
configuration only facilitates the Volmer-Heyrovsky reaction along the optimal
sites As and Li (as evident from Fig. 3(b(i,ii))) with similar adsorption and
Gibbs free energy of $-$0.53 eV and $-$0.29 eV respectively. Hence, the zig-
zag configuration is highly sensitive towards HER as compared to the planar
configuration. Overall, we observe that, the edge sites favour HER rather than
basal sites. Such superior activity towards HER places 2D TI LiMgAs at the top
of volcano plot closer to Sabatier’s optimum (as evident from Fig. 4) with
Gibbs free energy as low as $-$0.02 eV; giving rise to exchange current
density (Log${}_{10}(i_{0})$) of the order of $-$0.5 Acm-2. Also, the positive
Gibbs free energy at certain sites (see SI) thermodynamically favours and
readily facilitates HER. These features make 2D TI LiMgAs a novel candidate
for catalytic applications.

In summary, we propose that, 2D topological materials such as 2D TI can be
novel quantum catalysts owing to their non-trivial and robust topologies
(providing high density charge accumulation and carrier mobility) alongside
high surface-to-volume ratio. In this letter we discuss the case of 2D TI
LiMgAs which exhibits excellent catalytic activity towards HER. We propose
that, multilayered structures of such 2D materials can be designed to create
surfaces with such excellent catalytic properties. Also, we suggest that,
large-gap TI would perform better at room temperature due to the persistence
of edge states at such conditions.

## REFERENCES

## References

  * Obama (2017) B. Obama, Science 355, 126–129 (2017).
  * Seh  _et al._ (2017) Z. W. Seh, J. Kibsgaard, C. F. Dickens, I. Chorkendorff, J. K. Nørskov, and T. F. Jaramillo, Science 355, eaad4998 (2017).
  * Ding  _et al._ (2019) S. Ding, M. J. Hülsey, J. Pérez-Ramírez, and N. Yan, Joule 3, 2897–2929 (2019).
  * Zeng and Li (2015) M. Zeng and Y. Li, Journal of Materials Chemistry A 3, 14942–14962 (2015).
  * Strmcnik  _et al._ (2016) D. Strmcnik, P. P. Lopes, B. Genorio, V. R. Stamenkovic, and N. M. Markovic, Nano Energy 29, 29–36 (2016).
  * Chen  _et al._ (2011) H. Chen, W. Zhu, D. Xiao, and Z. Zhang, Physical review letters 107, 056804 (2011).
  * Sabatier (1920) P. Sabatier, (1920).
  * Gerischer (1958) H. Gerischer, Bulletin des Sociétés Chimiques Belges 67, 506–527 (1958).
  * Parsons (1958) R. Parsons, Transactions of the Faraday Society 54, 1053–1063 (1958).
  * Quaino  _et al._ (2014) P. Quaino, F. Juarez, E. Santos, and W. Schmickler, Beilstein journal of nanotechnology 5, 846–854 (2014).
  * Xie  _et al._ (2022) R. Xie, T. Zhang, H. Weng, and G.-L. Chai, Small Science , 2100106 (2022).
  * Li and Felser (2020) G. Li and C. Felser, Applied Physics Letters 116, 070501 (2020).
  * Wang  _et al._ (2017a) S. Wang, B.-C. Lin, A.-Q. Wang, D.-P. Yu, and Z.-M. Liao, Advances in Physics: X 2, 518–544 (2017a).
  * Sattigeri and Jha (2021) R. M. Sattigeri and P. K. Jha, Scientific Reports 11, 1–10 (2021).
  * Graf, Felser, and Parkin (2011) T. Graf, C. Felser, and S. S. Parkin, Progress in solid state chemistry 39, 1–50 (2011).
  * Casper  _et al._ (2012) F. Casper, T. Graf, S. Chadov, B. Balke, and C. Felser, Semiconductor Science and Technology 27, 063001 (2012).
  * Yan and de Visser (2014) B. Yan and A. de Visser, MRS Bulletin 39, 859–866 (2014).
  * Felser  _et al._ (2015) C. Felser, L. Wollmann, S. Chadov, G. H. Fecher, and S. S. Parkin, APL materials 3, 041518 (2015).
  * Giannozzi  _et al._ (2009) P. Giannozzi, S. Baroni, N. Bonini, M. Calandra, R. Car, C. Cavazzoni, D. Ceresoli, G. L. Chiarotti, M. Cococcioni, I. Dabo, _et al._ , Journal of physics: Condensed matter 21, 395502 (2009).
  * Perdew, Burke, and Ernzerhof (1996) J. P. Perdew, K. Burke, and M. Ernzerhof, Physical review letters 77, 3865 (1996).
  * Blöchl (1994) P. E. Blöchl, Physical review B 50, 17953 (1994).
  * Monkhorst and Pack (1976) H. J. Monkhorst and J. D. Pack, Physical review B 13, 5188 (1976).
  * Grimme (2006) S. Grimme, Journal of computational chemistry 27, 1787–1799 (2006).
  * Wu  _et al._ (2018) Q. Wu, S. Zhang, H.-F. Song, M. Troyer, and A. A. Soluyanov, Computer Physics Communications 224, 405–416 (2018).
  * Mostofi  _et al._ (2008) A. A. Mostofi, J. R. Yates, Y.-S. Lee, I. Souza, D. Vanderbilt, and N. Marzari, Computer physics communications 178, 685–699 (2008).
  * Jayabal  _et al._ (2018) S. Jayabal, J. Wu, J. Chen, D. Geng, and X. Meng, Materials today energy 10, 264–279 (2018).
  * Zhao and Wang (2020) A. Zhao and B. Wang, APL Materials 8, 030701 (2020).
  * Lee, Jun, and Lee (2017) C. H. Lee, B. Jun, and S. U. Lee, RSC advances 7, 27033–27039 (2017).
  * Nørskov  _et al._ (2005) J. K. Nørskov, T. Bligaard, A. Logadottir, J. Kitchin, J. G. Chen, S. Pandelov, and U. Stimming, Journal of The Electrochemical Society 152, J23 (2005).
  * Wang  _et al._ (2017b) P. Wang, X. Zhang, J. Zhang, S. Wan, S. Guo, G. Lu, J. Yao, and X. Huang, Nature communications 8, 1–9 (2017b).
  * Qu  _et al._ (2021) Q. Qu, B. Liu, W. S. Lau, D. Pan, and I. K. Sou, arXiv preprint arXiv:2112.04753 (2021).
  * Zhao  _et al._ (2020) X. Zhao, X. Yang, D. Singh, P. K. Panda, W. Luo, Y. Li, and R. Ahuja, The Journal of Physical Chemistry C 124, 7884–7892 (2020).
  * Liu  _et al._ (2022) W. Liu, X. Zhang, W. Meng, Y. Liu, X. Dai, and G. Liu, Iscience 25, 103543 (2022).
  * Hinnemann  _et al._ (2005) B. Hinnemann, P. G. Moses, J. Bonde, K. P. Jørgensen, J. H. Nielsen, S. Horch, I. Chorkendorff, and J. K. Nørskov, Journal of the American Chemical Society 127, 5308–5309 (2005).
  * Li  _et al._ (2018) J. Li, H. Ma, Q. Xie, S. Feng, S. Ullah, R. Li, J. Dong, D. Li, Y. Li, and X.-Q. Chen, Science China Materials 61, 23–29 (2018).
  * He  _et al._ (2019) Y. He, D. Yan, L. R. Ng, L. Shi, S. Wang, H. Lin, S.-H. Lin, H. Luo, and K. Yan, Materials Chemistry Frontiers 3, 2184–2189 (2019).
  * Kong  _et al._ (2021) X.-P. Kong, T. Jiang, J. Gao, X. Shi, J. Shao, Y. Yuan, H.-J. Qiu, and W. Zhao, The Journal of Physical Chemistry Letters 12, 3740–3748 (2021).
  * Yang  _et al._ (2021) Q. Yang, G. Li, Y. Zhang, J. Liu, J. Rao, T. Heine, C. Felser, and Y. Sun, npj Computational Materials 7, 1–8 (2021).
  * Ekspong, Gracia-Espino, and Wagberg (2020) J. Ekspong, E. Gracia-Espino, and T. Wagberg, The Journal of Physical Chemistry C 124, 20911–20921 (2020).
  * Yang  _et al._ (2020) Q. Yang, G. Li, K. Manna, F. Fan, C. Felser, and Y. Sun, Advanced Materials 32, 1908518 (2020).
  * Wang  _et al._ (2021) L. Wang, X. Zhang, W. Meng, Y. Liu, X. Dai, and G. Liu, Journal of Materials Chemistry A 9, 22453–22461 (2021).