text:
\subsection{Should we maintain waiting time information?}

Intuition tells us that if a packet has not been waiting long enough then perhaps it could afford waiting a little more but if a packet has waited too long, it may be better to just transmit it. That seems logical considering that we tried our best to code but we cannot wait too long because it hurts in terms of holding costs. Also, one could get waiting time information from time-stamps on packets that are always available. Given that, would we be making better decisions by also keeping track of waiting times of each packet? We answer that question by means of a theorem which requires the following lemma for a generic MDP $\{(X_n, D_n), n \ge 0\}$ where $X_n$ is the state of the MDP and $D_n$ is the action at time $n$.
\begin{lemma} \label{hist}
(Puterman \cite{puterman}) For an MDP $\{(X_n, D_n), n \ge 0\}$, given any history dependent policy and starting state, there exists a randomized Markov policy with the same long-run average cost.
\end{lemma}

Using the above lemma we show next that it is not necessary to maintain waiting time information.

\begin{theorem}
For the MDP $\{(Y_n, A_n), n \ge 0\}$, if there exists a randomized history dependent policy that is optimal, then there exists a randomized Markov policy $u^*$ that minimizes $V(u)$ defined in (\ref{gu_fn}). Further, one cannot find a policy which also uses waiting time information that would yield a better solution than $V(u^*)$.
\end{theorem}

\begin{citeField}
\begin{proof}
See \cite{opportunitisc-network-coding}.
\end{proof}
\end{citeField}

\begin{proofField}
\begin{proof}
From Lemma \ref{hist} if the MDP $\{(Y_n, A_n), n \ge 0\}$ has a history dependent policy that is optimal, then we can construct a randomized Markov policy that yields the  same long-run average cost given $Y_0 = (0,0)$. Therefore, if there exists a randomized history dependent policy that is optimal, then there exists a randomized Markov
policy $u^*$ that minimizes $V(u)$ defined in (\ref{gu_fn}).

Knowing the entire history of states and actions one can always determine the history of waiting times as well as the current waiting times of all packets. Therefore the optimal policy $u^\prime$ that uses waiting time information is equivalent to a history dependent policy. From Lemma \ref{hist}, we can always find a randomized Markov policy that yields the same optimal solution as $V(u^\prime)$.
\end{proof}
\end{proofField}

\subsection{Structure of the optimal policy}
In the previous sections, we showed that there exists an optimal policy that does not include the waiting time in the state of the system. In this section we focus on queuelength-based policies and determine the structure of the optimal policy. In the MDP literature (see Sennott \cite{sennott}), the conditions for the structure and location of optimal policy usually rely on the results of the infinite horizon $\beta$-discounted cost case and let $\beta$ approach 1 to obtain the average cost case. Accordingly, for our MDP $\{(Y_n, A_n), n \ge 0\}$, the total expected discounted cost incurred by a policy $\theta$ is
\BEQA
V_{\theta, \beta}(i,j) = E_\theta \left[ \sum_{n=0}^\infty \beta^n C(Y_n, A_n) | Y_0 = (i,j) \right] \label{eq:discount-cost}
\EEQA
In addition, we define $V_{\beta}(i,j) = \min_{\theta}V_{\theta,\beta}(i,j)$ as well as $v_{\beta}(i,j)=V_{\beta}(i,j)-V_{\beta}(0,0)$.

\newtheorem{property}[theorem]{Property}
\begin{propos}
$V_{\beta}(i,j)$ is finite for all $i$, $j$, and discount factor $\beta$. \label{prop:finte beta-discount}
\end{propos}

\begin{citeField}
\begin{proof}
See \cite{opportunitisc-network-coding}.
\end{proof}
\end{citeField}

\begin{proofField}
\begin{proof}
We denote the stationary policy of always transmitting by $\tilde{\theta}$. Hence, $V_{\beta}(i,j) \leq V_{\tilde{\theta},\beta}(i,j)$. Furthermore, we note that $V_{\tilde{\theta},\beta}(i,j) \leq \tilde{C}(i,j)/(1-\beta)$, where $\tilde{C}(i,j) \triangleq C_h\left([i-1]^+ + [j-1]^+\right)+C_t$. Thus, $V_{\beta}(i,j) < \infty$ and the proposition follows.
\end{proof}
\end{proofField}

Proposition \ref{prop:finte beta-discount} implies that $V_{\beta}(i,j)$ satisfies the optimality equation \cite{sennott},
\BEQA
V_\beta(i,j) = \min_{a \in \{0,1\}} [ C_h ([i-a]^+ + [j-a]^+) + C_t a \nonumber \\
+ \beta \sum_{k,\ell} V_\beta(k,\ell) P_a\bigl((i,j),(k,l)\bigr)].  \label{eq:optimality-eq}
\EEQA

The next lemma  specifies the conditions  that must be satisfied by the optimal stationary policy.
\begin{lemma} \label{stationary}
(Sennott \cite{sennott}) There exists a stationary policy that is optimal for the MDP $\{(Y_n,A_n), n \ge 0\}$ if the following conditions are satisfied: (i) $V_{\beta}(i,j)$ is finite for all $i$, $j$, and discount factor $\beta$; (ii) there exists a nonnegative $N$ such that $v_{\beta}(i,j) \geq -N$ for all $i$, $j$, and $\beta$; and (iii) there exists a nonnegative $M_{i,j}$ such that $v_{\beta}(i,j) \leq M_{i,j}$ and
\BEQA
\sum_{k,l} P_{a}\bigl((i,j),(k,l)\bigr)M_{k,l} < \infty
\EEQA
for every $i$, $j$, $\beta$, and action $a$.

\end{lemma}

Using Lemma~\ref{stationary} we show next that the MDP defined in this paper has an optimal policy that is stationary.
\begin{theorem}
For the MDP $\{(Y_n, A_n), n \ge 0\}$, there exists a stationary policy $u^*$ that minimizes $V(u)$ defined in (\ref{gu_fn}). \label{thm:stationary}
\end{theorem}

\begin{citeField}
\begin{proof}
See \cite{opportunitisc-network-coding}.
\end{proof}
\end{citeField}

\begin{proofField}
\begin{proof}
As described earlier it is sufficient to show that the three conditions in Lemma~\ref{stationary} are met. Proposition \ref{prop:finte beta-discount} results in the condition (i), while the condition (ii) on finding an $N$ is also straightforward since all the costs are positive.

Considering the policy of always transmitting $\tilde{\theta}$, the upper bound on $V_{\beta}(i,j)$ can be obtained from (\ref{eq:optimality-eq}) as $C^{(1)}_{i,j} V_{\beta}(1,0)+ C^{(2)}_{i,j} V_{\beta}(0,1) + C^{(3)}_{i,j} V_{\beta}(0,0)$ for some finite-valued $C^{(k)}_{i,j}$. It therefore remains to show that there exist nonnegative finite-valued $M_{1,0}$ and $M_{0,1}$ such that $v_{\beta}(1,0) \leq M_{1,0}$ and $v_{\beta}(0,1) \leq M_{0,1}$. Note that we take $A_n=1$ for the state $(1,1)$, and therefore
\BEQA
V_{\beta}(1,1) = \hat{C} + \hat{\beta}\bigl(\hat{p}_1 V_{\beta}(0,0) + \hat{p}_2 V_{\beta}(1,0) + \hat{p}_3 V_{\beta}(0,1) \bigr),
\EEQA
where $\hat{C}=C_t/(1-\beta \hat{p}_4)$ and $\hat{\beta}=\beta/(1- \beta \hat{p}_4)$. Hence, the upper bound on $V_{\beta}(0,1)$ and $V_{\beta}(1,0)$ can be obtained from (\ref{eq:optimality-eq}) as follows.
\BEQA
V_{\beta}(1,0) &\leq& \frac{C_t+ \beta \hat{p}_4 \hat{C}}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} + \frac{\beta \hat{p}_1 (1+ \hat{\beta} \hat{p}_4 ) V_{\beta}(0,0)}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} \nonumber \\
&&+ \frac{\beta \hat{p}_3 (1+ \hat{\beta} \hat{p}_4) V_{\beta}(0,1)}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} \label{eq: bound-v01}
\EEQA
\BEQA
V_{\beta}(0,1) &\leq& \frac{C_t+ \beta \hat{p}_4 \hat{C}}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} + \frac{\beta \hat{p}_1 (1+ \hat{\beta} \hat{p}_4 ) V_{\beta}(0,0)}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} \nonumber \\
&&+ \frac{\beta \hat{p}_2 (1+ \hat{\beta} \hat{p}_4) V_{\beta}(1,0)}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} \label{eq: bound-v10}
\EEQA
Based on (\ref{eq: bound-v01}) and (\ref{eq: bound-v10}), it follows that the condition (iii) is satisfied because there exist some nonnegative finite-valued $M_{0,1}$ and $M_{1,0}$ so that $V_{\beta}(1,0) \leq V_{\beta}(0,0) + M_{1,0}$ and $V_{\beta}(0,1) \leq V_{\beta}(0,0) + M_{0,1}$.

\end{proof}
\end{proofField}

Now that we know that the optimal policy is stationary, the question is
how do we find it. The standard methodology to obtain stationary policy
for infinite-horizon average cost minimization problem is to use a
linear program as described below.

Consider a generic MDP $\{(X_n,D_n), n \ge 0\}$ where $X_n$ is the state and $D_n$ is the action at time $n$. Assume that the MDP has a finite number of states in the state space and the number of possible actions is also finite. Assume that the Markov chain resulting out of any policy is irreducible. Let $u$ be a stationary randomized policy described for state $X_n = i$ and action $D_n = a$ as follows:
\[ u_{ia} = P\{D_n = a | X_n = i \} \]
for all $i$ in the state space and all $a$ in the action space. Note that $u_{ia}$ is the probability of choosing action $a$ when the system is in state $i$. Further, define the expected cost incurred when the system is in state $i$ and the action is $a$ as
\[ c_{ia} = E[C(X_n,D_n) | X_n = i, D_n = a] \]
where $C(X_n,D_n)$ is the cost incurred at time $n$ if action $D_n$ is taken when the system is in state $X_n$.

\begin{lemma}
(Serin and Kulkarni \cite{serinvgk}) The optimal randomized policy $u^*_{ia}$ that minimizes the long-run average cost per unit time (equal to the length of a slot) can be computed as
\[ u^*_{ia} = \frac{x^*_{ia}}{\sum_b x^*_{ib}} \]
where $x^* = [x^*_{ia}]$ is the optimal solution to the linear program:
\begin{eqnarray*}
\mbox{Minimize } & & \sum_i \sum_a c_{ia} x_{ia} \\
\mbox{subject to } & & \sum_i \sum_a x_{ia} = 1 \\
& & \sum_a x_{ja} - \sum_i \sum_a p_{ij}(a) x_{ia} = 0 \;\; \forall j \\
& & x_{ia} \ge 0 \;\; \forall i, a .
\end{eqnarray*}
\end{lemma}

As described in Ross \cite{rossmdp}, the linear program (LP) produces for each $i$ optimal values $x^*_{ia}$ that are all zero except one $a$ which would be 1. Hence the optimal policy would in fact be a stationary deterministic policy.

However, we cannot directly apply the above results to our MDP $\{(Y_n,A_n), n \ge 0\}$, as our MDP has infinite states and the Markov chain under every policy is not irreducible (for example if we always transmit, it is not possible to reach some of the states).  To circumvent that, we construct a finite size LP
with $N$ states and force it to be irreducible by creating dummy transitions
with probability $\epsilon > 0$ between some states. Let us call this
$LP(N,\epsilon)$. From the lemma above, $LP(N,\epsilon)$ has a stationary
deterministic policy that is optimal. By letting $N \rightarrow \infty$ and
$\epsilon \rightarrow 0$ we argue that our MDP would have an optimal
deterministic policy. With that said, it is not efficient to obtain the
optimal policy by solving $LP(N,\epsilon)$ for large $N$ and small
$\epsilon$.

We now know that the optimal policy is stationary deterministic. But, how do we find it? If we know that the optimal policy satisfies some structural properties then it is possible to search through the space of stationary deterministic policies and obtain the optimal one.

\begin{theorem}
For the MDP $\{(Y_n, A_n), n \ge 0\}$, the optimal policy is of threshold type. There exist the optimal thresholds $L^*_1$ and $L^*_2$ so that the optimal deterministic action in states $(i,0)$ is to wait if $i \leq L^*_1$, and to transmit without coding if $i > L^*_1$; while in state $(0,j)$ is to wait if $j \leq L^*_2$, and to transmit without coding if $j > L^*_2$. \label{thm:threshold}
\end{theorem}

\begin{citeField}
\begin{proof}
See \cite{opportunitisc-network-coding}.
\end{proof}
\end{citeField}

\begin{proofField}
\begin{proof}
Using the same notations as (\ref{eq:optimality-eq}), define $V_{\beta}(i,0) \triangleq \min_{a \in \{0,1\}}V_{\beta,a}(i)$, where $V_{\beta,a}(i)=  C_h ([i-a]^+) + C_t a + \beta \sum_{k,\ell} V_\beta(k,\ell) P_a\bigl((i,j),(k,l)\bigr)$. Let $i^* = \min \{i \in \mathbb{Z}^+: V_{\beta,0}(i) > V_{\beta,1}(i) \}$. Then the optimal stationary and deterministic action (for the total expected $\beta$-discounted cost) is $A_n=0$ for the states $(i,0)$ with $i < i^*$, and $A_n=1$ for the state $(i^*,0)$. Note that we do not care about the states $(i,0)$ with $i>i^*$  since they are not accessible as $(i^*,0)$ only transits to $(i^*-1,0)$, $(i^*,0)$, $(i^*-1,1)$, and $(i^*,1)$. The similar argument is applicable for the states $(0, j)$.

