# Two Dimensional Electromagnetic Scattering from Dielectric Objects using
Qubit Lattice Algorithm

George Vahala  Department of Physics, William & Mary, Williamsburg, VA23185
Min Soe  Department of Mathematics and Physical Sciences, Rogers State
University, Claremore, OK 74017  Linda Vahala  Department of Electrical &
Computer Engineering, Old Dominion University, Norfolk, VA 12319  Abhay K. Ram
Plasma Science and Fusion Center, MIT, Cambridge, MA 02139

$\bf{Abstract}$: A qubit lattice algorithm (QLA) is developed for Maxwell
equations in a two-dimensional Cartesian geometry. In particular, the initial
value problem of electromagnetic pulse scattering off a localized 2D
dielectric object is considered. A matrix formulation of the Maxwell
equations, using the Riemann-Silberstein-Weber vectors, forms a basis for the
QLA and a possible unitary representation. The electromagnetic fields are
discretized using a 16-qubit representation at each grid point. The
discretized QLA equations reproduce Maxwell equations to second order in an
appropriate expansion parameter $\epsilon$. The properties of scattered waves
depend on the scale length of the transition layer separating the vacuum from
the core of the dielectric. The time evolution of the fields gives interesting
physical insight into scattering when propagating fields are excited within
the dielectric medium. Furthermore, simulations show that the QLA recovers
Maxwell equations even when $\epsilon\sim 1$.

##  1 Introduction

It is important to develop algorithms that can be ideally parallelized on
classical supercomputers and, with a little tweaking, can also be run on
error-correcting quantum computers. One class of such mesoscopic algorithms is
the qubit lattice algorithm (QLA) [1-20]. QLA typically consists of an
interleaved sequence of unitary collision and streaming operators acting on an
appropriate basis set, e.g., a basis set of qubits. Under appropriate moments
and in the continuum limit the QLA operators can be so chosen that the desired
continuum equations will be recovered. For example, QLAs have been developed
for the one-dimensional (1D) nonlinear Schrodinger equation (NLS) and the
Korteweg-De Vries (KdV) equation [6, 9-11] to study soliton dynamics and to
benchmark the QLA. Different choice of unitary collision operators are needed
to, for example, recover the $\partial^{2}/\partial x^{2}$ for NLS or remove
this second derivative but have instead the $\partial^{3}/\partial x^{3}$ for
KdV.

The application of quantum information science to plasma physics has drawn
interest in recent years [21-24]. Electromagnetic waves are ubiquitous in
laboratory, space, and astrophysical plasmas. The waves can be externally
generated by an antenna and coupled to a plasma, or internally generated by a
plasma instability. In either case, an analysis of the propagation and damping
of waves is essential – whether for determining the spatial profile of power
deposition or for diagnosing the interior of a hot plasma. The allure for
developing a QLA for electromagnetic wave propagation is the connection
between the relativistically invariant Maxwell equations and the Dirac
equation for a relativistic particle [25-27]. Following this connection, Khan
[28] has used the Riemann-Silberstein-Weber vectors to express Maxwell
equations, for an inhomogeneous scalar dielectric medium, as a matrix
evolution equation of an 8-spinor. However, in this representation, the
8-spinor evolution equation is not fully unitary; the operators which include
the derivative of the refractive index are Hermitian. For a homogeneous
dielectric medium, the 8-spinor representation decouples into two independent
4-spinor equations which are immediately unitary. (Physically this implies
that in a homogeneous medium the two electromagnetic field polarizations
decouple.)

The backbone of the QLA for Maxwell equations is the realization that, for a
homogeneous medium, the 4-spinor representation has the same structure as the
Dirac equation for a massless free particle[1, 17]. The only difference being
in the linear couplings of the spinor components. Thus, we are able to
generalize Yepez’s [1] QLA construction for the Dirac equation to construct
the required unitary collision operator which recovers Maxwell equations to
second order accuracy in terms of a small parameter introduced in the
collision angle.

Recently [17, 29] we studied the 1D QLA for Maxwell equations by considering
the initial value problem of a _pulse_ propagating normal to a dielectric
slab. This is a generalization of the classic boundary value problem of an
incident _plane wave_ onto a discontinuous dielectric medium. From the
boundary conditions at the interface, assuming reflected and transmitted plane
waves, one obtains the classic Fresnel equations for the ratios of the
electric field amplitudes,

$\displaystyle\frac{E_{refl}}{E_{inc}}=\frac{n_{1}-n_{2}}{n_{1}+n_{2}}\qquad,\qquad\frac{E_{trans}}{E_{inc}}=\frac{2n_{1}}{n_{1}+n_{2}}$

where the plane wave propagates from medium with refractive index
$n_{1}\rightarrow n_{2}$. In our 1D QLA initial value problem of an incident
pulse onto a thin dielectric boundary layer we immediately realize there are
significant differences from the boundary value plane wave problem: the pulse
has finite width and at particular time intervals it will straddle the
boundary layer region with parts of the pulse in medium $n_{1}$ and parts of
it in medium $n_{2}$. In the QLA simulations there are no internal boundary
conditions applied. Interestingly all the plane wave jump conditions are
recovered by our 1D QLA simulations [17, 29] except for the ratio of the
transmitted to incident electric field amplitudes. In particular we find,

$\displaystyle\frac{E_{refl}}{E_{inc}}=\frac{n_{1}-n_{2}}{n_{1}+n_{2}}\qquad,\quad\frac{E_{trans}}{E_{inc}}=\frac{2n_{1}}{n_{1}+n_{2}}\sqrt{\frac{n_{2}}{n_{1}}}.$

The QLA simulations lead to an extra factor of $\sqrt{n_{2}/n_{1}}$ in the
ratio of the transmitted to the incident electric fields. The simulations show
the ubiquitousness of this factor, independent of the choices of $n_{1}$ and
$n_{2}$, as well as various pulse shapes. Following the simulation results
[29], we developed a theory for Gaussian pulses to prove the existence of this
factor $\sqrt{n_{2}/n_{1}}$ [29].

Here we are concerned with developing a 2D QLA and performing QLA simulations
for the propagation of a 1D electromagnetic pulse in the $x-$direction and
incident onto a 2D localized dielectric medium of refractive index $n(x,z)$.
In Sec. 2 we summarize the Khan [28] 8-spinor representation of the
inhomogeneous 2D Maxwell equations, while in Sec. 3 we discuss the details of
the 2D 16-qubit QLA for $x-z$ dependent fields. In Sec. 4 we present details
of the 2D QLA simulations off various dielectric geometries, showing cases
where there is multiple internal reflections within the dielectric medium and
conditions under whcih there are no significant internal reflections. We
discuss the $\nabla\cdot\bf{B}$ condition and the role of the collision angle
perturbation parameter $\varepsilon$ and its interpretation as a normalized
speed of light in the initial medium. In Sec. 5 we summarize our conclusions.

##  2 Matrix representation of Maxwell equations in a scalar dielectric medium

The Maxwell equations for wave propagation in a spatially dependent scalar
dielectric are,

$\displaystyle\nabla\bm{.}\mathbf{D}\ $ $\displaystyle=\ \rho_{f},\ $
$\displaystyle\ \nabla\bm{.}\mathbf{B}\ $ $\displaystyle=\ 0,$ (1)
$\displaystyle\nabla\times\mathbf{E}\ $ $\displaystyle=\
-\frac{\partial\mathbf{B}}{\partial t},\ $ $\displaystyle\
\nabla\times\mathbf{H}\ $ $\displaystyle=\
\mathbf{J}_{f}+\frac{\partial\mathbf{D}}{\partial t},$ (2)

where $\mathbf{E}(\mathbf{r},t)$ is the electric,
$\mathbf{D}(\mathbf{r},t)=\epsilon(\mathbf{r})\mathbf{E}(\mathbf{r},t)$ is the
displacement electric field, $\epsilon(\mathbf{r})$ is the permittivity of the
medium, $\mathbf{H}(\mathbf{r},t)=\mathbf{B}(\mathbf{r},t)/\mu_{0}$ is the
magnetic fields, $\mathbf{B}(\mathbf{r},t)$ is the magnetic flux density,
$\mu_{0}$ is the magnetic permeability of vacuum, $\rho_{f}(\mathbf{r},t)$ is
the free charge density,and $\mathbf{J}_{f}(\mathbf{r},t)$ is the free current
density. The electric and magnetic fields are assumed to be real. In terms of
the Riemann-Silberstein-Weber vectors [28],

$\mathbf{F^{\pm}}(\mathbf{r},t)\ =\ \sqrt{\epsilon(\mathbf{r})}\
\mathbf{E}(\mathbf{r},t)\ \pm\ i\
\frac{\mathbf{B}(\mathbf{r},t)}{\sqrt{\mu_{0}}},$ (3)

Maxwell equations take on the form,

$i\frac{\partial\mathbf{F^{\pm}}}{\partial t}=\pm
v_{ph}\nabla\times\mathbf{F^{\pm}}\pm\frac{1}{2}\nabla
v_{ph}\times(\mathbf{F^{\pm}}+\mathbf{F^{\mp}})-iv_{ph}\sqrt{\frac{\mu_{0}}{2}}\mathbf{J}_{f},$
(4) $\nabla\bm{.}\mathbf{F^{\pm}}=\frac{1}{2v_{ph}}\nabla
v_{ph}\bm{.}(\mathbf{F^{\pm}}+\mathbf{F^{\mp}})+v_{ph}\sqrt{\frac{\mu_{0}}{2}}\rho_{f}.$
(5)

where $v_{ph}$ is the phase velocity of the electromagnetic wave,

$v_{ph}=\frac{1}{\sqrt{\epsilon(\mathbf{r})\mu_{0}}}$ (6)

From (4) and (5), we note that the coupling between the two field
polarizations $\mathbf{F^{\pm}}$ occurs through the inhomogeneity in the
refractive index $n(\bf{r})=\sqrt{\epsilon(\bf{r})}$.

If we assume that there are no free charges or currents, i.e., $\rho_{f}=0$
and $\mathbf{J}_{f}=0$, and define an 8-spinor $\Psi^{\pm}$ having the form,

$\displaystyle{\Psi^{\pm}}=\begin{pmatrix}-F^{\pm}_{x}\pm iF^{\pm}_{y}\\\
F^{\pm}_{z}\\\ F^{\pm}_{z}\\\ F^{\pm}_{x}\pm iF^{\pm}_{y}\end{pmatrix},$ (7)

then, (4) and (5) can be written as [28],

$\displaystyle\frac{\partial}{\partial t}\begin{pmatrix}\Psi^{+}\\\
\Psi^{-}\end{pmatrix}=$ $\displaystyle-
v_{ph}\begin{pmatrix}\mathbf{M}\bm{.}\nabla-\bm{\Sigma}\bm{.}\displaystyle{\frac{\nabla\epsilon}{4\epsilon}}&iM_{z}\bm{\Sigma}\bm{.}\displaystyle{\frac{\nabla\epsilon}{2\epsilon}}\alpha_{y}\\\
iM_{z}\bm{\Sigma}^{*}\bm{.}\displaystyle{\frac{\nabla\epsilon}{2\epsilon}}\alpha_{y}&\mathbf{M}^{*}\bm{.}\nabla-\bm{\Sigma}^{*}\bm{.}\displaystyle{\frac{\nabla\epsilon}{4\epsilon}}\end{pmatrix}\begin{pmatrix}\Psi^{+}\\\
\Psi^{-}\end{pmatrix}.$ (8)

The $\mathbf{M}$ matrices are the tensor products of the Pauli spin matrices,
$\bm{\sigma}=(\sigma_{x},\sigma_{y},\sigma_{z}).$ with the $2\times 2$
identity matrix $\mathbf{I_{2}}$,

$\mathbf{M}=\bm{\sigma}\otimes\mathbf{I_{2}},\ \ \ \Longrightarrow\ \ \
M_{z}=\sigma_{z}\otimes\mathbf{I_{2}}.$ (9)

where

$\sigma_{x}=\begin{pmatrix}0&1\\\ 1&0\\\ \end{pmatrix}\ \ \
,\quad\sigma_{y}=\begin{pmatrix}0&-i\\\ i&0\\\ \end{pmatrix}\ \ \
,\quad\sigma_{z}=\begin{pmatrix}1&0\\\ 0&-1\\\ \end{pmatrix}.$ (10)

The $4\times 4$ matrices $\bm{\alpha}$ and $\bm{\Sigma}$ are defined by,

$\bm{\alpha}=\begin{pmatrix}0&\bm{\sigma}\\\ \bm{\sigma}&0\\\ \end{pmatrix},\
\ \ \bm{\Sigma}=\begin{pmatrix}\bm{\sigma}&0\\\ 0&\bm{\sigma}\\\
\end{pmatrix}.$ (11)

If we assume a 2D refractive index $n=n(x,z)$, the 8-spinor evolution equation
(8) reduces to,

$\frac{\partial}{\partial t}\begin{bmatrix}q_{0}\\\ q_{1}\\\ q_{2}\\\ q_{3}\\\
\end{bmatrix}=-\frac{1}{n(x,z)}\left(\frac{\partial}{\partial
x}\begin{bmatrix}q_{2}\\\ q_{3}\\\ q_{0}\\\ q_{1}\\\
\end{bmatrix}+\frac{\partial}{\partial z}\begin{bmatrix}q_{0}\\\ q_{1}\\\
-q_{2}\\\ -q_{3}\\\ \end{bmatrix}\right)+\frac{\partial n/\partial
x}{2n^{2}(x,z)}\begin{bmatrix}q_{1}+q_{6}\\\ q_{0}-q_{7}\\\ q_{3}-q_{4}\\\
q_{2}+q_{5}\\\ \end{bmatrix}+\frac{\partial n/\partial
z}{2n^{2}(x,z)}\begin{bmatrix}q_{0}-q_{7}\\\ -q_{1}-q_{6}\\\ q_{2}+q_{5}\\\
-q_{3}+q_{4}\\\ \end{bmatrix}$ (12) $\frac{\partial}{\partial
t}\begin{bmatrix}q_{4}\\\ q_{5}\\\ q_{6}\\\ q_{7}\\\
\end{bmatrix}=-\frac{1}{n(x,z)}\left(\frac{\partial}{\partial
x}\begin{bmatrix}q_{6}\\\ q_{7}\\\ q_{4}\\\ q_{5}\\\
\end{bmatrix}+\frac{\partial}{\partial z}\begin{bmatrix}q_{4}\\\ q_{5}\\\
-q_{6}\\\ -q_{7}\\\ \end{bmatrix}\right)+\frac{\partial n/\partial
x}{2n^{2}(x,z)}\begin{bmatrix}q_{5}+q_{2}\\\ q_{4}-q_{3}\\\ q_{7}-q_{0}\\\
q_{6}+q_{1}\\\ \end{bmatrix}+\frac{\partial n/\partial
z}{2n^{2}(x,z)}\begin{bmatrix}q_{4}-q_{3}\\\ -q_{5}-q_{2}\\\ q_{6}+q_{1}\\\
-q_{7}+q_{0}\\\ \end{bmatrix}.$ (13)

