\section{Introduction}
\label{sec:intro}

Quantum engineering applies traditional principles of engineering such as design and control to quantum phenomena, devices and systems. In particular, quantum state engineering (the application of control methods to quantum state preparation problems~\cite{d2021introduction, wiseman2009quantum}), or QSE,  is of interest for quantum computing \cite{ramakrishna1996relation, ball2021software}, networking \cite{duan2001long, muller2013room}, and sensing \cite{rembold2020introduction, poggiali2018optimal} applications.
In general, one can separate QSE into three classes: preparation \cite{domokos1994role,milburn1986dissipative, danageozian2022noisy}, stabilization \cite{rossi2018measurement,   viola1999dynamical} and purification \cite{ticozzi2014quantum, nielsen2010quantum} of quantum states.
Primarily, QSE strategies to prepare a target state in a high-dimensional Hilbert space make use of two techniques, and combinations thereof.
The first is based on unitary time evolution with respect to some known control Hamiltonian(s). This evolution is deterministic and known as coherent control, or unitary control \cite{wiseman2009quantum,sorensenthesis}.
The second technique uses measurement back-action to steer the quantum state stochastically and is known as incoherent control, or control-free \cite{hacohen2018incoherent,sorensenthesis}.

Two examples employing both methods in their QSE strategies are FUMES (fixed unitary evolution and measurements)~\cite{pedersen2014many} and Zeno-locked FUMES (Z-FUMES) ~\cite{sorensen2018quantum}.  The FUMES strategy is based on unitarily evolving a state with respect to a known Hamiltonian up to a point where the fidelity between the state in hand and the target state is maximized, $\mathcal{F(\psi,\psi_{\text{targ}}})=\bra{\psi}\ket{\psi_{\text{targ}}}$, then making a probabilistic projective measurement \cite{pedersen2014many}.
The Z-FUMES strategy implements the same search algorithm, but makes use of the quantum Zeno effect \cite{misra1977zeno, ghirardi1979small, itano1990quantum,Nodurft:22}, to ``lock'', i.e. halt the evolution of, certain subspaces of the system to gradually shrink the total search space \cite{facchi2002quantum, facchi2004unification, facchi2008quantum}.
Example applications of measurement back-action methods include the control of qubits for quantum computing \cite{franson2004quantum, paz2012zeno, dominy2013analysis, hacohen2018incoherent}, in control of quantum optical systems \cite{lee2002linear, Nodurft:22}, and in control of critical behaviour of quantum gases \cite{elliott2016quantum, fuji2020measurement, ivanov2020feedback}.

Recently, parallels between control problems and games have emerged as demonstrated by the application of AlphaZero~\cite{silver2016mastering}, which was initially developed for playing games like Go and chess, to the optimal control of inverted pendulums~\cite{moerland2018a0c}.
Furthermore, both control problems and games are concerned with selecting actions while interacting with some environment to change the system's state; typically based on some rules and signals from the environment \cite{bertsekas2019reinforcement}.  A substantial amount of interest has been focused on using games in quantum information science not only as a pedagogical tool to develop intuition, but also as a legitimate way to solve problems. For example, a quantum version of sudoku, referred to as SudoQ, was found to be closely related to the topic of mutually unbiased bases \cite{paczos2021genuinely}. Many quantum analogues to  games have been studied, such as Go \cite{ranchin2016quantum}, tic-tac-toe \cite{goff2006quantum,leaw2010strategic}, chess \cite{akl2010importance}, blackjack \cite{mura2020quantization}, roulette \cite{wang2000quantum}, and sudoku \cite{nechita2020sudoq,paczos2021genuinely}, with various motivations. In general, a game merges with principles of quantum mechanics by associating game pieces with quantum states and defining operators that evolve the game in analogous ways to the original gameplay.

Noticeably, a missing link exists between the emerging fields of QSE and quantum games. For example, experimental implementations of quantum games and associated gameplay require extensive control of the underlying quantum systems and rely on QSE. However, as we will focus on in this paper, the reverse relationship is also meaningful: the development of QSE strategies  inspired by games.

Here, we introduce a quantum version of the traditional West African sowing game mancala, which we refer to as ManQala, and explore its applicability as a framework for state engineering.
We present QSE strategies inspired by the game that match or surpass the performance of traditional unitary or measurement-based strategies. In particular, the advantages persist even when considering small systems and two-site interactions where one could expect the slightest advantage. Importantly, ManQala-inspired strategies show promise at scaling to higher dimensions better than (Z-)FUMES due to small search spaces and the parallelizability associated with their divide-and-conquer approach.
Hence, the strategies presented in this paper represent a potential path toward developing game-based QSE techniques with improved scaling properties compared to leading alternatives.

This paper is organized as follows.  In Section \ref{sec:engineering}, we provide an overview of the ManQala game and relate it to the basic goals of QSE. From these results, we present useful methods for developing game-inspired strategies for QSE and compare and contrast these to the strategies outlined by FUMES and Z-FUMES.
In Section \ref{sec:two_site}, we provide numerical simulations of ManQala, FUMES, and Z-FUMES algorithms for the scenario where the former has the least advantage against the latter. However, clear advantages for ManQala are demonstrated with respect to parallelization and variance.
Finally, Section \ref{sec:conclusion} concludes the paper.

\section{ManQala Quantum State Engineering Strategy}
\label{sec:engineering}
\subsection{Overview}

Mancala is the generic name for a collection of related games played worldwide for over a thousand years. Mancala games consist of pieces called stones (or seeds) and a game board that includes a set of valid locations, referred to as pits, for game piece placement. Additionally, mancala game boards have a special pit, or pits, called the Ruma.  Various rule sets exist, but mancala is generally a turn-based game where players alternate moving, or ``sowing," stones in counter-clockwise or leftward direction from pit-to-pit in a series of chained operations to collect the stones in a Ruma.

This Section develops techniques to play quantum mancala, or ManQala, that can be applied to any variation of the traditional game, including multiplayer iterations. However, we have found that even the most basic solitaire versions of mancala have a rich enough game structure to reveal significant and uniquely quantum features of ManQala. For this reason, throughout the rest of this paper, we will focus on Tchoukaillon, a solitaire version of mancala which is particularly amenable to mathematical analysis.

\begin{figure}
    \centering
    \includegraphics[width=\linewidth]{fig1v4.drawio.pdf}
\caption{\textbf{Example game boards for (a) Tchoukaillon (a solitaire variant of mancala) and its direct quantum analogue ManQala in (b).} Here, we show both boards with $N=3$ stones and $M=3$ lattice sites, and we represent sowing with arrows (which become two-site unitary operators in ManQala). The sequential unitary actions $U_1$ and $U_2$ in the Figure represent the deterministic quantum analogue of the first two Tchoukaillon moves via site-population permutations. The final step of the Tchoukaillon game has no deterministic unitary realization in the quantum version of the game. Hence, $U_3$ drives the state where the probability of observing the winning board is maximized. Upon observation (projective measurement), the target state is achieved with a probability of $6/9$ (where an additional unitary may be required), or the board reverts to the configuration before $U_3$, and the final step is repeated until successful.}
    \label{fig:board}
\end{figure}

Tchoukaillon was developed by Deledicq et al. \cite{deledicq1977wari} in 1977 and is itself a derivative of another, much older mancala variant called Tchouka \cite{sainte1929geometrie}. Game boards in Tchoukaillon are linear and consist of only a single Ruma, which we assume is the left-most pit by convention.   The sowing rules state that when a  player picks $N$ stones up from a pit, they leave that pit empty to sow all those stones to the pit on the left-hand side. Then, they proceed by picking up $N-1$ stones from that pit and sowing them to the next pit on the left, and so on until there are no stones remaining in their hands. In Tchoukaillon,  a player must end each round of sowing by placing the final stone in the Ruma, with under- and over-shooting resulting in losing the game. The win conditions for Tchoukaillon are, in fact, so restrictive that the initial game board ultimately determines whether a win is possible and, if so, prescribes the unique series of moves needed to win \cite{broline1995combinatorics, jones2013solitaire}.

Assuming we begin with a Tchoukaillon board for which winning is possible, then the series of moves that will result in winning can be described succinctly. In particular, the stones from the pits nearest to the Ruma (empty pit at the edge) need to be picked and sowed first, with this strategy repeated, moving to the next non-empty pit until the game board is cleared.
In Figure \ref{fig:board}(a), we visually present an example of this strategy for a winning board with a Ruma and two additional pits.

The game play in Figure \ref{fig:board}(a) consists of two movements; the first is equivalent to a permutation, such as in the first step when sowing into an empty pit, and the second is the merging movements that combine seeds from two pits. This distinction is significant as we consider a quantum version of the game since permutation can be performed deterministically with unitary evolution, while merging operations are nondeterministic. Notably, permutation movements alone bring the board ``closer" to the final configuration. This observation that deterministic permutation operations can significantly reduce the number of tunneling events needed to achieve the target state and effectively reduce board size will be the primary strategy we will use throughout this paper as we develop ManQala. Furthermore, even as we move away from problems that have direct analogies with mancala, we will see that pre-processing in this fashion reduces the problem space making the application of search-based quantum control approaches (e.g., Z-FUMES) more efficient.

In this paper, we aim to devise a family of QSE strategies, termed ManQala, that mimic the mechanics of a traditional Tchoukaillon game.
For context, in Figure~\ref{fig:board}(b) we include a simple example of the same game shown in Figure~\ref{fig:board}(a) but where ``stones'' are replaced with bosonic states and ``pits'' by system modes. This now constitutes a quantum system where we can apply ManQala. In this simple ManQala example, ``sowing'' is performed with unitary operations $U_i$, for $i = 1, 2, 3$.
Even in this basic example, with only three modes and three bosons, the gameplay diverges from mancala in two important ways.
First, since the quantum version manipulates amplitudes of quantum systems and avoids ``collapse,'' the game does not result in a ``winning'' configuration with certainty.  Secondly, the coherent evolution of the system potentially violates the directionality rules implied by all mancala games: there are projective measurement outcomes where ``stones'' move ``backwards'' in this quantum version. This phenomenon appears in certain outcomes shown in the last step of Figure~\ref{fig:board}(b).