Thus far we have shown that the threshold-based policy is optimal for the total expected $\beta$-discounted cost. According to \cite{optimal-control-of-batch}, it remains to show that the $V(u)$ in (\ref{gu_fn}) exists while $u$ is applied by a threshold-based policy. Since the steady state probability distribution of the Markov chain (induced from the MDP $\{(Y_n,A_n), n \ge 0\}$ associated with the threshold-based policy) can be computed as in Theorem \ref{thresholdl1l2}, $\lim_{N \rightarrow \infty} E_u[ \sum_{n=0}^N C(Y_n,A_n) | Y_0 = (0,0)]/(N+1)$ will converge \cite{Resnick-book}. The threshold-based policy is therefore also optimal for the long-run average cost.
\end{proof}
\end{proofField}

\begin{figure*}[htbp]
\begin{center}
\subfigure[]{
\vspace{-5ex}
\includegraphics[height=0.251\textwidth]{figures/tradeoff.eps}
\label{Fig:BER55,tradeoff}
}
\hspace{-20pt}
\subfigure[]{
\vspace{-5ex}
\includegraphics[height=0.251\textwidth]{figures/BER55.eps}
\label{Fig:BER55}
}
\hspace{-20pt}
\subfigure[]{
\vspace{-5ex}
\includegraphics[height=0.251\textwidth]{figures/LINE55.eps}
\label{Fig:LINE55}
}
\caption{(a) Trade-off between average delay and number of transmissions in a single relay using queue-length threshold policy for different Bernoulli arrival rates $(p_1,p_2)$, (b) Comparison of the minimum average cost (per packet) in a single relay with Bernoulli arrival rates $(0.5,0.5)$, for different policies, (c) Comparison of different policies in a line network with two intermediate nodes and two Bernoulli flows with mean arrival rates $(0.5,0.5)$}
\vspace{-0.2in}
\end{center}
\end{figure*}

\subsection{Analysis: obtaining the optimal deterministic stationary policy}
We have shown in the previous section that the optimal policy is stationary, deterministic and threshold type. The next step is to find it. Notice that we only need to consider the subset of deterministic stationary
policies.
\begin{theorem} \label{thresholdl1l2}
The optimal thresholds $L^*_1$ and $L^*_2$ are
\BEQA
(L^*_1,L^*_2) = \arg \min_{L_1,L_2} C_t \tau(L_1,L_2) + C_h \lambda(L_1,L_2)
\EEQA
where
\BEQA
\tau(L_1,L_2) &=& p_1 p_2 \pi_{0,0} + p_2 \sum_{i=1}^{L_1} \pi_{i,0} + p_1 \sum_{j=1}^{L_2} \pi_{0,j} + \nonumber \\
&&p_1 (1-p_2) \pi_{L_1,0} +  p_2 (1-p_1) \pi_{0,L_2} \\
\lambda(L_1,L_2) &=& \sum_{i=1}^{L_1} i \pi_{i,0}+ \sum_{j=1}^{L_2} j \pi_{0,j}
\EEQA
for which
\begin{eqnarray}
\pi_{0,0} &=& \frac{1}{\left( \frac{1 - \alpha^{L_1+1}}{1 - \alpha} \right) + \left( \frac{1 - 1/\alpha^{L_2+1}}{1 - 1/\alpha} \right) - 1} \\
\pi_{i,0} &=& \alpha^i \pi_{0,0} \\
\pi_{0,j} &=& \pi_{0,0}/\alpha^j \;\;  \\
\alpha &=& \frac{(1-p_2)p_1}{(1-p_1)p_2}
\end{eqnarray}\label{thm:optimal-threshold}
\end{theorem}

\begin{citeField}
\begin{proof}
See \cite{opportunitisc-network-coding}.
\end{proof}
\end{citeField}

\begin{proofField}
\begin{proof}
Let $L_1$ and $L_2$ be the thresholds. Our objective is to find their corresponding optimal values. Let $X_i(t)$ be the number of type $i$ packets at the beginning of the $t^{th}$ slot before any arrival or transmission. It is crucial to note that this observation time is different from when the MDP is observed. Then the bivariate stochastic process $\{(X_1(t),X_2(t)), t \ge 0\}$ is a discrete-time Markov chain. The states are $(0,0)$, $(1,0)$, $(2,0)$, $\ldots$, $(L_1,0)$, $(0,1)$, $(0,2)$, $\ldots$, $(0,L_2)$. Define $\alpha$ as a parameter such that
\[ \alpha = \frac{(1-p_2)p_1}{(1-p_1)p_2} . \]
Let $\pi_{i,j}$ be the steady-state probabilities of the Markov chain. The balance equations for $0 < i \le L_1$ and $0 < j \le L_2$ are:
\begin{eqnarray}
\pi_{i,0} &=& \alpha \pi_{i-1,0}  \\
\alpha \pi_{0,j} &=& \pi_{0,j-1}
\end{eqnarray}
Since $\pi_{0,0} + \sum_{i,j} \pi_{i,0} + \pi_{0,j} = 1$, we have
\begin{eqnarray}
\pi_{0,0} &=& \frac{1}{\left( \frac{1 - \alpha^{L_1+1}}{1 - \alpha} \right) + \left( \frac{1 - 1/\alpha^{L_2+1}}{1 - 1/\alpha} \right) - 1} \\
\pi_{i,0} &=& \alpha^i \pi_{0,0} \\
\pi_{0,j} &=& \pi_{0,0}/\alpha^j
\end{eqnarray}
for all $0 < i \le L_1$ and $0 < j \le L_2$.

The expected number of transmissions per slot (we count an individual and a paired transmission using network coding both as one transmission) is
\BEQA
\tau(L_1,L_2) &=& p_1 p_2 \pi_{0,0} + p_2 \sum_{i=1}^{L_1} \pi_{i,0} + p_1 \sum_{j=1}^{L_2} \pi_{0,j} +\nonumber \\
&& p_1 (1-p_2) \pi_{L_1,0} +  p_2 (1-p_1) \pi_{0,L_2}
\EEQA
The average number of packets in the system at the beginning of each slot is
\BEQA
\lambda(L_1,L_2) = \sum_{i=1}^{L_1} i \pi_{i,0} + \sum_{j=1}^{L_2} j \pi_{0,j}
\EEQA
Thus the long-run average cost per slot is
\BEQA
C_t \tau(L_1,L_2) + C_h \lambda(L_1,L_2)
\EEQA
which upon minimizing we get the optimal thresholds $L^*_1$ and $L^*_2$
\end{proof}
\end{proofField}

Whenever $C_h > 0$, it is relatively straightforward to obtain $L^*_1$ and $L^*_2$. Since it costs $C_t$ to transmit a packet and $C_h$ for a packet to wait for a slot, it would be better to transmit a packet than make a packet wait for more than $C_t/C_h$ slots. Thus $L^*_1$ and $L^*_2$ would always be less than $C_t/C_h$. Hence by completely
enumerating between $0$ and $C_t/C_h$ for both $L_1$ and $L_2$, we can obtain $L^*_1$ and $L^*_2$. One could perhaps find faster techniques than complete enumeration, but it certainly serves the purpose.

\section{Proof of Theorem \ref{thm:stationary}} \label{appendix:stationary}
As described earlier it is sufficient to show that the three conditions in Lemma~\ref{stationary} are met. Proposition \ref{prop:finte beta-discount} results in the condition (i), while the condition (ii) on finding an $N$ is also straightforward since all the costs are positive.

Considering the policy of always transmitting $\tilde{\theta}$, the upper bound on $V_{\beta}(i,j)$ can be obtained from (\ref{eq:optimality-eq}) as $C^{(1)}_{i,j} V_{\beta}(1,0)+ C^{(2)}_{i,j} V_{\beta}(0,1) + C^{(3)}_{i,j} V_{\beta}(0,0)$ for some finite-valued $C^{(k)}_{i,j}$. It therefore remains to show that there exist nonnegative finite-valued $M_{1,0}$ and $M_{0,1}$ such that $v_{\beta}(1,0) \leq M_{1,0}$ and $v_{\beta}(0,1) \leq M_{0,1}$. Note that we take $A_n=1$ for the state $(1,1)$, and therefore
\BEQA
V_{\beta}(1,1) = \hat{C} + \hat{\beta}\bigl(\hat{p}_1 V_{\beta}(0,0) + \hat{p}_2 V_{\beta}(1,0) + \hat{p}_3 V_{\beta}(0,1) \bigr),
\EEQA
where $\hat{C}=C_t/(1-\beta \hat{p}_4)$ and $\hat{\beta}=\beta/(1- \beta \hat{p}_4)$. Hence, the upper bound on $V_{\beta}(0,1)$ and $V_{\beta}(1,0)$ can be obtained from (\ref{eq:optimality-eq}) as follows.
\BEQA
V_{\beta}(1,0) &\leq& \frac{C_t+ \beta \hat{p}_4 \hat{C}}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} + \frac{\beta \hat{p}_1 (1+ \hat{\beta} \hat{p}_4 ) V_{\beta}(0,0)}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} \nonumber \\
&&+ \frac{\beta \hat{p}_3 (1+ \hat{\beta} \hat{p}_4) V_{\beta}(0,1)}{1- \beta \hat{p}_{2} (1+ \hat{\beta} \hat{p}_4 )} \label{eq: bound-v01}
\EEQA
\BEQA
V_{\beta}(0,1) &\leq& \frac{C_t+ \beta \hat{p}_4 \hat{C}}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} + \frac{\beta \hat{p}_1 (1+ \hat{\beta} \hat{p}_4 ) V_{\beta}(0,0)}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} \nonumber \\
&&+ \frac{\beta \hat{p}_2 (1+ \hat{\beta} \hat{p}_4) V_{\beta}(1,0)}{1- \beta \hat{p}_{3} (1+ \hat{\beta} \hat{p}_4 )} \label{eq: bound-v10}
\EEQA
Based on (\ref{eq: bound-v01}) and (\ref{eq: bound-v10}), it follows that the condition (iii) is satisfied because there exist some nonnegative finite-valued $M_{0,1}$ and $M_{1,0}$ so that $V_{\beta}(1,0) \leq V_{\beta}(0,0) + M_{1,0}$ and $V_{\beta}(0,1) \leq V_{\beta}(0,0) + M_{0,1}$.

\section{Proof of Theorem \ref{thm:threshold}} \label{appendix:threshold}
Using the same notations as (\ref{eq:optimality-eq}), define $V_{\beta}(i,0) \triangleq \min_{a \in \{0,1\}}V_{\beta,a}(i)$, where $V_{\beta,a}(i)=  C_h ([i-a]^+) + C_t a + \beta \sum_{k,\ell} V_\beta(k,\ell) P_a\bigl((i,j),(k,l)\bigr)$. Let $i^* = \min \{i \in \mathbb{Z}^+: V_{\beta,0}(i) > V_{\beta,1}(i) \}$. Then the optimal stationary and deterministic action (for the total expected $\beta$-discounted cost) is $A_n=0$ for the states $(i,0)$ with $i < i^*$, and $A_n=1$ for the state $(i^*,0)$. Note that we do not care about the states $(i,0)$ with $i>i^*$  since they are not accessible as $(i^*,0)$ only transits to $(i^*-1,0)$, $(i^*,0)$, $(i^*-1,1)$, and $(i^*,1)$. The similar argument is applicable for the states $(j, 0)$.

Thus far we have shown that the threshold-based policy is optimal for the total expected $\beta$-discounted cost. According to \cite{optimal-control-of-batch}, it remains to show that the $V(u)$ in (\ref{gu_fn}) exists while $u$ is applied by a threshold-based policy. Since the steady state probability distribution of the Markov chain (induced from the MDP $\{(Y_n,A_n), n \ge 0\}$ associated with the threshold-based policy) can be computed as in Theorem \ref{thresholdl1l2}, $\lim_{N \rightarrow \infty} E_u[ \sum_{n=0}^N C(Y_n,A_n) | Y_0 = (0,0)]/(N+1)$ will converge \cite{Resnick-book}. The threshold-based policy is therefore also optimal for the long-run average cost.

\section{Proof of Theorem \ref{thm:optimal-threshold}} \label{appendix:optimal-threshold}
Let $L_1$ and $L_2$ be the thresholds. Our objective is to find their corresponding optimal values. Let $X_i(t)$ be the number of type $i$ packets at the beginning of the $t^{th}$ slot before any arrival or transmission. It is crucial to note that this observation time is different from when the MDP is observed. Then the bivariate stochastic process $\{(X_1(t),X_2(t)), t \ge 0\}$ is a discrete-time Markov chain. The states are $(0,0)$, $(1,0)$, $(2,0)$, $\ldots$, $(L_1,0)$, $(0,1)$, $(0,2)$, $\ldots$, $(0,L_2)$. Define $\alpha$ as a parameter such that
\[ \alpha = \frac{(1-p_2)p_1}{(1-p_1)p_2} . \]
Let $\pi_{i,j}$ be the steady-state probabilities of the Markov chain. The balance equations for $0 < i \le L_1$ and $0 < j \le L_2$ are:
\begin{eqnarray}
\pi_{i,0} &=& \alpha \pi_{i-1,0}  \\
\alpha \pi_{0,j} &=& \pi_{0,j-1}
\end{eqnarray}
Since $\pi_{0,0} + \sum_{i,j} \pi_{i,0} + \pi_{0,j} = 1$, we have
\begin{eqnarray}
\pi_{0,0} &=& \frac{1}{\left( \frac{1 - \alpha^{L_1+1}}{1 - \alpha} \right) + \left( \frac{1 - 1/\alpha^{L_2+1}}{1 - 1/\alpha} \right) - 1} \\
\pi_{i,0} &=& \alpha^i \pi_{0,0} \\
\pi_{0,j} &=& \pi_{0,0}/\alpha^j
\end{eqnarray}
for all $0 < i \le L_1$ and $0 < j \le L_2$.