where, in terms of qubits $q_{i}$ ($i=0,1,\ldots 7$),
$\Psi^{+}=\left(q_{0},q_{1},q_{2},q_{3}\right)^{T}$,
$\Psi^{-}=\left(q_{4},q_{5},q_{6},q_{7}\right)^{T}$, with the superscript $T$
indicating the transpose of the row matrix.

##  3 Qubit Lattice Algorithm (QLA) for 2D Maxwell Equations

###  3.1 Overview of QLA

It is convenient to use the Cartesian coordinates to construct the QLA for
Maxwell equations since a 2D QLA reduces to the tensor product of two
orthogonal 1D QLAs. For the 2D refractive index $n(x,z)$, we will assume that
the electromagnetic fields are functions of $(x,z,t)$.

Now the 1D QLA is an interleaved sequence of non-commuting collision-stream
operators. The collision operator $C$ entangles the qubits at each lattice
site, while the streaming operator $S$ spreads this entanglement throughout
the lattice. Then the basic structure of the evolution operator is,

$\displaystyle U$
$\displaystyle=\overline{S}_{-}C\overline{S}_{+}C^{\dagger}\bm{.}\>S_{+}CS_{-}C^{\dagger},$
(14) $\displaystyle\overline{U}$
$\displaystyle=S_{+}C^{\dagger}S_{-}C\bm{.}\>\overline{S}_{-}C^{\dagger}\overline{S}_{+}C$

acting on a qubit vector $Q=\left(q_{0},q_{1},\ldots\right)^{T}$. In (14),
$C^{\dagger}$ is the adjoint of $C$, $S_{+}$ ($S_{-}$) streams half of the
qubits in $Q$ in the positive (negative) Cartesian direction while leaving the
other half of the qubits untouched, and $\overline{S}_{+}$
($\overline{S}_{-}$) streams those untouched qubits in the positive (negative)
direction. A small parameter $\varepsilon$ is introduced into the unitary
collision angle matrix. (We will discuss the significance of $\varepsilon$ in
Section 4.4, following the simulation results). The collision and streaming
operators are chosen in such a way that when,

$Q(t+\delta t)=\overline{U}UQ(t),$ (15)

is expanded to second order in $\varepsilon$ we recover the 1D parts of Eqs.
(12) and (13) that contain the time and spatial derivative of $Q$. The
remaining terms in Eqs. (12) and (13), which depend on the derivative of the
refractive index are recovered through a potential operator in which the
collision operator depends on $\varepsilon$.

Interestingly, the 2D QLA can use the same dimensionality of the qubit vector
$Q$ as in 1D but with $Q=Q(x,z,t)$. A simple notational generalization of Eq.
(15) leads to,

$Q(t+\delta t)=\overline{U}_{Z}U_{Z}.\overline{U}_{X}U_{X}Q(t)$ (16)

For appropriately chosen collision-stream operators we recover the required
$\partial/\partial t$, and the spatial derivative terms $\partial/\partial x$
and $\partial/\partial z$ in the limit of long times and long spatial scales
with $\varepsilon<<1$.

To determine the collision operator for x-dependence, we note in Eqs.
(12)-(13) that the qubit couplings of $\partial/\partial t$ with
$\partial/\partial x$ requires the coupling of $q_{0}$ \- $q_{2}$, $q_{1}$ \-
$q_{3}$, $q_{4}$ \- $q_{6}$, $q_{5}$ \- $q_{7}$. This can readily be achieved
by an $8\crossproduct 8$ collision matrix. However, to recover the coupling of
$\partial/\partial t$ \- $\partial/\partial z$ in Eqs. (12)-(13) we note that
in the 8-qubit representation has diagonal coupling $q_{0}$ \- $q_{0}$,
$q_{1}$ \- $q_{1}$, $q_{2}$ \- $q_{2}$, $...$. Since entanglement requires a
collision operator to act on at least 2 qubits we must extend to a 16-qubit
representation. This problem of diagonal coupling of an 8-qubit system can be
traced back to the diagonal structure of the Pauli spin matrix $\sigma_{z}$.
Since both $U_{X}$ and $U_{Z}$ act on the same qubit vector $Q(t)$, it is
reasonable to develop the 2D QLA for a 16-component qubit vector.

###  3.2 16-qubit QLA for 1D propagation in the $x$-direction

A 16-qubit formulation for 1D QLA propagation in the x-direction can be
determined from the unitary $16\crossproduct 16$ collision matrix
$\overline{C}_{X}$ and the $8\crossproduct 8$ submatrices $C_{8X}$,

$\overline{C}_{X}=\begin{bmatrix}C_{8X}(\theta)&0\\\
0&C_{8X}(\theta)\end{bmatrix}$ (17)

where

$C_{8X}(\theta)=\begin{bmatrix}\cos\theta&0&0&0&\sin\theta&0&0&0\\\
0&\cos\theta&0&0&0&\sin\theta&0&0\\\ 0&0&\cos\theta&0&0&0&\sin\theta&0\\\
0&0&0&\cos\theta&0&0&0&\sin\theta\\\ -\sin\theta&0&0&0&\cos\theta&0&0&0\\\
0&-\sin\theta&0&0&0&\cos\theta&0&0\\\ 0&0&-\sin\theta&0&0&0&\cos\theta&0\\\
0&0&0&-\sin\theta&0&0&0&\cos\theta\\\ \end{bmatrix}.$ (18)

with collision angle

$\theta=\frac{\varepsilon}{4n(x,z)}.$ (19)

The streaming operator $\overrightarrow{S}$ will stream the 8-qubit subset
$[\overline{q}_{0},\overline{q}_{1},\overline{q}_{2},\overline{q}_{3},\overline{q}_{8},\overline{q}_{9},\overline{q}_{10},\overline{q}_{11}]$,
while the streaming operator $\overline{\overrightarrow{S}}$ will stream the
remaining 8-qubit subset
$[\overline{q}_{4},\overline{q}_{5},\overline{q}_{6},\overline{q}_{7},\overline{q}_{12},\overline{q}_{13},\overline{q}_{14},\overline{q}_{15}]$.

To complete the 16-qubit 1D QLA for $x$-propagation, we need to define the
potential collision operators that will recover the $\partial n/\partial x$
terms in the (reduced) Eqs. (12)-(13). There will be two such potential
operators. The first will have block diagonal structure based on the
$2\crossproduct 2$ matrix

$P_{1}(\gamma)=\begin{bmatrix}\cos\gamma&\sin\gamma\\\
\sin\gamma&\cos\gamma\end{bmatrix}$ (20)

with

$\overline{P}_{1X}(\gamma)=\begin{bmatrix}P_{1}(\gamma)&0&0&0&0&0&0&0\\\
0&P_{1}(\gamma)&0&0&0&0&0&0\\\ 0&0&P_{1}(\gamma)&0&0&0&0&0\\\
0&0&0&P_{1}(\gamma)&0&0&0&0\\\ 0&0&0&0&P_{1}(\gamma)&0&0&0\\\
0&0&0&0&0&P_{1}(\gamma)&0&0\\\ 0&0&0&0&0&0&P_{1}(\gamma)&0\\\
0&0&0&0&0&0&0&P_{1}(\gamma)\\\ \end{bmatrix}.$ (21)

The potential collision angle is,

$\gamma=\varepsilon^{2}\frac{\textbullet\partial n/\partial x}{2n^{2}}.$ (22)

$\overline{P}_{1X}(\gamma)$ is Hermitian but not unitary. The second of the
potential collision operators, $\overline{P}_{2X}(\gamma)$, is a sparse
unitary operator based on two $8\crossproduct 8$ subpotential matrices,