Similar to other state engineering strategies, such as FUMES \cite{pedersen2014many} and the Zeno-locked FUMES (Z-FUMES) \cite{sorensen2018quantum}, ManQala uses two different methods to direct the evolution of a state: coherent unitary evolution and projective measurements.
Unlike FUMES and Z-FUMES, ManQala starts by driving the system deterministically to a point where random search via projective measurements is more feasible. Once the deterministic strategy is complete, a stochastic approach, such as (Z-)FUMES, is adopted on one or more subsets of the board while the rest remains Zeno-locked.
Additionally, ManQala can also be implemented in a parallel fashion where a given lattice can be fragmented into sublattices, each of which is evolved independently.

As stated, the goal in ManQala is similar to Tchoukaillon or any other mancala variant; to end the game with all of the seeds in the Ruma. Thus, our aim in ManQala is to engineer a quantum state such that final state of the board mimics the end of a mancala game.
While this goal appears restrictive, in the Appendix, we describe an approach for leveraging ManQala for quantum control problems with completely general target states.

\subsection{Formulation for systems with two-site bosonic hopping}

We now discuss the realization of ManQala-inspired QSE methods for controlling physical systems that exhibit two-site bosonic hopping due to their prevalence in practical situations.
Bosonic hopping occurs in a variety of physical systems, including coupled optical cavities~\cite{nohama2007quantum}, coupled waveguides~\cite{ ogden2008dynamics}, transmons coupled to superconducting cavities~\cite{ma2021quantum}, and ultracold atoms in optical lattices  that obey the Bose-Hubbard (B-H) model~\cite{gersch1963quantum}.
Implementation of the last two systems enable non-demolition measurement \cite{unruh1978analysis, braginsky1980quantum, belavkin1992nondemolition} of bosonic populations \cite{mekhov2009quantum, ma2021quantum,rogers2014characterization}. However, we restrict our states of interest to bosons on a lattice that evolve according to the one dimensional B-H model due to its simplicity in measurement \cite{rogers2014characterization}, and intuitive similarity to a traditional mancala game.

Here, each lattice site that carries bosonic modes is analogous to a pit on a mancala board such that the quantum analogue of the sowing operation can be implemented by boson hopping.
Therefore, the B-H Hamiltonian governing this scenario is given by,
\begin{gather}
    \hat{H}=-J\sum_{\langle i,j \rangle}{\hat{a}_i^\dagger\hat{a}_j}+\frac{V}{2}\sum_{i}\hat{n}_i(\hat{n}_i-1)-\mu\sum_i{\hat{n}_i}.
\end{gather}
Here, $\hat{a}_i^\dagger$ and $\hat{a}_i$ are bosonic creation and annihilation operators such that $\hat{n}_i=\hat{a}_i^\dagger\hat{a}_i$ gives the number of particles on site $i$ and $\langle i,j \rangle$ denotes summation over all neighboring sites $i,j$. The hopping amplitude $J$ describes the coupling strength between neighboring sites and the parameters $V$ and $\mu$ represent the on-site interaction and the chemical potential, respectively.

By following the lead of S{\o}rensen et al.~\cite{sorensen2018quantum}, we restrict our method to quantum systems described solely by the quadratic hopping part of the B-H Hamiltonian as the self-interaction potential and the chemical potential are set to $V=0$ and $\mu=0$. Our motivation in doing so is two-folds. First, removing the terms that prevent tunneling aids the search for the target state, similar to using high temperature parameters in initial stages of simulated annealing algorithms \cite{aarts2005simulated}. Second, the quadratic B-H model is exactly diagonalizable in the Heisenberg picture resulting in closed-form, analytic solutions for unitary evolution once those terms are omitted \cite{rai2008transport, ogden2008dynamics}.

In general, the engineering of a quantum state is an optimization problem where the controller interacts with the given system via time-dependent actuation, $\vb{\alpha}=\left(\vb{\alpha}_0,\dots,\vb{\alpha}_t,\dots ,\vb{\alpha}_T\right)$, for times $t \in [0,T]$.
Hence, the goal of ManQala is to specify $\alpha$ at all times using strategies derived from the game as shortcuts to optimization.
In ManQala, the control actions at any given time $t$ are constrained to a set of unitaries and projective measurements, $\vb{\alpha}_t=\left(\vb{U}_t,\vb{P}_t\right)$. Here, a control action of pure coherent evolution, $\vb{\alpha}_{t_{ini}}=\left(\vb{U}_{t_{ini}},\vb{P}_{t_{ini}}=I\right)$,  implements the time evolution operator $\vb{U}_{t_{ini}}=\exp\left(-iH(t_{f}-t_{ini})\right)$ of the total Hamiltonian that drives the state from the initial time, $\ket{\psi(t_{ini})}$, to the final, $\ket{\psi(t_{f})}$, segment as the measurement projection operator is just the identity $I$. Similarly, an action of pure projective number state measurements $\vb{\alpha}_t=\left(\vb{U}_t=I,\vb{P}_t=\bigotimes_{j=0}^{M-1} P^{(j)}\right)$ has the effect of probabilistically collapsing the state. Here $\bigotimes_{j=0}^{M-1} P^{(j)}$ denotes the tensor product of the projective measurement operators at each site $j$, ranging from $0$ to $M-1$. And, combining those, the action $\vb{\alpha}_{t_{ini}}=\left(\vb{U}_{t_{ini}}=I,\vb{P}_{t_{ini}}= \bigotimes_{j\neq m} P^{(j)}\right)$ exerts coherent time evolution on all the sites except the sites at $j=m$ (for $m\in [0, M-1]$), unless those obscure inter-site tunneling, via Zeno-locked time-evolution, $U_{ZL}(t_{ini})=\vb{P}_{t_{ini}}\exp\left(-i\vb{P}_{t_{ini}}H\vb{P}_{t_{ini}}(t_{f}-t_{ini})\right)$ \cite{facchi2002quantum, facchi2008quantum,sorensen2018quantum}.

If, for the given Bose-Hubbard model, the task in hand is steering an initial state, $\ket{\psi_0}$, towards a target state, $\ket{\psi_{\text{targ}}}$, then the control problem can be formulated as a combinatorial optimization problem of finding the actions $\vb{\alpha}$ that would minimize a distance metric between states, $\alpha^{\star}=\underset{\vb{\alpha}}{\arg\min}\; d(\psi_0,\psi_{\text{targ}};\vb{\alpha})$ \cite{korte2011combinatorial}. Here this distance metric, $d$, to be minimized could be coming from Schr\"{o}dinger, as in the quantum fidelity $\mathcal{F}(\psi_1,\psi_2)=\bra{\psi_1}\ket{\psi_2}$, or Heisenberg picture dynamics for a series of actions or actuators implemented in time, $\vb{\alpha}$. Also, this metric can be combined with other goal functions within a cost function to be minimized, $\mathcal{L}=\sum_j \lambda_j d_j$. Here $\lambda_j$ denotes a Lagrange multiplier for a metric or goal $d_j$, and these multipliers can be chosen to make the cost function a convex sum, $\sum_j \lambda_j=1$.

For our system of interest, a 1-D bosonic lattice governed by a Bose-Hubbard Hamiltonian, we can define a distance metric based on the number of tunneling events. Pedersen et al. initially proposed such a metric for Fock states to judge the performance of the FUMES algorithm \cite{pedersen2014many}. We can generalize the Pedersen metric to any site population via the following compact form. Given the M dimensional particle number expectation value vectors $\vb{n}_A=\left(\langle n_0 \rangle_{\psi_A},\dots,\langle n_{M-1} \rangle_{\psi_A}\right)$, and, $\vb{n}_B$ for states (or density matrices) $\ket{\psi_A}$ and $\ket{\psi_B}$, the number of tunneling events is given by
\begin{align}
    d_{T}\left(\vb{n}_A,\vb{n}_B\right)&=\sum_{k=0}^{M-2}\left|\left(\vb{n}_A-\vb{n}_B\right)_k+\left(\vb{n}_A-\vb{n}_B\right)_{k+1}\right|.
\end{align}

The global optimum of the number of tunneling events and the fidelity are the same when steering a system from an initial state to a target state. The same cannot be said for the intermediate steps. If we are given specific initial and target states, or their particle number expectation value vectors ($\vb{n}_0$ and $\vb{n}_\text{targ}$, respectively), we can define a bosonic distance akin to quantum (in-)fidelity for the particle number expectation value vector, $\vb{n}_A$, of a (probably unknown) state, $\ket{\psi_A}$, using the number of tunneling events given above, as the following,
\begin{align}\label{eq:bosonic_dist}
    d_B\left(\vb{n}_A,\vb{n}_{\text{targ}};\vb{n}_0\right)&=1-\frac{d_{T}(\vb{n}_A,\vb{n}_{\text{targ}})}{d_{T}(\vb{n}_0,\vb{n}_{\text{targ}})}.
    \end{align}
In this current form, the bosonic distance metric starts from zero for $\vb{n}_A=\vb{n}_0$ and takes on the maximum value of unity when $\vb{n}_A=\vb{n}_\text{targ}$ due to scaling with the number of tunneling events between the initial and target states.

ManQala initially tries to minimize a cost function
\begin{equation}\label{eq: loss}
\mathcal{L}_M=\lambda_1 \left(1-d_B\left(\vb{n}(\vb{\alpha}),\vb{n}_{\text{targ}};\vb{n}_0\right)\right)+\lambda_2 N_P(\vb{\alpha}) + \lambda_3 M_C(\vb{\alpha}).
\end{equation}
Here the term $\vb{n}(\vb{\alpha})$ denotes site populations after the actions $\alpha$ were implemented on the initial populations and $N_P(\vb{\alpha})$ denotes the number of projective measurements we apply to our system as actions.
Assuming a high $\lambda_2$, we try to avoid stochastic methods (e.g, Z-FUMES) while minimizing $d_B$, but use deterministic unitary actions (site population permutations) instead. Also, if we want to be consistent with mancala, we can penalize the actions that are inconsistent with it via a term $M_C(\vb{\alpha})$. For example, we can penalize the unitary actions that do not follow the mancala's sowing rule. On the other hand, this condition can be relaxed by tuning $\lambda_3$, or dropped altogether ($\lambda_3=0$) as a modified-ManQala (mod-ManQala) algorithm without losing any generality, while converging faster.  This is considered in appendix ~\ref{sec:examples} and can be achieved by Zeno-locking all other sites.