The expected number of transmissions per slot (we count an individual and a paired transmission using network coding both as one transmission) is
\BEQA
\tau(L_1,L_2) &=& p_1 p_2 \pi_{0,0} + p_2 \sum_{i=1}^{L_1} \pi_{i,0} + p_1 \sum_{j=1}^{L_2} \pi_{0,j} +\nonumber \\
&& p_1 (1-p_2) \pi_{L_1,0} +  p_2 (1-p_1) \pi_{0,L_2}
\EEQA
The average number of packets in the system at the beginning of each slot is
\BEQA
\lambda(L_1,L_2) = \sum_{i=1}^{L_1} i \pi_{i,0} + \sum_{j=1}^{L_2} j \pi_{0,j}
\EEQA
Thus the long-run average cost per slot is
\BEQA
C_t \tau(L_1,L_2) + C_h \lambda(L_1,L_2)
\EEQA
which upon minimizing we get the optimal thresholds $L^*_1$ and $L^*_2$

\subsection{Related Work}\label{sec:related}
Network coding research was initiated by seminal work by Ahlswede \emph{et al.} \cite{ACLY00} and since then attracted major interest from the research community. Many initial works on the network coding technique focused on establishing \emph{multicast} connections between a fixed source and a set of terminal nodes.

Network coding technique for wireless networks has been considered by Katabi \emph{et al.} \cite{Our-Sigcomm06}. They propose an architecture called COPE, which contains a special network coding layer between the IP and MAC layers.
In our earlier work \cite{RedSha10}, we showed how to design coding-aware routing controllers that would maximize coding opportunities (and hence reduce the number of transmissions) in multihop networks.  However, in contrast to all the above literature our objective here is to study the delicate tradeoff between transmission costs and waiting costs when network coding is an option.

