#  First-order commensurate-incommensurate magnetic phase transition in the
coupled FM spin-1/2 two-leg ladders

J. Jahangiri, H. Hadipour, S. Mahdavifar, and S. Farjami Shayesteh  Department
of Physics, University of Guilan, 41335-1914, Rasht, Iran

###### Abstract

We consider the spin-1/2 two-leg ladders with ferromagnetic (FM) interactions
along legs and rungs. Using the stochastic series expansion QMC method, we
study the low-temperature magnetic behavior of the system. An isolated
spin-1/2 FM two-leg ladder is in the gapped saturated FM phase at zero
temperature. As soon as the spin-1/2 FM two-leg ladders are connected with
antiferromagnetic (AFM) inter-ladder interaction, a first-order commensurate-
incommensurate quantum phase transition occurs in the ground state magnetic
phase diagram. In fact a jump in the magnetization curve is observed. We found
that, coupled spin-1/2 FM two-leg ladders are in a nonmagnetic phase at zero
temperature. Applying a magnetic field, the ground state of coupled spin-1/2
FM two-leg ladders remains in the nonmagnetic phase up to a quantum saturate
critical field.

###### pacs:

75.10.Jm; 75.10.Pq

##  I Introduction

Recently, spin-1/2 two-leg ladder systems have devoted considerable growth to
itself experimentally and theoreticallyDagotto ; Uehara ; Fujiwara ; Vanishri
; Plekhanov . The main interest to study of these systems is related to this
fact that the high-Tc superconductivity Uehara ; Fujiwara ; Vanishri
phenomenon occurs in these systems and also they have a gap in the spin
excitation spectrum.

In the study of spin-1/2 two-leg ladder systems with antiferromagnetic (AFM)
leg and rung interactions, the formation of spin singlets located on each rung
open the spin gap in the energy spectrum which is called the gaped spin liquid
phaseDagotto ; Rieira . These kind of AFM two-leg ladder systems are observed
in the natureAzuma ; Ruegg ; Watson ; Hong ; Oosawa ; Giamarchi ; Millet ;
Elfimov ; Korotin ; McCarron ; Siegrist ; Roth ; McElfresh ; Japaridze1 ;
Jahangiri1 . The effect of a magnetic field on the physical properties of
these compounds has been a field of intense studies. It is found that there
are two quantum critical fields in the ground state phase diagram of these
kind of spin-1/2 two-leg ladders. Generally, at low magnetic fields
($h<h_{c_{1}}$), there is a spin liquid phase (a gapped phase) at low
temperature Dagotto . Both magnetic susceptibility and the magnetization go up
first with cooling, then decay exponentially to zero at low temperatures.
Also, the specific heat has a single peak at low temperature due to transition
from disordered phase to the spin singlet gapped phase.Ruegg ; Wang . The
Tomonaga-Luttinger liquid (TLL) gapless phase is found in
$h_{c_{1}}<h<h_{c_{2}}$ regime at low temperaturesRuegg ; Wang . One of the
spin liquid ($h<(h_{c_{1}}+h_{c_{2}})/2$) or spin polarized
($h>(h_{c_{1}}+h_{c_{2}})/2$) phases at higher temperature is expected. The
thermodynamic properties like magnetization and the susceptibility have a
finite value at low temperature which show the vanishing of the energy gap in
the TLL phase. Specific heat shows a second peak and goes down linearly with
lowering temperature in the TLL regime Ruegg .

The spin-1/2 two-leg ladder systems with AFM legs and FM rungs are also
observed from experimental point of viewMasuda05 ; Tsujii09 . By means of the
specific heat and the magnetocaloric effect measurements, a phase boundary
between the spin liquid phase and the ordered phase is determinedTsujii09 . We
have to mention that, the ladders with FM leg and AFM rung exchange
interactions found experimentally during last two yearsYamaguchi13 ;
Yamaguchi14 ; Yamaguchi .

Recently, Nagashiwa and coworker synthesized chlorido-bridged
dinuclearcopper(II) complex with 2-methylisothiazol-3(2H)-one with chemical
formula [Cu(II) Cl(O-mi)2(μ-Cl)2)]Nagasawa . This compound is a quasi-two-leg
ladder system with FM exchange interaction in legs and rungs. The Weiss
temperature is estimated about 8.7 K, indicating ferromagnetic behavior. Also
no exotic phenomena due to spin frustration were observed within the measured
temperature range. From theoretical point of view, spin-1/2 two-leg ladders
with FM legs and rungs are much less studied. In a very recent work, the
temperature dependence of the magnetic susceptibility and the magnetic
structure factors is studied using the modified spin wave theory and the
numerical exact diagonalization techniqueHida12 . They have showed that in an
intermediate temperature range, their analytical results are consistent with
the numerical exact diagonalization results. The need for investigation of AFM
inter-ladder coupling in FM ladders ( FM exchange interaction in both legs and
rungs ) is also motivated by synthesizing the 3-Cl-4-F-V, 3-Br-4-F-V and 3-I-V
crystals recently which are the candidates for two-leg ladders with FM legs
and AFM rungs Yamaguchi13 ; Yamaguchi14 ; Yamaguchi .

In this paper we study the AFM inter-ladder interaction effect between FM two-
leg ladders in the presence of a magnetic field (see Fig. 1). This system for
large inter-ladder interaction can be considered as the ladders with FM legs
and AFM rungs by FM coupling. We used the recently developed stochastic series
expansion (SSE)Sandvik ; Syljuasen  QMC method to provide numerical simulation
results. The magnetization, the susceptibility and the specific heat are
calculated for large enough finite size systems. Our simulation results show
that isolated FM two-leg ladders are in an ordered phase at zero temperature.
As soon as the AFM inter-ladder interaction is added, a first-order
commensurate-incommensurate quantum phase transition occurs from the gapped
ferromagnetic phase to a nonmagnetic phase. By applying a uniform magnetic
field, the ground state of coupled ladders remains in this nonmagnetic phase
up to a saturated critical field.

The outline of the paper is as follows: In section II we introduce our
numerical simulation results for an isolated FM spin-1/2 two-leg ladder. In
section III we consider coupled FM ladders and present results of our QMC
simulation on the low-temperature magnetic behavior of the system. Finally we
conclude and summarize our results in section IV.

Figure 1: The schematic picture of FM two-leg ladders with AFM inter-ladder
interaction. The size of coupled ladders is $10\times 30$.

Figure 2: The spontaneous magnetization as a function of the temperature for
isolated spin-1/2 FM two-leg ladders. As it is seen, at zero temperature the
ground state of the system is in a saturated FM phase. By increasing the
temperature the induced thermal fluctuations decrease the magnetization of the
system. In the inset, the magnetic susceptibility in the absence of the
magnetic field is plotted as a function of the temperature. QMC simulation has
been carried out for Heisenberg model. The size of two-leg ladder is $2\times
100$.

##  II An isolated FM two-leg ladder

In this section we consider a FM spin-1/2 two-leg ladder system in the
presence of an external magnetic field. The Hamiltonian of the system is
written as

$\displaystyle{H}$ $\displaystyle=$ $\displaystyle J_{leg}\sum_{n,\alpha}{\bf
S}_{n,\alpha}\cdot{\bf
S}_{n+1,\alpha}-g\mu_{B}h\sum_{n,\alpha}S^{z}_{n,\alpha}$ (1) $\displaystyle+$
$\displaystyle J_{rung}\sum_{n}{\bf S}_{n,1}\cdot{\bf S}_{n,2}\,$

where $\bf S_{n,\alpha}$ is the spin $S=1/2$ operator on rung $n$
($n=1,...,L$) and leg $\alpha$ ($\alpha=1,2$). An applied magnetic field $h$
in the $Z$ direction leads to zeeman term. The rung and leg exchanges are
denoted by $J_{rung}$ and $J_{leg}$, respectively.
It is foundNagasawa  that the rung exchange $J_{rung}=-9.68~{}K$ is about four
times larger than $J_{leg}=-2.068~{}K$. In the following, we consider these
values in our QMC simulation approach. We have used the ALPSAlbu07  code which
is known as one of the best codes in this field. We have considered two-leg
ladders with the maximum size $N=2L=2\times 100$ and periodic boundary
conditions. The QMC simulation is performed for the maximum $1000000$
equilibration sweeps and $2000000$ measurement steps.

Figure 3: (a) Magnetic susceptibility $\chi(T)$ versus temperature for
isolated spin-1/2 FM two-leg ladders at different values of the magnetic
field. QMC simulation has been carried out for Heisenberg model.(b) Magnetic
specific heat per site versus the temperature for different values of the
magnetic field. QMC simulation has been carried out for Heisenberg model. The
size of two-leg ladder is $2\times 100$.

Fig. 2 presents the magnetization as a function of the temperature in the
absence of the magnetic field. Induced thermal fluctuations by increasing
temperature cause in decreasing the magnetization and it reaches zero for high
enough temperatures. The magnetic susceptibility is also shown in the inset of
Fig. 2. It only goes up with cooling the system which is in good agreement
with the experimental resultsNagasawa . The asymptotic behavior confirms that
the ground state of the system is in a magnetic ordered phase at $T=0$, which
is also in complete agreement with our results on the magnetization. In
addition, we have also studied the effect of the magnetic field on the
thermodynamic behavior of an isolated FM two-leg ladder system. Our QMC
simulation results are presented in Fig. 3(a) for different values of the
magnetic field $h=0.5~{}T$, $1.0~{}T$, $2.0~{}T$, and $3.0~{}T$. we have
calculated the spin gap according to expression
$\chi(T)\sim$exp$(-\Delta/T)/\sqrt{T}$. The obtained results are
$\Delta=0.88~{}K$, $1.6~{}K$, $2.6~{}K$, and $4.5~{}K$, for $h=0.5~{}T$,
$1.0~{}T$, $2.0~{}T$, and $3.0~{}T$, respectively.
As shown in Fig. 3(a), the magnetic susceptibility goes up first with lowering
temperature until it reaches to a maximum value, then decreases exponentially
down to zero at low temperatures. This exponential fall of susceptibility
indicates that there is a gap in the excitation spectrum of the FM two-leg
ladder system in the presence of a magnetic field. With decreasing the
magnetic field the peak of susceptibility curve increases and thus the spin
gap is weakened.
To complete our study on the thermodynamics of an isolated FM spin-1/2 two-leg
ladder, we have also calculated the specific heat, $C_{m}(T)$. Our numerical
results are presented in Fig. 3(b) for different values of the magnetic field.
As it is seen, at zero temperature the specific heat is zero, by increasing
the temperature it remains almost zero up to a threshold temperature which is
known as the indication of the spin gap. We have also checked the low
temperature results and found an exponential behavior which is also an
indication of the gapped phase.

##  III Coupled FM two-leg ladder system

High-field nuclear magnetic resonance and inelastic neutron scattering
measurements in some quasi-two-leg ladder systemsOosawa ; Giamarchi ;
Yamaguchi13 ; Yamaguchi14  show that weak coupling between ladders induces
$3D$ phase transition at low temperature region. In these compounds, phase
transition between quantum phases and the 3D gapless-Neel ordered phase occurs
at very low temperatures.

To the best of our knowledge, the effect of the inter-ladder coupling in
spin-1/2 two-leg ladders with FM legs and rungs has not been studied so far.
Interesting results are not expected for the inter-ladder FM coupling. For
this reason, we have considered the inter-ladder AFM coupling. We have
performed the QMC simulations on the AFM coupled FM two-leg ladder systems for
different values of the inter-ladder exchange $J_{in}$ and in the presence of
a magnetic field. The scheme of coupled ladders is illustrated in Fig. 1. The
numerical results are calculated for coupled ladders with
$J_{rung}=-9.68~{}K$, $J_{leg}=-2.068~{}K$,
$J_{in}/J_{leg}=-0.1,-0.2,...,-0.5$ and different sizes up to $5\times
2L=5\times(2\times 30)$.