$\overline{P}_{2X}(\gamma)=\begin{bmatrix}P_{11}(\gamma)&P_{12}(\gamma\\\
P_{12}(\gamma)&P_{11}(\gamma)\end{bmatrix}.$ (23)

These $8\crossproduct 8$ matrices are given by,

$P_{11}(\gamma)=\begin{bmatrix}\cos\gamma&0&0&0&0&0&0&0\\\
0&\cos\gamma&0&0&0&0&0&0\\\ 0&0&\cos\gamma&0&0&0&0&0\\\
0&0&0&\cos\gamma&0&0&0&0\\\ 0&0&0&0&\cos\gamma&0&0&0\\\
0&0&0&0&0&\cos\gamma&0&0\\\ 0&0&0&0&0&0&\cos\gamma&0\\\
0&0&0&0&0&0&0&\cos\gamma\\\ \end{bmatrix}.$ (24)

and

$P_{12}(\gamma)=\begin{bmatrix}0&0&0&0&\sin\gamma&0&0&0\\\
0&0&0&0&0&-\sin\gamma&0&0\\\ 0&0&0&0&0&0&\sin\gamma&0\\\
0&0&0&0&0&0&0&-\sin\gamma\\\ -\sin\gamma&0&0&0&0&0&0&0\\\
0&\sin\gamma&0&0&0&0&0&0\\\ 0&0&-\sin\gamma&0&0&0&0&0\\\
0&0&0&\sin\gamma&0&0&0&0\\\ \end{bmatrix}.$ (25)

###  3.3 16-qubit QLA for 1D z-propagation

For the 16-qubit vector $\overline{Q}$ an appropriate unitary collision
operator which couples the qubits $\overline{q}_{0}-\overline{q}_{2}$,
$\overline{q}_{1}-\overline{q}_{3}$, $\overline{q}_{4}-\overline{q}_{6}$,
$\overline{q}_{5}-\overline{q}_{7}$, $\overline{q}_{8}-\overline{q}_{10}$,
$\overline{q}_{9}-\overline{q}_{11}$, $\overline{q}_{12}-\overline{q}_{14}$,
$\overline{q}_{13}-\overline{q}_{15}$ is derived from the $4\crossproduct 4$
block diagonal structure,

$\overline{C}_{Z}(\theta)=\begin{bmatrix}C_{4}(\theta)&0&0&0\\\
0&C_{4}(\theta)^{T}&0&0\\\ 0&0&C_{4}(\theta)&0\\\ 0&0&0&C_{4}(\theta)^{T}\\\
\end{bmatrix},$ (26)

with the $4\crossproduct 4$ submatrix,

$C_{4}(\theta)=\begin{bmatrix}\cos\theta&0&\sin\theta&0\\\
0&\cos\theta&0&\sin\theta\\\ -\sin\theta&0&\cos\theta&0\\\
0&-\sin\theta&0&\cos\theta\\\ \end{bmatrix},$ (27)

where $\theta$ given by Eq. (19).

The streaming operator $\overrightarrow{S}_{Z}$ will stream the 8-qubit subset
$[\overline{q}_{0},\overline{q}_{1},\overline{q}_{4},\overline{q}_{5},\overline{q}_{8},\overline{q}_{9},\overline{q}_{12},\overline{q}_{13}]$,
while the streaming operator $\overline{\overrightarrow{S}}_{Z}$ will stream
the remaining 8-qubit subset
$[\overline{q}_{2},\overline{q}_{3},\overline{q}_{6},\overline{q}_{7},\overline{q}_{10},\overline{q}_{11},\overline{q}_{14},\overline{q}_{15}]$.

To recover the $\partial n/\partial z$ terms in the (reduced) Eqs. (12) -
(13), we introduce two potential collision operators. The first of the
potential collision operators has a form that mimics the coupling of the
unitary collision matrix $\overline{C}_{Z}$ with its $4\crossproduct 4$
diagonal block structure,

$\overline{P}_{1Z}(\gamma^{\prime})=\begin{bmatrix}P_{4}(\gamma^{\prime})&0&0&0\\\
0&P_{4}(\gamma^{\prime})&0&0\\\ 0&0&P_{4}(\gamma^{\prime})&0\\\
0&0&0&P_{4}(\gamma^{\prime})\\\ \end{bmatrix},$ (28)

where

$P_{4}(\gamma^{\prime})=\begin{bmatrix}\cos\gamma^{\prime}&0&-\sin\gamma^{\prime}&0\\\
0&\cos\gamma^{\prime}&0&-\sin\gamma^{\prime}\\\
-\sin\gamma^{\prime}&0&\cos\gamma^{\prime}&0\\\
0&-\sin\gamma^{\prime}&0&\cos\gamma^{\prime}\\\ \end{bmatrix}.$ (29)

This evolution potential collision operator is Hermitian. The second potential
collision operator has diagonal-like structure of two $8\crossproduct 8$
matrices,

$\overline{P}_{2Z}(\gamma^{\prime})=\begin{bmatrix}P_{81}(\gamma^{\prime})&P_{82}(\gamma^{\prime})\\\
P_{82}(\gamma^{\prime})&P_{81}(\gamma^{\prime})\\\ \end{bmatrix},$ (30)

where

$P_{81}(\gamma^{\prime})=\begin{bmatrix}\cos\gamma^{\prime}&0&0&0&0&0&0&0\\\
0&\cos\gamma^{\prime}&0&0&0&0&0&0\\\ 0&0&\cos\gamma^{\prime}&0&0&0&0&0\\\
0&0&0&\cos\gamma^{\prime}&0&0&0&0\\\ 0&0&0&0&\cos\gamma^{\prime}&0&0&0\\\
0&0&0&0&0&\cos\gamma^{\prime}&0&0\\\ 0&0&0&0&0&0&\cos\gamma^{\prime}&0\\\
0&0&0&0&0&0&0&\cos\gamma^{\prime}\\\ \end{bmatrix},$ (31)

and,

$P_{82}(\gamma^{\prime})=\begin{bmatrix}0&0&0&0&0&0&0&-\sin\gamma^{\prime}\\\
0&0&0&0&0&0&-\sin\gamma^{\prime}&0\\\ 0&0&0&0&0&-\sin\gamma^{\prime}&0&0\\\
0&0&0&0&-\sin\gamma^{\prime}&0&0&0\\\ 0&0&0&\sin\gamma^{\prime}&0&0&0&0\\\
0&0&\sin\gamma^{\prime}&0&0&0&0&0\\\ 0&\sin\gamma^{\prime}&0&0&0&0&0&0\\\
\sin\gamma^{\prime}&0&0&0&0&0&0&0\\\ \end{bmatrix}.$ (32)

The potential collision angle is similar to that for $x$-propagation except
that the derivative on the refractive index is with respect to $z$,

$\gamma^{\prime}=\varepsilon^{2}\frac{\textbullet\partial n/\partial
z}{2n^{2}}.$ (33)

###  3.4 16-qubit QLA for 2D for propagation in the $x-z$ plane

Piecing together the 1D propagation in $x$ and $z$ directions, we obtain the
2D QLA acting on the 16-qubit vector. Thus, for the $x$-dependence we have the
unitary collide-stream sequence in the $x$-direction,

$U_{X}=\overline{S}_{-X}\overline{C}_{X}\overline{S}_{+X}\overline{C}_{X}^{\dagger}.S_{+X}\overline{C}_{X}S_{-X}\overline{C}_{X}^{\dagger}$
(34)
$\overline{U}_{X}=S_{+X}\overline{C}_{X}^{\dagger}S_{-X}\overline{C}_{X}.\overline{S}_{-X}\overline{C}_{X}^{\dagger}\overline{S}_{+X}\overline{C}_{X}.$
(35)

For the $z$-dependence, the corresponding unitary collide-stream structure is,

$U_{Z}=\overline{S}_{-Z}\overline{C}_{Z}\overline{S}_{+Z}\overline{C}_{Z}^{\dagger}.S_{+Z}\overline{C}_{Z}S_{-Z}\overline{C}_{Z}^{\dagger}$
(36)
$\overline{U}_{Z}=S_{+Z}\overline{C}_{Z}^{\dagger}S_{-Z}\overline{C}_{Z}.\overline{S}_{-Z}\overline{C}_{Z}^{\dagger}\overline{S}_{+Z}\overline{C}_{Z}..$
(37)

The 2D 16-qubit QLA algorithm is,

$\overline{Q}(t+\delta
t)=\overline{P}_{1Z}\overline{P}_{2Z}.\overline{U}_{Z}.U_{Z}.\overline{P}_{1X}\overline{P}_{2X}.\overline{U}_{X}.U_{X}\overline{Q}(t)$
(38)

In the long time, long spatial scale limit ($\varepsilon<<1$) we obtain a set
of 16 partial differential equations for
$\big{[}\overline{q_{0}},...,\overline{q_{15}}\big{]}$. We recover the
8-spinor 2D representation, $\big{[}q_{0},...,q_{7}\big{]}$, of Maxwell
equations to $O(\varepsilon^{2})$, Eq. (12)-(13), by the identification,

$q_{0}=\overline{q}_{0}+\overline{q}_{2},\quad
q_{1}=\overline{q}_{1}+\overline{q}_{3},\quad
q_{2}=\overline{q}_{4}+\overline{q}_{6},\quad
q_{3}=\overline{q}_{5}+\overline{q}_{7},$ (39)
$q_{4}=\overline{q}_{8}+\overline{q}_{10},\quad
q_{5}=\overline{q}_{9}+\overline{q}_{11},\quad
q_{6}=\overline{q}_{12}+\overline{q}_{14},\quad
q_{7}=\overline{q}_{13}+\overline{q}_{15},$ (40)

The initial conditions correspond to the electromagnetic field components of
the pulse at $t=0$. Using the Riemann-Silberstein-Weber variables, we obtain
the initial condition on the 8-spinor $(q_{0},....q_{7})$. For the 16-qubit
$\overline{Q}(t=0)$ the initial condition is,

$\overline{q}_{0}=\overline{q}_{2}=q_{0}/2,\quad\overline{q}_{1}=\overline{q}_{3}=q_{1}/2,\quad\overline{q}_{4}=\overline{q}_{6}=q_{2}/2,\quad\overline{q}_{5}=\overline{q}_{7}=q_{3}/2,$
(41)
$\overline{q}_{8}=\overline{q}_{10}=q_{4}/2,\quad\overline{q}_{9}=\overline{q}_{11}=q_{5}/2,\quad\overline{q}_{12}=\overline{q}_{14}=q_{6}/2,\quad\overline{q}_{13}=\overline{q}_{15}=q_{7}/2.$
(42)

##  4 2D QLA SIMULATIONS

QLA simulations will be presented for an initial 1D Gaussian pulse propagating
in the $x-$direction that interacts with a small 2D cylindrical dielectric
with refractive index $n(x,z)$ (section 4.1), and with a small 2D conic
dielectric (section 4.2).

###  4.1 Gaussian Pulse interacting with a 2D Dielectric Cylinder :
$n_{1}<n_{2}$

Consider a 1D Gaussian electromagnetic pulse propagating in the $x-$direction
with polarization $E_{y}(x,t=0)$ and with $B_{z}(x,t=0)$ in a vacuum,
$n_{1}=1$. It propagates towards a dielectric cylinder located in the center
of square grid $l\crossproduct L$, with peak refractive index $n=3$ (see Fig.
1.)

(a) $E_{y}$ initial field , (b) dielectric cylinder

Figure 1: (a) The $E_{y}$ field of the initial electromagnetic Gaussian pulse
as it propagates in the vacuum ($n_{1}=1$), (b) a localized dielectric
cylinder with peak refractive index $n(x=L/2,z=L/2)=3$. Grid $L^{2}=8192^{2}$.

When the 1D pulse starts to interact with the 2D dielectric cylinder, the
electromagnetic fields take on 2D structure. In Fig. 2 we plot the electric
field component $E_{y}(x,z)$, both from the perspective of (a) $E_{y}>0$, and
(b) $E_{y}<0$

(a) $E_{y}>0$ perspective , (b) $E_{y}<0$ perspective

Figure 2: (a) The $E_{y}>0$ field after the pulse has started to overlap into
the dielectric cylinder, (b) the corresponding $E_{y}$ field, but from the
perspective $E_{y}<0$. There is a phase change of $\pi$ in the reflected
$E_{y}$ ring since $n_{2}>n_{1}$.

That part of the pulse which is propagating within the dielectric cylinder is
moving with a slower phase velocity than that part of the pulse that remains
in the vacuum and hence will lag the pulse that is in $n_{1}$ region. More
interesting is the ring region of the reflected pulse in which $E_{y}<0$. This
is readily seen in Fig. 2(b) and is somewhat expected from analogy with the 1D
scattering of a pulse propagating from region $n_{1}$ to region $n_{2}$ with
$n_{2}>n_{1}$.

As the main part of the pulse keeps propagating in the x-direction, there are
now internal reflections$/$transmissions of the fields from the dielectric
cylinder since the boundary layer region between the two media is quite thin.
These give rise to interesting wavefronts emanating from the dielectric
cylinder, Fig. 3

(a) $E_{y}>0$ perspective , (b) $E_{y}<0$ perspective

Figure 3: (a) The $E_{y}>0$ field after parts of the pulse have undergone
reflection$/$transmission within the dielectric cylinder, (b) the
corresponding $E_{y}$ field, but from the perspective $E_{y}<0$. The initial
ring of $E_{y}<0$ in Fig. 2 is radiated away from the cylinder while new
wavefronts are formed from the transient fields trapped within the dielectric.

(a) $E_{y}>0$ perspective , (b) $E_{y}<0$ perspective

Figure 4: The $E_{y}$ field later in the initial value simulation from the
perspective of (a) The $E_{y}>0$, and (b) $E_{y}<0$.

In Fig. 4 we plot the $E_{y}$ near the end of the QLA simulation.

The QLA is modeling the time evolution of the full Maxwell equations,
including the two divergence equations that are typically treated as initial
conditions. To ensure that $\nabla\cdot\mathbf{B}=0$ a $B_{x}(x,z)$ field
component must be generated when the 1D pulse interacts with the 2D dielectric
cylinder with $n(x,z)$. In Figs. 5-7 we plot the $B_{x}$-field at the time
instances corresponding to the time snapshots of Fig. 2-4.

(a) $B_{x}>0$ perspective , (b) $B_{x}<0$ perspective - c.f. Fig. 2

Figure 5: The $B_{x}(x,z)$ field generated from the interaction of the 1D
pulse with the 2D dielectric. Time snapshot corresponds to that of Fig. 2 and
is on the same scale as Fig. 2. (a) The $B_{x}>0$, and (b) $B_{x}<0$.

(a) $B_{x}>0$ perspective , (b) $B_{x}<0$ perspective - c.f. Fig. 3

Figure 6: The $B_{x}(x,z)$ field generated from the interaction of the 1D
pulse with the 2D dielectric. Time snapshot and axes scales corresponds to
that of Fig. 3. (a) The $B_{x}>0$, and (b) $B_{x}<0$.

(a) $B_{x}>0$ perspective , (b) $B_{x}<0$ perspective - c.f. Fig. 4

Figure 7: The $B_{x}(x,z)$ field generated from the interaction of the 1D
pulse with the 2D dielectric. Time snapshot and axes scales corresponds to
that of Fig. 4. (a) The $B_{x}>0$, and (b) $B_{x}<0$.

The mirror symmetry of Figs. 2-7 is a $\pi$-rotation about an axis parallel to
the x-axis and passing through the midpoint $z=L/2$ of the z-axis. The
simulation box is a square of side $L$.) From the QLA simulations we see
dipole structure in the generated $B_{x}$-field.

In Fig. 8 we plot the central differenced post-processed
$\nabla\cdot\mathbf{B}(x,z)$ for the time snapshot corresponding to Fig. 4 and
Fig. 7. The vertical axis scale is multiplied by a factor of $10^{-3}$ when
compared to the vertical axes scales in Fig. 4 and Fig. 7. Essentially,
$\nabla\cdot\mathbf{B}$ is zero everywhere, except at the localized $B_{x}$
structures (see Fig. 7) where $\nabla\cdot\mathbf{B}$ is done by 3 orders of
magnitude over the local values of $B_{x}$.

(a) $\nabla\cdot\mathbf{B}(x,z,t)>0$ perspective , (b)
$\nabla\cdot\mathbf{B}(x,z,t)<0$ perspective.

Figure 8: The $\nabla\cdot\mathbf{B}(x,z,t)$ from the QLA code. Time snapshot
corresponds to that of Fig. 4 and Fig. 7 - except the vertical axis should
here be scaled by a factor of $10^{-3}$: (a) $\nabla\cdot\mathbf{B}>0$, and
(b) $\nabla\cdot\mathbf{B}<0$

###  4.2 Gaussian Pulse interacting with a 2D Cylindrical Hole : $n_{1}>n_{2}$

In this next set of QLA simulations, we consider the 1D pulse now propagating
from high refractive index $n_{1}=3$ medium onto a cylindrical vacuum hole
with $n_{2}=1$. When the pulse starts to interact with the cylindrical hole,
the fields within the hole have a greater phase velocity than the pulse within
the incident higher refractive index medium so that that wavefront will lead
the pulse, as seen in Fig. 9(a) and (b).

(a) $E_{y}$ field in early stages, (b) $E_{y}$ field at late stages.

Figure 9: The electric field component $E_{y}$ for scattering of a pulse from
$n_{1}$ to $n_{2}$, but with $n_{1}>n_{2}$. (a) early stages of the scattered
field from the vacuum hole, (b) late stages of the scattered field.

Moreover, the first interaction of the pulse with the vacuum hole leads to a
positive ring of reflected electric field in contrast with the scattering from
region $n_{1}$ into region $n_{2}$ with $n_{1}<n_{2}$ where the reflected
electric field ring is negative. These signs on the reflected electric field
are, of course, reminiscent to the Fresnel jump conditions in 1D.

###  4.3 Gaussian Pulse interacting with a 2D Cylindrical Cone : $n_{1}<n_{2}$

We now consider QLA simulations of a Gaussian 1D pulse onto a dielectric cone,
Fig 10a.

(a) Dielectric cone, (b) $E_{y}$ field in early scattering stage from the
cone.

Figure 10: (a) The dielectric cone, with apex having $n_{2}=3$, (b) $E_{y}$ in
early stages of interacting with the dielectric cone.

Because the refractive index gradients are weak at the edges of the cone,
there is no prominent reflected ring of negative electric field, Fig 10(b), as
in the case of the sharp edge gradients in the dielectric cylinder case, Fig.
2(a). Later in time, Fig. 11, one sees only a secondary ring of predominantly
$E_{y}>0$ , Fig. 11(a) and (b).

(a) $E_{y}$ field - perspective of $E_{y}>0$. (b) $E_{y}$ field but now from
the perspective $E_{y}<0$.

Figure 11: At late stage in the interaction of the pulse with the dielectric
cone, one does not see strong internal wavefronts being emitted from the
dielectric cone. This should be compared to the emitted wavefronts from the
dielectric cylinder, Fig. 4.

Plots of $\nabla\cdot\mathbf{B}(x,z,t)$ for the scattering of the pulse from
dielectric cones are similar to that for scattering from the cylindrical
dielectric, Fig. 8, except the peak magnitudes are typically now reduced by a
further factor of $50$ over the sharp dielectric boundary layer of the vacuum-
cylinder interface .

###  4.4 The role of the collision angle perturbation parameter $\varepsilon$

in order to develop an explicit QLA we must introduce a perturbation parameter
$\varepsilon$ into the collision and potential operators. Here, we have
developed a 2D QLA for Maxwell equations in a scalar dielectric medium that
recovers the Maxwell equations to second order in $\varepsilon$. From the
simulations we can identify $\varepsilon$ to be the scaled speed of
propagation of the pulse in a vacuum. In our previous QLA for the nonlinear
Schrodinger equation and for the (3D) spinor Bose-Einstein condensate
equations, $\varepsilon$ was related to the soliton/quantum vortex amplitude.
For these nonlinear equations, the simulations of the QLA models revealed an
upper bound to $\varepsilon_{max}$ above which the QLA no longer recovered the
appropriate soliton/quantum vortex time behavior. This is the well known price
we are forced to pay when applying perturbation theory.

However, for our QLA for Maxwell equations we find that the QLA simulations
faithfully reproduce the Maxwell equations even for $\varepsilon=1.0$, the
maximal possible speed of pulse propagation. In Fig 12 - 14 we show the time
evolution snapshots of the $E_{y}$-field for two different values of
$\varepsilon$ : $\varepsilon=0.01$ and $\varepsilon=1.0$. Of course, the
computational time scales as $1/\varepsilon$.

(a) $E_{y}$ field for $\varepsilon=0.01$. (b) $E_{y}$ field for
$\varepsilon=1.00$