\subsection{Scenario from a Relay's Perspective}

Consider Figure~\ref{fig:network}(c).  We call two of the adjacent nodes to the relay \emph{R} as nodes 1 and 2. Say there is a flow $f_1$ that goes from node 1 to 2 and another flow $f_2$ from node 2 to 1, both of which are through the relay under consideration. The packets (type 1 and type 2) from both flows respectively go through separate queues, $q_1$ and $q_2$, at node \emph{R}. With respect to the relay we now define a \emph{slot} as the time between successive opportunities for the relay to transmit. In each slot a packet arrives from node $i$ (during its transmission opportunity) to $q_i$ with probability $p_i$ for $i=1,2$. Also, with probability $(1-p_i)$ no packet arrives from node $i$ in a slot. Thus, a maximum of 1 packet arrives from each adjacent node to the relay during a slot (this is according to the network definition and scheduling we described earlier). At the end of a slot, the relay gets an opportunity to transmit.

Notice that at the end of a slot, the relay can transmit a maximum of one packet. When both queues are non-empty, one packet from $q_1$ and one from $q_2$ can be transmitted together as a single packet using XOR coding. This scenario, in which transmitting a combination of packets results in decreasing the required number of transmissions, is referred as a \emph{coding opportunity}. Whenever such a coding opportunity exists between the packets of two flows, the relay encodes the packets and transmits the coded packet back to the adjacent nodes. However, if there is only one type of packet at the end of a slot, there are two options: (a) one of those packets gets transmitted without coding or (b) we wait for a future slot to receive a matching packet in the other queue to utilize the coding opportunity. We assume that transmissions within a type is according to a \emph{first-in-first-out} basis.

Note that
the relay node faces one of three kinds of situations: (i) one packet of one type and at least one packet of another type; (ii) only one type of packet(s); (iii) no packets. The decision in situations (i) and (iii) is straightforward, one would code using XOR in situation (i) and transmit, whereas do nothing in situation (iii). However in situation (ii), it is unclear as to what is the best course of action, do nothing (thus worsening delay) or transmit without coding (thus being inefficient). In other words, to wait or not to wait, that is the question.

\subsection{Markov Decision Process Model}
To develop a strategy for the relay to decide at every transmission opportunity, its best course of action, we use a Makov decision process (MDP) model. For $i=1,2$ and $n = 0, 1, 2, \ldots$, let $Y^i_n$ be the number of packets in queue $i$ at the end of time slot $n$ just before an opportunity to transmit. Let $A_n$ be the action chosen at the end of the $n^{th}$ time slot with $A_n = 0$ implying the action is to do nothing and $A_n = 1$ implying the action is to transmit. As we described before, if $Y^1_n + Y^2_n = 0$, then $A_n = 0$ because that is the only feasible action. Also, if $Y^1_n Y^2_n > 0$, then $A_n = 1$ because the best option is to transmit a coded XOR packet as it both reduces the number of transmissions as well as latency. However, when exactly one of $Y^1_n$ and $Y^2_n$ is non-zero, it is unclear what the best course of action is.

To develop a strategy for that, we first define costs for latency and transmission. Let $C_t$ be the cost for transmitting a packet and $C_h$ be the cost for holding a packet for a length of time equal to one slot. Without loss of generality, we assume that if a packet was transmitted in the same slot it arrived, its latency is zero. Also, the cost of transmitting a coded packet is the same as that of a non-coded packet. That said, our objective is to derive an \emph{optimal policy} that minimizes the \emph{long-run average cost per slot}. For that we define the MDP $\{(Y_n,A_n), n \ge 0\}$ where $Y_n = (Y^1_n,Y^2_n)$ is the state of the \emph{system} and $A_n$ the control action chosen at time $n$. The state space (i.e. all possible values of $Y_n$) is the set $\{(i,j): i \ge 0, j \le 1 \mbox{ or } j \ge 0, i \le 1 \}$.

Let $C(Y_n,A_n)$ be the cost incurred at time $n$ if action $A_n$ is taken when the system is in state $Y_n$. Therefore,
\BEQA
C(Y_n,A_n) = C_h ([Y^1_n-A_n]^+ + [Y^2_n-A_n]^+) + C_t A_n
\EEQA
where $[x]^+ = \max(x,0)$. The long-run average cost for some policy $u$ is given by
\BEQA \label{gu_fn}
V(u) = \lim_{N \rightarrow \infty} \frac{1}{N+1} E_u \left[ \sum_{n=0}^N C(Y_n,A_n) | Y_0 = (0,0) \right]
\EEQA
where $E_u$ is the expectation operator taken for the system under policy $u$. Notice that our initial state is an empty system, although the average cost would not depend on it. Our goal is to obtain the optimal policy $u^*$ that minimizes $V(u)$. For that we first describe the probability law for our MDP and then in subsequent section develop a methodology to obtain the optimal policy $u^*$.

For the MDP $\{(Y_n,A_n), n \ge 0\}$, the probability law can be derived for $i \ge 0$ and $j \ge 0$ as following in terms of $P_a\left(Y_n,Y_{n+1}\right)$, the transition probability from state $Y_n$ to $Y_{n+1}$ associated with action $a\in\{0,1\}$.
\BEQA
\left\{
\begin{array}{l}
P_1\bigl((i,j), ([i-1]^+,[j-1]^+) \bigr) = \hat{p}_1 \\
P_1\bigl((i,j), (\max(i,1),[j-1]^+) \bigr) = \hat{p}_2  \\
P_1\bigl((i,j), ([i-1]^+,\max(j,1)) \bigr) =  \hat{p}_3\\
P_1\bigl((i,j), (\max(i,1),\max(j,1)) \bigr) =  \hat{p}_4  \\
P_0\bigl((i,j), (i,j) \bigr) = \hat{p}_1  \\
P_0\bigl((i,j), (i+1,j) \bigr) = \hat{p}_2  \\
P_0\bigl((i,j), (i,j+1) \bigr) = \hat{p}_3  \\
P_0\bigl((i,j), (i+1,j+1) \bigr) = \hat{p}_4
\end{array}
\right.
\EEQA
where $\hat{p}_1 = (1-p_1)(1-p_2)$, $\hat{p}_2 = p_1(1-p_2)$, $\hat{p}_3= (1-p_1)p_2$, and $\hat{p}_4 = p_1 p_2$. Also note the caveats that: $i$ and $j$ cannot both be greater than 1; if $i = j = 0$, then $A_n = 0$; if $i > 0$ and $j > 0$, then $A_n = 1$.

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

\subsection{Main Results}\label{sec:results}
\input{main-results}

\section{System Overview}\label{sec:overview}
\input{model}

\section{Analysis}\label{sec:analysis}
\input{analysis}

\section{Numerical Experiments and Results} \label{sec:numer}
\input{numericals}

\section{Conclusion}

In this paper we developed  algorithms that explore the delicate tradeoff between waiting and transmitting using network coding.  We started
with the idea of exploring the whole space of history dependent policies, but showed step-by-step how we could move to simpler regimes, finally
culminating in a stationary deterministic queue-length threshold based policy.  The policy is attractive because its simplicity enables us to
characterize the thresholds completely, and we can easily illustrate its performance on multiple networks.  We showed by simulation how the performance of the policy is optimal in the Bernoulli arrival scenario, and how it also does well in other situations such as for line networks.  Our results also have some bearing on the general problem of queuing networks with shared resources that we will explore in the future.

\bibliographystyle{IEEEtran}

\section{Numerical Studies}\label{sec:numerical-1}

In this section we present several numerical results to demonstrate the analytical formulation as well as its extensions.
We study the performance of a number of policies:

\begin{enumerate}
\item Opportunistic Coding:  when a packet arrives, coding is performed if a compatible packet is available, otherwise transmission takes place immediately.
\item Queue-length-based threshold:  a Stationary Deterministic (SD) policy that our analysis suggests it should be optimal for the Bernoulli case.
\item Randomized-Queuelength-based threshold: a Stationary policy that Randomizes (SR) over deterministic policies. We expect that it would not perform any better than deterministic queue-length-based policies.
\item Queue-length-plus-Waiting-time-based thresholds: a History Dependent policy (HR) which is likely to give the best possible performance.
\item Waiting-time-based thresholds: an HR policy that we create for the purpose of comparison to illustrate that history on its own is only of limited value.
\end{enumerate}
We simulate these policies on two different cases: (i) the single relay with Bernoulli arrivals (Figures \ref{Fig:BER55,tradeoff} and \ref{Fig:BER55}) and (ii) a line network with $4$ nodes, in which the sources are Bernoulli (Figure \ref{Fig:LINE55}). Note that in this case, since the departures from one queue determine the arrivals into the other queue, the arrival processes are significantly different from Bernoulli.
Our simulations is done in Java and for each scenario we report the average results of $10^5$ iterations.

Our numerical studies illustrate that, as expected, a deterministic queue-length based policy is optimal for different network scenarios.
The results are intriguing as they suggest that achieving a near-perfect tradeoff between waiting and transmission costs is possible using simple policies; and coupled with optimal network-coding aware routing policies like the one in our earlier work \cite{RedSha10}, have the potential to exploit the positive externalities that network coding offers.


text:
\section{Introduction}
\label{sec:Intro}

Superluminous supernovae (SLSNe) are extremely bright, but rare, supernova-like events, peaking at luminosities in excess of $M_\mathrm{AB}\approx-21$\,mag, around a hundred times greater than classical core-collapse events. While at least two classes of SLSNe have been observationally identified \citep[see][]{GalYam2012,Quimby2011, Inserra2017}, the most common are known as SLSNe-I, or SLSNe-Ic, as they are hydrogen poor \citep{Quimby2011,Inserra2013} and spectroscopically similar to Type Ic supernovae. The power source of SLSNe-I remains unclear, but it is unlikely to be the radioactive decay of $^{56}$Ni\ that powers the light curves of normal SNe \citep[see][]{Chatzopoulos2009,Chomiuk2011,Inserra2013,Papadopoulos2015}. Alternative mechanisms could be the spin down of a rapidly-rotating  magnetar \citep[e.g.,][]{Kasen2010,Woosley2010,Bersten2016}, a pair-instability SN explosion \citep[e.g.,][]{Langer2007,Kasen2011,Kozyreva2017}, the interaction of SN ejecta with circumstellar material \citep[e.g.,][]{Woosley2007,Chevalier2011,Chatzopoulos2012,Chatzopoulos2013}, or the fallback of accreted material onto a compact remnant \citep{Dexter2013}.

Beyond the puzzle of their astrophysical nature, SLSNe are ideal probes of the high-redshift universe because of their high luminosity and long-lived (time-dilated) light curves. With the peak of their energy output in the ultraviolet (UV), redshifted into the optical at high redshift, studies \citep[e.g.,][]{Cooke2012,Berger2012,Howell2013,Pan2017} have detected a few SLSN candidates at $z>1.5$, and suggest that the SLSN rate at such redshifts is a factor of $\sim15$ higher than at low redshifts, possibly tracking the cosmic star-formation rate \citep{Prajs2017}. Therefore, there is significant potential for detecting many more SLSNe to $z\approx 4$ and beyond with forthcoming facilities like the Large Synoptic Survey Telescope \citep[LSST;][]{Scovacricchi2016}, \textit{Euclid} \citep{Inserra2017b}, and the \textit{Wide-Field Infrared Survey Telescope} \citep[\textit{WFIRST};][]{Yan2017}.

High-redshift observations of SLSNe-I can provide additional constraints on the physical processes that drive these events. A typical spectrum of a SLSN-I around maximum light can be well described by a hot, black-body continuum  with broad absorption lines produced by C, O, Si, Mg, and Fe with characteristic velocities of $10{,}000$ to $20{,}000$ km\,s$^{-1}$\ \citep{Quimby2011,Inserra2013}. These lines are especially prominent in the UV spectra of SLSNe-I, with a characteristic turnover at $\sim2900$\,\AA\ where strong line-blanketing from iron-group elements suppresses the black-body flux. These features provide information on the synthesized material and intrinsic metal abundance of the progenitor star, necessary to constrain the physical processes that govern SLSNe-I.

\citet{Yan2017}, using a \textit{Hubble Space Telescope} (\textit{HST}) spectrum of Gaia16apd at $z=0.102$, showed that SLSNe-I exhibit significantly less line blanketing in the UV than any classical-luminosity SN, and hence are likely metal-poor in the outer ejecta. However, given the scarsity of low-redshift SLSNe-I and difficulties of observing in the observer-frame UV, Gaia16apd and the recently discovered SN~2017egm \citep{Dong2017_SN2017egm,Bose_egm2017} are the only SLSNe-I in the local Universe ($z<0.3$) with rest-frame UV spectral information. At $z>1$, observations at optical wavelengths probe the rest-frame UV, presenting an avenue to determine the diversity of SLSNe-I in the UV, and thus provide constraints on progenitor scenarios.

In this paper we present DES16C2nm, a new SLSN-I discovered by the Dark Energy Survey (DES) Supernova Program \citep[DES-SN;][]{Bernstein2012}. At $z=1.998$, DES16C2nm\ is the highest-redshift spectroscopically confirmed SN (of any type) to date. The two SLSN candidates of \cite{Cooke2012} found in Canada-France-Hawaii Telescope Legacy Survey data were not spectroscopically confirmed in real time, but their redshifts ($z=2.05$ and 3.90) were measured from host-galaxy spectra. DES16C2nm\ also supersedes the highest-redshift spectroscopically confirmed Type Ia supernovae (SNe~Ia). For example, \citet{rodney2012} provide strong evidence for a spectroscopically confirmed SN Ia at $z=1.55$ (``SN Primo") detected as part of the \textit{HST} CANDELS project. Classifications of higher-redshift SNe~Ia rely on other information, such as model fits to the photometric light-curve data and/or prior knowledge of the host-galaxy redshift; thus, they do not possess independent spectroscopic confirmations \citep[e.g.,][]{riess2001,jones2013,rodney2014,rodney2016,Rubin2017}.

In Section~\ref{sec:observations}, we provide the observational data used to detect and classify DES16C2nm, while in Section~\ref{sec:analysis} we analyze the UV properties of this SLSN, and compare it to the literature. Section~\ref{sec:discussion} discusses the consequences of this discovery for ongoing and future searches of SLSNe. We summarize our conclusions in Section~\ref{sec:conclusions}. Throughout, we assume H$_0=70$\,km\,s$^{-1}$\,Mpc$^{-1}$ and a flat $\Lambda$CDM cosmology with $\Omega_\mathrm{matter}=0.3$.

\section{Observations}
\label{sec:observations}

DES16C2nm\ was discovered at $\alpha=03^{\mathrm{h}}40^{\mathrm{m}}14\fs83$ and $\delta=-29\arcdeg05\arcmin53\farcs 5$ (J2000) in the first DECam \citep{FlaugherDECam2015} images of the fourth season (Y4) of DES-SN \citep{Bernstein2012}. It was detected with the difference imaging pipeline \citep{Kessler2015} in all passbands ($griz$) taken on 2016 August 22 (all dates herein are UTC) and was not detected in the last DES-SN images taken in the previous season (Y3) on 2016 February 08. DES16C2nm\ did, however, have a marginal detection at $3.3\sigma$ (point source) in $g$-band DECam images taken as part of SUDSS\footnote{``Search Using DECam for Superluminous Supernovae'' (PI: Sullivan)} on 2016 March 9, but was not detected in any other SUDSS image taken at that time. DES16C2nm\ was first designated a transient on 2016 August 27 and monitored in all passbands ($griz$) on an average 7 day cadence by DES-SN until the end of January 2017, when it fell below the detection limit of the single-epoch DES-SN images. Further details of the DES-SN observing strategy and spectroscopic follow-up programs can be found in \citet{DAndreaSpectroscopy}. Information on the DES-SN difference-imaging search pipeline and machine-learning algorithms to identify transient objects can be found in \citet{Kessler2015} and \citet{Goldstein2015}.

Photometric measurements were made using the pipeline discussed by \citet{Papadopoulos2015} and \citet{Smith2016}, which has also been extensively used in the literature \citep[e.g.,][and references therein]{PTFphot}. This pipeline subtracts a deep template image from each individual SN image to remove the host-galaxy light using a point-spread-function (PSF) matching routine. SN photometry is then measured from the difference image using a PSF fitting technique. Figure~\ref{fig:c2nm_lc} shows the full light curve of DES16C2nm\ averaged with a 14-day window for clarity.

The time of maximum light, which varies with wavelength, can be best constrained from our $i$-band data. A third order polynomial fit to the observer-frame fluxes indicates that DES16C2nm\ reached a peak magnitude in the $i$ band of $23.12\pm0.08$ \citep[after correcting for foreground extinction using $E(B-V)=0.014$\,mag;][]{Schlegel1998} on MJD 57639$\pm$14. DES16C2nm\ peaked 33$\pm$21 days earlier at $23.43\pm0.10$ in the $r$ band, and 9$\pm$7 days later at $22.48\pm0.04$ in the $z$ band. The uncertainties on the time of maximum light are driven by the slow photometric evolution of DES16C2nm. In the $g$ band, most of our detections have low signal-to-noise ratio (S/N). Based on the available data, we estimate the $g$-band peak magnitude to be prior to the start of DES Y4 (MJD = 57623.4). The individual photometric measurements are listed in Table~\ref{tab:lc_table} and are also available from the WISeREP archive\footnote{\url{http://wiserep.weizmann.ac.il/}} \citep{WISEREP}.

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig1}
\caption{The photometric data of DES16C2nm\ from DES (filled circles), SUDSS $g$ band (open circle), Gemini/Flamingoes-2 (stars), \textit{HST} (black filled circle), VLT/FORS2 and VLT/HAWKI (crosses). The DES data have been averaged with a 14-day window for clarity.  3$\sigma$ upper limits are shown as downward arrows, and the various epochs of spectroscopy are shown as black upward arrows. The best-fit magnetar model evaluated at $z=1.9982$ (Section~\ref{sec:physical-modelling}) is shown as dashed lines, with the model of \citet{Piro2015} at early times (Section~\ref{sec:early-time}) plotted as dash-dotted lines. The colors correspond to different passbands. The phases presented are relative to peak luminosity in the observer-frame DES $i$ band (MJD = 57639) as highlighted by a black dot-dashed line.
\label{fig:c2nm_lc}}
\end{figure}

DES16C2nm\ was prioritized for follow-up spectroscopy based on its slowly evolving light curve (in both brightness and color). The first spectrum was obtained on 2016 October 09 \citep[][when the object was $i\approx23.0$\,mag]{C2nm_ATEL} at the Magellan-Clay Telescope at the Las Campanas Observatory, using the Low Dispersion Survey Spectrograph (LDSS-3). The spectrum was reduced using standard \texttt{IRAF} routines\footnote{Image Reduction and Analysis Facility,  distributed by the National Optical Astronomy Observatory, which is operated by the Association of Universities for Research in Astronomy (AURA) under a cooperative agreement with the U.S. National Science Foundation.}, and has an effective wavelength
coverage of 4500 to $10{,}000$\,\AA\ (observer frame). This spectrum showed evidence of the \ion{Mg}{2} absorption doublet (2796\,\AA\ and 2804\,\AA\ rest frame) from the host galaxy at 8387\,\AA\ and 8403\,\AA, but at low S/N.

DES16C2nm\ was then spectroscopically reobserved at the European Southern Observatory (ESO) Very Large Telescope (VLT) using the X-SHOOTER instrument on 2016 October 24 and 25, as well as the Keck-II telescope using the DEep Imaging Multi-Object Spectrograph \citep[DEIMOS;][]{Faber2003} instrument on 2016 October 25. These spectra unambiguously confirmed the presence of the \ion{Mg}{2} doublet at 8382\,\AA\ and 8402\,\AA, as well as additional absorption features produced by \ion{Fe}{2} (2344, 2383, 2587, 2600\,\AA\ rest frame). These features confirmed the redshift of DES16C2nm\ as $z=1.9982\pm0.0004$, where the uncertainty is the observed scatter in the redshift estimates obtained from the individual absorption features. Figure~\ref{fig:c2nm_spectra} shows the observer-frame optical spectral series of DES16C2nm\ including an additional spectrum taken at the VLT on 2016 November 22, once the high redshift of DES16C2nm\ was known.

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig2}
\caption{The spectral series of DES16C2nm, with rest-frame phase information (relative to peak luminosity in the observer-frame $i$ band (MJD = 57639)). The spectra have been smoothed (to 10\,\AA, 8\,\AA, 8\,\AA, and 12\,\AA, respectively), adjusted to match the colors from the nearest epoch of $griz$ photometry, and are offset for clarity. Prominent host-galaxy absorption features are labeled in red.
\label{fig:c2nm_spectra}}
\end{figure}

Figure~\ref{fig:c2nm_spectra_redshift} shows the Keck spectrum of DES16C2nm\ 15 rest-frame days after maximum light in $i$-band, highlighting the galaxy absorption features used to determine the redshift. For comparison, we also show the spectrum of iPTF13ajg \citep[a SLSN-I at $z=0.740$][]{Vreeswijk2014} at approximately the same phase (9 days after maximum light) in the light curve. The broad absorption
features at 2200\,\AA, 2450\,\AA, and 2700\,\AA\ (rest frame) are common in SLSN-I spectra around maximum light \citep{Quimby2011,Vreeswijk2014,Mazzali2016} and spectroscopically classify DES16C2nm\ as a SLSN-I at $z=1.9982$.

To constrain the rest-frame optical properties of DES16C2nm, a near-infrared (NIR) spectrum using WFC3/G141 on HST was obtained on 2016 December 20. Information about all spectra can be found in Table~\ref{tab:spec_table}. The spectra are also available from WISeREP.

\begin{figure*}
\centering
\includegraphics[width=0.95\textwidth]{fig3}
\caption{The rest-frame optical spectrum of DES16C2nm\ obtained at Keck-II on 2016 October 25. Prominent galaxy absorption features due to \ion{Mg}{2} and \ion{Fe}{2} are labeled in red. Also shown is a spectrum of iPTF13ajg \citep[$z=0.740$;][]{Vreeswijk2014} at a similar phase in the light curve. A velocity shift of 3{,}000\,km\,s$^{-1}$ has been applied to the iPTF13ajg spectrum as discussed in Section~\ref{subsec:uvspec}. Key spectral features from the SN identified by \citet{Mazzali2016} and discussed in Section~\ref{subsec:uvspec} are highlighted with downward arrows.
\label{fig:c2nm_spectra_redshift}}
\end{figure*}

Once the high redshift of DES16C2nm\ was established, further follow-up observations, including NIR imaging from \textit{HST}, Gemini/Flamingos-2, and VLT/HAWK-I and optical imaging from VLT/FORS2 (detailed in Table~\ref{tab:lc_ancilliary_table}), were obtained. Reductions of the \textit{HST}, VLT/HAWK-I, and VLT/FORS2 data were performed using the standard pipelines provided by the various observatories, with the Gemini/Flamingos-2 data reduced using the THELI pipeline \citep{Theli_Erben2005,Theli_Schirmer2013}, following standard procedures outlined by \citet{Theli_Schirmer2013}. Magnitudes were estimated using \texttt{SEXTRACTOR} \citep{Bertin1996}. These ancillary photometric data are shown in Figure~\ref{fig:c2nm_lc}.

The host galaxy of DES16C2nm\ is detected in stacked images from DES Science Verification (SV) that contain no SN light. Using \texttt{SEXTRACTOR}, we measure host-galaxy AB magnitudes (\texttt{MAG\_AUTO}) of $g$, $r$, $i$, $z$ = $24.98\pm0.13$, $25.64\pm0.32$, $24.85\pm0.19$, and $24.42\pm0.17$, respectively (after correcting for Galactic extinction). Using the \texttt{Z-PEG} photometric-redshift software \citep{LeBorgne2002}, we estimate the stellar mass of the host galaxy to be $\log(M/\ensuremath{\mathrm{M}_{\sun}})=10.1^{+0.7}_{-1.2}$ and a star-formation rate (SFR) of  $\log(\mathrm{SFR}/\ensuremath{\mathrm{M}_{\sun}}\,\mathrm{yr}^{-1})=1.3^{+0.2}_{-0.9}$, assuming a \citet{Kroupa2001} initial mass function and fixing the redshift at $z=1.998$. The host galaxy of DES16C2nm\ is not detected in any existing NIR catalogues, necessary to reliably constrain the continuum flux and metallicity at $z=2$. Despite this, these host-galaxy properties are consistent with the properties of other, lower-redshift SLSN-I host galaxies as seen in DES \citep{Papadopoulos2015,Smith2016,Pan2017} and in the literature \citep[e.g.,][]{Neill2011,Lunnan2014,Leloudas2015,Perley2016,Angus2016,Chen2017}.

\section{Analysis}
\label{sec:analysis}

The high redshift of DES16C2nm\ provides an opportunity to study the rest-frame UV properties of SLSNe-I, and, by comparing to literature events, to study their diversity and possible evolution with redshift. We first consider the photometric properties of DES16C2nm\ compared with other SLSNe-I in the literature. Phases given are relative to peak luminosity in the observer-frame $i$ band (MJD = 57639).

\subsection{Rest-Frame UV Light Curve}
\label{sec:rest-frame}

We use a standard $K$-correction procedure to estimate the rest-frame light curve of DES16C2nm. Figure~\ref{fig:c2nm_filter_response} shows the rest-frame wavelength range covered by our data collected on DES16C2nm, compared to the rest-frame ($z=0$) \textit{Swift} \citep{Gehrels2004, Roming2005, Poole2008, Breeveld2011} and Johnson \citep{Bessell1990} filters. This figure illustrates that the rest-frame $uvw2$ ($\lambda_{\mathrm{eff}}=2080$\,\AA), $uvm2$ (2255\,\AA), $uvw1$ (2615\,\AA), $U$ (3605\,\AA), $B$ (4413\,\AA), and $V$ (5512\,\AA) passbands roughly correspond to the observer-frame $g$, $r$, $i$, $z$, $J$, and $H$ passbands (respectively) for DES16C2nm. As our VLT and \textit{HST} spectra have limited wavelength coverage and do not overlap, we use the spectra of Gaia16apd \citep{Yan2017} at maximum light for $K$-corrections to the light curve of DES16C2nm. This spectrum is similar to that of DES16C2nm\ and is the only available spectrum of a SLSN-I that covers the full spectral range probed by the photometry of DES16C2nm\ (1200 to 8700\,\AA; Figure~\ref{fig:c2nm_filter_response}). To test the validity of this approach, we measure the scatter in the inferred absolute magnitude of DES16C2nm\ when using the maximum-light spectrum of Gaia16apd compared to the spectra of DES16C2nm, PS1-11bam \citep{Berger2012}, iPTF13ajg \citep{Vreeswijk2014}, SNLS06-D4eu \citep{Howell2013}, SCP06F6 \citep{Barbary2009}, and Gaia16apd \citep{Yan2017} after maximum light. These are the only literature SLSNe-I with spectra extending below 2000\,\AA in the rest-frame. We find standard deviations of 0.39 (in the $uvw2$ filter), 0.08 ($uvm2$), 0.16 ($uvw1$), 0.15 ($U$), 0.01 ($B$), and 0.14 ($V$)\,mag between the $K$-corrections determined using the spectrum of Gaia16apd at peak and the available literature spectra. No evidence of increased scatter is seen as a function of phase. These $K$-correction uncertainties are added in quadrature to the measured uncertainties of the rest-frame light curve of DES16C2nm\ and comparison literature events. Early-phase data ($<60$ days pre-peak) are $K$-corrected using a black body of $27{,}000$\,K, as discussed in Section~\ref{sec:early-time}.

At each epoch in the main light curve, we adjust the spectrum of Gaia16apd so that its synthetic photometry matches the observed photometry of DES16C2nm\ at $z=1.9982$ and calculate the cross-filter $K$-correction required to determine the rest-frame magnitudes in the filters listed above. We fit a polynomial function to the resulting rest-frame light curves, shown in Figure~\ref{fig:c2nm_restframe}, and determine peak absolute magnitudes of $uvm2=-21.41\pm0.10$, $uvw1=-21.69\pm0.07$, and $U=-22.28\pm0.04$ (AB). DES16C2nm\ is most luminous (in integrated flux) in the rest-frame $U$ band, and is one of the brightest SLSNe-I (at peak) discovered so far; only iPTF13ajg \citep{Vreeswijk2014} is brighter at peak ($U=-22.47$\,mag) using the same methodology. The phase of maximum light is statistically consistent for all three filters. We do not have sufficiently high-quality data around maximum light in the rest-frame $B$ and $V$ bands to make similar measurements.

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig4}
\caption{The rest-frame wavelength coverage for our observations of DES16C2nm. Our observed $g$, $r$, $i$, $z$, $Y$, $J$, and $F160W$ filters are shown as dashed lines but shifted back to the rest frame assuming $z=1.9982$. The solid lines are the rest-frame  \textit{Swift} $uvw2$, $uvm2$, $uvw1$, and Johnson $U$, $B$, $V$ filters. Our VLT and \textit{HST} spectra of DES16C2nm\ (at +15\,d and +34\,d, respectively) are shown in black with the composite spectrum of Gaia16apd (at maximum light) shown in orange. The filter pairs used for the cross-filter $K$-corrections (e.g., the DES $i$ band $\rightarrow$ $uvw1$) are plotted in the same color. The DES $z$ band is used to correct to rest-frame $U$ owing to the larger dataset around maximum light.
\label{fig:c2nm_filter_response}}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig5}
\caption{The rest-frame ($uvw2$, $uvm2$, $uvw1$, $U$, $B$, $V$) light curves of DES16C2nm. Magnitudes are estimated with a standard $K$-correction procedure, using the spectrum of Gaia16apd for the main light curve and a black body of 27{,}000\,K for the early-time data (see Sections~\ref{sec:rest-frame} and~\ref{sec:early-time}). Uncertainties are determined from the observer-frame light curve and include a filter-dependent $K$-correction uncertainty (see Section~\ref{sec:rest-frame}) added in quadrature. 3$\sigma$ upper limits are denoted with arrows. For clarity, the $uvm2$ and $uvw1$ data points have been offset by $-1$ and +1 day, respectively. The best-fit magnetar model (Section~\ref{sec:physical-modelling}) is shown as dashed lines, with the model of \citet{Piro2015} at early times (Section~\ref{sec:early-time}) plotted as a dash-dotted line.
\label{fig:c2nm_restframe}}
\end{figure}

\subsection{Physical Modeling}
\label{sec:physical-modelling}

The light curves of SLSNe-I are well described by the spin-down of a rapidly rotating magnetar \citep{Inserra2013,Papadopoulos2015,Smith2016}. We fit this model \citep[as described in Appendix D of][]{Inserra2013} to the observer-frame fluxes of DES16C2nm\ around maximum light ($-20<$ phase $<60$ days), fitting all filters simultaneously and show the best-fitting magnetar model in Figures~\ref{fig:c2nm_lc} and~\ref{fig:c2nm_restframe}. The best-fit model has an initial spin period of $P_\mathrm{ms}=1.33\pm0.18$\,ms, an initial magnetic field strength of $B_{14}=0.68\pm0.07\times 10^{14}$\,G, and a diffusion timescale of $\tau_\mathrm{m}=39.62\pm8.28$\,days assuming an opacity of $\kappa=0.1$ and an explosion energy of $10^{51}$erg. From these parameter values, we infer an ejecta mass of $M_\mathrm{ej}=6.23\pm2.45\,\ensuremath{\mathrm{M}_{\sun}}$. The best fitting model has $\chi_{\textrm{red}}^2=4.4$, suggesting that while the model is a good match to the light-curve and color evolution of DES16C2nm\, it does not capture the full variation, potentially due to the strong UV absorption observed in the spectral series of DES16C2nm\  (Figure~\ref{fig:c2nm_spectra}). These inferred parameters are consistent with the modeling of other SLSNe-I in the literature, such as SN2011kf \citep[e.g.][]{Nicholl2017}.

\subsection{Early-Time Data}
\label{sec:early-time}

DES16C2nm\ was first observed with a significance of 3.3$\sigma$ in SUDSS $g$-band imaging and 2.7$\sigma$ in $r$-band imaging on 2016 March 9, 61 rest-frame days prior to maximum light.  No other 3$\sigma$ detections are found in the previous 2\,yr of DES imaging.  While this detection is at low significance,  it is consistent in phase with the precursor peaks observed in other SLSNe \citep{Smith2016,Nicholl2015,Leloudas2012}. In particular, LSQ14bdq \citep{Nicholl2015} showed a bright and relatively fast precursor peak, 60 rest-frame days prior to the peak of the main SLSN. These precursors have peak temperatures of $\sim25{,}000$\,K and cool rapidly, with typical timescales of 15 rest-frame days \citep{Smith2016}, and are well modeled as shock cooling from extended material around the progenitor star \citep{Ofek2010,Piro2015}.

Considering a black body, the observer-frame $g$ and $r$-band fluxes of the precursor detection are best fit by a temperature and radius of $25{,}000$\,K and $7\times{10}^{14}$\,cm, respectively, consistent with values determined from other literature events \citep{Smith2016,Nicholl2015} and when all available photometric measurements ($g$, $r$, $i$, and $z$ band) are considered. Finally, in Figure~\ref{fig:c2nm_restframe}, we compare the rest-frame luminosity of this epoch with a shock-cooling model from \citet{Piro2015} with parameters consistent with those obtained for the light curve of LSQ14bdq \citep{Smith2016}. For this epoch, $K$-corrections are determined using the best-fitting black body with $27{,}000$\,K. The precursor epoch  has a peak luminosity comparable to the main light curve in $uvw2$ ($\lambda_{\textrm{eff}}=2600$\,\AA) and is consistent with the \citet{Piro2015} model of shock cooling from extended material (dash-dotted line).

\subsection{Comparison to Literature Events}
\label{sec:fuv_luminosity}

In Figures~\ref{fig:c2nm_restframe_comp} and~\ref{fig:c2nm_restframe_comp_color}, we compare the rest-frame UV light curves of DES16C2nm\ to SLSNe-I in the literature. Figure~\ref{fig:c2nm_restframe_comp} compares the rest-frame \textit{Swift} $uvw1$ light curve of DES16C2nm\ to SLSNe-I at low ($z<1$) and high ($z>1$) redshift. All SLSNe-I have been $K$-corrected with the procedure described for DES16C2nm\ using the observed filter having an effective wavelength closest to 2615\,\AA\ (the central wavelength of \textit{Swift} $uvw1$). Uncertainties due to our $K$-correction procedure are included for all events.

While the number of low-redshift SLSNe-I is small owing to the low intrinsic rate of these events and the limited volume probed, there is evidence of a homogeneous sample of SLSNe-I with similar peak luminosity distributions and evolution. The UV luminosity (at $\lambda_{\mathrm{eff}}=2615$\,\AA) of DES16C2nm\ is consistent with other SLSNe-I in the literature, including Gaia16apd at $z=0.102$. The exceptions are PTF11rks, which is known to be underluminous in all filters \citep{Inserra2013}, and SN~2015bn, which has been shown to evolve more slowly (photometrically and spectroscopically) than other events \citep{Nicholl2016a}. The remaining objects exhibit a scatter of $<0.3$\,mag at peak.

There is some evidence that the light curve of DES16C2nm\ is broader than other literature events, but this may be caused by uncertainties in the estimate of maximum light (4 rest-frame days; Section~\ref{sec:observations}), as the light curve shows little evolution around maximum light at these wavelengths. Further, with observations preferentially in the rest-frame optical, the time of maximum light for low-redshift SLSNe-I is typically estimated in the rest-frame $U$ band. DES16C2nm\ peaks 14$\pm$7 days after our fiducial estimate of maximum light in $U$-band.  At high redshift ($z>1$), the scatter in the luminosity distribution of the SLSNe-I is larger, but all events have $-22.1 < M_{uvw1} < -21.1$\,mag at peak (i.e., a scatter of $<1$\,mag). This includes the photometrically classified SN2213-1745 \citep{Cooke2012}, which has a host-galaxy spectroscopic redshift of 2.05. No evidence of a difference in the mean peak luminosity of SLSNe-I at high and low redshifts is observed, with $M_\textrm{peak}=-21.61\pm0.48$ and $M_\textrm{peak}=-21.40\pm0.29$\,mag, respectively.

Figure~\ref{fig:c2nm_restframe_comp_color} shows the rest-frame \textit{Swift} $uvm2-uvw1$ color evolution of SLSNe-I at low ($z<1$) and high ($z>1$) redshifts. In this analysis,
we follow the procedure described above, obtaining $K$-corrections for $uvm2$ and $uvw1$ from different observed filters. In all cases, SLSNe-I show little scatter in their rest-frame UV color near maximum light, with a scatter of $<1$\,mag, and they exhibit little evidence of significant color evolution ($\Delta \text{color} < 1$\,mag) around maximum light ($\pm10$ days).
At all redshifts, the majority of SLSNe-I have $uvm2-uvw1>0$\,mag at maximum light. From this analysis, there is no indication that SLSNe-I at high redshift exhibit different colors, or evolve differently, from those at lower redshifts.

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig6}
\caption{The $uvw1$ light curve of DES16C2nm compared to literature events at low ($z<1$; top panel) and high ($z>1$; lower panel) redshifts. $K$-corrections have been determined using the spectrum of Gaia16apd around maximum light as discussed in the text. An average of the available light curves is overplotted in black. Data for the literature objects are from various sources \citep{Chomiuk2011,Berger2012,Cooke2012,Inserra2013,Howell2013,Vreeswijk2014,Nicholl2016a,Yan2017,Pan2017}.
\label{fig:c2nm_restframe_comp}}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.95\textwidth]{fig7}
\caption{The rest-frame $uvm2-uvw1$ color evolution of DES16C2nm compared to literature events at low ($z<1$; top panel) and high ($z>1$; lower panel) redshifts. The color is determined by requiring observations in two distinct filters, as discussed in the text. Data for the literature objects are from various sources \citep{Chomiuk2011,Berger2012,Cooke2012,Inserra2013,Howell2013,Nicholl2016a,Yan2017,Pan2017}.
\label{fig:c2nm_restframe_comp_color}}
\end{figure}