Fig. 4(a) shows the magnetization, $M$, of the coupled system as a function of
the magnetic field in the vicinity of the zero temperature and
$J_{in}/J_{leg}=-0.2$. It is clearly seen that the magnetization is zero in
the absence of the magnetic field which shows that the induced quantum
fluctuations by inter-ladder interaction destroy the long-range FM order of
the ground state of isolated FM two-leg ladders. It means that in the ground
state phase diagram of the coupled FM ladders, the line $J_{in}/J_{leg}=0$
must be a quantum critical line. By applying the magnetic field, the
magnetization starts to increase and will be saturated in a critical magnetic
field, which depends on the value of the inter-ladder exchange interaction.
So, such behavior of magnetization upon contribution of AFM inter-ladder
interaction suggests, the existence of a nonmagnetic phase.

Figure 4: (a) The magnetization of spin-1/2 FM two-leg ladders with inter-
ladder AFM interaction as a function of the magnetic field in the vicinity of
the zero temperature and $J_{in}/J_{leg}=-0.2$. QMC simulation has been
carried out for Heisenberg model. The size of coupled ladders is $10\times
30$. (b) The magnetization versus inter-ladder $J_{in}$ interaction in the
absence of the magnetic field. The size of coupled ladders is $10\times 30$.
The effect of AFM inter-ladder interaction causes the system undergoes a
first-order phase transition. QMC calculation has been carried out for
Heisenberg model. In the above inset, specific heat per site was plotted as a
function of the temperature in the absence of the magnetic field by using QMC
simulation. In the bottom inset, using numerical lancsoz algorithm, the first
derivative of energy per site versus $J_{in}$ was plotted.

Now let us see what happens when we attempt to change the inter-ladder
interaction at zero temperature and in the absence of the magnetic field. Fig.
4(b) presents the magnetization versus inter-ladder $J_{in}$ interaction in
the absence of the magnetic field. The inter-ladder interaction effects
embedded in the coupled ladders drastically change the value of magnetization.
There is a sharp drop of magnetization in the low inter-ladder coupling about
$0.01J_{leg}$. This behavior is known as the main indication of a first-order
phase transition. Therefore it suggests the existence of a first-order
commensurate-incommensurate quantum phase transition in the ground state phase
diagram of the model. Moreover, to confirm the type of the mentioned quantum
phase transition in our model, we have also implemented the Lanczos algorithm
to find the ground state energy of the system. A very important indication of
the first order phase transition is the discontinuity in the first derivative
of the ground state energy at the quantum critical point. Using the numerical
Lanczos method, we have calculated the ground state energy for system sizes
$2\times(2\times L)=16,20$ and plotted the first derivative of the ground
state energy per site as a function of the inter-ladder interaction in the
bottom inset of Fig. 4(b). The results show a clear discontinuity in the first
derivative of ground state energy which is in agreement with our QMC results.
To find out the effect of inter-ladder AFM interaction, we have also presented
the QMC results for the specific heat, $C_{m}$, in the top inset of Fig. 4(b).
In this figure, we observe a second peak at very low temperatures which can be
considered as an indication of the mentioned nonmagnetic phase.

Figure 5: (a) Magnetization versus temperature for spin-1/2 FM two-leg ladders
coupled with AFM inter-ladder interaction at different values of the magnetic
field. QMC simulation has been carried out for Heisenberg model. (b) the
magnetic susceptibility versus the temperature for different values of the
magnetic field above and below quantum critical field. QMC simulation has been
carried out for Heisenberg model. The size of coupled ladders is $10\times
30$.

It is interesting to discuss the thermodynamic properties of coupled ladders
in the gapless phase $J_{in}=-0.2~{}J_{leg}$ for different magnetic fields. In
general there is a similarity between isolated FM ladders and the AFM coupled
FM ladders for high magnetic fields. But, the differences can be noticed
within the range of $0.0<h<0.5~{}T$. Fig. 5(a) shows the magnetization versus
the temperature for $h=0.2~{}T$, $h=0.3~{}T$, $h=0.45~{}T$, and $h=0.5~{}T$.
The magnetization is not saturated for $h<0.45~{}T$ at zero temperature. To
find the critical magnetic field $h_{c}$, we have performed the calculation
for other magnetic fields within the range of $0~{}T<h<0.5~{}T$. There is no
saturation in magnetization curve up to $h_{c}=0.42~{}T$ which is in
accordance with Fig. 4(a). In the inset of Fig. 5(a) we have plotted the
magnetization as a function of the temperature to show that there is not any
plateau in the curve of the magnetization. As shown in Fig. 5(b) the magnetic
susceptibility is plotted for different magnetic fields in the ratio of
$J_{in}/J_{leg}=-0.2$. There are indications that the FM two-leg ladder spin
systems under this weak AFM inter-ladder interaction undergo to a nonmagnetic
phase in the low magnetic fields. $\chi(T)$ goes to finite values at low
temperatures within the range of $h<h_{c}$. Also this behavior suggests that
the coupled ladders should be in gapless phase, whereas the exponential fall-
off of $\chi(T)$ above critical field is a signature of existence of gap in
this system.

Figure 6:  Magnetic specific heat per site versus the temperature for spin-1/2
FM two-leg ladders coupled with AFM inter-ladder interaction in the region of
the magnetic field $h<h_{c}=0.42T$. In the inset, the magnetic specific heat
per site is plotted for values of the field more than the quantum critical
field. QMC simulation has been carried out for Heisenberg model. The size of
coupled ladders is $10\times 30$.

In Fig. 6 the curve of $C_{m}(T)$ at $h<h_{c}=0.42~{}T$ and $h>h_{c}$ (in the
inset) is depicted.It can be clearly seen that below the quantum critical
field, a second peak appears at low temperatures, whereas as illustrated in
the inset, above the quantum critical field $h_{c}$, the second peak
disappears. These results indicate that the system undergoes a cross-over from
gapped phase to a nonmagnetic phase. Also this behavior suggests that the
coupled ladders should be in gapless phase. Generally, the weak AFM inter-
ladder interaction has the substantial effect at low temperatures within the
range of low magnetic fields $h<h_{c}=0.42~{}T$.

##  IV Conclusion

In summary, we have calculated the thermodynamic properties of FM two-leg
ladder like [Cu(II) Cl(O-mi)2(μ-Cl)2)]. We have performed stochastic series
expansion QMC using ALPS code to investigate spin-1/2 isolated FM two-leg
ladders and the effect of the AFM inter-ladder exchange interaction on the
low-temperature behavior of these type of ladders. For an isolated spin-1/2 FM
two-leg ladder, a gapped behavior was observed at zero temperature. In
principle, the ground state of an isolated spin-1/2 FM two-leg ladder is in
the saturated FM phase.

As soon as the inter-ladder AFM exchange interaction is added, a first-order
commensurate-incommensurate quantum phase transition occurs in the ground
state phase diagram. Numerical results of magnetization and the specific heat
showed that the gapped FM phase is replaced by a nonmagnetic phase. In the
presence of a magnetic field, the ground state of the coupled ladders remains
in this nonmagnetic phase up to a critical field $h_{c}$. The value of the
mentioned critical field depends on the value of the inter-lader AFM
interaction. Although in the case of [Cu(II) Cl(O-mi)2(μ-Cl)2)], the compound
consists of isolated two-leg ladder, but such an enhancement of coupled
interaction may occur upon chemical substitution.

Existence of the non-magnetic phase in this model is very similar to what can
be probably observed in the coupled spin-1/2 two-leg ladders with FM leg and
AFM rung exchange interactions in the presence of a magnetic fieldYamaguchi13
; Yamaguchi14 ; Yamaguchi . In fact, two-leg ladders with FM leg and rung
interactions consisting of weak AFM inter-ladder coupling can also be
considered as the two-leg ladders with FM leg and weak AFM rung exchange
interactions which are FM coupled. The observation of non-magnetic phase in
these new type of coupled ladders is stimulating for the future studies.

##  V Acknowledgement

We express our heartfelt thanks to G. I. Japaridze and T. Vekua for
stimulating discussions. Also, we thank Dr. Javad Vahedi for reading this
manuscript.