Figure 12: The effect of the QLA perturbation parameter $\varepsilon$ on the
evolution of the $E_{y}$ field soon after the pulse has interacted with the
dielectric cylinder.

(a) $E_{y}$ field for $\varepsilon=0.01$. (b) $E_{y}$ field for
$\varepsilon=1.00$

Figure 13: The development of $E_{y}$ with its peak (a) $0.0330$ , while for
(b) $0.0323$

(a) $E_{y}$ field for $\varepsilon=0.01$. (b) $E_{y}$ field for
$\varepsilon=1.00$

Figure 14: The late stage in the evolution of $E_{y}$ following its
interaction with the dielectric cylinder

##  5 Summary and Conclusions

We have performed detailed QLA simulations of the scattering of an
electromagnetic pulse off a localized 2D scalar dielectric medium. If the
strength of the spatial gradient of the dielectric boundary layer is large, we
find significant reflections/transmissions of the pulse within the dielectric.
This leads to the dielectric emitting outgoing wavefronts into the vacuum like
a quasi-antenna.

In our current formulation of the Maxwell equations, we are only solving
$\nabla\cdot\bf{B}=0$ to second order in the unitary collision angle parameter
$\varepsilon$. Nevertheless we do not seem to be tainted by this in the
simulations. A possible reason for this is that QLA is a mesoscopic
representation and the Maxwell equations are recovered in the continuum limit.
Hence the time evolution of the QLA simulation does not deal directly with the
magnetic field $\bf{B}$.

QLA’s are necessarily perturbative theories since only in extremely rare
instances can one perform a closed form representatioin of the collision
matrix. In our earlier work on solving the 1D Nonlinear Schrodinger equation
$(NLS)$ or the 2D and 3D Gross-Pitaevskii equation for the evolution of a
Bose-Einstein condensate $(BEC)$ ground state or the further generalizations
to spinor BECs, the perturbation parameter in the collision operators was
related to the amplitude of the wave function. The QLA recovers the desired
continuum equations perturbatively, and QLA simulations have determined an
$\varepsilon_{max}$ above which the QLA simulations do not yield solutions to
the desired continuum equations. For example, in 1D NLS, one recovers the
exact soliton-soliton collision features for $\varepsilon<\varepsilon_{max}$.
However, if we choose $\varepsilon>\varepsilon_{max}$ one sees the soliton
breakdown in time. All this is saying is that the QLA is now representing an
equation different from 1D NLS - because of the choice of too high an
$\varepsilon$. In our QLA representation of the Maxwell equations in scalar
media, we find that the $\varepsilon$ is just the normalized speed of light in
that medium. Our simulations show that the QLA holds for Maxwell equations
even for $\varepsilon=1$.

Finally QLA can be viewed from 2 sides: on the one side it is basically a
unitary qubit lattice representation of Maxwell equations which should be able
to be run on error-correcting quantum machines as they come on-line. It has
been noticed by Khan [28] that under the Riemann-Silberstein-Weber
representation, Eq. (3), the structure of Maxwell equations in a scalar
dielectric medium are non-unitary: the evolution operators that involve the
derivative on the dielectric function are Hermitian, and not unitary. In our
QLA this is seen in our potentital collision operators being non-unitary. This
will make the application of qubit algorithms for plasma physics to be more
challenging since clever constructs need to be performed in order to still
represent such non-unitary systems on a quantum computer [30] or else seek
different representations of the fields $\mathbf{E}$ and $\mathbf{B}$. Similar
comments can be made on how to represent nonlinear physics on a linear quantum
mechanical computer. The other way of looking at QLA is that it is an ideally
parallelized algorithm for running on classical supercomputers. Indeed our QLA
spinor BEC codes did not see saturation with nodes on the IBM $Mira$ machine,
even up to the maximum $786,432$ cores available to us (in 2015). This is also
why we have run on such large grids for our Maxwell equations: it is basically
to test out and tune the algorithm as we move to harder and harder problems.

##  6 Acknowledgments

This research was partially supported by Department of Energy grants DE-
SC0021647, DE-FG02-91ER-54109, DE-SC0021651, DE-SC0021857, and DE-SC0021653.
The simulations were performed on $CORI$ of the National Energy Research
Scientific Computing Center (NERSC), A U.S. Department of Energy Office of
Science User Facility located at Lawrence Berkeley National Laboratory,
operated under Contract No. DE-AC02-05CH11231.

##  7 References

[1] YEPEZ, J. 2002 An efficient and accurate quantum algorithm for the Dirac
equation. arXiv: 0210093.

[2] YEPEZ, J. 2005 Relativistic Path Integral as a Lattice-Based Quantum
Algorithm. Quant. Info. Proc. 4, 471-509.

[3] YEPEZ, J, VAHALA, G $\&$ VAHALA, L. 2009a Vortex-antivortex pair in a
Bose-Einstein condensate, Quantum lattice gas model of theory in the mean-
field approximation. Euro. Phys. J. Special Topics 171, 9-14

[4] YEPEZ, J, VAHALA, G, VAHALA, L $\&$ SOE, M. 2009b Superfluid turbulence
from quantum Kelvin wave to classical Kolmogorov cascades. Phys. Rev. Lett.
103, 084501.

[5] YEPEZ, J. 2016 Quantum lattice gas algorithmic representation of gauge
field theory. SPIE 9996, paper 9996-22

[6] OGANESOV, A, VAHALA, G, VAHALA, L, YEPEZ, J $\&$ SOE, M. 2016a.
Benchmarking the Dirac-generated unitary lattice qubit collision-stream
algorithm for 1D vector Manakov soliton collisions. Computers Math. with
Applic. 72, 386

[7] OGANESOV, A, FLINT, C, VAHALA, G, VAHALA, L, YEPEZ, J $\&$ SOE, M 2016b
Imaginary time integration method using a quantum lattice gas approach. Rad
Effects Defects Solids 171, 96-102

[8] OGANESOV, A, VAHALA, G, VAHALA, L $\&$ SOE, M. 2018. Effects of Fourier
Transform on the streaming in quantum lattice gas algorithms. Rad. Eff. Def.
Solids, 173, 169-174

[9] VAHALA, G, VAHALA, L $\&$ YEPEZ, J. 2003 Quantum lattice gas
representation of some classical solitons. Phys. Lett A310, 187-196

[10] VAHALA, G, VAHALA, L $\&$ YEPEZ, J. 2004. Inelastic vector soliton
collisions: a lattice-based quantum representation. Phil. Trans: Mathematical,
Physical and Engineering Sciences, The Royal Society, 362, 1677-1690

[11] VAHALA, G, VAHALA, L $\&$ YEPEZ, J. 2005 Quantum lattice representations
for vector solitons in external potentials. Physica A362, 215-221.

[12] VAHALA, G, YEPEZ, J, VAHALA, L, SOE, M, ZHANG, B, $\&$ ZIEGELER, S. 2011
Poincaré recurrence and spectral cascades in three-dimensional quantum
turbulence. Phys. Rev. E84, 046713

[13] VAHALA, G, YEPEZ, J, VAHALA, L $\&$SOE, M, 2012 Unitary qubit lattice
simulations of complex vortex structures. Comput. Sci. Discovery 5, 014013

[14] VAHALA, G, ZHANG, B, YEPEZ, J, VAHALA. L $\&$ SOE, M. 2012 Unitary Qubit
Lattice Gas Representation of 2D and 3D Quantum Turbulence. Chpt. 11 (pp. 239
- 272), in Advanced Fluid Dynamics, ed. H. W. Oh, (InTech Publishers, Croatia)

[15] VAHALA, G, VAHALA, L $\&$ SOE, M. 2020. Qubit Unitary Lattice Algorithm
for Spin-2 Bose Einstein Condensates: I – Theory and Pade Initial Conditions.
Rad. Eff. Def. Solids 175, 102-112

[16] VAHALA, G, SOE, M $\&$ VAHALA, L. 2020 Qubit Unitary Lattice Algorithm
for Spin-2 Bose Einstein Condensates: II – Vortex Reconnection Simulations and
non-Abelian Vortices. Rad. Eff. Def. Solids 175, 113-119

[17] VAHALA, G, VAHALA, L, SOE, M $\&$ RAM, A, K. 2020. Unitary Quantum
Lattice Simulations for Maxwell Equations in Vacuum and in Dielectric Media,
J. Plasma Phys $\bf{86}$, 905860518

[18] VAHALA, L, VAHALA, G $\&$ YEPEZ, J. 2003 Lattice Boltzmann and quantum
lattice gas representations of one-dimensional magnetohydrodynamic turbulence.
Phys. Lett A306, 227-234.

[19] VAHALA, L, SOE, M, VAHALA, G $\&$ YEPEZ, J. 2019a. Unitary qubit lattice
algorithms for spin-1 Bose-Einstein condensates. Rad Eff. Def. Solids 174,
46-55

[20] VAHALA, L, VAHALA, G, SOE, M, RAM, A $\&$ YEPEZ, J. 2019b. Unitary qubit
lattice algorithm for three-dimensional vortex solitons in hyperbolic self-
defocusing media. Commun Nonlinear Sci Numer Simulat 75, 152-159

[21] DODIN, I. Y. $\&$ STARTEV, E. A. 2021 On appliations of quantum computing
to plasma simulations. Phys. Plasmas $\bf{28}$, 092101

[22] ENGEL, A., SMITH, G $\&$ PARKER, S. E. 2019 Quantum Algorithm for the
Vlasov Equation, Phys. Rev. $\bf{100}$, 062315

[23] ENGEL, A., SMITH, G $\&$ PARKER, S. E. 2021. Linear Embedding of
nonlinear dynamial systems and prospects for efficient quantum algorithms,
Phys. Plasmas $\bf{28}$, 062305

[24] LIU, J-P, KOLDEN, H.O, KROVI, H. K, LOUREIRO, N. F, TRIVISA¡ K, $\&$
CHILDS, A. M. 2021. Proc. Natl. Acad. Sciences $\bf{118}$, e2026805118.

[25] LAPORTE, O. $\&$ UHLENBECK, G. E. 1931 Application of spinor analysis to
the Maxwell and Dirac equations. Phys. Rev. 37, 1380-1397.

[26] OPPENHEIMER, J. R. 1931 Note on light quanta and the electromagnetic
field. Phys. Rev. 38, 725-746.

[27] MOSES, E. 1959 Solutions of Maxwell’s equations in terms of a spinor
notation: the direct and inverse problems, Phys. Rev. 113, 1670-1679

[28] KHAN, S. A. 2005 Maxwell Optics: I. An exact matrix representation of the
Maxwell equations in a medium. Physica Scripta 71, 440-442; also arXiv:
0205083v1 (2002)

[29] RAM, A. K., VAHALA, G., VAHALA, L. $\&$ SOE, M 2021 Reflection and
transmission of electromagnetic pulses at a planar dielectric interface -
theory and quantum lattice simulations AIP Advances 11, 105116 (1-12).

[30] CHILDS, A, M $\&$ WIEBE, N. 2012. Hamiltonian simulation using linear
combinations of unitary operations. Quantum Info. Comput.12, 901–924.


n_{0}}}{1-q}\Big{]}\frac{(q^{-(n-m-1)(c-1)-b-l})_{l}}{(q^{(n-1)c+b-n_{0}+2})_{l}}\prod_{i=0}^{n-m-1}\frac{(q)_{(i+1)(c-1)}(q^{-i(c-1)-b})_{b}}{(q)_{b+i(c-1)}(q)_{c-1}}\prod_{j=1}^{n-n_{0}-1}(1-q^{(j+1)c})$
$\displaystyle\times
q^{\binom{l}{2}}\prod_{j=n-m}^{n-1}\frac{(q^{(j-n+m+1)(c-1)-b+\chi(j>n_{0})(j-n_{0})})_{(n-m)(c-1)+b+1}(q)_{(j-n+m+1)(c-1)+\chi(j>n_{0})(j-n_{0})}}{(q)_{j(c-1)+b+1+\chi(j>n_{0})(j-n_{0})}(q)_{c-\chi(j\leq
n_{0})}}.$

Recall the definition of $Q(d)=Q_{n,n_{0}}(d,b,c;M_{\mathfrak{r}})$ in (6.28).
For $d$ a nonnegative integer

(8.3)
$C_{n,n_{0}}(-d,b,c,l,m)=\operatorname*{CT}_{x}Q_{n,n_{0}}(d,b,c;M_{\mathfrak{r}})=\operatorname*{CT}_{x}Q(d)$

by taking $M_{\mathfrak{r}}$ as in (8.1) and $\mathfrak{r}=l+m$. In this
section, we always assume that the $M_{\mathfrak{r}}$ in $Q(d)$ and
$Q(d\>|\>u;k)$ is the polynomial in (8.1). Thus, to prove Proposition 8.1, it
suffices to compute
$\operatorname*{CT}\limits_{x}Q\big{(}(n-m-1)(c-1)+b+1\big{)}$. Since
$(n-m-1)(c-1)+b+1$ is a positive integer by the assumption $m<n$, we can apply
the Gessel–Xin operation to
$\operatorname*{CT}\limits_{x}Q\big{(}(n-m-1)(c-1)+b+1\big{)}$ and by (6.31),
we have

(8.4) $\operatorname*{CT}_{x}Q\big{(}(n-m-1)(c-1)+b+1\big{)}\\\ =\sum_{s\in
T\subseteq\\{1,\dots,n\\}}\sum_{\begin{subarray}{c}1\leq
u_{1}<\cdots<u_{s}\leq n\\\ 1\leq k_{1},\dots,k_{s}\leq
d\end{subarray}}\operatorname*{CT}_{x}Q\big{(}(n-m-1)c+b+1\>|\>u_{1},\dots,u_{s};k_{1},\dots,k_{s}\big{)}.$

We find that only one term in the sum of (8.4) does not vanish. We present
this result in the next lemma.

######  Lemma 8.2.

Let $Q(d)$ be defined as in (8.3). For $n-n_{0}\leq m<n$,

(8.5) $\operatorname*{CT}_{x}Q\big{(}(n-m-1)(c-1)+b+1\big{)}\\\
=\operatorname*{CT}_{x}Q\big{(}(n-m-1)(c-1)+b+1\>|\>1,\dots,n-m;(n-m-1)(c-1)+b+1,\dots,c+b,b+1\big{)}.$

###### Proof.