Of note, a target board to be reached (e.g, winning condition) can be decomposed into sub-boards where each sub-board population can be thought of as a pit. For example, for the three pit board configuration we examine here, the target board can be decomposed into sub-boards (sub-lattices) of $\{2-pits,1-pit\}$. For such segmentation of the board, the target board is demarcated into sub-board populations $\left(3,0,0\right)\rightarrow((3,0),0)\rightarrow \left(3,0\right)$. Using that, we can also split our initial board configuration in hand the same way $\left(0,1,2\right)\rightarrow ((0,1),2)\rightarrow \left(1,2\right)$. Both in the traditional and the quantum game, bringing the board into the winning condition first requires bringing it to the target sub-board ($\left(3,0\right)$ in our example). The winnable board configurations enable the player to move the stones from the pits with small number of stones right away into the target sub-board, effectively decoupling from the move of the pits with larger number of stones that could overshoot the Ruma.  In ManQala, whether or not mimicking each traditional move, this winnable board intuition is actualized by moving the particles from the sites with a few number of particles right away to their designated smaller sub-lattices deterministically only via unitary evolution so that we can Zeno-lock them. This way we can move the particles from sites with many particles to their designated, larger, target sub-lattice. Having locked the (sub)-lattices with few particles, and moved the rest to their sub-lattice, we can use probabilistic search methods via measurement back-action on this previously unlocked sublattice to find the right set of actions that would steer our system to the target state.

\begin{table}[t]
\centering
 \begin{tabular}{|p{2cm}|p{1.5cm}|p{0.6cm}|p{0.6cm}|p{1.2cm}|p{0.5cm}|}
 \hline
 Strategy & Zeno-lock & $\mathcal{F}$ & $d_B$ & Parallel & $M_C$\\ [1ex]
 \hline\hline
 ManQala & \checkmark & \checkmark &  \checkmark &  \checkmark & \checkmark \\
 \hline
 modified-ManQala &  \checkmark &  \checkmark &  \checkmark &  \checkmark & $\times$\\
 \hline
 FUMES & $\times$ &  \checkmark & $\times$ & $\times$& $\times$ \\
 \hline
 Z-FUMES &  \checkmark &  \checkmark &  $\times$ & $\times$& $\times$ \\ [1ex]
 \hline
 \end{tabular}
\caption{\textbf{Summary of strategies compared in this paper.} FUMES conducts a greedy, stochastic, non-parallelizable search based on fidelity $\mathcal{F}$ alone. Z-FUMES conducts the same search, but gradually shrinks the search-space via Zeno-lock. Both (mod-)ManQala start by minimizing bosonic distance, $d_B$, deterministically via permuting the populations of one two or three-site at a time
 to minimize stochasticity \& shrink search space and then implements Z-FUMES in parallel at various sub-lattices. Unlike ManQala, mod-ManQala does not necessarily adhere to the rules of mancala, as expressed by term $M_C$ in Eq.~\ref{eq: loss}. }
\label{table:compare}
\end{table}

To help clarify the differences between ManQala, FUMES, and Z-FUMES we include Table \ref{table:compare}.
A more detailed description of these differences in available in Appendix \ref{app:compare}.

\section{Numerical Simulations and Performance Comparisons}
\label{sec:two_site}

In the previous section, we presented the theoretical framework for a game-inspired quantum state engineering (QSE) strategy we call ManQala.
Here, we provide numerical simulations of the performance of ManQala and compare them against FUMES and Z-FUMES.
For clarity, we will consider in this section the same problem illustrated in Figure \ref{fig:board}(b).
Here, the initial state is given by $\ket{\psi}_0=\ket{0,1,2}_{\text{Fock}}$ and the target state by $\ket{\psi}_t=\ket{3,0,0}_{\text{Fock}}$ where each ket represents, for example, modes in a bosonic lattice.
 The Hilbert space dimension is $R=\binom{N+M-1}{N}=10$ for $M= 3$ sites and $N=3$ particles.  Thus, in this configuration, there are $R=10$ possible Fock states.

Assuming prior knowledge of the total number of particles $N$ in the system, we can deduce the state of the entire lattice by measuring only $M-1$ of the sites.
Hence, for the problem we consider here with $N=M=3$, we can represent the state of the system as a sequence of two numbers, in this case, the number of particles in the leftmost site (Ruma) and the next nearest site.  We denote all ten possible configurations as
$\vb{L}=[\vb{l}^{(0)}\mathbin{,}\dots\mathbin{,}\vb{l}^{(9)}]=[(0\mathbin{,}1)\mathbin{,}(0\mathbin{,}0)\mathbin{,}(0\mathbin{,}2)\mathbin{,}(1\mathbin{,}0)\mathbin{,}(1\mathbin{,}2)\mathbin{,}(2\mathbin{,}1)\mathbin{,}(1\mathbin{,}1)\mathbin{,}(0\mathbin{,}3)\mathbin{,}(2\mathbin{,}0)\mathbin{,}(3\mathbin{,}0)]_{\text{Fock}}$.
In the particular example shown in Figure \ref{fig:board}(b), $\vb{l}^{(0)}$ and $\vb{l}^{(9)}$ are the initial and target states respectively.

The FUMES protocol uses unitary evolution to maximize the fidelity with the final state followed by a single projective measurement.
To find these unitary evolutions, we first identify the distance between all possible states $\vb{L}$ and the target state. For each state in $\vb{L}$, there is a corresponding unitary time-evolution duration that maximizes the probability of observing the target state and can be also written in a vector form.
We write these times again in a vector of the form $\vb{T}=\left[t_{\text{desig}}^{(0)},\dots,t_{\text{desig}}^{(9)}\right]$.
For the target state $\vb{l}^{(9)}$ we obtain these values using QuTiP ~\cite{johansson2012qutip} by numerically solving Schr\"{o}dinger's equation via exact diagonalization. The resulting time scales are given by $\vb{T}=[1.66\mathbin{,}2.22\mathbin{,}1.33\mathbin{,}1.33\mathbin{,}0.89\mathbin{,}0.555\mathbin{,}1.11\mathbin{,}0.11\mathbin{,}0.89\mathbin{,}0]$.

If we instead consider situations where we Zeno-lock certain sites, such as in Z-FUMES, the optimal time-evolution values change.  Zeno-locking only occurs in this example when the $j=2$ site has the targeted number of particles (in this case zero particles) in it, $\ket{\cdot, \cdot, 0}$, and not the others, $\ket{\cdot, 0, \cdot}$ and $\ket{0,\cdot,\cdot}$. Locking the $j=0$ (Ruma) site when it has zero particles would be counterproductive as the target state has nonzero particles in that site. However, one may be tempted to lock the intermediate site ($j=1$) when it has the target number of particles (zero), but this would obstruct the tunneling between the sites $j=0$ and $j=2$.
Zeno-locking the site $j=2$ when it has zero particles in it reduces the set of possible configurations $\vb{L}$ to the subset $\vb{L}_Z=[(1\mathbin{,}2)\mathbin{,}(2\mathbin{,}1)\mathbin{,}(0\mathbin{,}3)\mathbin{,}(3\mathbin{,}0)]_{\text{Fock}}$.
 Designated time durations become the following for this case, $\vb{T}_Z=[0.953\mathbin{,}0.615\mathbin{,}1.567\mathbin{,}0]$, where the designated time duration vector for the states to be evolved while Zeno-locking is replaced with the ones from the usual FUMES while keeping the rest same.

 Hilbert space reduction using Zeno-locking, as shown in the difference in the dimensionality between $\vb{T}$ and $\vb{T}_{Z}$, is precisely why Z-FUMES outperforms FUMES in general.
 Note, however, that Z-FUMES only applies Zeno locking in a stochastic fashion.
For example, if Z-FUMES encounters a $0$ on the second site and Zeno-locks it so that the two-site sublattice to the left has the correct amount of particles, the search space reduces to $R=\binom{N+M-1}{N}=4$ for ($N=3, M=2$).
In comparison, ManQala and its variants drive the system deterministically exactly to this configuration instead of waiting to encounter it during the random search.
Finally, we note that since FUMES does not use Zeno-locking at all the algorithm searches the entire $R=10$ dimensional space. Hence, intuitively, we expect both ManQala and Z-FUMES to outperform FUMES in terms of resources required to reach the target state.

To reach the target state using ManQala, that is limiting the ability to permute to two-sites at a time while adhering to the sowing rules of mancala, we begin by driving our system to the $\vb{L}_{Z}$ subspace and Zeno-locking the $j=2$ mode. To achieve this we use three two-site unitaries of $\Delta t=\pi/2$. Here each unitary permutes the particle population of adjacent Fock states of sites $j$ and $j+1$ carrying $N$ particles, $U(\pi/2)\ket{k, N-k} = \exp\left(-i(a_ja_{j+1} + \text{H.C})\pi/2\right)\ket{k,N-k}= \ket{N-k,k}$. In the case given in Figure \ref{fig:board}, we need a total deterministic evolution time of $\Delta t = 3\pi/2$ to drive the system into the Zeno-locked configuration of $\ket{2,1,0}$. Once there we apply the aforementioned Z-FUMES with time durations $T_Z$.