## References

  * (1) E. Dagotto and T. M. Rice, Science 271, 618 (1996).
  * (2) M. Uehara, T. Nagata, J. Akimitsu, H. Takahashi, N. Muri and K. Kinoshita, J. Phys. Soc. Jpn. 65, 2764 (1996).
  * (3) N. Fujiwara, N. Mori, Y. Uwatoko, T. Matsumoto, N. Motoyama, and S. Uchida, Phys. Rev. Lett. 90, 137001 (2003).
  * (4) S. Vanishri, D. Braithwaite, B. Salce, C. Marin, and J. Flouquet, Phys. Rev. B 81, 094511 (2010).
  * (5) E. Plekhanov, A. Avella1, and F. Mancini, Eur. Phys. J. B 77 , 381 (2010).
  * (6) E. Dagotto, J. Riera, D. Scalapino, Phys. Rev. B 45, 5744 (1992).
  * (7) M. Azuma, Z. Hiroi, M. Takano, K. Ishida, and Y. Kitaoka, Phys. Rev. Lett. 73, 3463 (1994).
  * (8) C. Ruegg, K. Kiefer, B. Thielemann, D. F. McMorrow, V. Zapf, B. Normand, M. B. Zvonarev, P. Bouillot, C. Kollath, T. Giamarchi, S. Capponi, D. Poilblanc, D. Biner, and K.W. Kramer, Phys. Rev. Lett. 101, 247202 (2008).
  * (9) B. C. Watson, V. N. Kotov, M. W. Meisel, D. W. Hall, G. E. Granroth, W. T. Montfrooij, S. E. Nagler, D. A Jensen, R. Backov, M. A. Petruska, G. E. Fanucci, and D. R. Talham, Phys. Rev. Lett. 86, 5168 (2001).
  * (10) T. Hong, Y. H. Kim, C. Hotta, Y. Takano, G. Tremelling, M. M. Turnbull, C. P. Landee, H.-J. Kang, N. B. Christensen, K. Lefmann, K. P. Schmidt, G. S. Uhrig, and C. Broholm, Phys. Rev. Lett. 105, 137207 (2010).
  * (11) M. Matsumoto, B. Normand, T. M. Rice, and M. Sigrist, Phys. Rev. Lett. 89, 077203 (2002). A. Oosawa, M. Ishii, and H. Tanaka, J. Phys. Cond. Matt. 11, 265 (1999). H. Tanaka, A. Oosawa, T. Kato, H, Uekusa, Y. Ohashi,K. Kakurai, and A. Hoser, cond-mat/0101276. S. Wessel and S. Haas, Eur. Phys. J. B. 16, 393 (2000).
  * (12) G. Chaboussant, Y. Fagot-Revurat, M. H. Julien, M. E. Hanson, C. Berthier, M. Horvatic, L. P.Levy, and O. Piovesana, Phys. Rev. Lett. 80, 2713 (1998). T. Giamarchi and A. M. Tsvelik, Phys. Rev. B 59, 11398 (1999); H. Mayaffre, M. Horvati´c, C. Berthier, M.-H. Julien, P. S´egransan, L. L´evy, and O. Piovesana, Phys. Rev. Lett. 85, 4795 (2000).
  * (13) P. Millet, C. Satto, J. Bonvoisin, B. Normand, K. Penc, M. Albrecht, and F. Mila, Phys. Rev. B 57, 5005 (1998).
  * (14) M. A. Korotin, I. S. Elfimov, V. I. Anisimov, M. Troyer, and D. I. Khomskii, Phys. Rev. Lett. 83, 1387 (1999).
  * (15) M. A. Korotin, V. I. Anisimov, T. Saha-Dasgupta, and I. Dasgupta, J. Phys.: Condens. Matter 12, 113 (2000).
  * (16) E. M. McCarron, M. A. Subramanian, J. C. Calabrese, and R. L. Harlow, Mater. Res. Bull. 23, 1355 (1988).
  * (17) T. Siegrist, L. F. Schneemeyer, S. A. Sunshine, and J. V. Waszczak, Mater. Res. Bull. 23, 1429 (1988).
  * (18) R. S. Roth, C. J. Rawn, J. J. Ritter, and B. P. Burton, J. Am. Ceram. Soc. 72, 1545 (1989).
  * (19) M. W. McElfresh, J. M. D. Coey, P. Strobel, and S. vonMolnar, Phys. Rev. B 40, 825 (1989).
  * (20) G. I. Japaridze, A. Langari, and S. Mahdavifar, J. Phys.: Condens. Matter 19, 076201, (2007); F. Amiri, S. Mahdavifar, H. Hadipour, and M. Shahri Naseri, Journal of Low Temperature Physics, 177, 203-216, (2014).
  * (21) J. Jahangiri, H. Hadipour, S. Mahdavifar, and S. Farjami Shayesteh, Physica B, 459, 52, (2014).
  * (22) X. Wang and L. Yu, Phys. Rev. Lett. 84, 5399 (2000).
  * (23) T. Masuda, A. Zheludev, H. MAnaka, J.-H. Chung, arXiv:cond-mat/0506382.
  * (24) H. Tsujii, et al. , J. Phys.: Condens. Matter 150, 042217 (2009).
  * (25) H. Yamaguchi, K. Iwase, T. Ono, T. Shimokawa, H. Nakano, Y. Shimura, N. Kase, S. Kittaka, T. Sakakibara, T. Kawakami, and Y. Hosokoshi, Phys. Rev. Lett. 110, 157205 (2013).
  * (26) Hironori Yamaguchi, Hirotsugu Miyagai, Tokuro Shimokawa, Kenji Iwase, Toshio Ono, Yohei Kono, Naoki Kase, Koji Araki, Shunichiro Kittaka, Toshiro Sakakibara, Takashi Kawakami, Kouichi Okunishi, and Yuko Hosokoshi, Journal of the Physical Society of Japan 83, 033707 (2014).
  * (27) H. Yamaguchi, H. Miyagai, M. Yoshida, M. Takigawa, K. Iwase, T. Ono, N. Kase, K. Araki, S. Kittaka, T. Sakakibara, T. Shimokawa, T. Okubo, K. Okunishi, A. Matsuo, and Y. Hosokoshi, phys. Rev. B 89, 220402(R), (2014).
  * (28) M. Kato, K. Hida, T. Fujihara and A. Nagasawa. European Journal of Inorganic Chemistry, 2011, 495 (2011).
  * (29) Kazuo Hida, Takashi Tino, J. phys. Soc. Jpn. 81, 034707, (2012).
  * (30) A. W. Sandvik, Phys. Rev. B 59, R14157 (1999).
  * (31) O. F. Syljuasen and A. W. Sandvik, Phys. Rev. E 66, 046701 (2002).
  * (32) A. F. Albuquerque, et. al, Journal of Magnetism and Magnetic Materials 310, 1187 (2007).


# A new proof of Stanley’s theorem on the strong Lefschetz property

Ho V. N. Phuong  University of Sciences, Hue University, 77 Nguyen Hue St.,
Hue, Vietnam<EMAIL_ADDRESS>and  Quang Hoa Tran  University of
Education, Hue University, 34 Le Loi St., Hue City, Viet Nam
<EMAIL_ADDRESS>
###### Abstract.

A standard graded artinian monomial complete intersection algebra
$A=\Bbbk[x_{1},x_{2},\ldots,x_{n}]/(x_{1}^{a_{1}},x_{2}^{a_{2}},\ldots,x_{n}^{a_{n}})$,
with $\Bbbk$ a field of characteristic zero, has the strong Lefschetz property
due to Stanley in 1980. In this paper, we give a new proof for this result by
using only the basic properties of linear algebra. Furthermore, our proof is
still true in the case where the characteristic of $\Bbbk$ is greater than the
socle degree of $A$, namely $a_{1}+a_{2}+\cdots+a_{n}-n$.

###### Key words and phrases:

Artinian algebras, complete intersections, Stanley’s theorem, Strong Lefschetz
property

###### 2020 Mathematics Subject Classification:

Primary 13C40; Secondary 13E10, 14M10

##  1\. Introduction

Let $\Bbbk$ be a field and $R=\Bbbk[x_{1},x_{2},\ldots,x_{n}]$ be a standard
graded polynomial ring over $\Bbbk$ in $n$ variables. A graded artinian
$\Bbbk$-algebra $A=R/I$ is said to have the strong Lefschetz property if there
is a linear form $\ell\in A_{1}$ such that the multiplication

$\times\ell^{s}:A_{i}\longrightarrow A_{i+s}$

has maximal rank for all $s$ and all $i$, i.e., $\times\ell^{s}$ is either
injective or surjective, for all $s$ and all $i$. Such linear form $\ell$ is
called a strong Lefschetz element of $A.$

Three papers represent the beginning of the study of what is presently called
Lefschetz properties that were written by R. P. Stanley [S80] in 1980; by J.
Watanabe [W87] in 1987; and by L. Reid, L. G. Roberts and M. Roitman [RRR91]
in 1991. These papers proved essentially the following same result.

######  Theorem (Stanley’s theorem).

If $\Bbbk$ is a field of characteristic zero and
$R=\Bbbk[x_{1},x_{2},\ldots,x_{n}]$, then every artinian monomial complete
intersection algebra

$A=R/(x_{1}^{a_{1}},x_{2}^{a_{2}},\ldots,x_{n}^{a_{n}})$

has the strong Lefschetz property with $x_{1}+x_{2}+\cdots+x_{n}$ as a strong
Lefschetz element.

In the case $\Bbbk=\mathbb{C}$, Stanley used the fact that $A$ is isomorphic
to the cohomology ring of a product of projective spaces and he applied the
Hard Lefschetz Theorem to conclude that the divisor lattice of monomials in
$A$ has the Sperner property. Watanabe proved the result by using the theory
of modules over special linear Lie algebra $\mathfrak{sl}_{2}$, and Reid,
Roberts and Roitman used Hilbert function techniques from commutative algebra
in order to obtain this theorem. The conclusion in these three papers as well
as the techniques of proof are of interest in algebraic geometry,
combinatorics, representation theory, and commutative algebra.

In this paper, we will give a new proof of this theorem by using only the
basic properties of linear algebra. Furthermore, our proof is true not only
for the case where the characteristic of $\Bbbk$ is zero, but also for the
case where the characteristic is large enough, see Theorem 3.1. More
precisely, firstly let $I=(x_{1}^{2},x_{2}^{2},\ldots,x_{n}^{2})$ be an
artinian quadratic monomial complete intersection ideal of $R$. We see that
the set of all square-free monomials of degree $i$ forms a $\Bbbk$-basis of
$\Bbbk$-vector space $B_{i}$, for all $i$, where $B=R/I$. Based on these
bases, we construct the matrix of the multiplications
$\times(x_{1}+x_{2}+\cdots+x_{n})^{t}:B_{i}\longrightarrow B_{i+t}$ for all
$0\leq i\leq n$ and $0\leq t\leq n-i$ and show that these multiplications have
maximal rank. The main result is the following.

######  Theorem (Theorem 2.7).

Assume $\Bbbk$ is of characteristic zero or greater than $n$. Then the algebra
$B=R/(x_{1}^{2},x_{2}^{2},\ldots,x_{n}^{2})$ has the strong Lefschetz property
with $x_{1}+x_{2}+\cdots+x_{n}$ as a strong Lefschetz element.

Then we show that any artinian monomial complete intersection $A$ can be
viewed as a sub-algebra of an artinian quadratic monomial complete
intersection $B$ such that $A$ and $B$ have the same socle degree. By applying
Theorem 2.7, we get that $A$ has also the strong Lefschetz property, namely
Stanley’s theorem is proved. Furthermore, our proof is still true in the case
where the characteristic of $\Bbbk$ is greater than the socle degree of $A$,
namely $a_{1}+a_{2}+\cdots+a_{n}-n$, see Theorem 3.1.

##  2\. Artinian quadratic monomial complete intersection algebras

######  Definition 2.1.

For any standard graded artinian $\Bbbk$-algebra
$A=R/I=\bigoplus_{i=0}^{d}A_{i}$, the Hilbert function of $A$ is the function

$h_{A}:\mathbb{N}\longrightarrow\mathbb{N}$

defined by $h_{A}(t)=\dim_{\Bbbk}A_{t}$. As $A$ is artinian, its Hilbert
function is equal to its $h$-vector that one can express as a finite sequence

$\underline{h}_{A}=\left(h_{0},h_{1},h_{2},\ldots,h_{d}\right),$

with $h_{i}=h_{A}(i)>0$ and $d$ is the last index with this property. The
integer $d$ is called the socle degree of $A$.

The $h$-vector $\underline{h}_{A}$ is said to be unimodal if there exists an
integer $t\geq 1$ such that $h_{0}\leq h_{1}\leq h_{2}\leq\cdots\leq h_{t}\geq
h_{t+1}\geq\cdots\geq h_{d}.$ The $h$-vector $\underline{h}_{A}$ is said to be
symmetric if $h_{d-i}=h_{i}$ for every
$i=0,1,\ldots,\lfloor\frac{d}{2}\rfloor.$

In this section, we consider the case where
$I=(x_{1}^{2},x_{2}^{2},\ldots,x_{n}^{2})$ is an artinian quadratic monomial
complete intersection ideal in $R=\Bbbk[x_{1},x_{2},\ldots,x_{n}]$. Now set
$A=R/I=\bigoplus_{j=0}^{n}A_{j}$. Hence $A=R/I$ is an artinian complete
intersection of the socle degree $n$, namely $h_{A}(j)=0$ for all $j>n$ and
moreover

$h_{A}(j)=h_{A}(n-j)=\binom{n}{j}$

for all $j=0,1,\ldots,n$. The $h$-vector of $A$ is

$\left(1,n,\binom{n}{2},\binom{n}{3},\ldots,\binom{n}{3},\binom{n}{2},n,1\right).$

In particular, the $h$-vector of $A$ is unimodal and symmetric. Furthermore,
we have the following.

######  Lemma 2.2.

The set of all square-free monomials forms a $\Bbbk$-basis of $A$.

We denote by $\mathfrak{B}$ the set of all square-free monomials in $R$ and by
$\mathfrak{B}_{t}$ the set of all square-free monomials of degree $t$ in $R.$
By Lemma 2.2, $\mathfrak{B}$ is a $\Bbbk$-basis of $A$ and $\mathfrak{B}_{t}$
is a $\Bbbk$-basis of $A_{t}.$ We will list the monomials of
$\mathfrak{B}_{t}$ in the decreasing order with respect to the reverse
lexicographic order with $x_{1}>x_{2}>\cdots>x_{n}$, i.e.,

$\mathfrak{B}_{t}=\\{x_{i_{1}}x_{i_{2}}\ldots x_{i_{t}}\mid 1\leq
i_{1}<i_{2}<\cdots<i_{t}\leq n\\}.$

For example

$\mathfrak{B}_{1}=\\{x_{1},x_{2},\ldots,x_{n}\\},$