\subsection{Rest-Frame UV Spectral Evolution}
\label{subsec:uvspec}

We now consider the spectral diversity and evolution of SLSNe-I compared to DES16C2nm. Figure~\ref{fig:c2nm_spectra_comp} shows a temporal series of UV spectra of DES16C2nm\ compared to other UV spectral data from the literature. As optical observations at $z>1$ probe the rest-frame UV spectrum, the vast majority of SLSNe-I with available rest-frame UV data around maximum light are at $z>1$, and in particular $z>1.5$. At $z<1$, only Gaia16apd has rest-frame spectral data below 1800\,\AA.

At $\lambda>2000$\,\AA, the vast majority of SLSNe-I exhibit strong absorption features at $\sim2200$\,\AA\ \citep[identified as a blend of \ion{C}{3}, \ion{C}{2}, and \ion{Ti}{3} by][]{Mazzali2016}, at $\sim2400$\,\AA\ (identified as \ion{C}{2}, \ion{Ti}{3}, and \ion{Si}{2}), and at $\sim2650$\,\AA\ (identified as \ion{Mg}{2} and \ion{C}{2}). These features are ubiquitous to all SLSNe-I, with the exception of SNLS-06D4eu and DES15E2mlf, which only exhibit absorption at $\sim2200$\,\AA. These spectra are modeled by \citet{Mazzali2016} to have higher temperatures ($\sim18{,}000$\,K) than canonical events (such as iPTF13ajg, with $T\approx12{,}000$\,K). At these temperatures, in the \citet{Mazzali2016} model, \ion{C}{2} and \ion{Mg}{2} are ionised to \ion{C}{3} and \ion{Mg}{3}, respectively. The absence of \ion{C}{2} and \ion{Mg}{2} reduces absorption at $\sim2400$\,\AA\ and $\sim2650$\,\AA, but the presence of \ion{C}{3} preserves the absorption feature at $\sim2200$\,\AA. The higher intrinsic temperature of these SLSNe results in higher expansion velocities, resulting in the observed absorption features being blueshifted relative to other events. With higher intrinsic temperatures, the black bodies for these events peak at bluer wavelengths than for lower-temperature SLSNe, such as iPTF13ajg.