Alternatively, if we instead use mod-ManQala, we require only one three-site unitary of duration $\Delta t = \sqrt{2}\pi/2$ to deterministically reach the Zeno-locked configuration due to relaxing the need to imitate mancala. Here each unitary acting on Fock states of sites $j, j+1, j+2$ permutes the populations of sites $j$ and $j+2$, while leaving $j+1$ untouched. The three-site unitary  given by $U(\sqrt{2}\pi/2) = \exp\left(-i\sqrt{2}(a_ja_{j+1} + a_{j+1}a_{j+2} + \text{H.C})\pi/2\right)$ implements the permutation $U(\sqrt{2}\pi/2)\ket{k,l,N-l-k}= \ket{N-l-k,l,k}$.  To be more specific, consider a demarcation of the three-dimensional lattice in sub-lattices $\left\{2-site, 1-site\right\}$, i.e, $ \vb{\tilde{S}}^{\star}=\left[s_1,s_2\right]=\left[(0,1),2\right]$.
The initial site population for this $\vb{\tilde{S}}^{\star}$ sub-lattice segmentation is $\vb{n}_0=\left((0,1),2\right)=\left(1,2\right)$.
ManQala tries to be as consistent as possible with the winning strategy of the analogous classical Tchoukaillon board and hence drives the system into $\vb{n}_M^{\star} = \left((2,1),0\right) = \left(3,0\right)
$ populations with respect to segmentation $\vb{\tilde{S}}$ and corresponding permutation $\tilde{\pi}$. The permutation to drive the initial populations into the Zeno-locked sub-lattice $\left(3,0\right)$ is the following:
\begin{equation}
\tilde{\pi}_M^{\star}=\begin{pmatrix}
0 & 1  & 2  \\
2 & 1  & 0
\end{pmatrix}
\end{equation}

Here $\tilde{\pi}_{M^{\star}}$ denote the site population permutations for both the ManQala and mod-ManQala strategies, i.e, exchanging sites $0$ and $2$ while keeping site $1$ the same.
Its corresponding matrix representations $\tilde{P}_{\tilde{\pi}_{M^{\star}}}$ is a column-reversed identity matrix.
In the segmentation $\vb{\tilde{S}}^{\star}$, both of these representations yield $\eta=\left(\tilde{P}_{\tilde{\pi}}\vb{n}_0-\vb{n}_{\text{targ}}\right)=\left(0,0\right)$.
In practice, we first identify these permutation operators and then compile them into two and three-site unitaries (i.e, ``moves" in the previous section) based on the traditional game constraints or lack thereof.

\begin{figure}[t]
\centering
\includegraphics[width=\linewidth]{dBcompare.pdf}
 \caption{\textbf{Numerical simulation of game-inspired quantum state engineering}.
 Given the initial state $\ket{0,1,2}$, the average (expected) bosonic distance of observing the target state $\ket{3,0,0}$ for different quantum state engineering strategies computed using $1000$ stochastic trajectories each in QuTiP. (a) For each stochastic trajectory the non-deterministic part of a given strategy is repeated until convergence. The dashed lines mark when each strategy achieves $0.99$ bosonic distance, $d_B$ (defined in the text). (b) Non-deterministic part is only repeated twice for each stochastic trajectory. Red (FUMES), green (Z-FUMES), blue (ManQala), and purple (mod-ManQala) curves denote the average $d_B$ of a given strategy over $1000$ trajectories, while the shaded areas are the respective standard deviations. Note that a projective measurement does not occur until the emergence of a shaded area (coloring) corresponding to a standard deviation.}
 \label{fig:compare1}
\end{figure}

Figure~\ref{fig:compare1} shows the comparison of expected bosonic distance between different quantum state engineering strategies for initial state $\ket{\psi_0}=\ket{0,1,2}$ and target state $\ket{\psi_{\text{targ}}}=\ket{3,0,0}$ over a thousand stochastic, Monte-Carlo trajectories. In terms of the bosonic distance, FUMES, Z-FUMES, and mod-ManQala start with a steep linear ramp as they all implement a three-site interaction. When the fidelity between the state in hand and the target state is maximized at $J t_{\text{desig}}^{(0)} = 1.66$ both (Z-)FUMES apply a projective measurement, leading to different stochastic trajectories (green and red coloring in the Figure \ref{fig:compare1} representing the standard deviation of these). Both (mod-)ManQala aim to achieve $\ket{2,1,0}$ deterministically, and their bosonic distances ascend during the course of their time-evolution, albeit slowly for ManQala due to constraints. Once ManQala achieves a local peak at $Jt=3\pi/2$ and mod-ManQala achieves the same at $Jt=\sqrt{2}\pi/2$, they make a downward turn as they are both optimizing for fidelity now (using Z-FUMES) by both evolving for $Jt_{\text{desig}}^{Z}=0.615$ in the Zeno-locked space (i.e, the second element of $\vb{T}_Z$), and make projective measurements at those spots (leading to blue and purple coloring for their respective variances).

In this Zeno-locked space mod-ManQala follows the designated measurement times $\vb{T}_Z$ based on measurement results, while ManQala, following the rules of the traditional game, always brings the system back to the $\ket{2,1,0}$ and repeats. Because of this, the mean (expected) trajectory progresses differently in time for ManQala, and mod-ManQala converges to a $d_B = 0.99$ much faster ($Jt \sim 5.1$), although they achieve the same exact statistics given in part $b)$ of Figure \ref{fig:compare1}.
Since we are driving the system into Zeno-locked subspaces determinisitically, and querying a smaller search space (mod)-ManQala has much less variance. In Figure~\ref{fig:compare1}(a) each protocol is repeated indefinitely until achieving a unity fidelity such that FUMES has an average standard deviation of $0.21$, while Z-FUMES has $0.17$, mod-ManQala has $0.06$, and ManQala has $0.06$ in bosonic distance until observing $0.99$ bosonic distance. This phenomenon is much more pronounced in  Figure~\ref{fig:compare1}(b)
as just a small number of protocol repetitions is enough to achieve near unity fidelities with the target state.
For completeness, we provide results related to the repeated application of all three protocols in Appendix \ref{app:rep}.

\begin{figure}[t]
    \centering
    \includegraphics[width=\linewidth]{particlenumber.pdf}
    \caption{\textbf{Time evolutions of the expected number of particles for three selected stochastic trajectories:  (a) FUMES, (b) Z-FUMES and (c) mod-ManQala}. The horizontal axis shows the site number and the color corresponds to the expected particle number. The dashed lines represent the times a projective measurement occurs. Note in (a) and (b), the time between the first and second projective measurements is where the Heisenberg picture dynamics halt (Mott-insulator state). In (c) there is only one probabilistic event (measurement). This Figure represents a single (randomly chosen but representative) stochastic instance for each strategy out of many possibilities.}
    \label{fig:compare2}
\end{figure}

To further illustrate the difference between these quantum-state engineering strategies, we compare the expected particle numbers at each site with the same aforementioned initial and target states, as shown in Figure ~\ref{fig:compare2}. This figure shows individual (randomly chosen but representative) evolutions for FUMES, Z-FUMES and mod-ManQala as compared to Figure \ref{fig:compare1} which averages many such evolutions to find averages. While not as useful to understanding the general behavior of each protocol, Figure \ref{fig:compare2} provides an intuitive understanding of how (Z-)FUMES and mod-MaQala strategies differ in their overall approach to solving the same problem. Note that the dashed lines in Figure \ref{fig:compare2} indicate projective measurements. (Z-)FUMES implements a measurement each time the probability of observing the target state is maximized in a given (Zeno-locked) configuration. Alternatively (mod-)ManQala strategies evolve the sites deterministically towards states where Zeno-locking can be used to reduce the Hilbert space (in this case making the population in the $j=2$ mode $0$).
As pictured in Figure \ref{fig:compare2}, this particular stochastic run is successful at projecting to the correct state in panel (c) on the first projection, however, if this were not the case mod-ManQala would again try to maximize fidelity before repeating the projective measurement. Note that (Z-)FUMES evolves the states in time for the next projective measurement even when the particle expectation numbers, as well as the bosonic distance we defined $d_B$, are frozen in time. In parts a) and b) of Figure \ref{fig:compare2}, the first measurement represented by a dashed line projects the system into a Mott-Insulator state $\ket{1,1,1}$, where particle expectations are not changing in time under the effect of unitary evolution. The second projective measurement, represented by a second dashed line, takes them out of this state.

In this section, we have considered scenarios where the target state mimics the end state of the original solitaire mancala game, meaning all bosons end up in a single mode. However, we note that ManQala can be applied more generally to problems with arbitrary target states. These general approaches require us to loosen our adherence to  mancala (game rules, directions). For concreteness, in Appendix \ref{sec:examples} we describe how ManQala can be applied to two important physical systems, those of superfluids and Mott-insulator systems with site and particle numbers of five.
In particular, we show in Appendix \ref{sec:examples} how the ManQala framework can divide more significant, hard-to-tackle problems into small, manageable, and parallelizable ones.

\section{Conclusion}
\label{sec:conclusion}
In this paper, we devised a quantum engineering strategy that we term ManQala, inspired by the traditional solitaire game Tchoukaillon and illustrated the differences between our approach and other competing strategies. In particular, we provided numerical comparisons of ManQala and ManQala-inspired strategies against FUMES and Z-FUMES.
In all cases we found that ManQala strategies ultimately match or outperform FUMES and Z-FUMES.

ManQala augments existing quantum state engineering strategies by adding a preprocessing stage that consists of deterministic unitary permutations. These permutations reduce the Hilbert space of the problem, improving the performance of search-based strategies such as FUMES and Z-FUMES. More specifically, FUMES is a greedy, stochastic algorithm that optimizes the fidelity between the initial and target state through unitary evolution of the whole Hamiltonian followed by the collapse of the state by observation. On the other hand, Z-FUMES uses the same stochastic and greedy algorithm as FUMES but with the additional feature that if we end up in subspaces of the target state during probabilistic jumps, we can Zeno-lock these subspaces and only evolve the remaining sites. By contrast, ManQala-based strategies intentionally drive the system into target subspaces/sublattices of the overall state through deterministic unitary evolution into configurations that allow for an overall reduction in Hilbert space size through the Zeno-locking of certain modes. Then, once demarcated, ManQala strategies use local algorithms to control each subspace/sublattice to minimize the bosonic hopping distance. ManQala's use of subspaces and sublattices naturally lends itself to parallelization, which would further improve the performance of ManQala over existing strategies as problem spaces increase in dimension.

In our formulation of ManQala, we have chosen to use the bosonic hopping distance to inform the algorithm's actions instead of overall fidelity. Since ManQala focuses on sublattices, within the execution of the protocol, the overall fidelity may decrease before rapid improvement. This decrease in fidelity is due to the algorithm focusing on bosonic distances between sublattices at any individual step and not the global fidelity. Ultimately our quantum version of a mancala game has provided a helpful framework for thinking about state engineering in quantum systems. The observed performance advantages of ManQala over competing strategies suggest an exciting connection between  games and quantum systems engineering, and future work should continue exploring this relationship.