$\mathfrak{B}_{2}=\\{x_{1}x_{2},x_{1}x_{3},x_{2}x_{3},\ldots,x_{1}x_{n},x_{2}x_{n},x_{3}x_{n},\ldots,x_{n-1}x_{n}\\}\text{
and }$

$\mathfrak{B}_{3}=\\{x_{1}x_{2}x_{3},x_{1}x_{2}x_{4},x_{1}x_{3}x_{4},\ldots,x_{n-3}x_{n-2}x_{n-1},x_{1}x_{2}x_{n},x_{1}x_{3}x_{n},\ldots,x_{n-2}x_{n-1}x_{n}\\}.$

Denote by $M_{m\times n}(\Bbbk)$ the set of all $m\times n$ matrices with
entries in the field $\Bbbk$. For any matrix $M\in M_{m\times n}(\Bbbk)$, it
is known that ${\operatorname{rank}}(M)\leq\min\\{m,n\\}$. We say that $M$ has
maximal rank  if ${\operatorname{rank}}(M)=\min\\{m,n\\}$.

Now we fix a general linear form
$\ell=a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}$ of $R.$ Consider the
multiplication $\times\ell^{t}:A_{i}\longrightarrow A_{i+t}$ for some $0\leq
i\leq n$ and $0\leq t\leq n-i.$ Let $M_{i}^{t}$ be the matrix of
$\times\ell^{t}$ with respect to the two bases $\mathfrak{B}_{i}$ and
$\mathfrak{B}_{i+t}$. Thus $\times\ell^{t}:A_{i}\longrightarrow A_{i+t}$ has
maximal rank if and only if $M_{i}^{t}$ has maximal rank. When $t=1$ we will
denote by $M_{i}$ instead of $M_{i}^{1}$. Note that when $t=0$, $M_{i}^{t}$ is
the identity matrix.

######  Proposition 2.3.

With the above notations. Then the following assertions are equivalent:

  1. (i)

$A$ has the strong Lefschetz property.

  2. (ii)

$M_{i}^{t}$ has maximal rank for all $0\leq i\leq n$ and $0\leq t\leq n-i$.

  3. (iii)

$M_{i}^{n-2i}$ has maximal rank for all $0\leq i<\frac{n}{2}.$

###### Proof.

Clearly, (i) is equivalent to (ii) by the definition. The equivalence of (ii)
and (iii) follows from the basic properties of compositions of linear
applications and the fact that $\dim_{k}(A_{i})=\dim_{k}(A_{n-i})$ for all
$0\leq i<\frac{n}{2}.$ ∎

Now, set $\overline{R}:=R/(x_{n})\cong\Bbbk[x_{1},x_{2},\ldots,x_{n-1}]$ and
denote by $\overline{I}$ the image of $I$ in $\overline{R}.$ Therefore,
$\overline{I}=(x_{1}^{2},x_{2}^{2},\ldots,x_{n-1}^{2})$ and

$\overline{A}:=\overline{R}/\overline{I}=\frac{\Bbbk[x_{1},x_{2},\ldots,x_{n-1}]}{(x_{1}^{2},x_{2}^{2},\ldots,x_{n-1}^{2})}$

is also an artinian quadratic monomial complete intersection algebra. Denote
by $\overline{\mathfrak{B}}_{t}$ the set of all square-free monomials of
degree $t$ in $\overline{R}.$ By Lemma 2.2,

$\overline{\mathfrak{B}}_{t}=\\{x_{i_{1}}x_{i_{2}}\ldots x_{i_{t}}\mid 1\leq
i_{1}<i_{2}<\cdots<i_{t}\leq n-1\\}$

is a $\Bbbk$-basis of $\overline{A}_{t}$. Note that

(2.1)
$\mathfrak{B}_{t}=\overline{\mathfrak{B}}_{t}\sqcup\mathfrak{B}_{t}^{\prime},$

where

$\mathfrak{B}_{t}^{\prime}=\\{x_{i_{1}}x_{i_{2}}\ldots x_{i_{t-1}}x_{n}\mid
1\leq i_{1}<i_{2}<\cdots<i_{t-1}\leq n-1\\}.$

We identify $\mathfrak{B}_{t}^{\prime}$ with the set

$\overline{\mathfrak{B}}_{t-1}=\\{x_{i_{1}}x_{i_{2}}\ldots x_{i_{t-1}}\mid
1\leq i_{1}<i_{2}<\cdots<i_{t-1}\leq n-1\\}.$

Let $\ell=a_{1}x_{1}+a_{2}x_{2}+\cdots+a_{n}x_{n}$ be a linear form in $R$ and
let $\overline{\ell}$ be the image of $\ell$ in $\overline{R}$. We denote by
$\overline{M}_{i}^{t}$ the matrix of
$\times\overline{\ell}^{t}:\overline{A}_{i}\longrightarrow\overline{A}_{i+t}$
with respect to the two bases $\overline{\mathfrak{B}}_{i}$ and
$\overline{\mathfrak{B}}_{i+t}$.

######  Lemma 2.4.

For any $1\leq i\leq n-1$ and $1\leq t\leq n-i$, the matrix $M_{i}^{t}$ of
$\times\ell^{t}:A_{i}\longrightarrow A_{i+t}$ with respect to the two bases
$\mathfrak{B}_{i}$ and $\mathfrak{B}_{i+t}$ can be expressed by a $2\times 2$
block matrix of form

$M_{i}^{t}=\begin{bmatrix}\overline{M}_{i}^{t}&&0\\\ \\\
a_{n}t\overline{M}_{i}^{t-1}&&\overline{M}_{i-1}^{t}\end{bmatrix},$

where $0$ is the zero matrix.

###### Proof.

We see immediately that

$\ell^{t}=\sum_{j=0}^{t}\binom{t}{j}(\overline{\ell})^{t-j}(a_{n}x_{n})^{j}=\overline{\ell}^{t}+a_{n}t(\overline{\ell})^{t-1}x_{n}$

in $A$. The result follows from the definition of the matrix of
$\times\ell^{t}:A_{i}\longrightarrow A_{i+t}$ with respect to the two bases
$\mathfrak{B}_{i}$ and $\mathfrak{B}_{i+t}$ and using the decomposition of the
two bases $\mathfrak{B}_{i}$ and $\mathfrak{B}_{i+t}$ as in (2.1) where we
identify

$\mathfrak{B}_{i}^{\prime}\equiv\overline{\mathfrak{B}}_{i-1}\quad\text{and}\quad\mathfrak{B}_{i+t}^{\prime}\equiv\overline{\mathfrak{B}}_{i+t-1}.$

We get the desired conclusion. ∎

######  Example 2.5.

Assume the characteristic of $\Bbbk$ is zero or greater than $4$. Consider
$R=\Bbbk[x_{1},x_{2},x_{3},x_{4}]$,
$A=R/{(x_{1}^{2},x_{2}^{2},x_{3}^{2},x_{4}^{2})}$ and the linear form
$\ell=x_{1}+x_{2}+x_{3}+x_{4}$. Then the matrix of the multiplication
$\times\ell^{2}:A_{1}\longrightarrow A_{3}$ with respect to the bases
$\mathfrak{B}_{1}$ and $\mathfrak{B}_{3}$ is

$M_{1}^{2}=\left[\begin{array}[]{c c c|c}2&2&2&0\\\ \hline\cr 2&2&0&2\\\
2&0&2&2\\\ 0&2&2&2\end{array}\right]=\begin{bmatrix}\overline{M}_{1}^{2}&&0\\\
\\\ 2\overline{M}_{1}&&\overline{M}_{0}^{2}\end{bmatrix}$

A straightforward computation shows that $\det(M_{1}^{2})=-2^{4}.3^{2}\neq 0$,
hence the map $\times\ell^{2}:A_{1}\longrightarrow A_{3}$ is an isomorphism.

The following lemma is useful to determine the rank of block matrices.

######  Lemma 2.6.

Let $A\in M_{m\times n}(\Bbbk),B\in M_{n\times p}(\Bbbk),P\in M_{n\times
n}(\Bbbk)$ such that $P$ is nonsingular. Assume that $M$ is a
$(m+n)\times(n+p)$ matrix such that $M$ is written in $2\times 2$ block matrix
as follows

$M=\begin{bmatrix}AP&&0\\\ \\\ P&&PB\end{bmatrix},$

Then

${\operatorname{rank}}(M)=n+{\operatorname{rank}}(APB).$

###### Proof.

We have that

$\begin{bmatrix}I_{m}&&-A\\\ \\\
0&&P^{-1}\end{bmatrix}\times\begin{bmatrix}AP&&0\\\ \\\
P&&PB\end{bmatrix}\begin{bmatrix}I_{n}&&B\\\ \\\
0&&-I_{p}\end{bmatrix}=\begin{bmatrix}0&&APB\\\ \\\ I_{n}&&0\end{bmatrix},$

and conclude immediately. ∎

Now we prove the main result in this section.

######  Theorem 2.7.

Assume that the characteristic of $\Bbbk$ is zero or greater than $n$. Then
the algebra $A=R/(x_{1}^{2},x_{2}^{2},\ldots,x_{n}^{2})$ has the strong
Lefschetz property with $\ell=x_{1}+x_{2}+\cdots+x_{n}$ as a strong Lefschetz
element.

###### Proof.

Set $\ell=x_{1}+x_{2}+\cdots+x_{n}$. Note first that since
$\dim_{\Bbbk}(A_{0})=\dim_{\Bbbk}(A_{n})=1$, the matrix of the map
$\times\ell^{n}:A_{0}\longrightarrow A_{n}$ is
$M_{0}^{n}=\begin{pmatrix}n!\end{pmatrix}$. Therefore, $\det(M_{0}^{n})=n!\neq
0$ since the characteristic of $\Bbbk$ is zero or greater than $n$.

Now to prove the theorem, by Proposition 2.3, it is enough to show that the
matrix $M_{i}^{n-2i}$ of $\times\ell^{n-2i}:A_{i}\longrightarrow A_{n-i}$ has
maximal rank for all $0\leq i<\frac{n}{2}$. We show the assertion by induction
on $n$.

Firstly, for $n=1,2$. We only have the case $i=0$. However, in this case the
assertion holds as we have remarked at the beginning of the proof. Now we
assume that the assertion holds for any artinian quadratic monomial complete
intersection algebra in the polynomial ring in $<n$ variables. For integers
$n\geq 3$ and $i$ satisfying $0<i<\frac{n}{2}$, we have to show that the
matrix $M_{i}^{n-2i}$ of $\times\ell^{n-2i}:A_{i}\longrightarrow A_{n-i}$ has
maximal rank. By Lemma 2.4, $M_{i}^{n-2i}$ can be written in the form of
$2\times 2$ block matrix

$M_{i}^{n-2i}=\begin{bmatrix}\overline{M}_{i}^{n-2i}&&0\\\ \\\
(n-2i)\overline{M}_{i}^{n-2i-1}&&\overline{M}_{i-1}^{n-2i}\end{bmatrix}.$

Note that $0<n-2i<n$, hence $n-2i$ is an invertible element of $\Bbbk$.
Observe that $M_{i}^{n-2i}$ and $\overline{M}_{i}^{n-2i-1}$ are square
matrices of size $\binom{n}{i}\times\binom{n}{i}$ and
$\binom{n-1}{i}\times\binom{n-1}{i}$, respectively. Moreover,

$\overline{M}_{i}^{n-2i}=\overline{M}_{n-i-1}\overline{M}_{i}^{n-2i-1}\quad\text{and}\quad\overline{M}_{i-1}^{n-2i}=\overline{M}_{i}^{n-2i-1}\overline{M}_{i-1}.$