For events where absorption at $\sim2200$\,\AA, $\sim2400$\,\AA, and $\sim2650$\,\AA\ is seen, there is no evidence of evolution or significant diversity in the strength of these lines around maximum light, consistent with the $uvw1$ luminosity distribution determined in  Figure~\ref{fig:c2nm_restframe_comp}. The spectra of DES16C2nm\ are consistent with those of literature SLSNe-I, with some evidence of a lower strength in the $\sim2400$\,\AA\ absorption feature. However, Figure~\ref{fig:c2nm_spectra_comp} suggests diversity in the observed velocity distribution of SLSNe-I. \cite{Liu2017} measured the photospheric velocity evolution of SLSNe-I, from the \ion{Fe}{2} 5169\,\AA\ feature. They show that SLSNe velocities range from $10{,}000$ to $20{,}000$ km\,s$^{-1}$\ around maximum light, before falling linearly at phases greater than 10 days after peak. This  result is consistent with that found by \citet{Chomiuk2011} and \citet{Inserra2013}, and matches the dispersion observed in Figure~\ref{fig:c2nm_spectra_comp}. At comparable phases, DES16C2nm\ shows a lower velocity than Gaia16apd and reveals no evidence of velocity evolution in the $\sim2650$\,\AA\ feature (see also Figure~\ref{fig:c2nm_spectra}), but is consistent with the velocity evolution of other events, such as iPTF13ajg. Considering all available spectra, we find no evidence of a correlation between line velocity and far-UV (FUV) luminosity or color (see Section~\ref{sec:fuv_luminosity}).

Below $\lambda<2000$\,\AA\ all events exhibit absorption at $\sim1950$\,\AA, determined to be a blend of \ion{Fe}{3} and \ion{Co}{3}, and an additional feature at $\sim1700$\,\AA, tentatively identified as \ion{Al}{3} and \ion{Si}{3} by \citet{Mazzali2016}.  For SLSNe-I with higher intrinsic temperatures, such as SNLS-06D4eu and DES15E2mlf, the black body peaks in this wavelength range. There is no evidence of varying absorption at $\lambda<$2000\,\AA\, so the diversity in this wavelength range is primarily driven by differences in the underlying temperature distribution.

\begin{figure}
\centering
\includegraphics[width=0.90\textwidth]{fig8}
\caption{The FUV spectroscopic evolution of SLSNe-I. A rest-frame UV spectral time series of DES16C2nm\ and compiled literature SLSNe-I as a function of phase from maximum light. Low-redshift ($z<1$) SLSNe-I are plotted with dashes, while high-redshift ($z>1$) events are shown as solid lines. The spectra have been smoothed and offset for clarity. Key spectral features from the SNe identified by \citet{Mazzali2016} and discussed in Section~\ref{subsec:uvspec} at 267, 240, and 220\,nm are highlighted with vertical lines. \textit{Swift} filter responses are also shown to highlight the effective wavelength coverage probed by these spectra compared to the photometric analysis in Figures~\ref{fig:c2nm_restframe_comp} and ~\ref{fig:c2nm_restframe_comp_color}. Data for the literature objects are from various sources \citep{Barbary2009,Berger2012,Howell2013,Vreeswijk2014,Yan2017,Pan2017}.
\label{fig:c2nm_spectra_comp}}
\end{figure}

\section{Discussion}
\label{sec:discussion}

\subsection{Rest-Frame UV: Implications for High-Redshift Searches}

The discovery and spectroscopic confirmation of SLSNe-I at $z=2$ provides unique insights into how to identify such events at higher redshifts. With lower metallicities and younger stellar populations at $z>2$, these studies are key to distinguishing whether SLSNe-I show diversity with respect to the metallicity, mass, or age of the stellar population, thereby constraining progenitor scenarios. Observations of SLSNe-I at $z>2$ open an avenue to measuring the interstellar medium \citep[ISM;][]{Berger2012} in distant galaxies, measuring cosmological parameters beyond the reach of SNe~Ia \citep{Inserra2014}, and finding the explosions of Population III stars \citep{Cooke2012}.

At low redshift, SLSNe-I are typically identified by their blue color, driven by their spectral energy distribution (SED) peaking in the rest-frame $U$ band, and by their long-duration light curves. However, as discussed in Section~\ref{subsec:uvspec}, at higher redshifts, the $U$-band flux is redshifted toward redder filters, and the rest-frame UV and FUV become prominent in the selection. At $z=2$, the rest-frame $U$-band flux is no longer visible in optical filters (Figure~\ref{fig:c2nm_filter_response}), and only the UV flux is observed in optical searches. Figure~\ref{fig:c2nm_restframe} characterizes the UV properties of DES16C2nm, highlighting that in the UV, significant absorption and a turnover in the black body result in reduced flux in the FUV, compared to the optical, with decreasing flux toward the Lyman limit. The consequence of this is that at high redshift ($z>1.5$), SLSNe-I have a characteristic red observer-frame color and long-duration light curves.

To identify SLSNe-I at $z>2$ requires information on the UV spectrum and evolution. As highlighted in Section~\ref{subsec:uvspec}, data in this wavelength range are sparse, with only DES16C2nm, Gaia16apd, PS1-11bam, and DES15E2mlf having data that extend to $\lambda<1700$\,\AA. Figure~\ref{fig:slsn_mag_col_evol} shows the luminosity and color evolution of SLSNe-I at maximum light inferred from these spectra as a function of redshift. The spectra have been normalized and adjusted to the peak magnitude and color of each event. These spectra are then redshifted between 0 and 4, and integrated through the DECam $r$ and $z$ passbands. Figure~\ref{fig:slsn_mag_col_evol} shows the evolution in luminosity and color for these spectra, along with other events in the literature. Where required, $K$-corrections have been determined from the spectrum of Gaia16apd. The single-epoch 5$\sigma$ magnitude limits of the DES deep and shallow fields are shown along with those expected for LSST wide-field and deep-drilling fields \citep{Scovacricchi2016,ScolnicPrivate}. These limits suggest that in a single epoch, DES can detect SLSNe-I that are spectroscopically similar to Gaia16apd and DES16C2nm, to $z=3.2$ in $z$-band observations of its deep fields or $z=3.8$ for objects that are spectroscopically similar to DES15E2mlf. For the LSST deep-drilling fields, the maximum redshifts in the $z$ band are 3.5 for the DES16C2nm\ spectrum and 4.3 when considering the DES15E2mlf spectrum.

This analysis can be extended to the observer-frame NIR, where surveys such as \textit{Euclid} \citep[with 5$\sigma$ limiting magnitude per visit $J\approx24.1$ in the deep fields and an irregular cadence of 10 visits to each  of two fields in a 6-month observing window for 5\,yr;][]{Inserra2017b} and \textit{WFIRST} \citep[limiting magnitude per exposure, $J=22.4$, 24.6,  and 26.2, and a regular cadence of 5 days;][]{Hounsell2017} will search for high-redshift SLSNe-I. An object spectrally similar to DES16C2nm\ can be detected to $z=3.7$ with \textit{Euclid} and $z=1.4$, 4.4, and 6.6 in the \textit{WFIRST} shallow, medium, and deep surveys, respectively.

From the lower panel of Figure~\ref{fig:slsn_mag_col_evol}, SLSNe-I in the literature are usually characterized as being observationally blue at low redshift, with all but one event having $r-z<0$\,mag at $z<1$. This is well matched by the optical and NIR spectrum of Gaia16apd. At intermediate redshifts ($z\approx1.5$), where the $z$ band probes the peak of the black-body emission in the rest-frame $U$ band, and the $r$ band probes the absorption triplet at $\lambda\approx2500$\,\AA, SLSNe-I in the literature are red with $0.0<r-z<0.5$\,mag. The sole exception is the intrinsically hot, and therefore bluer, DES15E2mlf, which still has $r-z>0$\,mag.

The lower panel of Figure~\ref{fig:slsn_mag_col_evol} provides a diagnostic to identify SLSNe-I at $z>2$. In this redshift range, the available spectra, which are warped to be consistent with available photometry, all indicate that SLSNe-I have $r-z>0.5$\,mag at maximum light, with increasing color as a function of redshift. This observation is in good agreement with DES16C2nm\ and the photometrically classified SN2213-1745 at $z=2.05$ \citep{Cooke2012}.

At $z>2$, SLSNe-I will have characteristic observer-frame timescales of $\sim6$ months, with little luminosity evolution over this time. This, combined with the magnitude and color evolution described above, will enable the robust identification of these events from existing datasets, such as DES, HSC, PS1, SNLS, and SDSS, and upcoming facilities such as LSST, \textit{Euclid}, and \textit{WFIRST}. Given the slow evolution of SLSNe-I and time-dilation effects at high redshift, these estimates are conservative. Current and upcoming surveys will be able to combine single-epoch images over month-long timescales to obtain deep stacks with which to identify SLSNe-I to $z>4$.

\begin{figure}
\centering
\includegraphics[width=0.90\textwidth]{fig9}
\caption{The observer-frame evolution of SLSNe-I. \textit{Upper panel}: The apparent $r$-band evolution of SLSNe-I
as a function of redshift. DES16C2nm\ is shown as a purple star, with literature SLSNe-I in orange and the photometrically
confirmed objects of \citet{Cooke2012} shown as black crosses. Values determined from the maximum-light
spectrum of Gaia16apd, normalized to the peak magnitude of Gaia16apd, are shown in blue, with the
corresponding DES16C2nm\ spectrum from VLT in red and DES15E2mlf in green. $K$-corrections for literature events
have been determined using the Gaia16apd spectrum. The magnitude limits for the DES deep and shallow
fields and LSST wide-field and deep-drilling fields are also shown. \textit{Second panel}: As above, only for the $z$ band. \textit{Third panel}: The $J$-band evolution of SLSNe-I as a function of redshift. The magnitude limits for the \textit{Euclid} and \textit{WFIRST} shallow, medium, and deep surveys are also shown. \textit{Lower panel}: The $r-z$ color evolution
of SLSNe-I as a function of redshift as inferred from the upper two panels.  A horizontal line of  $r-z=0$\,mag highlights the difference between low ($z<1$) and high ($z>1$) redshift events.
\label{fig:slsn_mag_col_evol}}
\end{figure}

\section{Conclusions}
\label{sec:conclusions}