Denote by $e:=(n-m-1)(c-1)+b+1$ for short. We will show that only the term
$\operatorname*{CT}\limits_{x}Q(e\>|\>1,\dots,n-m;e,\dots,c+b,b+1)$ in the sum
of (8.4) does not vanish. We first show that the $s$ in (8.4) can only be
$n-m$.

If $s>n-m$ then $e<(s-1)(c-1)+b+1$. Then by the property (1) of Lemma 6.8 we
have $Q(e\>|\>u;k)=0$, where $u=(u_{1},\dots,u_{s})$ and
$k=(k_{1},\dots,k_{s})$ are the integer sequences in (8.4).

If $1\leq s<n-m$ then $e>s(c-1)$. It follows that only the cases (2) and (3)
of Lemma 6.8 can occur. If (3) of Lemma 6.8 applies, or (2) of Lemma 6.8 holds
and $u_{s}=n$, then $\operatorname*{CT}\limits_{x}Q(e\>|\>u;k)=0$. If (2) of
Lemma 6.8 applies and $u_{s}\neq n$, then

$\operatorname*{CT}_{x_{u_{s}}}Q(e\>|\>u;k)=\sum_{\begin{subarray}{c}u_{s}<u_{s+1}\leq
n\\\ 1\leq k_{s+1}\leq
e\end{subarray}}Q(e\>|\>u_{1},\dots,u_{s},u_{s+1};k_{1},\dots,k_{s},k_{s+1}).$

But this contradicts the Gessel–Xin operation.

By the above argument we can conclude that the $s$ in (8.4) can only be $n-m$,
otherwise the summands in the right-hand side of (8.4) vanish. Then (8.4)
reduces to

(8.6) $\operatorname*{CT}_{x}Q(e)=\sum_{\begin{subarray}{c}1\leq
u_{1}<\cdots<u_{n-m}\leq n\\\ 1\leq k_{i}\leq
e\end{subarray}}\operatorname*{CT}_{x}Q(e\>|\>u^{\prime};k^{\prime}),$

where $u^{\prime}=(u_{1},\dots,u_{n-m})$ and
$k^{\prime}=(k_{1},\dots,k_{n-m})$.

We complete the proof by showing that all the terms in the sum of (8.6) vanish
except only when $k_{i}=(n-m-i)(c-1)+b+1$ and $u_{i}=i$ for $i=1,\dots,n-m$.

Since $1\leq k_{i}\leq e$ for $i=1,\dots,n-m$, by Corollary 6.5 with $s=n-m$,
at least one of the following cases holds:

  1. (1)

$1\leq k_{i}\leq b$ for some $i$ with $1\leq i\leq n-m$;

  2. (2)

$-c+1\leq k_{i}-k_{j}\leq c-2$ for some $(i,j)$ with $1\leq i<j\leq n-m$;

  3. (3)

$k_{i}=(n-m-i)(c-1)+b+1$ for $i=1,\dots,n-m$.

We then carry out similar argument as that in the proof of Lemma 6.8.

For $k=(k_{1},k_{2},\dots,k_{s})$, $u=(u_{1},u_{2},\dots,u_{s})$ and a
rational function $F$, recall that $E_{u,k}F$ is the result of replacing
$x_{u_{i}}$ in $F$ with $x_{u_{s}}q^{k_{s}-k_{i}}$ for $i=0,1,\dots,s-1$. Set
$u_{0}=k_{0}:=0$. If (1) holds, then $Q(e\>|\>u^{\prime};k^{\prime})$ has the
factor

$E_{u^{\prime},k^{\prime}}\Big{[}\big{(}qx_{u_{i}}/x_{0}\big{)}_{b}\Big{]}=\big{(}q^{1-k_{i}}\big{)}_{b}=0.$

If (2) holds, then $Q(e\>|\>u^{\prime};k^{\prime})$ has the factor

$E_{u^{\prime},k^{\prime}}\Big{[}\big{(}x_{u_{i}}/x_{u_{j}}\big{)}_{c-1}\big{(}qx_{u_{j}}/x_{u_{i}}\big{)}_{c-1}\Big{]},$

which is equal to

$E_{u^{\prime},k^{\prime}}\Big{[}q^{\binom{c}{2}}(-x_{u_{j}}/x_{u_{i}})^{c-1}\big{(}q^{-c+1}x_{u_{i}}/x_{u_{j}}\big{)}_{2c-2}\Big{]}=q^{\binom{c}{2}}(-q^{k_{i}-k_{j}})^{c-1}\big{(}q^{k_{j}-k_{i}-c+1}\big{)}_{2c-2}=0.$

If (3) holds and $u_{n-m}>n-m$, then $Q(e\>|\>u^{\prime};k^{\prime})$ has the
factor

$E_{u^{\prime},k^{\prime}}\Big{[}\big{(}qx_{u_{n-m}}/x_{0}\big{)}_{b+1}\Big{]}=\big{(}q^{1-k_{n-m}}\big{)}_{b+1}=\big{(}q^{-b}\big{)}_{b+1}=0.$

In conclusion, $Q(e\>|\>u^{\prime};k^{\prime})$ does not vanish only when
$k_{i}=(n-m-i)(c-1)+b+1$ and $u_{i}=i$ for $i=1,\dots,n-m$. Together with
(8.6) gives (8.5). ∎

We find that the right-hand side of (8.5) can be expressed by
$B_{n,n_{0}}(a,b,c,l,\mu)$. We state this result in the next lemma.

######  Lemma 8.3.

For $n-n_{0}\leq m<n$ and $c>b+1$,

(8.7)
$\operatorname*{CT}_{x}Q\big{(}(n-m-1)(c-1)+b+1\>|\>1,\dots,n-m;(n-m-1)(c-1)+b+1,\dots,c+b,b+1\big{)}\\\
=\frac{(q^{c})_{l}}{(q)_{l}}\prod_{i=0}^{n-m-1}\frac{(q)_{(i+1)(c-1)}(q^{-i(c-1)-b})_{b}}{(q)_{b+i(c-1)}(q)_{c-1}}\times
B_{m,n_{0}-n+m}\big{(}c-b-2,(n-m)(c-1)+b+1,c,0,l\big{)},$

where $B_{n,n_{0}}(a,b,c,l,\mu)$ is defined in (1.8).

###### Proof.

By the definition of $Q(d\>|\>u,k)$ in (6.29) with $M_{\mathfrak{r}}$ defined
in (8.1), we can write the left-hand side of (8.7) as

(8.8) $\operatorname*{CT}_{x}G\times C\times L,$

where

$\displaystyle G$
$\displaystyle=x_{n-m}^{-l}q^{-(b+1)l}h_{l}\Big{[}\frac{x_{n-m}(1-q^{c-1})}{1-q}\sum_{i=1}^{n-m}q^{-(n-m-i)(c-1)}+\sum_{i=n-m+1}^{n}\frac{1-q^{c-\chi(i\leq
n_{0})}}{1-q}x_{i}\Big{]}$
$\displaystyle=x_{n-m}^{-l}q^{-(b+1)l}h_{l}\Big{[}\frac{x_{n-m}(1-q^{(n-m)(c-1)})}{1-q}q^{-(n-m-1)(c-1)}+\sum_{i=n-m+1}^{n}\frac{1-q^{c-\chi(i\leq
n_{0})}}{1-q}x_{i}\Big{]},$ (8.9)
$C=\prod_{i=1}^{n-m}\frac{(q^{-(n-m-i)(c-1)-b})_{b}}{(q^{-(i-1)(c-1)})_{(i-1)(c-1)}(q)_{(n-m-i)(c-1)+b}}\prod_{1\leq
i<j\leq n-m}(q^{(i-j)(c-1)})_{c-1}(q^{(j-i)(c-1)+1})_{c-1},$

and

$\displaystyle L$
$\displaystyle=\prod_{j=n-m+1}^{n}\frac{(q^{-b}x_{j}/x_{n-m})_{b+1}}{(q^{-(n-m-1)(c-1)}x_{n-m}/x_{j})_{(n-m-1)(c-1)+b+1}}$
$\displaystyle\quad\times\prod_{n-m+1\leq i<j\leq
n}(x_{i}/x_{j})_{c-\chi(i\leq n_{0})}(qx_{j}/x_{i})_{c-\chi(i\leq n_{0})}$
$\displaystyle\quad\times\prod_{i=1}^{n-m}\prod_{j=n-m+1}^{n}(q^{-(n-m-i)(c-1)}x_{n-m}/x_{j})_{c-1}(q^{(n-m-i)(c-1)+1}x_{j}/x_{n-m})_{c-1}.$

It is routine to check that

(8.10)
$C=\prod_{i=0}^{n-m-1}\frac{(q)_{(i+1)(c-1)}(q^{-i(c-1)-b})_{b}}{(q)_{b+i(c-1)}(q)_{c-1}},$

and

$\displaystyle L$
$\displaystyle=\prod_{j=n-m+1}^{n}\frac{(q^{-b}x_{j}/x_{n-m})_{b+1}}{(q^{-(n-m-1)(c-1)}x_{n-m}/x_{j})_{(n-m-1)(c-1)+b+1}}$
$\displaystyle\quad\times\prod_{n-m+1\leq i<j\leq
n}(x_{i}/x_{j})_{c-\chi(i\leq n_{0})}(qx_{j}/x_{i})_{c-\chi(i\leq n_{0})}$
$\displaystyle\quad\times\prod_{j=n-m+1}^{n}(q^{-(n-m-1)(c-1)}x_{n-m}/x_{j})_{(n-m)(c-1)}(qx_{j}/x_{n-m})_{(n-m)(c-1)}.$

For $c>b+1$, we can simplify $L$ as

$L=\prod_{j=n-m+1}^{n}(q^{b+1}x_{n-m}/x_{j})_{c-b-2}(q^{-b}x_{j}/x_{n-m})_{(n-m)(c-1)+b+1}\\\
\times\prod_{n-m+1\leq i<j\leq n}(x_{i}/x_{j})_{c-\chi(i\leq
n_{0})}(qx_{j}/x_{i})_{c-\chi(i\leq n_{0})}.$

Letting $x_{n-m}q^{b+1}\mapsto x_{0}$, $n_{0}-n+m\mapsto n_{0}^{\prime}$,
$c-b-2\mapsto a^{\prime}$, $(n-m)(c-1)+b+1\mapsto b^{\prime}$ and
$(x_{n-m+1},x_{n-m+2},\dots,x_{n})\mapsto(x_{1},x_{2},\dots,x_{m})$, we find
that

(8.11) $\operatorname*{CT}_{x}G\times
L=\operatorname*{CT}_{x_{0},\dots,x_{m}}x_{0}^{-l}h_{l}\Big{[}\frac{q^{c-b^{\prime}-1}-q^{a^{\prime}}}{1-q}x_{0}+\sum_{i=1}^{m}\frac{1-q^{c-\chi(i\leq
n_{0}^{\prime})}}{1-q}x_{i}\Big{]}\\\
\times\prod_{i=1}^{m}(x_{0}/x_{i})_{a^{\prime}}(qx_{i}/x_{0})_{b^{\prime}}\prod_{1\leq
i<j\leq m}(x_{i}/x_{j})_{c-\chi(i\leq
n_{0}^{\prime})}(qx_{j}/x_{i})_{c-\chi(i\leq n_{0}^{\prime})}.$

By (4.16) and (4.17) we can write (8.11) as

$\operatorname*{CT}_{x}G\times
L=\frac{(q^{c})_{l}}{(q)_{l}}\operatorname*{CT}_{x_{0},\dots,x_{m}}x_{0}^{-l}P_{(l)}\Big{(}\Big{[}\frac{q^{c-b^{\prime}-1}-q^{a^{\prime}}}{1-q^{c}}x_{0}+\sum_{i=1}^{m}\frac{1-q^{c-\chi(i\leq
n_{0}^{\prime})}}{1-q^{c}}x_{i}\Big{]};q,q^{c}\Big{)}\\\
\times\prod_{i=1}^{m}(x_{0}/x_{i})_{a^{\prime}}(qx_{i}/x_{0})_{b^{\prime}}\prod_{1\leq
i<j\leq m}(x_{i}/x_{j})_{c-\chi(i\leq
n_{0}^{\prime})}(qx_{j}/x_{i})_{c-\chi(i\leq n_{0}^{\prime})}.$

By the definition of $B_{n,n_{0}}(a,b,c,l,\mu)$ in (1.8), the constant term
$\operatorname*{CT}\limits_{x}G\times L$ is in fact

$\frac{(q^{c})_{l}}{(q)_{l}}B_{m,n_{0}^{\prime}}(a^{\prime},b^{\prime},c,0,l)=\frac{(q^{c})_{l}}{(q)_{l}}B_{m,n_{0}-n+m}\big{(}c-b-2,(n-m)(c-1)+b+1,c,0,l\big{)}.$

Together with (8.10) gives

$\operatorname*{CT}_{x}C\times G\times
L=\frac{(q^{c})_{l}}{(q)_{l}}\prod_{i=0}^{n-m-1}\frac{(q)_{(i+1)(c-1)}(q^{-i(c-1)-b})_{b}}{(q)_{b+i(c-1)}(q)_{c-1}}\\\
\times B_{m,n_{0}-n+m}\big{(}c-b-2,(n-m)(c-1)+b+1,c,0,l\big{)}.$

Then (8.7) follows. ∎

Now by Lemma 8.2 and Lemma 8.3, we can give a proof of Proposition 8.1.

###### Proof of Proposition 8.1.

By (8.3), (8.5) and (8.7), we have

(8.12) $C_{n,n_{0}}(a,b,c,l,m)|_{-a=(n-m-1)c+b+1}\\\
=\frac{(q^{c})_{l}}{(q)_{l}}\prod_{i=0}^{n-m-1}\frac{(q)_{(i+1)(c-1)}(q^{-i(c-1)-b})_{b}}{(q)_{b+i(c-1)}(q)_{c-1}}\times
B_{m,n_{0}-n+m}\big{(}c-b-2,(n-m)(c-1)+b+1,c,0,l\big{)}.$

By the expression (1.9) for $B_{n,n_{0}}(a,b,c,l,\mu)$ with

$(n,n_{0},a,b,l,\mu)\mapsto(m,n_{0}-n+m,c-b-2,(n-m)(c-1)+b+1,0,l),$

it is straightforward to get