As $\overline{A}=\overline{R}/\overline{I}$ has the strong Lefschetz property
by the inductive hypothesis, $\overline{M}_{i}^{n-2i-1}$ is a nonsingular
matrix. It follows from Lemma 2.6 that

${\operatorname{rank}}(M_{i}^{n-2i})=\binom{n-1}{i}+{\operatorname{rank}}(\overline{M}_{n-i-1}\overline{M}_{i}^{n-2i-1}\overline{M}_{i-1}).$

We observe that
$\overline{M}_{n-i-1}\overline{M}_{i}^{n-2i-1}\overline{M}_{i-1}$ is the
matrix of

$\times(\overline{\ell})^{n-2i+1}:\overline{A}_{i-1}\longrightarrow\overline{A}_{n-i}.$

It is an isomorphism since $\overline{A}$ has the strong Lefschetz property.
Hence

${\operatorname{rank}}(\overline{M}_{n-i-1}\overline{M}_{i}^{n-2i-1}\overline{M}_{i-1})=\binom{n-1}{i-1}.$

It follows that

${\operatorname{rank}}(M_{i}^{n-2i})=\binom{n-1}{i}+\binom{n-1}{i-1}=\binom{n}{i}.$

This implies that $\ell^{n-2i}:A_{i}\longrightarrow A_{n-i}$ is an
isomorphism. This finishes the induction and the proof. ∎

##  3\. Proof of Stanley’ theorem

Finally, we show that Stanley’s theorem follows from Theorem 2.7.

######  Theorem 3.1.

Let $\Bbbk$ be a field and $R=\Bbbk[x_{1},x_{2},\ldots,x_{n}]$. Then

$R/(x_{1}^{d_{1}},x_{2}^{d_{2}},\ldots,x_{n}^{d_{n}})$

has the strong Lefschetz property if the characteristic of $\Bbbk$ is zero or
greater than $d_{1}+d_{2}+\cdots+d_{n}-n$.

###### Proof.

To simplicity, denote
$A=R/(x_{1}^{a_{1}+1},x_{2}^{a_{2}+1},\ldots,x_{n}^{a_{n}+1})$, with
$a_{1},a_{2},\ldots,a_{n}$ are the positive integers. Assume that the
characteristic of $\Bbbk$ is zero or greater than $a_{1}+a_{2}+\cdots+a_{n}$.
We need to show that $A$ has the strong Lefschetz property.

Note that $A$ is an artinian monomial complete intersection algebra with the
socle degree $m=a_{1}+a_{2}+\cdots+a_{n}$. Set
$\alpha_{i}=\sum_{j=1}^{i}a_{j}$ for $i=1,\ldots,n$. Now we let
$B~{}=~{}\Bbbk[x_{1},x_{2},\ldots,x_{m}]/(x_{1}^{2},x_{2}^{2},\ldots,x_{m}^{2})$.
By Theorem 2.7, the algebra $B$ has the strong Lefschetz property with
$\ell=x_{1}+x_{2}+\cdots+x_{m}$ as a strong Lefschetz element. Set
$S:=\Bbbk[y_{1},y_{2},\ldots,y_{n}]$ and consider the algebra homomorphism
$\phi:S\longrightarrow B$ given by

$\displaystyle y_{1}$ $\displaystyle\longmapsto x_{1}+\cdots+x_{\alpha_{1}}$
$\displaystyle y_{2}$ $\displaystyle\longmapsto
x_{\alpha_{1}+1}+\cdots+x_{\alpha_{2}}$ $\displaystyle\cdots$ $\displaystyle
y_{n}$ $\displaystyle\longmapsto x_{\alpha_{n-1}+1}+\cdots+x_{\alpha_{n}}.$

Set $J=(y_{1}^{a_{1}+1},y_{2}^{a_{2}+1},\ldots,y_{n}^{a_{n}+1})$. We have the
following assertion.

Claim: ${\operatorname{Ker}}(\phi)=J$.

Proof of Claim: First, for each $j=1,2,\ldots,n$, we see that

$\phi(y_{j}^{a_{j}+1})=(\underbrace{x_{\alpha_{j-1}+1}+\cdots+x_{\alpha_{j}}}_{a_{j}\;\text{variables
}})^{a_{j}+1}=0$

in $B$. In other words, $y_{j}^{a_{j}+1}\in{\operatorname{Ker}}(\phi)$, so
$J\subset{\operatorname{Ker}}(\phi)$. Assume the contrary that
${\operatorname{Ker}}(\phi)\neq J$. Select a homogeneous element $f$ of
largest degree with $f\in{\operatorname{Ker}}(\phi)$ and $f\notin J$. It
follows that $f$ represents a non-trivial element in the socle of $S/J$. Note
that $S/J$ is an artinian monomial complete intersection algebra and its socle
is a $\Bbbk$-vector space spanned by $y_{1}^{a_{1}}\ldots y_{n}^{a_{n}}$.
Hence there exists a non-zero element $c\in\Bbbk$ such that
$f=cy_{1}^{a_{1}}\ldots y_{n}^{a_{n}}+g$, where $g\in J$. Thus, $\phi(g)=0$
and

$\phi(f)=c(x_{1}+\cdots+x_{\alpha_{1}})^{a_{1}}\ldots(x_{\alpha_{n-1}+1}+\cdots+x_{\alpha_{n}})^{a_{n}}=ca_{1}!\ldots
a_{n}!x_{1}x_{2}\ldots x_{m}.$

Note that the characteristic of $\Bbbk$ is zero or greater than
$m=a_{1}+a_{2}+\cdots+a_{n}$, hence $ca_{1}!\ldots a_{n}!$ is an invertible
element of $\Bbbk$. Thus $\phi(f)=ca_{1}!\ldots a_{n}!x_{1}x_{2}\ldots
x_{m}\neq 0$ in $B$. This contradicts $f\in{\operatorname{Ker}}(\phi).$ The
contradiction completes the proof of Claim.

By the above claim, we get the following algebra isomorphisms

$A\simeq S/{\operatorname{Ker}}(\phi)\simeq{\operatorname{Im}}(\phi)\subseteq
B.$

It follows that we can identify $A$ with a sub-algebra of $B$. Furthermore,
$A$ and $B$ have the same socle degree, namely $m$. We have the commutative
diagrams

(3.5)

where the vertical maps are the canonical inclusions and
$\ell=x_{1}+x_{2}+\cdots+x_{m}$. Since $B$ has the strong Lefschetz property,
the maps $\times\ell^{m-2i}:B_{i}\longrightarrow B_{m-i}$ is bijective, for
all $0\leq i<\frac{m}{2}$. By (3.5), we get that
$\times\ell^{m-2i}:A_{i}\longrightarrow A_{m-i}$ is injective. Since
$\dim_{\Bbbk}A_{i}=\dim_{\Bbbk}A_{m-i}$, it implies that
$\times\ell^{m-2i}:A_{i}\longrightarrow A_{m-i}$ is bijective, for all $0\leq
i<\frac{m}{2}$. Thus $A$ has the strong Lefschetz property. The proof is
completed. ∎

## Acknowledgments

This work is supported by the Vietnam Ministry of Education and Training under
grant number B2022-DHH-01. The second author is also partially supported by
the Core Research Program of Hue University under grant number
NCM.DHH.2020.15. Part of this paper was written while the second author
visited the Vietnam Institute for Advanced Study in Mathematics (VIASM), he
would like to thank VIASM for the very kind support and hospitality. The
authors are grateful to the anonymous referee for his/her careful reading of
the manuscript and many useful suggestions.

## References

  * [RRR91] L. Reid, L. G. Roberts, M. Roitman, _On complete intersections and their Hilbert functions_ , J Canad. Math. Bull. 34 (1991), no. 4, 525–535.
  * [S80] R. P. Stanley, _Weyl groups, the hard Lefschetz theorem, and the Sperner property_ , SIAM J. Algebraic Discrete Methods 1 (1980), no. 2, 168–184.
  * [W87] J. Watanabe, _The Dilworth number of Artinian rings and finite posets with rank function_ , in: Commutative algebra and combinatorics (Kyoto, 1985), vol. 11 of Adv. Stud. Pure Math. (1987), 303–312.


B^{\top}\widetilde{W}^{-1}B-\widetilde{B}^{\top}\widetilde{W}^{-1}\widetilde{B}\right\rVert_{2}$
by utilising Lemma 4, and equations (87), (91), to give,

$\Pr\Big{(}\left\lVert
B^{\top}\widetilde{W}^{-1}B-\widetilde{B}^{\top}\widetilde{W}^{-1}\widetilde{B}\right\rVert_{2}\geq\delta\Big{)}\leq
2(N-L)^{2}\exp\Bigg{(}-\frac{2M^{2}\delta^{2}}{r_{\widetilde{W}}^{2}L^{2}(N-L)^{2}}\Bigg{)}.$
(92)

Letting the RHS be equal to $\Lambda$ and solving for $\delta$, one can show
with probability $1-\Lambda$,

$\left\lVert
B^{\top}\widetilde{W}^{-1}B-\widetilde{B}^{\top}\widetilde{W}^{-1}\widetilde{B}\right\rVert_{2}\leq\frac{r_{\widetilde{W}}L(N-L)}{M}\sqrt{\frac{1}{2}\log\Bigg{(}\frac{2(N-L)^{2}}{\Lambda}\Bigg{)}}.$
(93)

This bounds the second term in Eq. (86) leaving us with $\left\lVert
W^{-1}-\widetilde{W}^{-1}\right\rVert_{2}$, which can be bound,

$\displaystyle\left\lVert W^{-1}-\widetilde{W}^{-1}\right\rVert_{2}$
$\displaystyle\leq c_{W^{-1}}c_{\widetilde{W}^{-1}}\left\lVert
W-\widetilde{W}\right\rVert_{2}$ (94) $\displaystyle\leq
c_{W^{-1}}c_{\widetilde{W}^{-1}}\sqrt{\frac{L^{2}}{2M}\log\left(\frac{2L^{2}}{\Lambda}\right)}$
(95)

where we define $c_{A}:=\left\lVert A\right\rVert_{2}$ for a given matrix $A$
with $A^{-1}$ being the pseudo-inverse for when $A$ is singular. The first
inequality uses the fact that $\left\lVert
W^{-1}-\widetilde{W}^{-1}\right\rVert=\left\lVert
W^{-1}(\widetilde{W}-W)\widetilde{W}^{-1}\right\rVert\leq\left\lVert
W^{-1}\right\rVert\left\lVert\widetilde{W}^{-1}\right\rVert\left\lVert\widetilde{W}-W\right\rVert$
and the second inequality uses the bound in Eq. (82). Now putting together the
bounds in equations (72), (75), (83), (82), (93), (86), (95) and (60), we
have,

$\displaystyle||K-\widetilde{K}||_{2}\leq
L\sqrt{\frac{1}{2M}\log\Bigg{(}\frac{2L^{2}}{\Lambda}\Bigg{)}}+\sqrt{\frac{NL}{2M}\log\Bigg{(}\frac{2NL}{\Lambda}\Bigg{)}}+$
$\displaystyle\frac{r_{\widetilde{W}}L(N-L)}{M}\sqrt{\frac{1}{2}\log\Bigg{(}\frac{2(N-L)^{2}}{\Lambda}\Bigg{)}}$
(96)
$\displaystyle+c_{B}^{2}c_{W^{-1}}c_{\widetilde{W}^{-1}}\sqrt{\frac{L^{2}}{2M}\log\left(\frac{2L^{2}}{\Lambda}\right)}+\mathcal{O}\Bigg{(}\frac{N}{\sqrt{L}}\Bigg{)}$
$\displaystyle\implies||K-\widetilde{K}||_{2}\leq\widetilde{\mathcal{O}}\Bigg{(}\frac{NL}{M}+$
$\displaystyle\frac{N}{\sqrt{L}}\Bigg{)}$ (97)