\begin{acknowledgments}
We acknowledge the primary support of this work from the IBM-HBCU Quantum Center at Howard University.  Additionally, the views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. Additionally, this material is based upon work supported by, or in part by, the Army Research Laboratory and the Army Research Office under contract/grant numbers W911NF-19-2-0087 and W911NF-20-2-0168.  TAS's contribution is based upon work supported by the U.S. Department of Energy, Office of Science, National Quantum Information Science Research Centers, Co-design Center for Quantum Advantage (C2QA) under contract number DE-SC0012704.
\end{acknowledgments}


\section{Transformer Architectures for Long Texts}
\label{section4}

Considering the quadratic complexity of self-attention modules, Transformer-based PLMs do not scale well in long texts under limited computational resources. Instead of preprocessing long texts  (Section~\ref{section3}), we discuss effective architectures $\mathcal{M}$ (Equation~\ref{eq1}) for Transformer models with reduced complexity.
Previous surveys have extensively discussed various ways to improve the \textit{computation efficiency} of Transformer~\cite{tay2022efficient,LIN2022111}. Here, we mainly discuss the variants that can efficiently extend their maximum context length. Besides, we introduce pretraining objectives and strategies of Transformers designed for long texts.

\subsection{Efficient Transformers}

The main consumption of time and memory comes from the self-attention mechanism in a Transformer model. A number of models are proposed to decrease the $O(n^2)$ complexity to efficiently model longer texts.
In the rest of this section, we will discuss three major kinds of self-attention variants and how encoder-decoder attention can be improved.

\paragraph{Fixed Attention Patterns}
Based on the principle of locality of language, we can restrict attention with fixed patterns, in which each token can only attend to a few tokens according to various strategies rather than the whole sequence.
For example, the block-wise attention partitions the input text into non-overlapping blocks, and tokens can only attend to those in the same block since they are semantically similar~\cite{qiu-etal-2020-blockwise}. Similarly, local attention (\emph{a.k.a.,}\xspace sliding window attention) restricts each query token to its neighbors within a fixed-size window, which can achieve $O(n)$ complexity\footnote{In fact, the complexity of local attention is $O(wn)$ where w is the length of the window.}~\cite{beltagy2020longformer,zaheer2020big}. Longformer~\cite{beltagy2020longformer} proposes a dilated attention mechanism in which there are gaps between windows, resulting in the expansion of the receptive field without additional computation. In addition, Big Bird~\cite{zaheer2020big} employs random attention, in which each token attends to a set of random tokens to enhance the model's ability to learn non-local interactions.
Considering the \textit{long-range  dependency}, global attention is employed, where selected tokens can interact with all tokens throughout the entire sequence. We heuristically select global locations or add additional global special tokens according to task-specific requirements~\cite{beltagy2020longformer,zaheer2020big}.
LongT5~\cite{guo-etal-2022-longt5} creates transient global attention that is constructed dynamically prior to attention operations.

\paragraph{Learnable Attention Patterns}

In addition to fixed patterns, content-based learnable attention patterns are also useful  to capture both local and global relations. The core idea is learning to assign tokens to different baskets based on the input content. Each query token can only attend to the keys in the same basket, which can improve attention efficiency. Reformer~\cite{NikitaKitaev2020ReformerTE} leverages locality-sensitive hashing to assign similar queries and keys into different hash baskets. Similarly, the K-means algorithm is used by the Routing Transformer~\cite{YiTay2020SparseSA} to cluster tokens. Sparse Sinkhorn attention~\cite{YiTay2020SparseSA} first splits a sequence into blocks and then proposes a meta sorting method to produce a query-key block assignment scheme.

\paragraph{Attention Approximation}

The preceding methods aim to select a subset of tokens for each query to focus on. As an alternative way to reduce the $O(n^2)$ complexity, we can approximate the multiplication of the query and key matrices.
In the self-attention mechanism,
we need to calculate the similarity scores between the query and all keys, resulting in a large computation cost.
By using kernel-based approximations,
the softmax operation can be replaced with linear dot-product of kernel feature maps $\phi(\cdot)$, \emph{i.e.,}\xspace $\exp(\mathbf{q}_j^\top  \mathbf{k}_i) \approx \phi(\mathbf{q}_j)^\top\phi(\mathbf{k}_i)$. Afterwards, the output of self-attention can be computed as  $\mathbf{o}_j=\frac {\phi(\mathbf{q}_j)^\top\sum_{i=1}^n \phi(\mathbf{k}_i) \mathbf{v}_i^\top}{\phi(\mathbf{q}_j)^\top\sum_{i=1}^n \phi(\mathbf{k}_i)}$. Here, $\sum_{i=1}^n \phi(\mathbf{k}_i)$ and $\sum_{i=1}^n \phi(\mathbf{k}_i) \mathbf{v}_i^\top$ would  only be calculated once and reused for each query $\mathbf{q}_j$, significantly reducing the computation complexity~\cite{Transformerrnn}. In addition, different feature maps can be explored for better approximating softmax attention~\cite{Transformerrnn,HaoPeng2021RandomFA,KrzysztofChoromanski2020MaskedLM,choromanski2020rethinking}.
Considering the low-rank structure of the attention matrix,
Linformer~\cite{SinongWang2020LinformerSW} projects keys and values into representations with a small projected length. Similarly, Luna~\cite{ma2021luna} decomposes attention into two nested operators and packs the information across the long sequence into shorter condensed tokens.

\paragraph{Efficient Encoder-decoder Attention}
Most previous work has focused on modifying the self-attention module, while the encoder-decoder attention module has been seldom discussed. As the length of the generated text increases, efficient encoder-decoder attention is increasingly vital due to the computational and memory costs. Considering the redundancy of attention heads~\cite{clark2019does,voita-etal-2019-analyzing}, HEPOs~\cite{huang-etal-2021-efficient} assign different encoder-decoder attention heads with different subsets of tokens. Similar to content selection, \citet{manakul-gales-2021-sparsity} decompose the encoder-decoder attention into two parts, \emph{i.e.,}\xspace sentence-level attention dynamically extracts salient sentences and token-level attention only attends to tokens in the extracted subset.

\subsection{Recurrent Transformers}

The recurrent Transformer is another approach to tackling the issue of limited context length. Unlike efficient Transformers that simplify the attention structure, recurrent Transformer keeps the full self-attention mechanism. Typically, a long document is split into a series of chunks as Section~\ref{section3-chunking}. Instead of processing each chunk separately, we cache the history information of previous chunks. When the subsequent segment is fed into the model, the cached information can be exploited to mitigate the context fragmentation problem.

-Transformer-XL~\cite{dai-etal-2019-transformer} first proposes a recurrence mechanism for Transformers. The hidden states of the previous segment are concatenated with the current segment as the input to the next layer. However, those representations of very distant segments will be discarded due to limitations of storage cost. To alleviate this problem, Compressive Transformer~\cite{rae2019compressive} condenses past representations into more coarse-grained memories.
Due to the uni-directional self-attention, Compressive Transformer and Transformer-XL still have a fixed memory size.
In order to eliminate this limitation, Memformer~\cite{wu2021memformer} designs a memory system with multiple slots to store history information. Memory cross attention and memory slot attention are proposed to retrieve and update the memory dynamically. ERNIE-Doc~\cite{ding-etal-2021-ernie} enhances recurrent mechanisms through the same-layer recurrence, \emph{i.e.,}\xspace passing the concatenation of the hidden states of the current segment and the previous segment at the next layer to the next layer, further extending the context length while maintaining fine-grained representations. In addition, a retrospective feed mechanism is applied,  making the global context information of a document available for each segment.

\subsection{Pretraining for Long Texts}

Recently, pretraining has been proven to be an effective way to learn task-agnostic representations for improving performance on various NLP tasks, especially in the data-scarcity setting. Typically, PLMs are pretrained with texts that are typically shorter than the target data.
Due to the discrepancy between short and long texts, different pretraining configurations should be explored for the lengthy sequences. Considering that pretraining on long documents from scratch is expensive, we can continue pretraining based on existing PLMs checkpoints~\cite{beltagy2020longformer,zaheer2020big}.

The pretraining tasks are essential for Transformer models to acquire task-agnostic representations from data. Generally, PLMs adopt standard language modeling~\cite{radford2019language} and denoising autoencoding objectives~\cite{devlin2018bert,lewis2019bart}.
To pretrain on long documents, the majority of models adopt masked language modeling (MLM) as their objectives, such as Longformer~\cite{beltagy2020longformer} and Big Bird~\cite{zaheer2020big}. Since the MLM task mainly focuses on token-level semantics, more pretraining objectives have been explored for sentence-level or document-level relations. HIBERT~\cite{zhang-etal-2019-hibert} randomly masks the whole sentences from long documents and employs the sentence prediction task for better capturing inter-sentence relations. Similarly, PEGASUS~\cite{zhang2020pegasus} proposes a gap sentences generation (GSG) task, where top-k
sentences selected based on the ROUGE1 scores compared to the rest of the document are masked to be reconstructed. Despite being designed for text summarization tasks, the GSG task has been shown effective for different long text tasks~\cite{guo-etal-2022-longt5,phang2022investigating}. Additionally, ERNIE-Doc~\cite{ding-etal-2021-ernie} introduces the document-aware segment-reordering objective to reorganize the permuted segments.

\section{Application}
\label{section6}
The technique of long text modeling is widely useful in a variety of downstream applications.
In this part, we mainly discuss four typical applications, \emph{i.e.,}\xspace text summarization, question answering, text classification, and text matching.