$\displaystyle B_{m,n_{0}-n+m}\big{(}c-b-2,(n-m)(c-1)+b+1,c,0,l\big{)}$
$\displaystyle\quad=(-1)^{l}q^{\binom{l}{2}}\frac{(q)_{l}}{(q^{c})_{l}}h_{l}\Big{[}\frac{1-q^{nc-
n_{0}}}{1-q}\Big{]}\frac{(q^{-(n-m-1)(c-1)-b-l})_{l}}{(q^{(n-1)c+b-n_{0}+2})_{l}}\prod_{j=1}^{n-n_{0}-1}(1-q^{(j+1)c})$
$\displaystyle\quad\prod_{j=n-m}^{n-1}\frac{(q^{(j-n+m+1)(c-1)-b+\chi(j>n_{0})(j-n_{0})})_{(n-m)(c-1)+b+1}(q)_{(j-n+m+1)(c-1)+\chi(j>n_{0})(j-n_{0})}}{(q)_{j(c-1)+b+1+\chi(j>n_{0})(j-n_{0})}(q)_{c-\chi(j\leq
n_{0})}}.$

Then we obtain the expression for $C_{n,n_{0}}(a,b,c,l,m)|_{-a=(n-m-1)c+b+1}$
in (8.2). ∎

##  9\. Case (3) of Lemma 6.8

In this section, we give a proof of Case (3) of Lemma 6.8. For this case, we
have to deal with the constant term of a certain rational function, where the
degree of an indeterminate (say $x$) in the numerator is larger than the
degree of $x$ in the denominator. The method used in this section extends the
Laurent series proof of constant term identities, such as the Gessel–Xin proof
of the $q$-Dyson constant term identity in [9], and the Laurent series proof
of the first-layer coefficients of the $q$-Dyson product by Lv et al. in [16].

Suppose
$Q_{n,n_{0}}(d,b,c;M_{\mathfrak{r}})=Q_{n,0}(d,b,c-1;M_{\mathfrak{r}})$ for
$n_{0}\geq n$. (When we specify $M_{\mathfrak{r}}$ to be (7.1) and (8.1) to
prove Theorem 1.1 and Theorem 1.2 respectively, it is the case.) Moreover,
since the Case (3) of Lemma 6.8 does not occur for $n_{0}=0,1$, we assume
$2\leq n_{0}\leq n-1$ in this section.

###  9.1. The Laurent polynomiality of $Q(d\>|\>u;k)$

In this subsection, we show that the rational function $Q(d\>|\>u;k)$ (defined
in (6.29)) is either 0, or can be written as a Laurent polynomial. This is the
content of the next lemma.

######  Lemma 9.1.

Let $(u_{1},u_{2},\dots,u_{s})$ be an integer sequence such that $1\leq
u_{1}<u_{2}<\cdots<u_{s}\leq n$ and set $U=\\{u_{1},u_{2},\dots,u_{s}\\}$.
Denote $r=\big{|}\\{u_{i}\>|\>u_{i}\leq n_{0},i=1,\dots,s\\}\big{|}$. For
$0\leq r\leq n_{0}-2$ and $1\leq d\leq s(c-1)+b+\chi(s>n_{0})(s-n_{0})$,
$Q(d\>|\>u;k)$ is either 0, or can be written as a Laurent polynomial of the
form

(9.1) $x_{u_{s}}^{l}\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\Big{(}p_{i}(x_{i}/x_{u_{s}})x_{i}^{d-s(c-1)-\chi(i>n_{0})(s-r)}\Big{)}\prod_{\begin{subarray}{c}1\leq
i<j\leq n\\\ i,j\notin U\end{subarray}}\big{(}x_{i}/x_{j}\big{)}_{c-\chi(i\leq
n_{0})}\big{(}qx_{j}/x_{i}\big{)}_{c-\chi(i\leq n_{0})},$

where $p_{i}(z)$ is a polynomial in $z$ and

$l=(n-s)\big{(}s(c-1)-d\big{)}+(s-r)(n-n_{0}-s+r).$

Recall that $Q(d\>|\>u;k)$ can be written as (6.33). We can further write it
as

(9.2) $Q(d\>|\>u;k)=\prod_{\begin{subarray}{c}1\leq i<j\leq n\\\ i,j\notin
U\end{subarray}}\big{(}x_{i}/x_{j}\big{)}_{c-\chi(i\leq
n_{0})}\big{(}qx_{j}/x_{i}\big{)}_{c-\chi(i\leq n_{0})}\times H\times C\times
V^{\prime}\times L^{\prime},$

where

$H=E_{u,k}\big{(}x_{0}^{-\mathfrak{r}}\times M_{\mathfrak{r}}\big{)},$
$\displaystyle C=$
$\displaystyle\prod_{i=1}^{s}(q^{k_{i}-d})^{-1}_{d-k_{i}}(q)^{-1}_{k_{i}-1}\prod_{\begin{subarray}{c}1\leq
i<j\leq s\\\ i\leq
r\end{subarray}}(-1)^{c-1}q^{\binom{c}{2}+(c-1)(k_{i}-k_{j})}\prod_{r+1\leq
i<j\leq s}(-1)^{c}q^{\binom{c+1}{2}+c(k_{i}-k_{j})}$ $\displaystyle\
\times\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}(-1)^{d}q^{\binom{d+1}{2}-dk_{s}}\prod_{\begin{subarray}{c}i=1\\\
i\notin
U\end{subarray}}^{n}\prod_{j=1}^{r}(-1)^{c-1}q^{(c-1)\big{(}k_{s}-k_{j}+\chi(u_{j}>i)\big{)}+\binom{c-1}{2}}$
$\displaystyle\ \times\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\prod_{j=r+1}^{s}(-1)^{c-\chi(i\leq
n_{0})}q^{(c-\chi(i\leq
n_{0}))\big{(}k_{s}-k_{j}+\chi(u_{j}>i)\big{)}+\binom{c-\chi(i\leq
n_{0})}{2}},$

(9.3)
$V^{\prime}=\prod_{i=1}^{s}(q^{1-k_{i}})_{b}\prod_{\begin{subarray}{c}1\leq
i<j\leq s\\\ i\leq r\end{subarray}}(q^{k_{j}-k_{i}-c+1})_{2c-2}\prod_{r+1\leq
i<j\leq s}(q^{k_{j}-k_{i}-c})_{2c},$

and

(9.4) $\displaystyle L^{\prime}$
$\displaystyle=\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\frac{(q^{1-k_{s}}x_{i}/x_{u_{s}})_{b}}{(x_{u_{s}}/x_{i})^{d}\big{(}q^{1-k_{s}}x_{i}/x_{u_{s}}\big{)}_{d}}\prod_{\begin{subarray}{c}i=1\\\
i\notin
U\end{subarray}}^{n}\prod_{j=1}^{r}(x_{u_{s}}/x_{i})^{c-1}\big{(}q^{k_{j}-k_{s}-c+2-\chi(u_{j}>i)}x_{i}/x_{u_{s}}\big{)}_{2c-2}$
$\displaystyle\ \ \times\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\prod_{j=r+1}^{s}(x_{u_{s}}/x_{i})^{c-\chi(i\leq
n_{0})}\big{(}q^{k_{j}-k_{s}-c+1+\chi(i\leq
n_{0})-\chi(u_{j}>i)}x_{i}/x_{u_{s}}\big{)}_{2c-2\chi(i\leq n_{0})}.$

For certain conditions, $L^{\prime}$ can be written as a Laurent polynomial.
That is, the product $\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}(q^{1-k_{s}}x_{i}/x_{u_{s}})_{d}$ in the denominator of
$L^{\prime}$ is in fact a factor of the numerator of $L^{\prime}$.

######  Lemma 9.2.

For $s\in\\{1,2,\dots,n\\}$, let $0\leq r\leq\min\\{n_{0}-2,s\\}$, $1\leq
d\leq s(c-1)+b+\chi(s>n_{0})(s-n_{0})$. For $i=1,\dots,s$ the $k_{i}$ satisfy
$1\leq k_{i}\leq d$, and there exists a permutation $w\in\mathfrak{S}_{s}$ and
nonnegative integers $t_{1},\dots,t_{s}$ such that

(9.5) $k_{w(1)}=b+t_{1},$

and

(9.6) $k_{w(j)}-k_{w(j-1)}=c-1+\chi(w(j)>r)\chi(w(j-1)>r)+t_{j}\quad\text{for
$2\leq j\leq s$.}$

Here the $t_{j}$ satisfy

(9.7) $s-r\leq\sum_{j=1}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}\leq
c-1+\chi(s>n_{0})(s-n_{0}),$

$w(0):=0$, and $t_{j}>0$ if $w(j-1)<w(j)$ for $1\leq j\leq s$. Then the
rational function $L^{\prime}$ defined in (9.4) can be written as the form

(9.8) $x_{u_{s}}^{l}\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\Big{(}p_{i}(x_{i}/x_{u_{s}})x_{i}^{d-s(c-1)-\chi(i>n_{0})(s-r)}\Big{)},$

where

$l=(n-s)\big{(}s(c-1)-d\big{)}+(s-r)(n-n_{0}-s+r),$

and the $p_{i}(z)$ are polynomials in $z$.

###### Proof.

Let

$\displaystyle S_{0}:=$
$\displaystyle\\{1-k_{s},2-k_{s},\dots,d-k_{s}\\},\quad
B:=\\{1-k_{s},2-k_{2},\dots,b-k_{s}\\},$ $\displaystyle S_{j}:=$
$\displaystyle\\{k_{j}-k_{s}-c+2-\chi(u_{j}>i),\dots,k_{j}-k_{s}+c-1-\chi(u_{j}>i)\\}$

for $j=1,\dots,r$ and $i\in\\{1,\dots,n\\}\setminus U$, and

$S_{j}:=\\{k_{j}-k_{s}-c+1+\chi(i\leq
n_{0})-\chi(u_{j}>i),\dots,k_{j}-k_{s}+c-\chi(i\leq n_{0})-\chi(u_{j}>i)\\}$

for $j=r+1,\dots,s$ and $i\in\\{1,\dots,n\\}\setminus U$. Assuming the
conditions of the lemma, we show that the product

$\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\big{(}q^{1-k_{s}}x_{i}/x_{u_{s}}\big{)}_{d}$

in the denominator of $L^{\prime}$ is in fact a factor of its numerator. Then
$L^{\prime}$ can be written as a Laurent polynomial, rather than a rational
function. To achieve this, it is equivalent to showing that

(9.9) $S_{0}\subseteq\bigcup_{j=1}^{s}S_{j}\bigcup B.$

Since $S^{\prime}_{j}:=\\{k_{j}-k_{s}-c+2,\dots,k_{j}-k_{s}+c-2\\}\subseteq
S_{j}$ for $j=1,\dots,s$, (9.9) holds if we show that

(9.10) $S_{0}\subseteq\bigcup_{j=1}^{s}S^{\prime}_{j}\bigcup B.$

To obtain (9.10), it suffices to prove

  1. (1)

$b\geq k_{w(1)}-c+1$;

  2. (2)

$k_{w(s)}+c-2\geq d$;

  3. (3)

$k_{w(j-1)}+c-2\geq k_{w(j)}-c+1$ for $j=2,\dots,s$.

To prove (1), we need to find the upper bound for $k_{w(1)}$. By (9.6) we have

(9.11)
$\sum_{j=2}^{s}\big{(}k_{w(j)}-k_{w(j-1)}\big{)}=k_{w(s)}-k_{w(1)}=(s-1)(c-1)+\sum_{j=2}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

Then

(9.12)
$k_{w(1)}=k_{w(s)}-(s-1)(c-1)-\sum_{j=2}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

Since the $t_{j}$ satisfy Proposition 6.3, by (6.12b) we have

(9.13) $\sum_{j=2}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}\geq
s-r-1$

for $r<s$. It is clear that the inequality (9.13) also holds for $r=s$. Hence,
substituting (9.13) into (9.12) gives

(9.14) $k_{w(1)}\leq k_{w(s)}-(s-1)(c-1)-(s-r-1).$

Since $r\leq n_{0}-2$ and $k_{w(s)}\leq d\leq
s(c-1)+b+\chi(s>n_{0})(s-n_{0})$,

$k_{w(1)}\leq c-1+b+(s-n_{0})-\big{(}s-(n_{0}-2)-1\big{)}=c+b-2$

for $s>n_{0}$. Thus (1) holds for $s>n_{0}$. If $s\leq n_{0}$, then
$k_{w(s)}\leq d\leq s(c-1)+b$. Substituting this into (9.12) yields

$k_{w(1)}\leq
c-1+b-\sum_{j=2}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}\leq c-1+b.$

Consequently, (1) holds if $s\leq n_{0}$. In conclusion, (1) holds for all the
$s$.

To prove (2), we need to find the lower bound for $k_{w(s)}$. By (9.11)

$k_{w(s)}=k_{w(1)}+(s-1)(c-1)+\sum_{j=2}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

Substituting (9.5) into the above equation gives

$k_{w(s)}=b+(s-1)(c-1)+\sum_{j=1}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

If $s>n_{0}$ then by (9.7) and $r\leq n_{0}-2$ we have

$k_{w(s)}\geq b+(s-1)(c-1)+s-r\geq
b+(s-1)(c-1)+s-n_{0}+2=b+s(c-1)+s-n_{0}-c+3\geq d-c+3.$

Hence, (2) holds for $s>n_{0}$. If $s\leq n_{0}$, then by the fact that
$t_{1}\geq 1$ we have

$k_{w(s)}\geq b+(s-1)(c-1)+1=s(c-1)+b-c+2\geq d-c+2.$

Thus (2) also holds for $s\leq n_{0}$. In conclusion, (2) holds for all $s$.

If (3) fails for some $i\in\\{2,\dots,s\\}$, then

$k_{w(i)}-k_{w(i-1)}\geq 2(c-1).$

Together with (9.6) gives

(9.15) $k_{w(s)}-k_{w(1)}=\sum_{j=2}^{s}\big{(}k_{w(j)}-k_{w(j-1)}\big{)}\geq
s(c-1)+\sum_{\begin{subarray}{c}j=2\\\ j\neq
i\end{subarray}}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

Substituting (9.5) into the above equation, we have

$k_{w(s)}\geq s(c-1)+b+\sum_{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}.$

We conclude contradictions by discussing the following cases:

  * •

For $r<s$ and $s>n_{0}$, using (6.12b) again and $r\leq n_{0}-2$ yields

$k_{w(s)}\geq s(c-1)+b+s-r-1\geq s(c-1)+b+s-(n_{0}-2)-1=s(c-1)+b+s-n_{0}+1>d.$

This contradicts the assumption $k_{i}\leq d$ for all $i$.

  * •

If $r=s>n_{0}$ then it contradicts to the condition $r\leq\min\\{n_{0}-2,s\\}$
in the lemma.

  * •