where in the second line we use the fact that $N>>L$ and the notation
$\widetilde{\mathcal{O}}$ to hide $\log$ dependencies. Furthermore, Eq. (97)
assumes that the matrix norms $c_{B},c_{W^{-1}},c_{\widetilde{W}^{-1}}$ do not
depend on the system dimension – i.e. $L$ and $N$. For cases of $c_{W^{-1}}$
and $c_{\widetilde{W}^{-1}}$, since we are really taking the pseudo-inverse by
selecting a $k$ rank approximation of $W$ with the $k$ largest positive
eigenvalues, it is possible in some sense retain control over these terms. The
norm of $B$ on the other hand is entirely dependent on the dataset. The worst
case scenario suggests a bound using the Frobenius norm,
$c_{B}\leq||B||_{F}=\sqrt{\sum_{i}^{N}\sum_{j}^{L}|B_{ij}|^{2}}\approx\sqrt{L(N-L)\overline{k}^{2}}$,
where $\overline{k}$ is the average kernel element. This is however a loose
upper bound that provides no further insight and it is often the case
$\overline{k}<<1/N$ for quantum kernels.

One of the main objectives of Eq. (97) is to understand the sampling
complexity required to bound the error between estimated and real kernels. We
find that to ensure this error is bounded we require $M\sim NL$. However, this
does not account for the potentially vanishing kernel elements that we discuss
further in B.8. Eq. (97) also highlights the competing interests of increasing
$L$ to obtain a better Nyström approximation while at the same time benefiting
from decreasing $L$ to reduce the error introduced from finite sampling many
elements.

####  B.5.3 Proof of Lemma 3: Prediction error of SVM-NQKE due to finite
sampling

In the previous section, we obtained a bound to $\left\lVert
K-\widetilde{K}\right\rVert$ that suggested $M\sim NL$ to bound this term with
respect to the error of finite samples that is introduced. This however does
not identify the samples required in order to bound the error on the output of
the SVM. In the noiseless case with Nyström approximation, given that we have
hypothesis of the form,
$h(x)=\mathrm{sign}\left(\sum_{i=1}^{N}\alpha_{i}k(x,x_{i})\right)$, where
$\alpha$ is obtained at training, let
$f(x)=\sum_{i=1}^{N}\alpha_{i}k(x,x_{i})$ so that
$h(x)=\mathrm{sign}\left(f(x)\right)$. We equivalently let the SVM constructed
through the estimated kernel be denoted as
$\widetilde{h}(x)=\mathrm{sign}\left(\widetilde{f}(x)\right)$ where
$\widetilde{f}(x)=\sum_{i=1}^{N}\alpha_{i}^{\prime}k^{\prime}(x,x_{i})$. In
this section, closely following [12] we obtain a bound on
$|f(x)-\widetilde{f}(x)|$ that will elucidate the samples required to suppress
the shot noise of estimation. We start by expanding,

$\displaystyle|f(x)-\widetilde{f}(x)|$
$\displaystyle=\left\lvert\sum_{i=1}^{N}\alpha_{i}^{\prime}k^{\prime}(x,x_{i})-\sum_{i=1}^{N}\alpha_{i}k(x,x_{i})\right\rvert$
(98)
$\displaystyle\leq\sum_{i=1}^{N}\left\lvert\alpha_{i}^{\prime}k^{\prime}(x,x_{i})-\alpha_{i}k(x,x_{i})\right\rvert$
(99)
$\displaystyle=\sum_{i=1}^{N}\left\lvert(\alpha_{i}^{\prime}-\alpha_{i})\left[k^{\prime}(x,x_{i})-k(x,x_{i})\right]+\alpha_{i}\left[k^{\prime}(x,x_{i})-k(x,x_{i})\right]+(\alpha_{i}^{\prime}-\alpha_{i})k(x,x_{i})\right\rvert$
(100)
$\displaystyle\leq\left\lVert\alpha\right\rVert_{2}\cdot\left\lVert\nu(x)\right\rVert_{2}+\left\lVert\alpha^{\prime}-\alpha\right\rVert_{2}\cdot\left\lVert\nu(x)\right\rVert_{2}+\sqrt{N}\left\lVert\alpha^{\prime}-\alpha\right\rVert_{2},$
(101)

where we let $\nu_{i}(x)=\nu_{i}=k^{\prime}(x,x_{i})-k(x,x_{i})$, and where
the last line uses the Cauchy-Schwarz inequality and the fact that
$k(\cdot,\cdot)\leq 1$. The term $\left\lVert\nu\right\rVert_{2}$ is bounded
in a similar fashion to (86), as the kernel function is passed through the
Nyström feature map (NFM). This gives
$\left\lVert\nu\right\rVert_{2}\leq\mathcal{O}(\sqrt{L^{2}/2M}+NL/M)$ where we
assume $c_{k},c_{W^{-1}},c_{\widetilde{W}^{-1}}$ to be bounded independent of
$N$. Both terms, $\left\lVert\alpha\right\rVert_{2}$ and
$\left\lVert\alpha^{\prime}-\alpha\right\rVert_{2}$, need slightly more work.

The SVM dual problem in (19) can be written in the following quadratic form
for $\mu=0$ with regularisation $\lambda$,

minimise
$\displaystyle\frac{1}{2}\alpha^{\top}\left(Q+\frac{1}{\lambda}\mathbb{I}\right)-1^{\top}\alpha$
subject to: $\displaystyle\alpha_{i}\geq 0,\forall i=1,....,N.$ (102)

where $Q_{ij}=y_{i}y_{j}K_{ij}$. This allows us to use the following
robustness Lemma on quadratic programs.

######  Lemma 5.

([56], Theorem 2.1) Given a quadratic program of the form in (102), let
$Q^{\prime}$ be a perturbation of $Q$ with a solution of $\alpha^{\prime}$ and
$\alpha$ respectively. Given that $\left\lVert
Q^{\prime}-Q\right\rVert_{\mathrm{F}}\leq\epsilon<\lambda_{\mathrm{min}}$,
where $\lambda_{\mathrm{min}}$ is the minimum eigenvalue of
$Q+\frac{1}{\lambda}\mathbb{I}$, then,

$\left\lVert\alpha^{\prime}-\alpha\right\rVert_{2}\leq\epsilon(\lambda_{\mathrm{min}}-\epsilon)^{-1}\left\lVert\alpha\right\rVert_{2}.$
(103)

Note, this Lemma assumes small perturbations and breaks down for when
$\epsilon\geq\lambda_{\mathrm{min}}$. It can be shown from analysing the
solutions from the KKT conditions that
$\mathbb{E}[\left\lVert\alpha\right\rVert_{2}^{2}]=\mathcal{O}(N^{2/3})$ – see
[12] (Lemma 16) for further details. This finally leaves us with bounding
$\left\lVert Q^{\prime}-Q\right\rVert_{\mathrm{F}}$. We know,

$\displaystyle\left\lVert Q^{\prime}-Q\right\rVert_{\mathrm{F}}^{2}$
$\displaystyle=\sum_{ij}|Q^{\prime}_{ij}-Q_{ij}|^{2}=\sum_{ij}|y_{i}y_{j}K^{\prime}_{ij}-y_{i}y_{j}K_{ij}|^{2}$
(104) $\displaystyle=\sum_{ij}|K^{\prime}_{ij}-K_{ij}|^{2}=\left\lVert
K^{\prime}-K\right\rVert_{\mathrm{F}}^{2}.$ (105)

Since we are bounding the error between estimated and real matrices (both
including Nyström approximation), we in fact require the bound
$\left\lVert\widetilde{K}-\widehat{K}\right\rVert_{\mathrm{F}}$ from (54) and
(71), i.e. we have $K=\widehat{K}$ and $K^{\prime}=\widetilde{K}$. We compute
this in Section B.5.2 to be $\left\lVert
K^{\prime}-K\right\rVert_{\mathrm{F}}\leq\mathcal{O}\left(\frac{NL}{M}+\sqrt{\frac{NL}{M}}\right)$
– noting that we always weakly bound the spectral norm with the Frobenius
norm,
$\left\lVert\cdot\right\rVert_{2}\leq\left\lVert\cdot\right\rVert_{\mathrm{F}}$.
Therefore, using Lemma 5 with the fact that $\lambda_{\text{min}}\geq
1/\lambda$ for constant $\lambda$, we have,

$\left\lVert\alpha^{\prime}-\alpha\right\rVert_{2}\leq\mathcal{O}\left(\frac{N^{5/6}\sqrt{L}}{\sqrt{M}}\right).$
(106)

Substituting these results into Eq. (101), we obtain the bound on the error of
the model output,

$|f(x)-\widetilde{f}(x)|\leq\mathcal{O}\left(\frac{N^{4/3}\sqrt{L}}{\sqrt{M}}\right)=\mathcal{O}\left(\sqrt{\frac{N^{8/3}L}{M}}\right),$
(107)

as required. Therefore we see that $M\sim N^{3}L$ is sufficient to suppress
error in the model output. Note, Eq. (107) only shows the term most difficult
to suppress with respect to $M$.

###  B.6 Processing datasets for numeric analysis

This work observes the performance of the QRF on five publicly available
datasets. In certain cases, continuous features were selected as class labels
by introducing a separating point in $\mathbb{R}$ such as to split the number
of data points evenly in two. A summary of the original datasets are presented
in the table below.

Datasets
---
Name | Denoted | # of points | $|\mathcal{X}|$ |  Class labels |  Reference
Fashion MNIST | $\mathcal{D}_{\mathrm{FM}}$ | 70,000 | $28\times 28$ |  Originally $10$ classes with $7000$ per class. Binary class transformation uses class $0$ (top) and $3$ (dress). |  Zolando’s article images [57]
Breast Cancer | $\mathcal{D}_{\mathrm{BC}}$ | 569 | 30 |  This is a binary class dataset. |  UCI ML Repository [58]
Heart Disease | $\mathcal{D}_{\mathrm{H}}$ | 303 | 13 |  The class is defined as $0$ and $1$ for when there is respectively a less than or greater than $50\%$ chance of disease. |  UCI ML Repository [58]
Ionosphere | $\mathcal{D}_{\mathrm{Io}}$ | 351 | 34 |  This is a binary class dataset. |  UCI ML Repository [58]

Note: $|\mathcal{X}|$ indicates the dimension of the feature space after
accounting for any removal of categorical features and the possible use of a
feature to create class labels. Finally, the analysis of various QRF
parameters use the Fashion MNIST dataset. To ensure the analysis has tractable
computation, $300$ points are sampled for each training and testing (unless
otherwise stated) – which partially accounts for the variance in accuracies
observed.

####  B.6.1 Data pre-processing

Given the original dataset
$\mathcal{S}_{\mathrm{tot}}^{\prime\prime}=\\{(x_{i}^{\prime\prime},y_{i})\\}_{i=1}^{N}$
where $x_{i}^{\prime\prime}\in\mathbb{R}^{D^{\prime}}$ and
$y_{i}\in\\{-1,+1\\}$ in this section we show the pre-processing steps
undertaken prior to the QRF learning process. The first step mean-centres each
of the features of the dataset and employs principal component analysis [59]
to obtain $D<D^{\prime}$ dimensional points, giving a the dataset
$\mathcal{S}_{\mathrm{tot}}^{\prime}=\\{(x_{i}^{\prime},y_{i})\\}_{i=1}^{N}$
where $x^{\prime}\in\mathbb{R}^{D}$. In practice, this dimensionality
reduction technique is a common pre-processing step for both classical and
quantum ML. The technique selects the $D$-most primary directions in which the
data is spread and subsequently projects the data points onto the plane
spanned by those directions – see [38] for more details. This gives us control
over the dimensionality of the data given to the QRF – this being especially
important with the $\Phi_{\mathrm{IQP}}$ embedding over $n$ qubits requiring
an exact dimension of $n$. Furthermore, PCA relies on the principle that data
often lies in a lower dimensional manifold [25] hence, resulting in PCA
reduction often aiding the learning model to avoid noise. Therefore it becomes
crucial to include the pre-processing step of a PCA reduction when comparing
between learning models. This highlights observation in the main text where we
see a degradation in performance when increasing number of qubits for the
Fashion MNIST data. Though it may seem as though we can make a statement about
the ineffectiveness of quantum kernels with increasing qubit numbers, this
misses the effect of PCA in the pre-processing step. This is why both the
classical and quantum models struggle when $D$ is increased.