The first confirmation of a SLSN-I at $z=2$ provides new insights into these ultraluminous events. The spectroscopic similarity between DES16C2nm\ at $z=1.9982$, iPTF13ajg at $z=0.740$, and Gaia16apd at $z=0.102$ highlights that these events exist at all redshifts, and show little evolution with cosmic time. Comparing the UV luminosity and color evolution of SLSNe-I at a range of redshifts, we find no evidence of a difference in mean luminosity or color between SLSNe-I at high and low redshift. After maximum light, these events show similar spectroscopic features in the UV in the range 2000--3000\,\AA.

The enormous luminosity of these events means that it is theoretically possible to discover and monitor them to $z>4$. However, at $z>1.5$ identifying these objects requires an understanding of the FUV spectra of SLSNe-I, for which only a handful of objects exist. In its first 4\,yr of operations, DES has discovered and spectroscopically confirmed the two highest-redshift SLSNe-I to date. These objects show differing levels of absorption in the rest-frame UV at $\lambda<2000$\,\AA, but the implications from both events are clear: SLSNe-I are identified by their blue intrinsic colors at low redshift, while at the highest redshifts ($z>1.5$) these events are observationally red.  The next challenges for surveys such as DES, HSC, LSST, \textit{Euclid}, and \textit{WFIRST} is to discover and spectroscopically confirm these objects to $z>3$.

\acknowledgments
\section*{Acknowledgements}

This paper has gone through internal review by the DES collaboration. It has Fermilab Preprint number PUB$-$17$-$380$-$AE.

We acknowledge support from EU/FP7-ERC grant 615929. R.C.N. would like to acknowledge support from STFC grant ST/N000688/1 and the Faculty of Technology at the University of Portsmouth. L.G. was supported in part by the U.S. National Science Foundation (NSF) under grant AST-1311862. P.J.B.'s work on SLSNe is supported by the {\it Swift} GI program through grant NNX15AR41G. A.V.F.'s group is grateful for financial assistance from the TABASGO Foundation, the Christopher R. Redlich Fund, and the Miller Institute for Basic Research in Science (U.C. Berkeley). We also thank the anonymous referee for comments.

Based in part on data obtained from the ESO Science Archive Facility under programs 298.D-5010 and 198.A-0915.
Based in part on observations obtained at the Gemini Observatory, under program GS-2016B-DD-6, which is operated by the Association of Universities for Research in Astronomy, Inc., under a cooperative agreement with the NSF on behalf of the Gemini partnership: the NSF (United States), the National Research Council (Canada), CONICYT (Chile), Ministerio de Ciencia, Tecnolog\'{i}a e Innovaci\'{o}n Productiva (Argentina), and Minist\'{e}rio da Ci\^{e}ncia, Tecnologia e Inova\c{c}\~{a}o (Brazil).
Based in part on observations made with the NASA/ESA {\it Hubble Space Telescope}, obtained at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. These observations are associated with program GO-14899.

Based in part on observations at Cerro Tololo Inter-American Observatory, National Optical Astronomy Observatory, which is operated by the Association of Universities for Research in Astronomy (AURA) under a cooperative agreement with the NSF.
Some of the data presented herein were obtained at the W.M. Keck
Observatory, which is operated as a scientific partnership among the
California Institute of Technology, the University of California, and
NASA; the observatory was made possible by the generous financial
support of the W.M. Keck Foundation. We also acknowledge the help of
T. G. Brink in obtaining the Keck spectrum.

This research used resources of the National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231.