If $s\leq n_{0}$ then $d\leq s(c-1)+b$. By (9.15) and $k_{w(1)}=b+t_{1}\geq
b+1$, we have

$k_{w(s)}\geq s(c-1)+k_{w(1)}+\sum_{\begin{subarray}{c}j=2\\\ j\neq
i\end{subarray}}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}\geq
s(c-1)+b+1>d.$

This also contradicts the assumption $k_{i}\leq d$ for all $i$.

Therefore, (3) holds.

Since (1)-(3) hold, we obtain (9.9). It follows that $L^{\prime}$ is a Laurent
polynomial of the form

$\displaystyle\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\frac{p_{i}(x_{i}/x_{u_{s}})}{(x_{u_{s}}/x_{i})^{d}}\prod_{\begin{subarray}{c}i=1\\\
i\notin
U\end{subarray}}^{n}\bigg{(}\prod_{j=1}^{r}(x_{u_{s}}/x_{i})^{c-1}\prod_{j=r+1}^{s}(x_{u_{s}}/x_{i})^{c-\chi(i\leq
n_{0})}\bigg{)}$ $\displaystyle\ \ =\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\bigg{(}\frac{p_{i}(x_{i}/x_{u_{s}})}{(x_{u_{s}}/x_{i})^{d}}\prod_{j=1}^{s}(x_{u_{s}}/x_{i})^{c-1}\prod_{j=r+1}^{s}(x_{u_{s}}/x_{i})^{\chi(i>n_{0})}\bigg{)}$
$\displaystyle\ \ =x_{u_{s}}^{l}\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\Big{(}p_{i}(x_{i}/x_{u_{s}})x_{i}^{d-s(c-1)-\chi(i>n_{0})(s-r)}\Big{)},$

where the $p_{i}(z)$ are polynomials in $z$, and

$l=(n-s)\big{(}s(c-1)-d\big{)}+(s-r)(n-n_{0}-s+r).\qed$

By Lemma 9.2 and Lemma 6.4, we can give a proof of Lemma 9.1.

###### Proof of Lemma 9.1.

Recall that $Q(d\>|\>u;k)$ can be written as the form in (9.2). By Lemma 6.4
with $t=c-1+\chi(s>n_{0})(s-n_{0})$, at least one of the following cases
holds:

  1. (1)

$1\leq k_{i}\leq b$ for some $i$ with $1\leq i\leq s$;

  2. (2)

$-c+1\leq k_{i}-k_{j}\leq c-2$ for some $(i,j)$ such that $1\leq i<j\leq s$
and $i\leq r$;

  3. (3)

$-c\leq k_{i}-k_{j}\leq c-1$ for some $(i,j)$ such that $r<i<j\leq s$;

  4. (4)

there exists a permutation $w\in\mathfrak{S}_{s}$ and nonnegative integers
$t_{1},\dots,t_{s}$ such that

(9.16) $k_{w(1)}=b+t_{1},$ and
$k_{w(j)}-k_{w(j-1)}=c-1+\chi(w(j)>r)\chi(w(j-1)>r)+t_{j}\quad\text{for $2\leq
j\leq s$.}$

Here the $t_{j}$ satisfy

$s-r\leq\sum_{j=1}^{s}\big{(}t_{j}+\chi(w(j)>r)\chi(w(j-1)>r)\big{)}\leq
c-1+\chi(s>n_{0})(s-n_{0}),$

$w(0):=0$, and $t_{j}>0$ if $w(j-1)<w(j)$ for $1\leq j\leq s$.

If one of the cases (1)-(3) holds, then $V^{\prime}$ defined in (9.3) is zero
by a similar argument as that in the first part of the proof of Lemma 6.8.
Since $V^{\prime}$ is a factor of $Q(d\>|\>u;k)$, we can conclude that
$Q(d\>|\>u;k)=0$.

If Case (4) holds and $0\leq r\leq\min\\{n_{0}-2,s\\}$, then $Q(d\>|\>u;k)$
can be written as the form of (9.1) by Lemma 9.2. Here $C,V^{\prime}\in K$ can
be put into the coefficients of some polynomial $p_{i}$, and
$H=E_{u,k}\big{(}x_{0}^{-\mathfrak{r}}\times M_{\mathfrak{r}}\big{)}$ is also
of the form $\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}p_{i}(x_{i}/x_{u_{s}})$. ∎

###  9.2. Proof of Case (3) of Lemma 6.8

In this subsection, we give a proof of the Case (3) of Lemma 6.8. We present
it in the next lemma.

######  Lemma 9.3.

Assume the conditions of Lemma 6.8. If $s\neq n$ and

(9.17) $s(c-1)+\chi(s>n_{0})(s-n_{0})+1\leq d\leq
s(c-1)+(s-r)(n-n_{0}-s+r)/(n-s),$

then

$\operatorname*{CT}_{x}Q(d\>|\>u;k)=0.$

###### Proof.

Recall that $r$ is defined as

$r=\big{|}\\{u_{i}\>|\>u_{i}\leq n_{0},i=1,2,\dots,s\\}\big{|}.$

Then $0\leq r\leq\min\\{n_{0},s\\}$. We first show that $r\neq n_{0}-1,n_{0}$
in this lemma.

Since

$\frac{(s-r)(n-n_{0}-s+r)}{n-s}\bigg{|}_{r=n_{0}-1}=\frac{(s-n_{0}+1)(n-s-1)}{n-s}<s-n_{0}+1\leq\chi(s>n_{0})(s-n_{0})+1,$

the lower bound of $d$ exceeds its upper bound in (9.17) for $r=n_{0}-1$.
Hence, $r\neq n_{0}-1$. Since

$\frac{(s-r)(n-n_{0}-s+r)}{n-s}\bigg{|}_{r=n_{0}}=s-n_{0}<\chi(s>n_{0})(s-n_{0})+1,$

the lower bound of $d$ also exceeds its upper bound in (9.17) for $r=n_{0}$.
Hence, $r\neq n_{0}$. Therefore, we conclude that (9.17) implies $0\leq r\leq
n_{0}-2$. Then $0\leq r\leq\min\\{n_{0}-2,s\\}$.

Since $0\leq r\leq\min\\{n_{0}-2,s\\}$, we can apply Lemma 9.1 to obtain that
$Q(d\>|\>u;k)$ is either 0, or can be written as a Laurent polynomial of the
form

$L:=x_{u_{s}}^{l}\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n}\Big{(}p_{i}(x_{i}/x_{u_{s}})x_{i}^{d-s(c-1)-\chi(i>n_{0})(s-r)}\Big{)}\prod_{\begin{subarray}{c}1\leq
i<j\leq n\\\ i,j\notin U\end{subarray}}\big{(}x_{i}/x_{j}\big{)}_{c-\chi(i\leq
n_{0})}\big{(}qx_{j}/x_{i}\big{)}_{c-\chi(i\leq n_{0})},$

where $p_{i}(z)$ is a polynomial in $z$,
$l=(n-s)\big{(}s(c-1)-d\big{)}+(s-r)(n-n_{0}-s+r)$ and
$U=\\{u_{1},\dots,u_{s}\\}$. Notice that by taking the constant term of $L$
with respect to $x_{u_{s}}$, we can write
$\operatorname*{CT}\limits_{x_{u_{s}}}L$ as a finite sum of the form

$P:=c\times\frac{\prod_{\begin{subarray}{c}i=1\\\ i\notin
U\end{subarray}}^{n_{0}}x_{i}^{d-s(c-1)}}{\prod_{\begin{subarray}{c}i=n_{0}+1\\\
i\notin
U\end{subarray}}^{n}x_{i}^{s(c-1)-d+s-r}}\prod_{\begin{subarray}{c}i=1\\\
i\notin U\end{subarray}}^{n}x_{i}^{t_{i}}\prod_{\begin{subarray}{c}1\leq
i<j\leq n\\\ i,j\notin U\end{subarray}}\big{(}x_{i}/x_{j}\big{)}_{c-\chi(i\leq
n_{0})}\big{(}qx_{j}/x_{i}\big{)}_{c-\chi(i\leq n_{0})},$

where $c\in K$ and the $t_{i}$ are nonnegative integers such that
$\sum_{\begin{subarray}{c}i=1\\\ i\notin U\end{subarray}}^{n}t_{i}=l$. We will
show that $\operatorname*{CT}\limits_{x}P=0$.

Let

$\displaystyle(x_{1},\dots,\hat{x}_{u_{1}},\dots,\hat{x}_{u_{s}},x_{n})$
$\displaystyle\mapsto z:=(z_{1},\dots,z_{n-s})\quad\text{and}$
$\displaystyle(t_{1},\dots,\hat{t}_{u_{1}},\dots,\hat{t}_{u_{s}},t_{n})$
$\displaystyle\mapsto(t^{\prime}_{1},\dots,t^{\prime}_{n-s}).$

Then

(9.18)
$\operatorname*{CT}_{x}P=c\times\operatorname*{CT}_{z}\frac{\prod_{i=1}^{n_{0}-r}z_{i}^{d-s(c-1)}}{\prod_{i=n_{0}-r+1}^{n-s}z_{i}^{s(c-1)-d+s-r}}\prod_{i=1}^{n-s}z_{i}^{t^{\prime}_{i}}\prod_{1\leq
i<j\leq n-s}\big{(}z_{i}/z_{j}\big{)}_{c-\chi(i\leq
n_{0}-r)}\big{(}qz_{j}/z_{i}\big{)}_{c-\chi(i\leq n_{0}-r)},$

where $\sum_{i=1}^{n-s}t^{\prime}_{i}=l$. If we further take
$s(c-1)-d+s-r\mapsto h$, $n-s\mapsto n^{\prime}$ and $n_{0}-r\mapsto
n^{\prime}_{0}$ in (9.18), then

(9.19)
$\operatorname*{CT}_{x}P=c\times\operatorname*{CT}_{z}\frac{\prod_{i=1}^{n^{\prime}_{0}}z_{i}}{\prod_{i=n^{\prime}_{0}+1}^{n^{\prime}}z_{i}^{h}}\prod_{i=1}^{n^{\prime}}z_{i}^{t^{\prime}_{i}+d-s(c-1)-1}\prod_{1\leq
i<j\leq n^{\prime}}\big{(}z_{i}/z_{j}\big{)}_{c-\chi(i\leq
n^{\prime}_{0})}\big{(}qz_{j}/z_{i}\big{)}_{c-\chi(i\leq n^{\prime}_{0})}.$

Note that these substitutions for $P$ do not change its constant term. By the
condition $s(c-1)+\chi(s>n_{0})(s-n_{0})+1\leq d$ in the lemma, we have

$h=s(c-1)-d+s-r\leq-\chi(s>n_{0})(s-n_{0})-1+s-r\leq-(s-n_{0})-1+s-r=n_{0}-r-1=n^{\prime}_{0}-1.$

For $d\leq s(c-1)+(s-r)(n-n_{0}-s+r)/(n-s)$ and $r\leq n_{0}-2$ we have

$h=s(c-1)-d+s-r\geq s-r-(s-r)(n-n_{0}-s+r)/(n-s)\geq
s-r-(s-r)(n-s-2)/(n-s)>0.$

Then $1\leq h\leq n^{\prime}_{0}-1$. By $0\leq r\leq\min\\{n_{0}-2,s\\}$ and
the assumption $2\leq n_{0}\leq n-1$, we have $n_{0}^{\prime}=n_{0}-r\geq 2$
and $n_{0}^{\prime}=n_{0}-r\leq n_{0}-s\leq n-1-s=n^{\prime}-1$. It is clear
that $d-s(c-1)>0$ by the condition $d\geq s(c-1)+\chi(s>n_{0})(s-n_{0})+1$ in
the lemma. Then $t^{\prime}_{i}+d-s(c-1)-1\geq 0$ for all the $i$. Hence, we
can apply Lemma 3.10 to the right-hand side of (9.19) and obtain
$\operatorname*{CT}\limits_{x}P=0$. It follows that
$\operatorname*{CT}\limits_{x}Q(d\>|\>u,k)=0$. ∎

### Acknowledgements

This work was supported by the National Natural Science Foundation of China
(No. 12071311, 12171487).