The second step in pre-processing is unique to quantum models. Before data can
be inserted into the QRF algorithm, we are required to process these classical
vectors $x^{\prime}\in\mathbb{R}^{D}$ so that features can be effectively
mapped to single qubit rotations. This is done by observing each dimension
(feature), $\Omega_{i}$, of the space consumed by the set of all data points
(including training and testing) and normalising so that the range of values
lie between $0$ and $\pi$. Mathematically we make the transformation,
$x_{i}^{\prime}\xrightarrow{}x_{i}=\pi(r^{\mathrm{min}}_{i}+x^{\prime})/(r^{\mathrm{max}}_{i}-r^{\mathrm{min}}_{i})$
where
$r^{\mathrm{min}}_{i}=\min\\{x^{\prime}|(x^{\prime},y)\in\mathcal{S}_{\mathrm{tot}}^{\prime}\\}$
and $r^{\mathrm{max}}_{i}$ is defined similarly. The final dataset is
therefore given by $\mathcal{S}_{\mathrm{tot}}=\\{(x_{i},y)\\}_{i=1}^{N}$
where $x_{i}\in[0,\pi]^{D}$ and $y_{i}\in\\{-1,+1\\}$. The embedding into half
a rotation $[0,\pi]$, as opposed to full rotations of $[0,2\pi]$ or
$[-\pi,\pi]$, is to ensure that the ends of the feature spectrum,
$r^{\mathrm{min}}$ and $r^{\mathrm{max}}$, are not mapped to similar quantum
states.

####  B.6.2 Relabelling datasets for optimal quantum kernel performance,
$\mathscr{R}_{\Phi}^{\text{QK}}$

To demonstrate that QML is able to achieve an advantage over it’s classical
counterpart, a crucial first-step would be to show that there at least exist
artificial datasets in which quantum models outperform classical methods. We
generate such a dataset by relabelling a set of real data points so that a
classical kernel struggles and quantum kernel does not. This is done by
maximising the model complexity – and hence generalisation error – of the
classical kernel while at the same time minimising the model complexity of the
quantum kernel. This is precisely the strategy followed in [33], where the
regime of potential quantum advantage was posited to be related to – what the
authors referred to as – the geometric difference, $G$, between quantum and
classical models. This quantity was shown to provide an upper-bound to the
ratio of model complexities – more specifically,
$G_{CQ}\geq\sqrt{s_{C}/s_{Q}}$. The task of relabelling is therefore to solve
the following optimisation problem,

$Y^{*}=\operatorname*{arg\,max}_{Y\in\\{0,1\\}^{N}}\frac{s_{C}}{s_{Q}}=\operatorname*{arg\,max}_{Y\in\\{0,1\\}^{N}}\frac{Y^{\top}(K^{C})^{-1}Y}{Y^{\top}(K^{Q})^{-1}Y}$
(108)

where $Y^{*}=[y_{1},...,y_{N}]$ are the optimal relabelled instances and
$K^{C}$, $K^{Q}$ are Gram matrices for the classical and quantum kernels,
respectively. This is related to the process of maximising the kernel target
alignment measure [37], where in order for a kernel to have high performance,
the targets, $Y$, must be well aligned with the transformed set of instances.
The quantity is more intuitive and has the form,

$\mathcal{T}(K)=\frac{\sum_{i=1}^{N}\sum_{j=1}^{N}K_{ij}y_{i}y_{j}}{N\sqrt{\sum_{i=1}^{N}\sum_{j=1}^{N}K_{ij}^{2}}}=\frac{Y^{\top}KY}{N\left\lVert
K\right\rVert_{F}}$ (109)

where $||\cdot||_{F}$ is the Frobenius norm. Therefore, the equivalent
optimisation problem of Eq. (108) becomes the minimisation of the quantity
$\mathcal{T}(K^{C})/\mathcal{T}(K^{Q})$. Nevertheless, the optimisation
problem in Eq. (108) can be transformed to a generalised eigenvalue problem of
the following form by replacing $Y\xrightarrow{}\phi\in\mathbb{R}^{N}$,

$(K^{C})^{-1}\phi=\lambda(K^{Q})^{-1}\phi$ (110)

where $\phi$ and $\lambda$ are the eigenvectors and eigenvalues respectively.
As (108) is a maximisation problem the solution is therefore the eigenvector
$\phi^{*}$ associated with the largest eigenvalue $\lambda^{*}$. To obtain an
exact solution, we use the fact that the generalised eigenvalue decomposition
is related to the regular decomposition of
$\sqrt{K^{Q}}(K^{C})^{-1}\sqrt{K^{Q}}$ with identical eigenvalues
$\lambda_{i}$. Hence, supposing a decomposition of
$\sqrt{K^{Q}}(K^{C})^{-1}\sqrt{K^{Q}}=Q\Lambda Q^{\top}$, where
$\Lambda=\mathrm{diag}(\lambda_{1},...,\lambda_{N})$, it can be shown that
$\phi^{*}=\sqrt{K^{Q}}q^{*}$ [60], where $q^{*}$ is the eigenvector associated
with the largest eigenvalue, $\lambda^{*}$. The continuous vector $\phi^{*}$
can then be transformed into labels by simply taking the sign of each entry.
Furthermore, following [33] we also inject randomness, selecting the label –
for a given data point $x_{i}$ – as $y_{i}=\mathrm{sign}(\phi_{i})$ with
probability $0.9$ and randomly assigning $y_{i}=\pm 1$ otherwise. This is
relabelling strategy is denoted as
$(y_{i})_{i}=\mathscr{R}_{\Phi}^{\text{QK}}(\\{(x_{i},y_{i}^{\prime})\\}_{i})$.

It is important to note, the relabelling of datasets is dependent on the
specific quantum and classical kernels employed. In this work, the radial
basis function  kernel is used as the classical kernel and we obtain different
labels depending on the quantum embedding used, $\Phi_{\mathrm{IQP}}$ or
$\Phi_{\mathrm{Eff}}$.

####  B.6.3 Relabelling datasets for optimal QRF performance,
$\mathscr{R}_{\Phi}^{\text{QRF}}$

Classically, SVMs require kernels in cases where points in the original
feature space are not linearly separable. A simple example is shown in Figure
7a where any single hyperplane in this space cannot separate the two classes.
However, it is clear that a tree structure with multiple separating
hyperplanes has the ability to separate the clusters of points. This inspires
a relabelling strategy that attempts to separate instances into four regions
using a projection to a particular axis. Since we are able to only compute the
inner products of instances and do not have access to the direct induced
Hilbert space, we randomly select two points, $x^{\prime}$ and
$x^{\prime\prime}$, to form the axis of projection. Projection of point $z$
onto this axis is given by the elementary vector projection,

$\frac{\langle
z-x^{\prime},x^{\prime\prime}-x^{\prime}\rangle_{\mathcal{H}}}{\sqrt{\lvert\langle
x^{\prime\prime}-x^{\prime},x^{\prime\prime}-x^{\prime}\rangle_{\mathcal{H}}\rvert}}$
(111)

where we have specified the inner product over the reproducing Hilbert space
$\mathcal{H}$ associate with some quantum kernel $k$. Using the fact that
points $x^{\prime}$ and $x^{\prime\prime}$ are fixed, we define a projection
measure of the form,

$P(x_{i})=\langle x_{i},x^{\prime\prime}\rangle_{\mathcal{H}}-\langle
x_{i},x^{\prime}\rangle_{\mathcal{H}}=k(x_{i},x^{\prime\prime})-k(x_{i},x^{\prime}):=P_{i}$
(112)

where $P_{i}:=P(x_{i})$ for $x_{i}\in\mathcal{S}|_{\mathcal{X}}$. We now label
the classes such that we have alternating regions,

$Y_{i}=\begin{cases}0&\text{if }P_{i}<P^{(\mathrm{q1})}\text{ or
}P^{(\mathrm{q2})}\leq P_{i}<P^{(\mathrm{q3})}\\\
1&\text{otherwise}\end{cases}$ (113)

where $P^{(\mathrm{q1})},P^{(\mathrm{q2})},P^{(\mathrm{q3})}$ are the first,
second and third quartiles of $\\{P_{i}\\}_{i=1}^{N}$, respectively. An
illustration of this relabelling process can be seen in Figure 7a. One should
note, unlike the relabelling strategy of Section B.6.2, here we do not compare
against the performance of the classical learner. The intuition – and what we
observe numerically – is that a clear division in the quantum induced Hilbert
space does not translate to a well-defined division employing classical
kernels. Therefore we have a labelling scheme that is in general both hard for
classical learners as well as QSVMs. This relabelling process will be referred
to as
$(y_{i})_{i}=\mathscr{R}_{\Phi}^{\text{QRF}}(\\{(x_{i},y_{i}^{\prime})\\}_{i})$.

Figure 7: Both Figures depict concept classes that are not learnable by simple
hyperplanes. (a) Two points are randomly selected (green) for the relabellingn
process $\mathscr{R}_{\Phi}^{\text{QRF}}$ elaborated in B.6.3. This creates an
alternating pattern in $\mathcal{H}_{\Phi}$. Note, in high dimension points
become sparsely separated, resulting in only slight advantage of the QRF
against other learners. (b) Here we observe an extension of the DLP
classification problem [12] into two dimensions. The torus is split into four
alternating regions at $s^{\prime}$ and $s^{\prime\prime}$. Since this
separation exists in log-space, classical learners are presumed unable to
solve this problem due to the hardness of solving DLP. Furthermore, since
multiple hyperplanes are required, a simple quantum kernel also fails.

###  B.7 Learning advantage with a QRF

In the main text we asserted that the QRF can extend the linear hypotheses
available to linear quantum models. In this section we show that there are
problems that are both difficult for quantum kernels (and by extension QNNs
[15]) and classical learners. We claim advantages using the QRF model by
observing the hypothesis set available as a result of the QDT structure. We
assume that we have $L=N$ models. In other words, we look at QDTs that do not
take a low-rank Nyström approximation.

To show there exist concept classes that are unlearnable by both classical
learners and quantum linear models we extend the DLP-based concept class given
in [12]. The work looks at the class
$\mathscr{C}_{\text{QK}}=\\{f_{s}^{\text{QK}}\\}_{s\in\mathbb{Z}_{p}^{*}}$
where,

$f_{s}^{\text{QK}}(x)=\begin{cases}+1&\text{if}\log_{g}x\in[s,s+\frac{p-3}{2}]\\\
-1&\text{otherwise},\end{cases}$ (114)

and $x\in\mathbb{Z}_{p}^{*}$, for generator $g$ of
$\mathbb{Z}_{p}^{*}=\\{1,2,...,p-1\\}$ with large prime $p$. Each concept of
the concept class divides the set $\mathbb{Z}_{p}^{*}$ into two sets, giving
rise to a binary class problem. It is important to note, the problem is a
trivial $1$D classification task on the assumption one can efficiently solve
the DLP problem. However, it can be shown that the DLP problem lies in BQP and
is otherwise presumed to be classically intractable. This gives rise to a
quantum advantage in learning the concept class $\mathscr{C}_{\text{QK}}$ with
a quantum kernel with the following quantum feature map:

$\ket{\Phi_{\text{DLP}}^{q}(x_{i})}=\frac{1}{\sqrt{2^{q}}}\sum_{j\in\\{0,1\\}^{q}}\ket{x_{i}\cdot
g^{j}}$ (115)

where $x_{i}\in\\{0,1\\}^{n}$ over $n=\lceil\log_{2}p\rceil$ qubits, and
$q=n-t\log n$ for some fixed $t$. This state can be efficiently prepared with
a fault-tolerant quantum computer using Shor’s algorithm [61]. Such embeddings
can be interpreted as interval states, as they are a superposition over an
interval in log-space, $[\log x,\log x+2^{q}-1]$. The subsequent kernel
function,
$k(x_{i},x_{j})=|\langle\Phi_{\text{DLP}}^{q}(x_{j})|\Phi_{\text{DLP}}^{q}(x_{i})\rangle|^{2}$
can therefore be interpreted as the interval intersection of the two states in
log-space. Guarantees of the inability to classically estimate these kernel
elements up to additive error follow identically to proofs supplied in [12].

Now, to show that there exist advantages of using a QRF, we construct a
different concept class,
$\mathscr{C}_{\text{QRF}}=\\{f_{s^{\prime},s^{\prime\prime}}^{\text{QRF}}\\}_{s^{\prime},s^{\prime\prime}\in\mathbb{Z}_{p}^{*}}$
where we have,

$f_{s^{\prime},s^{\prime\prime}}^{\text{QRF}}(x)=\begin{cases}+1&\text{if}\log_{g}x^{(0)}\in[s^{\prime},s^{\prime}+\frac{p-3}{2}]\text{
and }\log_{g}x^{(1)}\notin[s^{\prime\prime},s^{\prime\prime}+\frac{p-3}{2}]\\\
+1&\text{if}\log_{g}x^{(0)}\notin[s^{\prime},s^{\prime}+\frac{p-3}{2}]\text{
and }\log_{g}x^{(1)}\in[s^{\prime\prime},s^{\prime\prime}+\frac{p-3}{2}]\\\
-1&\text{otherwise}\end{cases},$ (116)

and where $x=(x^{(0)},x^{(1)})\in\mathbb{Z}_{p}^{*}\times\mathbb{Z}_{p}^{*}$
for generator $g$ of $\mathbb{Z}_{p}^{*}$. This can be interpreted as a
separation of a torus into four segments as shown in Figure 7b. The associated
quantum feature map can be constructed through the tensor product,
$\ket{\Phi_{\text{DLP}^{\otimes
2}}^{q}(x_{i})}=\ket{\Phi_{\text{DLP}}^{q}(x_{i}^{(0)})}\ket{\Phi_{\text{DLP}}^{q}(x_{i}^{(1)})}$
over $n=2\lceil\log_{2}p\rceil$ qubits. This gives a kernel function of the
form,
$k(x_{i},x_{j})=|\langle\Phi_{\text{DLP}}^{q}(x_{j}^{(0)})|\Phi_{\text{DLP}}^{q}(x_{i}^{(0)})\rangle|^{2}\cdot|\langle\Phi_{\text{DLP}}^{q}(x_{j}^{(1)})|\Phi_{\text{DLP}}^{q}(x_{i}^{(1)})\rangle|^{2}$
which by Theorem 2 is a valid product kernel of DLP kernels. The
interpretation of this kernel function is now a $2$D interval (area) in log-
space.

Since concepts $\mathscr{C}_{\text{QRF}}$ can not be learned with a single
hyperplane in log-space, a quantum kernel with a $\Phi_{\text{DLP}^{\otimes
2}}^{q}$ embedding will be unable to learn this concept. Classical methods
also fail due to the assumed hardness of the DLP problem. In comparison, a QDT
with its tree structure, is able to construct multiple decision boundaries to
precisely determine the regions of different classes. In practice, there is
high likelihood of any single QDT overfitting to the given samples – hence
requiring an ensemble of QDTs to form a QRF model.

Finally, it important to note that we are only claiming that the concept class
$\mathscr{C}_{\text{QRF}}$ is unlearnable by QSVMs and potentially learnable
by a QRF. There clearly exist a hypothesis $h_{c}\in\mathbb{H}_{\text{QDT}}$
that emulates a particular concept $c\in\mathscr{C}_{\text{QRF}}$. However,
this does not say anything about the ability of the QRF algorithm to obtain
$h_{c}$ with a particular training set sampled from $c$. Hence there remains
the question of whether there exists an evaluation algorithm $\mathcal{A}$,
such that given a training set
$\mathcal{S}_{c}=\\{x_{i},c(x_{i})\\}_{i=1}^{N}$, we have
$\mathcal{A}(\mathcal{S}_{c})|_{x=x^{\prime}}=h(x^{\prime})\approx
c(x^{\prime})$ for some predefined $c\in\mathscr{C}_{\text{QRF}}$.

###  B.8 Limitations of quantum kernel methods

Recent work [62] has shown that quantum kernels can be constructed to present
quantum advantage using any BQP decision problem; however, there is a lack of
evidence that it provides any benefit when dealing with real-world data.
Though they are crucial milestones in the development of QML, such
constructions – including the advantage shown in [12] – embed solutions to the
learning problem with the specific embedding employed. It is hard to see the
set of model hypotheses, arising from the DLP embedding [12], be useful in any
other problem disregarding the specific example it was designed for.
Therefore, as was required in the development of effective classical kernels,
further research is required to construct relevant embeddings for practical
problems [14].

Obtaining appropriate embeddings, one needs to also consider the curse of
dimensionality [63]. With greater dimensions, a larger number of samples of
data points are required to understand patterns in this space. Though
obtaining a separation between sparsely distributed points is generally easier
(Cover’s theorem [23]), they are far more prone to overfitting. Therefore,
generalisability seems to be unlikely with the exponential growth of the
Hilbert space with respect to the number of qubits. Furthermore, as the
dimensions increase, points are sent to the peripheries of the feature space,
resulting in the inner product becoming meaningless in high dimension. This
results in kernel matrix elements being exponentially (with respect to the
number of qubits) suppressed to zero. Hence, each kernel element would require
an exponentially large number of samples to well-approximate the vanishing
kernel elements. Though it was seen that the Nyström approximation allowed for
a smaller complexity of shots to bound the error in the kernel matrix, $M\sim
NL$ (see Section B.5), this does not take into account a vanishing kernel
element. Bernoulli trials have variance, $\frac{(1-k)k}{M}$ for kernel element
$k$. This means that for $k\sim 2^{-n}$ we are required to have
$M\sim\mathcal{O}(2^{n})$ to distinguish elements from zero. This was
discussed in [13] and specific embeddings were constructed so that kernel
elements did not vanish with larger numbers of qubits. To further aide with
this problem, reducing the bandwidth parameter of quantum kernels is seen to
improve generalisation [64, 65]. In essence, both these methods work to reduce
the volume of Hilbert space explored, resulting in larger inner products.

Finally, there is also the practical questions of the effect of noise and
finite sampling error on the kernel machine optimisation. The SVM problem is
convex, however this is not true once errors are incorporated. In [12], the
effect of such errors to the optimal solution are explored. It is shown that
the noisy halfspace learning problem is robust to noise with
$M\sim\mathcal{O}(N^{4})$. However, this is an extremely large number of shots
that very quickly becomes impractical for even medium-size datasets. It is
crucial that work is done to reduce this complexity if we are to see useful
implementations of kernel methods. In the case of the QRF, we welcome weak
classifiers and there are arguments for such errors being a natural
regulariser to reduce overfitting [42].

##  Appendix C Summary of Variables

There are many moving parts and hyperparameters to the QRF model. We therefore
take the chance to list out most of the parameters used throughout the paper.
Hopefully this saves many the headache of scavenging for definitions.

Parameter List
---
$\mathscr{C}$ |  Concept class. See Section B.7 for concept class based on DLP. | $C$ |  Penalty parameter for fitting SVM, $C\propto 1/\lambda$.
$\mathcal{C}$ |  The set of classes. | $d$ |  Maximum depth of QDT.
$D$ |  Dimension of the original classical feature space, $x_{i}\in\mathbb{R}^{D}$ or equivalently $D=\mathrm{dim}(\mathcal{X})$. | $\mathcal{D}$ |  Indicates a specific dataset with $\mathcal{S}=\\{(x_{i},y_{i})|(x_{i},y_{i})\sim\mathcal{D}\\}_{i=1}^{N}$ forming the training set.
$G_{KW}$ |  Geometric difference between kernels $K$ and $W$ – see discussion in Section B.6.2. | $\mathcal{H}$ |  Hilbert space. $\mathcal{H}_{\Phi}$ refers to the quantum feature space induced by the embedding $\Phi$.
$\mathbb{H}$ |  Hypothesis set - see Section A.3. | $k(x^{\prime},x^{\prime\prime})$ |  Kernel function.
$K$ |  Gram matrix or also referred to as the kernel matrix, $K_{ij}=k(x_{i},x_{j})$. | $L$ |  Number of landmark points chosen for Nyström approximation – see Section A.4.
$M$ |  Number of samples taken from each quantum circuit (shots). | $n$ |  Number of qubits.
$N$ |  Total number of training instances. | $\mathcal{N}_{\Phi,L}^{(i)}$ |  Denotes $i^{\text{th}}$ node with embedding $\Phi$ and $L$ landmark points.
$\mathbf{N}(\cdot)$ |  Nyström feature map. See definition in Eq. (58). | $\mathcal{R}(h)$ |  Generalisation error for hypothesis $h$ – see Def. 4. $\widehat{\mathcal{R}}(h)$ refers to the empirical error.
$\mathfrak{R}_{\mathcal{S}}$ |  Rademacher complexity over dataset $\mathcal{S}$. The Empirical Rademacher complexity is then given by $\widetilde{\mathfrak{R}}_{\mathcal{S}}$, see Section A.3. | $\mathscr{R}_{\Phi}$ |  Relabelling function for a given embedding $\Phi$. Can either be $\mathscr{R}^{\text{QK}}_{\Phi}$ or $\mathscr{R}^{\text{QRF}}_{\Phi}$ with explanations in Sections B.6.2 and B.6.3 respectively.
$s_{K}$ |  Model complexity for kernel $K$ defined as $s_{K}=Y^{\top}K^{-1}Y$ for given training labels $Y$. | $\mathcal{S}^{(i)}$ |  Training set available at node $i$. $\mathcal{S}_{\mathrm{tot}}$ refers to all data points (including training and testing) from a given dataset. $\mathcal{S}|_{\mathcal{X}}$ refers to the data vectors.
$T$ |  Number of trees in the QRF. | $\mathcal{T}(K)$ |  Kernel target alignment measure given Gram matrix $K$. Quantity defined in Eq. (109).
$\lambda$ |  Regularisation parameter for fitting SVM, $\lambda\propto 1/C$. | $\Phi$ |  Indicates the quantum embedding and takes the form $\Phi_{\mathrm{IQP}}$ or $\Phi_{\mathrm{Eff}}$ defined in Section B.2.
$\gamma_{i}$ |  Margin at node labelled $i$. | $F^{(i)}(\cdot)$ |  Pseudo class map that defines the binary class for the splitting at node $i$. Refer to Section B.3.
$\mathcal{X}$ |  Feature space. | $\mathcal{Y}$ |  The set of class labels.