\paragraph{Text Summarization}
Text summarization is an application of condensing a source text into a brief text while retaining the essential details.
When summarizing long documents in an extractive way, content redundancy tends to occur, \emph{i.e.,}\xspace segments with similar meanings are extracted.  Graph-based and hierarchy-based methods are employed due to their ability to reduce the redundancy between extracted sentences~\cite{phan-etal-2022-hetergraphlongsum,cho2022toward}.
In addition, instead of directly computing the confidence scores, \citet{xiao2020systematically} explore more complex methods to balance redundancy and importance. In abstractive summarization, local attention or chunking mechanism are utilized to capture the semantic information of long documents~\cite{guo-etal-2022-longt5,liu2022leveraging}. Based on the information, a fluent, coherent summary can be generated. Besides, the two methods above can be combined into hybrid summarization, \emph{i.e.,}\xspace
 an extraction-then-generation pipeline~\cite{manakul-gales-2021-long,mao-etal-2022-dyle,pilault-etal-2020-extractive}.

\paragraph{Question Answering}
Long document question answering aims to understand the source document and extract or generate answers given a question. Besides the methods that directly extract answers, most works follow a retrieve-then-read process, \emph{i.e.,}\xspace we first select relevant evidence and then apply a PLM to extract spans or generate the answer on the brief evidence~\cite{nie2022capturing}. As for the multi-hop QA tasks, the reasoning process spans multiple articles, and these articles are concatenated into a long document. Then, multi-step reasoning iteratively retrieves and updates the answer based on the question~\cite{ding2020cogltx}.

\paragraph{Text Classification}
Text classification aims to assign  texts into a number of pre-defined  categories, with applications including sentiment analysis, natural language inference, and news classification. For PLMs, the embedding of the special token (\emph{e.g.,}\xspace \texttt{[CLS]}) is taken as the representation of the entire document and fed into a softmax function for predicting the classification label.  In long document classification, fine-tuning a BERT after truncating long texts can be a competitive baseline~\cite{park-etal-2022-efficient}. Besides this method, efficient attention, chunking, and selection mechanism have been employed to enhance the semantic modeling by preprocessing more tokens~\cite{zhang-etal-2019-hibert,beltagy2020longformer,ding2020cogltx}. While, \citet{park-etal-2022-efficient} systematically evaluate different models and conclude that complex models do not consistently work well across datasets, demonstrating the need for advanced models with robust performance.

\paragraph{Text Matching}

Text matching aims to estimate the semantic relation between a source and target text pair according to their similarity. Semantic matching between long document pairs has a variety of applications, such as article recommendation and citation recommendation, but it is more challenging due to the need for a comprehensive understanding of  semantic relations~\cite{10.1145/3308558.3313707,yang2020beyond}.
In existing work, a two-tower Siamese network structure~\cite{bromley1993signature} is widely used by  calculating  the similarity between the representations of two documents.
To condense the long document into a low-dimensional vector,
similar approaches for long text classification can be also used. For example, SMITH~\cite{yang2020beyond} chunks a long document into several segments and aggregates information from different segments into the document-level representation through inter-segment Transformer layers.

\section{Special Characteristics of Long Text}
\label{section5}
By utilizing the techniques described in Sections~\ref{section3} and~\ref{section4}, it is possible to model a long document in an effective manner. At the same time, compared to short texts, long documents have more \textit{special characteristics} $\mathcal {C}$ (Equation~\ref{eq1}) that must be taken into account. As shown in Table~\ref{tab2}, we mainly consider three typical characteristics: long-term dependency, inter-sentence relation, and discourse structure, and discuss how to enforce  these characteristics when modeling long texts.

\begin{table*}

\centering
\small
\begin{tabular}{c|c|l}
\toprule
Characteristics &Methods& Related Works \\
\midrule
\multirow{4}{*}{\tabincell{c} {long-term\\ dependency}}& \tabincell{c}{Enhancing\\ local attention} &\tabincell{l}{Global attention~\cite{beltagy2020longformer,zaheer2020big},\\segment-level representations~\cite{pang2022long}, and state space models~\cite{zuo2022efficient}.}\\\cmidrule{2-3}
& \tabincell{c}{Modeling cross\\segment interaction} &\tabincell{l}{Recurrence mechanism~\cite{gong-etal-2020-recurrent}, memory module~\cite{cui2021sliding},\\cross-segment encoder~\cite{pappagari2019hierarchical}, and multi-stage framework~\cite{zhang-etal-2022-summn}}\\\midrule
\multirow{4}{*}{\tabincell{c} {Inter-sentence\\Relations}}&\tabincell{c} {Hierarchy-based\\models}&\tabincell{l} { Inter-sentence encoder layers~\cite{zhang-etal-2019-hibert,ruan-etal-2022-histruct,cho2022toward}\\and additional sentence-level cross-attention module~\cite{rohde2021hierarchical}}\\\cmidrule{2-3}
&\tabincell{c}{Graph-based\\models}&\tabincell{l}{Graphs with hierarchical structures~\cite{phan-etal-2022-hetergraphlongsum},\\and topic enhanced graphs~\cite{cui-etal-2020-enhancing,zhang2022hegel}}\\\midrule

\multirow{4}{*}{\tabincell{c}{Discourse\\Structure}}&\tabincell{c}{Explicitly\\designing models}&\tabincell{l}{Hypergraphs with section hyperedges~\cite{zhang2022hegel},\\section title embedding, and section position embedding~\cite{ruan-etal-2022-histruct}}\\\cmidrule{2-3}
&\tabincell{c}{Implicitly\\enhancing models}&\tabincell{l}{Section segmentation objective~\cite{cho2022toward}\\and chunking according to the sections~\cite{liu2022leveraging}}
\\

\bottomrule
\end{tabular}
\caption{Categories of special characteristics of long texts.}
    \label{tab2}
\end{table*}

\subsection{Long-term Dependency}
long-term dependency is an important property of long documents, where distant tokens may be related to each other in the semantics. Equipped with the self-attention mechanism, Transformer is more capable of  modeling  long-term dependency than recurrent neural networks~\cite{vaswani2017attention}. Nonetheless, lengthy documents are typically divided into disjoint segments or encoded with the sparse attention mechanism, jeopardizing long-distance semantic relations. To tackle this issue, there are two major methods to preserve long-term dependency on long documents.

\paragraph{Enhancing Local Attention}
Considering the \textit{computation efficiency} requirement, local attention is typically substituted for full self-attention when modeling long texts~\cite{beltagy2020longformer,zaheer2020big,guo-etal-2022-longt5,ainslie-etal-2020-etc}. With a small receptive field, the model with local attention has a limited ability for capturing long-term dependencies.Global attention mentioned in Section~\ref{section4} is an effective method of enhancing local attention~\cite{beltagy2020longformer,zaheer2020big}. Further, Top Down Transformer~\cite{pang2022long} stacks the segment-level Transformer layers on top of the Transformers with local attention to obtain segment-level representations. Then, the segment-level outputs are used to enhance token representations through cross-attention. SAPADE~\cite{zuo2022efficient} employs state space models tailored for long input before local self-attention layers to capture long-term dependency.

\paragraph{{Modeling Cross-segment Interaction}}
Independently encoding each segment cannot well capture long-distance interactions across different segments since they can only aggregate local information.
. To resolve this issue, we can enable unidirectional or bidirectional information flow across segments via additional modules.
RCM~\cite{gong-etal-2020-recurrent} and RoBERT~\cite{pappagari2019hierarchical} encode each snippet into a low-dimensional vector to transfer information between segments with a recurrent function such as an LSTM and a gated function.
Recurrent Transformers modify Transformer architectures to transmit both fine-grained and coarse-grained memories of preceding representations into current window~\cite{dai-etal-2019-transformer,rae2019compressive}.
Another way to model global information is the memory network that can preserve past segments' information. In SSN-DM~\cite{cui2021sliding}, salient information is maintained through a dynamic memory module and interacts with the current segment using graph neural networks (GNNs). Similarly, CGSN~\cite{nie2022capturing} utilizes a hierarchical global graph to preserve and dynamically update multi-level historical information.
Besides the unidirectional approaches mentioned above, we can also model the bidirectional interaction across windows. Normally, we stack segment-level representations into a sequence. Then, this sequence is processed by a cross-segment encoder (\emph{e.g.,}\xspace Transformer and BiGRU) that may be stacked on the top of the segment-wise Transformer or inserted into each Transformer layer.
~\cite{pappagari2019hierarchical,grail2021globalizing}.
SUMM$^N$~\cite{zhang-etal-2022-summn} proposes a multi-stage split-then-summarize framework in which the concatenation of each segment's local summary serves as the input to the subsequent stage. Therefore, in the final step, the entire receptive field is ensured in the brief input.

\subsection{Inter-sentence Relations}
A long document usually consists of multiple paragraphs and sentences. For existing Transformer models, a special token such as \texttt{[CLS]} is typically inserted at the beginning of each sentence to represent a sentence. However, the vast majority of Transformer models are pretrained to learn token-level representations, which cannot well capture cross-sentence dependency. In this case, it is insufficient for the representation of the special token to aggregate complex intra-sentence and inter-sentence information. There are two primary types of methods for capturing inter-sentence relations: graph-based and hierarchy-based models.

\paragraph{Hierarchy-based Models}
From top to bottom, a long document can be divided into paragraphs, sentences, and tokens. In order to utilize the hierarchical information containing complex inter-sentence dependencies, Transformer architectures can be modified in a hierarchical manner.
Inspired by HAN~\cite{yang-etal-2016-hierarchical} that designs hierarchical RNN modules, multiple studies propose stacking inter-sentence Transformer layers on top of off-the-shelf pretrained Transformer encoders~\cite{zhang-etal-2019-hibert,ruan-etal-2022-histruct,cho2022toward}. As for Transformer encoder-decoder models, HAT~\cite{rohde2021hierarchical} and HMNet~\cite{zhu-etal-2020-hierarchical} inserts an additional cross-attention module that attends over the hidden states encoded by the sentence-level Transformer.

\paragraph{Graph-based Models}
Graph-based model is another approach to modeling high-order dependency. Generally, a lengthy document can be transformed into a graph where semantic units are represented as nodes and intricate relationships are modeled as the edges. Therefore, downstream tasks can be converted  into a node classification problem. In this setting, the Transformer model serves as an encoder to initialize the hidden states of each node. The majority of work constructs the graph at the sentence level. Latent topic models are adopted to extract a variety of topics in a document. Each topic has its own representations and these topic representations are connected with sentence representations through edges~\cite{cui-etal-2020-enhancing,zhang2022hegel}.
Additionally, heterogeneous graphs with hierarchical structures can enrich the node representations with the word- and passage-level information~\cite{phan-etal-2022-hetergraphlongsum,doan-etal-2022-multi}. After constructing the graph, a graph neural network is utilized to update the hidden states of nodes by aggregating the information of neighbors to learn various cross-sentence relations, and these hidden states are fed into a classifier for ranking or predicting confidence scores.