## References

  * [1] V. A. Alba, V. A. Fateev, A. V. Litvinov and G. M. Tarnopolskiy, _On combinatorial expansion of the conformal blocks arising from AGT conjecture_ , Lett. Math. Phys. 98 (2011), 33–64.
  * [2] S. P. Albion, E. M. Rains and S. O. Warnaar, _AFLT-type Selberg integrals_ , Commun. Math. Phys. 388 (2021), 735–791.
  * [3] R. Askey, _Some basic hypergeometric extensions of integrals of Selberg and Andrews_ , SIAM J. Math. Anal. 11 (1980), 938–951.
  * [4] T. H. Baker and P. J. Forrester, _Generalizations of the $q$-Morris constant term identity_, J. Combin. Theory, Ser. A 81 (1998), 69–87.
  * [5] T. W. Cai, _Macdonald symmetric functions of rectangular shapes_ , J. Combin. Theory Ser. A 128 (2014), 162–179.
  * [6] P. J. Forrester and S. O. Warnaar, _The importance of the Selberg integral_ , Bull. Amer. Math. Soc. (N.S.) 45 (2008), 489–534.
  * [7] G. Gasper and M. Rahman, _Basic Hypergeometric Series_ , Encyclopedia of Mathematics and its Applications, Vol. 35, second edition, Cambridge University Press, Cambridge, 2004.
  * [8] I. M. Gessel, L. Lv, G. Xin and Y. Zhou, _A unified elementary approach to the Dyson, Morris, Aomoto, and Forrester constant terms_ , J. Combin. Theory Ser. A 115 (2008), 1417–1435.
  * [9] I. M. Gessel and G. Xin, _A short proof of the Zeilberger–Bressoud $q$-Dyson theorem_, Proc. Amer. Math. Soc. 134 (2006), 2179–2187.
  * [10] L. Habsieger, _Une $q$-intégrale de Selberg et Askey_, SIAM J. Math. Anal. 19 (1988) 1475–1489.
  * [11] J. Haglund, _The $q,t$-Catalan Numbers and the Space of Diagonal Harmonics: With an appendix on the combinatorics of Macdonald polynomials_, Univ. Lecture Ser., vol. 41, Amer. Math. Soc., Providence, RI, (2008).
  * [12] K. W. J. Kadell, _A proof of Askey’s conjectured $q$-analogue of Selberg’s integral and a conjecture of Morris_, SIAM J. Math. Anal. 19 (1988), 969–986.
  * [13] G. Károlyi, Z. L. Nagy, F. V. Petrov, and V. Volkov, _A new approach to constant term identities and Selberg-type integrals_ , Adv. Math. 277 (2015), 252–282.
  * [14] A. Lascoux, _Symmetric Functions and Combinatorial Operators on Polynomials_ , CBMS Reg. Conf. Ser. Math., Vol. 99, Amer. Math. Soc., Providence, RI, 2003.
  * [15] M. Lassalle, _A short proof of generalized Jacobi-Trudi expansions for Macdonald polynomials_ , Contemp. Math. 417 (2006), 271–280.
  * [16] L. Lv, G. Xin and Y. Zhou, _A family of $q$-Dyson style constant term identities_, J. Combin. Theory Ser. A 116 (2009), 12–29.
  * [17] I. G. Macdonald, _A new class of symmetric functions_ , Actes du 20e Séminaire Lotharingien, vol. 372/S-20, Publications I.R.M.A., Strasbourg, 1988, pp. 131–171.
  * [18] I. G. Macdonald, _Symmetric Functions and Hall Polynomials_ , 2nd edition, The Clarendon Press, Oxford University Press, 1995.
  * [19] W. G. Morris, _Constant Term Identities for Finite and Affine Root System: Conjectures and Theorems_ , Ph.D. thesis, Univ. Wisconsin–Madison, 1982.
  * [20] E. M. Rains and S. O. Warnaar, _Bounded Littlewood identities_ , Mem. Amer. Math. Soc., 270 (2021), No 1317, vii+115pp.
  * [21] A. Selberg, _Bemerkninger om et multipelt integral_ , Norsk Mat. Tidsskr. 26 (1944), 71–78.
  * [22] J. R. Stembridge, _First layer formulas for characters of $SL(n,\mathbb{C})$_, Trans. Amer. Math. Soc. 299 (1987), 319–350.
  * [23] S. O. Warnaar, _$q$ -Selberg integrals and Macdonald polynomials_, Ramanujan J. 10 (2005), 237–268.
  * [24] G. Xin, _The Ring of Malcev–Neumann Series and the Residue Theorem_ , Ph.D Thesis, Brandeis University, 2004.
  * [25] G. Xin, _A fast algorithm for MacMahon’s partition analysis_ , Electron. J. Combin. 11 (2004), R58, 20 pp.
  * [26] G. Xin and Y. Zhou, _A Laurent series proof of the Habsieger–Kadell $q$-Morris identity_, Electron. J. Combin. 21 (2014), #P3.38.
  * [27] D. Zeilberger and D. M. Bressoud, _A proof of Andrews’ $q$-Dyson conjecture_, Discrete Math. 54 (1985), 201–224.
  * [28] Y. Zhou, _On the $q$-Dyson orthogonality problem_, Adv. Appl. Math. 130 (2021), 102224.


# Benchmarking Neural Machine Translation for Southern African Languages

Laura Martinus
Explore Data Science Academy, South Africa
<EMAIL_ADDRESS>
Jade Z. Abbott
Retro Rabbit, South Africa
<EMAIL_ADDRESS>

###### Abstract

Unlike major Western languages, most African languages are very low-resourced.
Furthermore, the resources that do exist are often scattered and difficult to
obtain and discover. As a result, the data and code for existing research has
rarely been shared. This has lead a struggle to reproduce reported results,
and few publicly available benchmarks for African machine translation models
exist. To start to address these problems, we trained neural machine
translation models for 5 Southern African languages on publicly-available
datasets. Code is provided for training the models and evaluate the models on
a newly released evaluation set, with the aim of spur future research in the
field for Southern African languages.

##  1 Introduction

Africa has over 2 000 languages across the continent [Eberhard et al., 2019].
South Africa itself has 11 official languages, and many more unofficial
languages. Unlike major Western languages, the multitude of African languages
are very low-resourced. Furthermore, the resources that do exist are often
scattered and difficult to obtain or discover. The datasets are often owned by
small institutions and research is published in smaller African conferences
and never published online. As a result, the data and code for existing
research has rarely been shared, meaning researchers struggle to reproduce the
results properly, and few publicly available benchmarks for African machine
translation models exist.

To begin to solve the highlighted problems, we train neural machine
translation (NMT) models for a subset of Southern African languages, for which
parallel publicly-available datasets exist and publish the code on
GitHub111Available online at: https://github.com/LauraMartinus/ukuxhumana. We
evaluate the models on the new Autshumato evaluation set for machine
translation of Southern African languages [McKellar, 2017], in an attempt to
spur future research in machine translation of Southern African languages.

Translation models are trained for English to Afrikaans, isiZulu, Northern
Sotho, Setswana and Xitsonga, using state-of-the-art NMT architectures,
namely, Convolutional Sequence-to-Sequence (ConvS2S) and Transformer
architectures [Chahuneau et al., 2013].

11footnotetext:  Presented at ACL 2019 Workshop on Widening Natural Language
Processing

##  2 Languages

The isiZulu, N. Sotho, Setswana, and Xitsonga languages belong to the Southern
Bantu group of African languages [Mesthrie and Rajend, 2002]. The Bantu
languages are agglutinative and all exhibit a rich noun class system, subject-
verb-object word order, and tone [Zerbian, 2007]. Northern Sotho and Setswana
are closely related and highly mutually-intelligible. Xitsonga is a language
of the Vatsonga people [Bill, 1984]. The language of isiZulu belongs to the
Nguni language family, and is known for its morphological complexity [Keet and
Khumalo, 2017]. Afrikaans is an analytic West-Germanic language, that
descended from Dutch settlers [Roberge, 2002].

##  3 Related Work

Machine translation research for Southern African languages is scarce
[Martinus and Abbott, 2019, Abbott and Martinus, 2018, Wilken et al., 2012,
McKellar, 2014]. Much of the research suffers from the problems described
above. For example, Van Niekerk report BLEU scores as high as 37.9 for
English-to-Northern Sotho translation and 71 for English-to-Afrikaans
translation, but neither the datasets nor the code are published [van Niekerk,
2014]. Wilken et. al. use publicly-available parallel datasets, but reports
using monolingual datasets which were not released [Wilken et al., 2012].

##  4 Data

The Autshumato parallel corpora are aligned parallel corpora of South African
governmental data [Groenewald and Fourie, 2009], for English to Afrikaans,
isiZulu, Northern Sotho, Setswana, and Xitsonga.222Available online at:
https://repo.sadilar.org/handle/20.500.12185/404

| Afrikaans | isiZulu | Northern Sotho | Setswana | Xitsonga
---|---|---|---|---|---
Sentences | 53 172 | 26 728 | 30 777 | 123 868 | 193 587
Table 1:  Number of parallel sentences for English-to-Target language

Table 1 highlights how low resourced these datasets are. The datasets had many
duplicates which we removed to avoid data leakage between training and test
sets.

A newly proposed Autshumato evaluation set for machine translation of South
African languages has been released [McKellar, 2017]. The evaluation set
consists of 500 sentences translated separately by four different professional
human translators for each of the 11 official South African languages. We
evaluated our models on this benchmark.

##  5 Architectures

Limited work has been done using NMT techniques for African languages. We
trained translation models for two popular NMT architectures, namely, ConvS2S
[Gehring et al., 2017] and Transformer [Vaswani et al., 2017]333The hyper-
parameters used for each architecture are available online here:
https://github.com/LauraMartinus/ukuxhumana .

##  6 Results

The BLEU scores for each model on English-to-Target language are presented in
Table 2. The Transformer model outperformed the ConvS2S model for all
languages. These results serve as initial baseline results for the given
languages on the evaluation set.

Model | Afrikaans | isiZulu | Northern Sotho | Setswana | Xitsonga
---|---|---|---|---|---
ConvS2S | 12.30 | 0.52 | 7.41 | 10.31 | 10.73
Transformer | 20.60 | 1.34 | 10.94 | 15.60 | 17.98
Table 2:  BLEU Scores for English-to-Target language on evaluation dataset

We supply a few qualitative sample translations in Table 3 and Table 4, as
well as multi-head attention visualisations, to demonstrate the performance of
the models.

We notice that the performance of techniques on a specific target language is
related to corpus size and morphological typology of the language. Afrikaans
is not agglutinative, thus despite having less than half the number of
sentences as Xitsonga and Setswana, the model achieves better performance than
the other languages. Xitsonga and Setswana are both agglutinative, but have
much more data, so their models achieve higher performance than Northern Sotho
or isiZulu. The models for isiZulu achieved the worst performance. We
attribute the bad performance to the morphological complexity of the language
(discussed in Section 2), the size of the dataset and poor quality of the
data.

Table 3: English to isiZulu Translations: We show the reference translation, translation by the Transformer model, and translation back to English performed by an isiZulu speaker. Source |  Note that the funds will be held against the Vote of the Provincial Treasury pending disbursement to the SMME Fund .
---|---
Target |  Lemali izohlala emnyangweni wezimali .
Transformer |  Qaphela ukuthi izimali zizobanjwa kweVME esifundazweni saseTreasury zezifo ezithunyelwa ku-MSE .
Back Translation |  Be aware that the money will be held by VME with facilities of Treasury with diseases sent to MSE .
Table 4: English to Xitsonga Translations: We show the reference translation, translation by the Transformer model, and translation back to English performed by a Xitsonga speaker. Source |  we are concerned that unemployment and poverty persist despite the economic growth experienced in the past 10 years .
---|---
Target |  hi na swivilelo leswaku mpfumaleko wa mitirho na vusweti swi ya emahlweni hambileswi ku nga va na ku kula ka ikhonomi eka malembe ya 10 lawa ya hundzeke .
Transformer |  hi na swivilelo leswaku mpfumaleko wa mitirho na vusweti swi ya emahlweni hambileswi ku nga va na ku kula ka ikhonomi eka malembe ya 10 lawa ya hundzeke .
Back Translation |  We have concerns that there is still lack of jobs and poverty even though there has been economic growth in the past 10 years.

(a) Visualization of multi-head attention for Layer 1 for the word “cannot”.
The coloured bars are individual attention heads. The word “cannot” is
translated to “kan nie … nie” where the second negative “nie” occurs at the
end of the sentence.

(b) Visualization of multi-head attention for Layer 2 for the word “a”. The
coloured bars are individual attention heads. The word “a” is translated to
“’n”, as is successfully captured by the attention mechanism.

Figure 1: Visualizations of multi-head attention for an English sentence
translated to Afrikaans using the Transformer model.

##  7 Conclusion and Future Work

By publishing the code, datasets and baseline results on a discoverable
platform, for machine translation of the above languages and evaluating them
on a publicly-available evaluation set, we begin to address the problems of
discoverability, reproducibility, and comparability in the research of machine
translation of African languages. Future work will include results for other
Southern African languages so we can provide baselines for all official
languages in South Africa, by using unsupervised and transfer-learning NMT
techniques.

## Acknowledgements

The authors would like to thank Mbongiseni Ncube, Reinhard Cromhout, and
Vongani Maluleke for assisting us with the back-translations. Research
supported with Cloud TPUs from Google’s TensorFlow Research Cloud (TFRC).
33footnotetext:  This work is licensed under a Creative Commons Attribution
4.0 International Licence. Licence details:
http://creativecommons.org/licenses/by/4.0/.

## References

  * [Abbott and Martinus, 2018]  Jade Z Abbott and Laura Martinus.  2018\.  Towards neural machine translation for African languages.  arXiv preprint arXiv:1811.05467.
  * [Bill, 1984]  Mary C. Bill.  1984\.  100 years of Tsonga publications, 1883–1983.  African Studies, 43(2):67–81.
  * [Chahuneau et al., 2013]  Victor Chahuneau, Eva Schlinger, Noah A Smith, and Chris Dyer.  2013\.  Translating into morphologically rich languages with synthetic phrases.  In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1677–1687.
  * [Eberhard et al., 2019]  David M Eberhard, Gary F. Simons, and Charles D. Fennig.  2019\.  Ethnologue: Languages of the worlds. twenty-second edition.
  * [Gehring et al., 2017]  Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N Dauphin.  2017\.  Convolutional sequence to sequence learning.  arXiv preprint arXiv:1705.03122.
  * [Groenewald and Fourie, 2009]  Hendrik J Groenewald and Wildrich Fourie.  2009\.  Introducing the Autshumato integrated translation environment.  In Proceedings of the 13th Annual Conference of the EAMT, Barcelona, May, pages 190–196. Citeseer.
  * [Keet and Khumalo, 2017]  C Maria Keet and Langa Khumalo.  2017\.  Grammar rules for the isizulu complex verb.  Southern African Linguistics and Applied Language Studies, 35(2):183–200.
  * [Martinus and Abbott, 2019]  Laura Martinus and Jade Z. Abbott.  2019\.  A Focus on Neural Machine Translation for African Languages.  arXiv e-prints, page arXiv:1906.05685, Jun.
  * [McKellar, 2014]  Cindy A. McKellar.  2014\.  An English to Xitsonga statistical machine translation system for the government domain.  In Proceedings of the 2014 PRASA, RobMech and AfLaT International Joint Symposium, pages 229–233.
  * [McKellar, 2017]  Cindy Arlene McKellar.  2017\.  Autshumato machine translation evaluation set.  CTexT.
  * [Mesthrie and Rajend, 2002]  Rajend Mesthrie and Mesthrie Rajend.  2002\.  Language in South Africa.  Cambridge University Press.
  * [Roberge, 2002]  Paul T Roberge.  2002\.  Afrikaans: considering origins.  Language in South Africa, pages 79–103.
  * [van Niekerk, 2014]  Daniel R van Niekerk.  2014\.  Exploring unsupervised word segmentation for machine translation in the South African context.  In Proceedings of the 2014 PRASA, RobMech and AfLaT International Joint Symposium, pages 202–206.
  * [Vaswani et al., 2017]  Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  2017\.  Attention is all you need.  In Advances in Neural Information Processing Systems, pages 5998–6008.
  * [Wilken et al., 2012]  Ilana Wilken, Marissa Griesel, and Cindy McKellar.  2012\.  Developing and improving a statistical machine translation system for English to Setswana: a linguistically-motivated approach.  In Twenty-Third Annual Symposium of the Pattern Recognition Association of South Africa, page 114.
  * [Zerbian, 2007]  Sabine Zerbian.  2007\.  A first approach to information structuring in Xitsonga/Xichangana.  Research in African Languages and Linguistics, 7(2005-2006):1–22.