Funding for the DES Projects has been provided by the U.S. Department of Energy, the U.S. NSF, the Ministry of Science and Education of Spain,
the Science and Technology Facilities Council of the United Kingdom, the Higher Education Funding Council for England, the National Center for Supercomputing
Applications at the University of Illinois at Urbana-Champaign, the Kavli Institute of Cosmological Physics at the University of Chicago,
the Center for Cosmology and Astro-Particle Physics at the Ohio State University,
the Mitchell Institute for Fundamental Physics and Astronomy at Texas A\&M University, Financiadora de Estudos e Projetos,
Funda{\c c}{\~a}o Carlos Chagas Filho de Amparo {\`a} Pesquisa do Estado do Rio de Janeiro, Conselho Nacional de Desenvolvimento Cient{\'i}fico e Tecnol{\'o}gico and
the Minist{\'e}rio da Ci{\^e}ncia, Tecnologia e Inova{\c c}{\~a}o, the Deutsche Forschungsgemeinschaft and the Collaborating Institutions in the Dark Energy Survey.

The Collaborating Institutions are Argonne National Laboratory, the University of California at Santa Cruz, the University of Cambridge, Centro de Investigaciones Energ{\'e}ticas,
Medioambientales y Tecnol{\'o}gicas-Madrid, the University of Chicago, University College London, the DES-Brazil Consortium, the University of Edinburgh,
the Eidgen{\"o}ssische Technische Hochschule (ETH) Z{\"u}rich,
Fermi National Accelerator Laboratory, the University of Illinois at Urbana-Champaign, the Institut de Ci{\`e}ncies de l'Espai (IEEC/CSIC),
the Institut de F{\'i}sica d'Altes Energies, Lawrence Berkeley National Laboratory, the Ludwig-Maximilians Universit{\"a}t M{\"u}nchen and the associated Excellence Cluster Universe,
the University of Michigan, the National Optical Astronomy Observatory, the University of Nottingham, The Ohio State University, the University of Pennsylvania, the University of Portsmouth,
SLAC National Accelerator Laboratory, Stanford University, the University of Sussex, Texas A\&M University, and the OzDES Membership Consortium.

The DES data management system is supported by the U.S. NSF under grants AST-1138766 and AST-1536171.
The DES participants from Spanish institutions are partially supported by MINECO under grants AYA2015-71825, ESP2015-66861, FPA2015-68048, SEV-2016-0588, SEV-2016-0597, and MDM-2015-0509,
some of which include ERDF funds from the European Union. IFAE is partially funded by the CERCA program of the Generalitat de Catalunya.
Research leading to these results has received funding from the European Research
Council under the European Union's Seventh Framework Program (FP7/2007-2013) including ERC grant agreements 240672, 291329, and 306478.
We  acknowledge support from the Australian Research Council Centre of Excellence for All-sky Astrophysics (CAASTRO), through project number CE110001020.

This manuscript has been authored by Fermi Research Alliance, LLC under Contract No. DE-AC02-07CH11359 with the U.S. Department of Energy, Office of Science, Office of High Energy Physics. The publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.

\facilities{Blanco (DECAM), VLT:Kueyen (X-SHOOTER), Keck:II (DEIMOS), Magellan:Clay (LDSS-3), Gemini:South (Flamingoes-2), HST (WFC3), VLT:Antu (FORS2), VLT:Antu (HAWK-I)}

\bibliographystyle{apj}

redpajama_set_name: RedPajamaArXiv


text:
\section*{Introduction}

All successful technologies are based on harnessing a specific resource, such as energy, electricity or information. The ability to generate, control, transform and ultimately, find useful applications for quantum resources, is central to the development of quantum technologies \cite{feynman, ddv, 2qrev, qkd_review}.

Controlling the simplest quantum systems, the qubit, is relatively straightforward \cite{Barenco, mike_ike}. We can achieve complete control over the 2-dimensional Hilbert space of a qubit with rotations generated by Pauli matrices $X$ and $Z$. The natural next step is to go to $d$-dimensional systems, or qudits. In this case we have the generalised Pauli matrices $X_d$ and $Z_d$. Progressing in this direction, we need to find physical implementations for qudits, together with the experimental ability to control them.

Orbital angular momentum (OAM) is one of the most used implementations for photonic qudits. Photon states $\ket{\ell}$ carry an OAM of $\ell\hbar$, where $\ell=0, \pm1, \pm2,\ldots $ is a theoretically unbounded integer. OAM states have a helical phase front, with $\ell\ne 0$ corresponding to the number of helices.

Photonic OAM states have been used in entanglement generation \cite{mair, fickler, krenn1} and alignment-free quantum key distribution \cite{align_free, vallone_oam}. Thus OAM is attractive since it allows us to use a larger alphabet to transmit quantum information with a single photon. However, without the appropriate tools, a larger alphabet for encoding information has only a limited functionality. This brings us to the problem of how to implement efficiently the generalised Pauli operators $X_d$ and $Z_d$ for qudits \cite{bloch_qudit}.

For photonic OAM states, $Z_d$ can be implemented with Dove prisms. An open question is how to implement a cyclic permutation $X_d$ for any dimension $d$. Experimentally, cyclic $X_d$ gates for OAM states have been realised only for $d=4$ \cite{cyclic1} and $d=5$ \cite{cyclic2}.

In this article we propose a general scheme to perform cyclic permutations $X_d$ for any set of $d$ consecutive states. We then generalise it for cyclic permutations $X_d(p)$ of an arbitrary set of $d$, equally spaced states $\{ \ket{\ell_0}, \ket{\ell_0+p},\ldots, \ket{\ell_0+(d-1)p} \}$. For any dimension $d$, the minimal implementation of both $X_d$ and $X_d(p) $ requires a single sorter $S_d$ and two spiral phase plates (SPPs) \cite{Beijer, Allen, Oemr, Wang}. To arrive at this setup, we use quantum information methods and quantum network analysis. This approach has been employed previously to design a universal quantum sorter \cite{sorter} and spin measuring devices \cite{ri1, ri3}.

We focus on OAM encoded qudits, as several experimental tools are already available \cite{leach1, leach2, giovannini, berk, mirh, babazadeh, LG_sorter}. Nevertheless, our scheme can be extended in principle to other degrees of freedom as well.

\section*{Results}

\subsection*{Cyclic $X_d$ gate}

We now introduce our setup for performing the cyclic gate. Let $\h_d$ be the Hilbert space of a qudit, $\dim \h_d= d$ and let $\{\ket{j} \}_{j=0}^{d-1}$ be an orthonormal basis of $\h_d$. The generalised Pauli operators $X_d$, $Z_d$ are defined as:
\begin{eqnarray}
X_d:\ \ &&\ket{j} \mapsto \ket{j\oplus 1}\\
Z_d:\ \ &&\ket{j} \mapsto \omega^j \ket{j}
\label{Xd}
\end{eqnarray}
with $\oplus$ addition mod $d$ and $\omega= e^{2\pi i/d}$ a root of unity of order $d$. The gate $X_d$ performs a cyclic permutation of the basis states, i.e., maps the set $\{ \ket{0}, \ket{1}, \ldots, \ket{d-1}\}$ to $\{ \ket{1}, \ket{2}, \ldots, \ket{0}\}$.

Our scheme for the $X_d$ gate is shown in Fig.\ref{Xd_MZI}. The main element of our proposal is a $d$-dimensional sorter $S_d$ introduced in Ref.~\cite{sorter, sorter1}. A quantum sorter $S_d$ is a device which directs an incoming particle into different outputs (i.e., sorts) according to the value of an internal degree of freedom $\Sigma$. In the following we take $\Sigma$ to be orbital angular momentum (OAM). Nevertheless, the setup is general and can be implemented for other variables as well, like wavelength \cite{sorter} or radial quantum number \cite{radial_s1, radial_s2}.

The quantum sorter $S_d$ is formally equivalent to a controlled-$X_d$ gate between the degree of freedom we want to sort (OAM, $\Sigma$ etc) and spatial modes $m$, see Fig.~\ref{sorter}:
\begin{equation}
S_d:= C(X_d):\ \ \ket{i}_{OAM} \ket{j}_m \mapsto \ket{i}_{OAM} \ket{j\oplus i}_m
\label{S_d}
\end{equation}
where $\ket{i}_{OAM}, \ket{j}_m$ are OAM and mode qudits, respectively. Thus a photon in OAM state $\ket{i}$ incident on port (mode) 0 will exit on port $(i \bmod d)$ with unit probability.

Apart from the sorter $S_d$ another ingredient are spiral phase plates \cite{Beijer, Allen, Oemr, Wang} of order $n$. The action of the SPP on OAM states is:
\begin{equation}
\mathrm{SPP}(n):\ \ \ket{i}_{OAM} \mapsto \ket{i+n}_{OAM}
\label{SPP}
\end{equation}
with $n \in \mathbb{Z}$ integer. This transformation adds (or subtracts) $n$ units of OAM. Since this is normal addition, it shifts the whole $\mathbb{Z}$ axis by $n$ units.

\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{fig1.pdf}
\caption{Cyclic $X_d$ gate. The gate performs the transformation ${\ket{i} \mapsto \ket{i\oplus 1}}$ on a qudit. (a) Equivalent quantum network. Spatial modes are used as a qudit ancilla, which is factorised before and after the gate, i.e., starts and ends up in the state $\ket{0}_m$. There are two SPPs of order $+1$ and $-d$ (green) and two $C(X_d)$ gates (cyan). The $\mathrm{SPP}(-d)$ acts only on mode $0$ (open circle on the control mode qudit). (b) Implementation. Photons enter from the left and all OAM states are shifted by $\mathrm{SPP}(+1)$. The sorter $S_d$ redirects each state to the corresponding output. The state $\ket{d}_{OAM}$ exits on spatial mode $0$ and after the $\mathrm{SPP}(-d)$ becomes $\ket{0}_{OAM}$; all other OAM states $\ket{j}, j\ne d$, are left invariant. Finally, all states enter the inverse sorter $S_d^{-1}$ and end up in the same spatial mode $\ket{0}_m$.}
\label{Xd_MZI}
\end{figure}

We now discuss how the $X_d$ gate in Fig.~\ref{Xd_MZI} works. The first SPP adds $+1$ to all OAM states. Then the sorter $S_d$ directs each OAM state $\ket{i}_{OAM}$ to the corresponding output $\ket{i\bmod d}_m$, eq.~\eqref{S_d}. Since sorting on modes is done modulo $d$, the state $\ket{d}_{OAM}$ will exit on mode $0$. Consequently, only the state on mode $0$ needs to be shifted by $-d$; in terms of quantum networks, this is equivalent to a controlled-$\mathrm{SPP}(-d)$ gate, with the control on the mode $k=0$ (open circle on control qudit in Fig.\ref{Xd_MZI}). After this operation the states from all spatial modes are recombined on mode $0$ by the gate $C(X_d)^{-1}$, which is nothing else but a sorter run in reverse $S_d^{-1}$. This decouples the OAM and mode qudits, such that the final state is factorised and the photon always exits on mode 0 with unit probability. Thus the gate in Fig.~\ref{Xd_MZI} performs the following sequence:
\begin{eqnarray}
\nonumber \ket{i}_{OAM} \ket{0}_m &\stackrel{+1}{\longrightarrow}& \ket{i+1}_{OAM} \ket{0}_m \\
\nonumber &\stackrel{S_d}{\longrightarrow}& \ket{i+1}_{OAM} \ket{i\oplus 1}_m \\
\nonumber &\stackrel{-d^{[0]}}{\longrightarrow}& \ket{i\oplus 1}_{OAM} \ket{i\oplus 1}_m \\
&\stackrel{S_d^{-1}}{\longrightarrow}& \ket{i\oplus 1}_{OAM} \ket{0}_m
\end{eqnarray}

Since the ancilla is decoupled after the gate, an arbitrary superposition of OAM states transforms under the cyclic gate $X_d$ as
\begin{equation}
\alpha_0\ket{0}+ \alpha_1 \ket{1}+ \ldots + \alpha_{d-1}\ket{d-1}\ \  \rightarrow\ \  \alpha_{d-1}\ket{0}+ \alpha_0\ket{1}+ \ldots+ \alpha_{d-2}\ket{d-1}
\end{equation}
Consequently, our scheme preserves coherence and can be used in arbitrary quantum algorithms.

\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{fig2.pdf}
\caption{Universal quantum sorter $S_d$. Top: equivalent quantum network. The controlled-$X_d$ gate $C(X_d)$ is decomposed on Fourier gates $F, F^\dag$ and a $C(Z_d)$ gate. Bottom: implementation as a multimode interferometer with path-dependent phase shifts $Z_d^j$ acting on the variable to be sorted $\Sigma$.}
\label{sorter}
\end{figure}

\subsection*{Resources}

Our implementation of the cyclic $X_d$ gate requires two sorters $S_d$ and two SPPs (of order $+1$ and $-d$, respectively). This result is important: the number of SPPs is constant (two), and thus independent of the qudit dimension $d$. A Michelson configuration simplifies this to a single sorter and two SPPs, see section below.

Each sorter $S_d$ requires $d-1$ phases $Z_d$ (on OAM) and two Fourier gates $F_d, F_d^\dag$ on spatial modes \cite{sorter}, Fig.~\ref{sorter}. Fourier gates for spatial modes \cite{barak, taki, tabia, kita} can be implemented in several ways.

In integrated optics the Fourier gate is performed by a single slab coupler \cite{cincotti}, e.g., as used in arrayed waveguide gratings (AWG) \cite{WavLow}. Commercially available AWGs containing Fourier gates have tens to hundreds of spatial modes (channels).

In bulk optics the Fourier transform can be implemented with a pair of confocal lenses with waveguides attached \cite{cincotti}. Alternatively, the Fourier gate can be decomposed in $O(d^2)$ linear optics elements (beamsplitters and phase-shifters) \cite{tabia, reck, clements}. For $d=2^p, p\in \mathbb N$, the Fourier transform on $d$ modes can be implemented with $O(\tfrac{d}{2} \log d)$ linear optical elements (beamsplitters and phase-shifters) \cite{barak, crespi}. The resource scaling for the $X_d$ gate is summarised in Table \ref{t1}.

\begin{table}[h]
\begin{center}
\begin{tabular}{l||c|c|c}
& SPPs & Fourier $F$ & $Z_d$ phases \\
\hline
resources & 2 & 4, integrated optics & $2(d-1)$\\
& & $O(d^2)$, linear optics & \\
& & $O(\tfrac{d}{2} \log d)$, if $d=2^p$ &
\end{tabular}
\end{center}
\caption{Resource scaling for the cyclic $X_d$ gate.}
\label{t1}
\end{table}

We now briefly discuss possible implementations. Given the scaling discussed above and the current advances in photonics, we expect to have sizes $d\sim 5-10$ in bulk optics and $d\sim 100$ in integrated photonics.

\subsection*{Generalised $X_d$ gate}

The previous setup implements a cyclic $X_d$ gate on the set $\{ \ket{0}, \ket{1}, \ldots, \ket{d-1}\}$. We now discuss two generalisations.

\noindent {\em (i) Cyclic permutation for $d$ consecutive values.}
The first generalisation is to perform a cyclic $X_d$ gate on an arbitrary set of $d$ consecutive OAM values $\{ \ket{\ell_0}, \ket{\ell_0+1}, \ldots , \ket{\ell_0+d-1}\}$. From the general transformation of the sorter, we know that a state with OAM $\ell_0$, incident on spatial mode $0$, will exit on spatial mode $k= \ell_0 \bmod d$. Thus the only modification of the scheme in Fig.~\ref{Xd_MZI} is to move $\mathrm{SPP}(-d)$ from mode 0 to mode $k$, Fig.~\ref{Xdp_MZI}(a).

A second method to perform the cyclic $X_d$ gate on the set $\{ \ket{\ell_0}, \ket{\ell_0+1}, \ldots , \ket{\ell_0+d-1}\}$ is to first shift all OAM states with $-k$, then perform the usual $X_d$ gate, and finally shift back all states with $+k$, Fig.~\ref{Xdp_MZI}(b).

Importantly, the value of the shift $k$ is bounded by the dimension $d$ of the qudit and not by $\ell_0$, since $0\le k <d$. This is noteworthy -- although OAM with large values $\ell=10010$ have been experimentally prepared \cite{OAM10010}, SPPs with such large values are very difficult to manufacture. Therefore, for $\ell \gg d$ we need to shift the state only with a much smaller value ${(\ell_0 \bmod d)} < d$, irrespective of the magnitude of $\ell_0$. Thus the same device can be used to perform the cyclic $X_d$ gate on any set of $d$ consecutive OAM states. In this case the only change is the position of $\mathrm{SPP}(-d)$ (for the first method), or adding two extra $\mathrm{SPP}(\pm k)$ (for the second method).

\begin{figure}[t]
\centering
\includegraphics[width=0.5\textwidth]{fig3.pdf}
\caption{Generalised cyclic gate $X_d(p)$. The gate performs a cyclic permutation on the set $\{ \ket{\ell_0}, \ket{\ell_0+p},\ldots, \ket{\ell_0+(d-1)p} \}$. There are two ways to correct for the initial state $\ell_0$: (a) by moving $\mathrm{SPP}(-pd)$ to spatial mode $k$, with $k= \ell_0 \bmod d$; (b) by inserting before and after the sorters two SPPs, $\mathrm{SPP}(-k)$ and $\mathrm{SPP}(k)$. Note that $0\le k< d$.}
\label{Xdp_MZI}
\end{figure}

\noindent {\em (ii) Cyclic permutation for $d$, equally spaced values.}
Let $p\in \mathbb{N}^+$ be a positive integer. We now show how to implement a cyclic permutation with step $p$
\begin{equation}
\{ \ket{0}, \ket{p},\ldots, \ket{(d-1)p} \} \mapsto \{ \ket{p}, \ket {2p},\ldots, \ket{0} \}
\end{equation}
We define the generalised gate $X_d(p)$
\begin{equation}
X_d(p):\ \ \ket{j p} \mapsto \ket{(j\oplus 1) p}
\end{equation}
with $j=0,\ldots, d-1$, $p\in \mathbb{N}^+$ and $\oplus$ addition mod $d$. The gate is characterised by two parameters: the qudit dimension $d$ and the step $p$ between two consecutive values; clearly $X_d(1)= X_d$.

The implementation of $X_d(p)$ uses the same architecture as before, but with a different sorter $S_d^{1/p}$: this directs each state $\ket{j p}_{OAM}$ on a separate mode $\ket{j}_m$. From the decomposition $S_d^{1/p}= F^\dag C(Z_d^{1/p}) F$, it follows that we can implement $S_d^{1/p}$ with a setup similar to Fig.~\ref{sorter}, but with different mode-dependent phases $Z_d^{j/p}$ inside the interferometer.

The setup for $X_d(p)$ is shown in Fig.~\ref{Xdp_MZI}. As before, $\mathrm{SPP}(p)$ first shift all OAM states with $p$. The sorter $S_d^{1/p}$ separates the states according to the OAM values, $\ket{j p}_{OAM} \ket{0}_m \mapsto \ket{j p}_{OAM} \ket{j}_m$. Then $\mathrm{SPP}(-pd)$ maps $\ket{dp}_{OAM} \mapsto \ket{0}_{OAM}$, after which the sorter $S_d^{-1/p}$ combines back all states on mode $\ket{0}_m$.

As before, we can implement a cyclic gate $X_d(p)$ on an arbitrary set of equally spaced OAM values $\{ \ket{\ell_0}, \ket{\ell_0+p},\ldots, \ket{\ell_0+(d-1)p} \}$ in two ways, Fig.~\ref{Xdp_MZI}:\\
(a) by moving $\mathrm{SPP}(-pd)$ on mode $k$, with $k= \ell_0 \bmod d$; or\\
(b) by using two $\mathrm{SPP}(\pm k)$ before and after the sorters.

To summarise, for any dimension $d$ and initial state $\ell_0$, the generalised gate $X_d(p)$ requires only two sorters $S_d^{1/p}, S_d^{-1/p}$ and two spiral phase plates $\mathrm{SPP}(p)$, $\mathrm{SPP}(-pd)$.

\subsection*{Simplification: Michelson setup}

We can further simplify our scheme if we use a Michelson instead of the Mach-Zehnder interferometer. In this case we need only one sorter $S_d^{1/p}$, Fig.~\ref{Xdp_MI}. The first part of the scheme is identical to the one discussed previously. The state $\ket{dp}_{OAM}$ exits on spatial mode $k$ and, after a reflection on $\mathrm{SPP}(-pd)$, becomes $\ket{0}_{OAM}$. All other OAM states undergo a double reflection on the retro-reflector $R$ and remain unchanged. Finally, all states re-enter the sorter from the opposite direction, thus performing $S_d^{-1/p}$, and end up in the same spatial mode $\ket{0}_m$. A circulator $C$ separates the output from the input. Note that a spiral phase plate acts as its inverse if the photon enters from the opposite direction; thus in Fig~\ref{Xdp_MI}(b) we need only a single $\mathrm{SPP}(-k)$.

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth]{fig4.pdf}
\caption{Michelson interferometer configuration for $X_d(p)$ gate. This is the folded version of the Mach-Zehnder setup in Fig.\ref{Xdp_MZI}. The state $\ket{dp}_{OAM}$ exits on spatial mode $0$ and after a reflection on $\mathrm{SPP}(-pd)$ becomes $\ket{0}_{OAM}$. All other OAM states $\ket{jp}_{OAM}, j\ne d$, are left invariant by a double reflection on retro-reflectors $R$. Subsequently, all states re-enter the sorter from the opposite direction, thus performing $S_d^{-1/p}$, and end up in the same spatial mode $\ket{0}_m$. A circulator $C$ separates the output from the input. Cases (a) and (b) are equivalent to Fig.~\ref{Xdp_MZI} (a), (b), respectively.}
\label{Xdp_MI}
\end{figure}

\section*{Discussion}

The ability to control higher-dimensional quantum systems is essential for developing useful quantum technologies. Due to coherence constraints, efficiency will play a key role in the success of real-life quantum protocols. In this article we designed implementations for cyclic permutations $X_d$ in $d$ dimensions, one of the building blocks for constructing arbitrary single-qudit gates. The scheme is deterministic, works at single-particle level and can be applied to arbitrary superpositions of qudit states. Regarding the resource scaling, both $X_d$ and $X_d(p)$ gates require a linear number of phase-shifts $Z_d$. Remarkably, for any dimension $d$ the number of spiral phase plates SPPs is two, thus constant.

Although our focus has been on orbital angular momentum, the method is general and can be adapted to other degrees of freedom. This will require a sorter $S_d$ and shift gates (the equivalent of SPP) for the respective degree of freedom. Since a general scheme for a universal quantum sorter exists \cite{sorter}, a future challenge to implement the cyclic gate $X_d$ for a particular degree of freedom $\Sigma$ is to find appropriate implementations for shift gates $\ket{i}_\Sigma \mapsto \ket{i+n}_\Sigma$.

A possible application of the generalised cyclic permutation $X_d(p)$ is quantum communication, e.g., in QKD protocols with Fibonacci coding for key distribution \cite{FibSimon, FibZiwen}.

\noindent{\em Note added.} While finishing this article we became aware of another method for performing $X_d$ gates for OAM \cite{Xd_gao}.