\subsection{Discourse Structure}
Discourse is defined as the semantic unit containing multiple sentences in the NLP field. In contrast to short texts, long documents (\emph{e.g.,}\xspace scientific articles and books) usually have complex discourse structures, \emph{e.g.,}\xspace sections, and paragraphs.
By leveraging such structural information, models can boost their performance on downstream tasks.

On the one hand, it is possible to explicitly design models to inject discourse structure information. Typically, a scientific article consists of several sections that contain multiple sentences, and different sections focus on different semantic topics.
Based on this property, HEGEL~\cite{zhang2022hegel} creates hyper-edges to connect all of the sentences within a section. Hierarchical position embedding is designed by HIBRIDS~\cite{cao-wang-2022-hibrids} and HiStruct+~\cite{ruan-etal-2022-histruct} to better capture the section-level discourse structure. Furthermore, the title of each section that highly summarizes the theme of the segment should be taken into account~\cite{ruan-etal-2022-histruct}.

On the other hand, this characteristic can also be exploited implicitly. To enhance performance on long document summarization, an additional section segmentation task, \emph{i.e.,}\xspace predicting section boundaries, is proposed in Lodoss~\cite{cho2022toward}. Additionally, we can exploit the inductive bias of discourse structure when chunking the document into multiple segments. Each section will be viewed as a separate segment~\cite{liu2022leveraging,manakul-gales-2021-long}.

\section{Conclusion and Future Directions}
\label{section7}
In this paper, we provide an overview of the recent advances in long text modeling based on Transformer models. We first summarize the preprocessing techniques for long input texts, efficient Transformer architectures for reducing the computation complexity, and special characteristics in long texts. Furthermore, four typical applications based on long text modeling  are discussed. We conclude this paper by presenting several future directions for long text modeling:

\paragraph{Exploring Architectures for Long Texts}

The Transformer model has achieved remarkable success in NLP, but the quadratic computation complexity limits its application to long texts. Even though there are different variants that can efficiently model long texts, their performance still generally underperforms the full self-attention mechanism.  Therefore, it is worthwhile to explore more efficient architectures for modeling long texts. Recently, state space models~(SSMs) have shown their superiority in multiple long sequence modeling tasks.  SPADE~\cite{zuo2022efficient} enhances local attention with SSMs, greatly outperforming existing models with only linear complexity. In the meantime, all-MLP architectures
have been shown to be cost-effectively competitive with Transformers~\cite{liu2021pay}, and we can further explore their potential for modeling long text domains.

\paragraph{Designing Long-text PLMs}
Transformer models have been widely adopted for long text tasks, and most of them adopt the MLM objective or its variants with different masking techniques~\cite{devlin2018bert,zhang-etal-2019-hibert}. ERNIE-Doc proposes coarser-grained pretraining methods (\emph{e.g.,}\xspace document-aware segment-reordering objective) to capture high-level semantics, which can be considered a powerful complement to MLM. Moreover, task-specific pretraining objectives demonstrate their effectiveness in various long document tasks~\cite{zhang2020pegasus,guo-etal-2022-longt5}. In the future, it will be promising to investigate how to design advanced pretraining methods and develop more powerful models specially for long texts.

\paragraph{Eliminating Gaps between Existing PLMs and Long Texts} Reusing existing PLMs in long texts is a promising method but the majority of them are not designed for long texts~\cite{gong-etal-2020-recurrent,ivgi2022efficient,zhang-etal-2022-summn}. As discussed in Section~\ref{section3}, there are mainly three types of approaches to adapting existing PLMs to long texts, \emph{i.e.,}\xspace text truncation, text chunking, and text selection. Although these methods can transform long texts into sequences that can be directly processed by the PLMs, there still exists a gap between the processed segments and the pretraining texts.
In addition, salient information may be lost and dependencies may be broken during the stage of preprocessing. Consequently, future research can investigate how to eliminate the mismatch between the model and data and how to preserve information to the greatest extent possible.

\paragraph{Modeling in Low-resource Settings}
There is a great need for data to train a Transformer due to its large number of parameters. However, Low-resource settings are common in real practice where labeled data for supervised training is scarce.
To overcome the challenge, efficient tuning techniques can be employed to bridge the gap between pretraining and finetuning while avoiding overfitting~\cite{pu-etal-2022-two}.
Besides, data augmentation is another effective method  for long text summarization tasks. Se3~\cite{moro2022semantic} splits a long document into multiple segments with the corresponding targets for separate summarization, creating more data instances to alleviate the data scarcity problem. Additionally, \citet{bajaj-etal-2021-long} extract salient snippets and transfer the knowledge from a BART continually pretrained on
datasets on a related domain.
Since manually collecting and processing long texts are time-consuming, more effort is required to process long texts in low-resource situations.

\paragraph{Modeling with Large Language Models}
Recently, large language models (LLMs) have achieved remarkable performance in various NLP tasks and satisfy human preferences due to their strong zero-shot or few-shot generalization capabilities. Typically, the maximum lengths of the context window in LLMs greatly exceed those in traditional PLMs, (\emph{e.g.,}\xspace 2048 tokens in GPT-3~\cite{brown2020language} and 4000 tokens in InstructGPT~\cite{ouyang2022training}), making it possible for LLMs to directly process the long document. Meanwhile, we can directly employ LLMs to handle long text tasks through task instructions or a few exemplars without fine-tuning the model, significantly reducing the computation consumption. However, there still exist texts exceeding the maximum length and the length of each exemplar is limited by the total length in the few-shot settings. Therefore, it is still worth exploring how to process long texts with LLMs to deal with the length limitation and satisfy special characteristics. As a pioneer work in applying LLM to long text problems, PCW~\cite{ratner2022parallel} chunks the lengthy input and separately encodes each window with an LLM. Then, all windows will be attended to during the generation stage using the fusion-in-decoder mechanism~\cite{izacard2020leveraging}.

\section{Introduction}
In real life, long text is one major form of information medium that records human activities or daily events,
\emph{e.g.,}\xspace academic articles, official reports, and meeting scripts.
Due to the ever-growing volume, it is difficult for humans to read, process, and extract vital and pertinent information from large-scale long texts. Consequently, there is a strong demand for NLP systems to automatically model long texts and extract information of human interest. Generally, the task of long text modeling aims to capture salient semantics from text via informative representations (\emph{e.g.,}\xspace keywords), which would be useful for various downstream applications. For example, summarizing a long scientific paper in arXiv into its abstract~\cite{cohan-etal-2018-discourse} and classifying a long legal document into different categories~\cite{wan2019long}.

To deal with tasks involving long text modeling, many previous studies have been conducted based on recurrent neural networks (RNNs)~\cite{yang-etal-2016-hierarchical}, with the two prominent variants of LSTM~\cite{cohan-etal-2018-discourse} and GRU~\cite{yang-etal-2016-hierarchical}. Nevertheless, RNNs cannot effectively handle long-range dependencies existing in long texts. Recently, Transformer based models~\cite{vaswani2017attention}, especially the pretrained language models (PLMs), have achieved great success in NLP~\cite{devlin2018bert,radford2019language,lewis2019bart}. When it comes to employing PLMs in long text tasks, many works just adopt the same approaches to processing relatively short texts without considering the difference with long texts~\cite{lewis2019bart}.

However, modeling long texts is a challenging task in NLP. First, existing PLMs impose a \textit{length limitation} of each input sequence. Each PLM predefines a maximum context length that is usually exceeded by the length for long texts, making tokens beyond the maximum length directly discarded. Therefore, how to preprocess long texts to adapt existing PLMs is worthy of in-depth study.
In addition, \textit{computation efficiency} is an unavoidable issue. As the length of the document increases, the time and memory consumption required to model the text increase quadratically, creating a significant burden for practical applications.
Besides, the lengthy document contains more \textit{special characteristics} compared with the short text. Since long texts are typically domain-specific articles having complex hierarchical structures, there is a high demand for considering long-term dependency\footnote{Long-term dependency is also known as long-range dependency in some papers~\cite{pang2022long}.}, inter-sentence relations, and discourse structure.

Despite existing works reviewing related fields, there is no survey that systematically summarizes the recent progress in long text modeling. \citet{koh2022empirical} give a brief overview of the research on long document summarization but do not go deep into the core technique of long text modeling. \citet{tay2022efficient} and~\citet{LIN2022111} focus on the topic of improving the computation efficiency of Transformer models in long text modeling.
Different from existing reviews, this survey  attempts to provide a more general and comprehensive overview of long text modeling based on Transformer models, rather than being limited  to a specific application or topic.

The remaining sections of this survey are organized as follows (see Figure~\ref{fig1}).
To start with, we give a formal definition of long text modeling in Section~\ref{section2}. To model long texts of arbitrary length, we introduce preprocessing methods that handle the \textit{length limitation} for PLMs in Section~\ref{section3} and Transformer architectures that efficiently extend maximum context size while keeping \textit{computation efficiency} in Section~\ref{section4}. Since long texts have \textit{special characteristics}, we explain how to design model architecture to satisfy these characteristics in Section~\ref{section5}.
Subsequently, typical applications are presented in Section~\ref{section6}.
Finally, we draw a conclusion from the survey and present some future directions in Section~\ref{section7}.

\section{Overview of Long Text Modeling}
\label{section2}
To begin with, we provide a formal definition of long text modeling. In this survey, a {long text} is represented as a sequence of tokens $\mathcal{X}=(x_1, \dots, x_n)$, which may contain thousands of or more tokens in contrast to short or {normal texts that can be directly processed by Transformer.
Due to the predetermined maximum context length of PLMs, it is challenging for a Transformer model to encode an entire long sequence. Consequently, a preprocessing function $g(\cdot)$ is utilized to transform the lengthy input into a shorter sequence or a collection of snippets  (Section~\ref{section3}).
Besides, a lengthy document will contain \textit{special characteristics} $\mathcal{C}$
that must be taken into account in the modeling process, \emph{e.g.,}\xspace long-term dependency, inter-sentence relations, and discourse structure (Section~\ref{section5}).
Further, a Transformer architecture $\mathcal{M}$ is employed to capture context information from the input data and model the semantic mapping relation from input $\mathcal{X}$ to an expected output $\mathcal{Y}$ (Section~\ref{section4}).
Based on the concepts, the task of modeling long texts is formally described as follows:
\begin{equation}
   \label{eq1} \mathcal{Y}=f\big(g(\mathcal{X});\mathcal{C},\mathcal{M}\big).
\end{equation}

According to the type of the output $\mathcal{Y}$, we can classify long text modeling tasks into two major categories (Section~\ref{section6}):
\begin{itemize}[leftmargin=*]
    \itemsep0em
    \item The output $\mathcal Y$ is a sequence. The setting of the task needs to capture key semantics of the long texts to obtain target sequences.

    There are two kinds of methods: the extraction method encodes the input text with an encoder and then predicts the output spans based on token-level or sentence-level representations such as question answering~\cite{gong-etal-2020-recurrent}; the generation method employs an encoder-decoder framework to generate an output text from scratch such as text summarization~\cite{cui2021sliding}.
    \item The output $\mathcal{Y}$ is a label. The setting of the task needs to capture the crucial semantic information of the entire document for accurate classification. The input $\mathcal{X}$ is first condensed into a low-dimensional vector. Afterward, The document-level representation is fed into a classifier or employed for similarity comparison with other documents. Typical applications include text classification~\cite{park-etal-2022-efficient} and text matching~\cite{yang2020beyond}.
\end{itemize}

\section{Preprocessing Long Input Texts}
\label{section3}
Existing Transformer-based PLMs~\cite{devlin2018bert,radford2019language,lewis2019bart} predefine the maximum sequence length, \emph{e.g.,}\xspace  BERT can only process up to 512 tokens.
According to Section~\ref{section2}, when the sequence length $n$ exceeds the maximum context size $t$, the preprocessing function $g(\cdot)$ is employed to transform the input document into one or more short segments (see Equation~\ref{eq1}). In this section, we introduce three major text preprocessing techniques to circumvent the \textit{length limitation} of PLMs, \emph{i.e.,}\xspace truncation, chunking, and content selection, as summarized in Table~\ref{tab1}.

\begin{table}[htb]
    \centering
    \begin{tabular}{ll}\toprule
        Preprocessing& Formulation\\\midrule
        Text truncation & $g(\mathcal{X})=(x_1,\dots, x_t), t \le n$  \\
        Text chunking&$g(\mathcal{X})=\{\mathbf{s}_1,\dots,\mathbf{s}_l\}, \mathcal{X}=\mathbf{s}_1 \cup \cdots \cup \mathbf{s}_l$\\
         Text selection &$g(\mathcal{X})=(\mathbf{s}_{r_1},\dots,\mathbf{s}_{r_k}), k \le l$\\

         \bottomrule
    \end{tabular}
    \caption{Preprocessing methods and their formulation. Each snippet is a sequence of tokens $\mathbf{s_i}=(x_{i,1},\dots,x_{i,m_i})$, where $m_i$ is no larger than the maximum length $t$ of the model.}
    \label{tab1}
\end{table}
\subsection{Truncating Long Texts}

The simplest option is to truncate the long input text into a relatively brief sequence within a  predefined maximum length~\cite{lewis2019bart,park-etal-2022-efficient}, which then can be processed by an off-the-shelf PLM. In practice, the truncated text usually ranges from the beginning of the input text to the maximum length allowed by the model.

Text truncation is significantly influenced by the lead bias of the source text~\cite{zhang-etal-2022-summn}. When the crucial information is included in the segment  within the truncation length, a PLM fine-tuned with the truncated text can serve as a strong and efficient baseline, even outperforming more sophisticated models~\cite{park-etal-2022-efficient}. However, as the length increases, the salient information of a long document is typically distributed evenly throughout the entire document. Consequently, text truncation may result in significant performance degradation due to the loss of information~\cite{koh2022empirical}. In certain tasks that need to extract from the input, it would be unable to locate target spans out of truncated texts.

\subsection{Chunking Long Texts} \label{section3-chunking}
The principle of locality has been extensively observed in natural language, \emph{i.e.,}\xspace closer texts in the document have similar semantics~\cite{liu2022leveraging}. Therefore, based on this principle, we can identify and group semantically similar segments in a long text. Given the input $\mathcal{X}$ of arbitrary length, instead of viewing it as a complete sequence, we chunk it into a sequence of snippets.
Each snippet is a sequence of tokens within the maximum length of the model,
and the union of snippets is equal to the raw input.  Then, a PLM is employed to encode each chunk to capture the local information, followed by an aggregation operation.

\paragraph{Designing Chunking Mechanism}
The strategy of chunking has a significant effect on the performance of downstream tasks. Commonly, the long document is divided into multiple non-overlapping parts with a fixed stride size. However, neighboring  sentences may be split into different segments, resulting in a context fragmentation problem and incomplete answers~\cite{dai-etal-2019-transformer,gong-etal-2020-recurrent}. A straightforward solution is to permit the segments to overlap~\cite{chalkidis2022exploration}. Moreover, RCM~\cite{gong-etal-2020-recurrent} proposes a reinforcement learning method to determine the stride size flexibly. When chunking lengthy and domain-specific articles, it is also essential to consider their discourse structures.
For instance, each section in a scientific paper typically covers the same topic, thus it is natural to view each section as an individual segment~\cite{liu2022leveraging}.

\paragraph{Aggregating Different Chunks}
Various methods can be utilized to aggregate the information of different chunks, depending on the downstream tasks.
To obtain the segment-level representations, a special token (\emph{e.g.,}\xspace \texttt{[CLS]}) is usually prepended at the beginning of each segment. Then, aggregation functions such as max-pooling and mean-pooling are employed to condense these segment representations into the document representation~\cite{li2020parade}.
For sequence extraction tasks, the target sequence can be extracted independently from each chunk. Afterward, we select the answer with the highest score or concatenate the sequences into the final output.
When it comes to text generation tasks, there are multiple methods to utilize the context information from each segment encoded separately. The simplest method is to concatenate the texts independently generated for each segment, which may lead to repetition issues. Based on the fusion-in-decoder module employed in open-domain QA~\cite{izacard2020leveraging}, SLED~\cite{ivgi2022efficient} encodes local context in the encoder and handles global dependency in the decoder with all effective tokens across chunks. Inspired by the principle of locality, PageSum~\cite{liu2022leveraging} makes local predictions based on individual pages and combines regional hidden states of the decoder to make final predictions.

Different from text truncation, text chunking can utilize the entire document, avoiding losing important information in the discarded text.
Nevertheless, the receptive field of PLMs is limited to a segment, resulting in the break of the long-range dependency that spans multiple segments~\cite{ding2020cogltx}. In addition, when we extract the answer from each segment independently, Since the answers are extracted from each segment independently, it is difficult to compare the scores of each segment's answer to select the best one as the final output~\cite{wang2019multi,gong-etal-2020-recurrent}.

\subsection{Selecting Salient Texts}

Based on the basic assumption that the salient information occupies only a small portion of a lengthy document and few yet important sequences can sufficiently represent the entire document~\cite{ding2020cogltx}, it is a common practice to employ a two-stage pipeline (\emph{a.k.a.,}\xspace content selection), \emph{i.e.,}\xspace identifying and concatenating relevant portions of the long text into a sequence and processing this sequence with a PLM.
As described above, the input text can be represented as a sequence of snippets. In this case, top-$k$ relevant snippets are selected and concatenated by the retriever $g(\cdot)$, without exceeding the PLM's maximum length.

\paragraph{Designing Retrievers}
The retriever's ability is critical to the success of selecting salient texts. Previous research has utilized unsupervised retrieval methods (\emph{e.g.,}\xspace TextRank~\cite{mihalcea2004textrank}) that do not require training labels to enhance the simple truncation methods~\cite{park-etal-2022-efficient}. Besides, a supervised retriever can lead to additional performance improvements. LoBART~\cite{manakul-gales-2021-long} and Ext-TLM~\cite{pilault-etal-2020-extractive} employs a hierarchical RNN model to select key sentences. \citet{zhao-etal-2021-ror-read} use an existing PLM to extract fragments in conjunction with the text chunking mechanism. Inspired by the working memory mechanism of humans, CogLTX~\cite{ding2020cogltx} proposes the MemRecall procedure, which enables multi-step reasoning to extract critical text blocks via retrieval-competition and rehearsal-decay periods.

\paragraph{Training Retrievers}
A significant challenge of content selection is to balance the training of the two stages.
A simple method is to train the two modules in two stages separately. To train the retriever, a variety of specific methods are adopted in different situations.
For unsupervised cases in which it is difficult to obtain golden salient texts, CogLTX iteratively removes each block to adjust the relevance label based on the change of loss of the final output.
While, in certain tasks (\emph{e.g.,}\xspace text summarization and question answering), the golden segments can be located automatically according to the target sequence~\cite{manakul-gales-2021-long,nie2022capturing}. Hence, we can train the retriever with the relevance labels in a supervised manner. To bridge the gap between data distributions of the training and inference stages, it is recommended to train the Transformer model using the union of ground-truth and extracted snippets~\cite{ding2020cogltx}.
However, two-stage training may result in a significant disparity between the two modules, particularly for hybrid summarization tasks. To address these problems, reinforcement learning techniques are employed to optimize the entire model~\cite{bae2019summary}. Furthermore, DYLE~\cite{mao-etal-2022-dyle} assigns dynamic weights to each extracted fragment at each decoding step and proposes consistency loss to bridge the gap between the two stages.

Previous work shows that downstream tasks such as question answering can benefit from salient content selection~\cite{nie2022capturing}.
However, the quality of the extracted texts heavily depends on the dependency on snippets throughout the long texts~\cite{zhang-etal-2022-summn}.