# Time scales for charge-transfer based operations on Majorana systems

R. Seoane Souto1,2, K. Flensberg1 and M. Leijnse1,2 1Center for Quantum
Devices and Station Q Copenhagen, Niels Bohr Institute, University of
Copenhagen, DK-2100 Copenhagen, Denmark
2Division of Solid State Physics and NanoLund, Lund University, Box 118,
S-22100 Lund, Sweden

###### Abstract

In this article we analyze the efficiency of operations based on transferring
charge from a quantum dot (QD) to two coupled topological superconductors,
which can be used for performing nonabelian operations on Majorana bound
states (MBSs). We develop a method which allows us to describe the full time-
evolution of the system as the QD energy is manipulated. Using a full counting
statistics analysis, we set bounds to the operation time scales. The lower
bound depends on the superconducting phase difference due to a partial
decoupling of the different MBSs parity sectors, while the upper bound is set
by the tunneling of quasiparticles to the MBSs. Using realistic parameters, we
find the existence of a regime where the operation can be carried out with a
fidelity close to unity. Finally, we propose the use of a two operations
protocol to quantify the effect of the dephasing and accumulated dynamical
phases, demonstrating their absence for certain superconducting phase
differences.

##  I Introduction

Prediction of the existence of Majorana bound states (MBSs) at the ends of a
topological superconductor (TS) has given hope of observing nonabelian
statistics (for recent reviews see Alicea (2012); Leijnse and Flensberg
(2012); Beenakker (2013); Aguado (2017); Lutchyn  _et al._ (2018)), which can
potentially be used for topological quantum computation Nayak  _et al._
(2008). Earliest evidence of their existence were based on local probes
coupled to the ends of a TS, showing the build-up of a zero bias peak, firstly
measured in Ref. Mourik  _et al._ (2012). More recently, some experiments have
shown additional pieces of evidence consistent with the presence of MBSs in
proximity-induced superconducting devices such as the zero bias conductance
quantization Nichele  _et al._ (2017); Zhang  _et al._ (2018), interferometry
signatures Whiticar  _et al._ , exponential scaling with length in Coulomb
blockaded islands Albrecht  _et al._ (2016) and interactions between zero-
energy states and quantum dot (QD) orbitals Deng  _et al._ (2016).

However, an unambiguous proof of their topological origin would rely on the
demonstration of their nonabelian statistics. Some previous theoretical
proposals in this direction were based on a spatial exchange of MBSs in a
multiterminal device Alicea  _et al._ (2011) and others used tunneling or
Coulomb blockade to manipulate the ground state manifolds Sau  _et al._
(2011); Hyart  _et al._ (2013); Aasen  _et al._ (2016). Alternatively,
signatures of the predicted nonabelian statistics can emerge after a sequence
of manipulations of the quantum state of a set of MBSs, using charge-transfer
based operations of QDs coupled to TSs Flensberg (2011). The dependence of the
final state on the order in which the operations are performed would reveal
the nonabelian nature of MBSs.

In this work, we analyze the efficiency of the charge-transfer operation of a
QD coupled to two TS electrodes Flensberg (2011), schematically represented in
Figs. 1 a) and b). During the operation, the QD level energy is swept from
negative to positive energies well outside the superconducting gap, as
illustrated in Fig. 1 c). As a consequence, the electron initially residing in
the QD is transferred to the TSs. In a successful operation the QD empties
into the MBSs (solid arrows in Fig. 1 d)). As an example, starting from an
initial $\left|p_{L},p_{R}\right\rangle_{i}=\left|1,-1\right\rangle$ state
(where $\pm 1$ means even/odd MBS parity of one of the leads), it evolves to a
superposition between $\left|1,1\right\rangle$ and $\left|-1,-1\right\rangle$
after a successful operation, with weights proportional to the tunneling
amplitudes to the right and left TSs, respectively, and a relative phase given
by the superconducting phase difference. Differently from Ref. Flensberg
(2011), we consider the full time dynamics of the system, taking also into
account the degrees of freedom from the continuum of states. This allows us to
analyze various sources of errors such as the non-adiabatic effects, which can
make the QD charge relax (dashed arrows in Fig. 1 d)), and the role of excited
quasiparticles above the superconducting gap, which can produce undesired
parity changes.

Figure 1: a) Schematic representation of the device consisting of two long TS
wires (blue) embedded into a superconducting loop. b) Enlarged representation
of the ends of the wires, which host MBSs ($\gamma_{L,R}^{A,B}$), and the QD
used for the operations. c) Time evolution of the QD energy level. d) Energy
representation, where curved arrows represent the processes of the electron
tunneling to the MBSs (solid lines) or to the continuum of states (dashed
lines) during the manipulation of the QD level energy (thick horizontal line).

In order to analyze the change in the MBSs parity, we use a full counting
statistics formalism which allows us to keep track of the transferred
electrons in the junction. For experimentally accessible temperatures, we find
an optimal manipulation rate window where operations can be performed with
high fidelity. We propose a protocol based on $2$ charge transfer operations,
where the QD level returns back to its original value at the final time, as a
way of quantifying the influence of dephasing and accumulated dynamical
phases. Deviations between the initial and final states provides a measurement
of the effect of the different sources of errors.

##  II Theoretical framework

We consider two TSs coupled to a QD schematically shown in Figs. 1 a) and b)
and described by the Hamiltonian

$H=H_{L}+H_{R}+H_{QD}+H_{T}\,.$ (1)

Here,
$H_{\nu}=\sum_{n}\left(\hat{\Psi}_{n,\nu}^{\dagger}\hat{h}_{0,\nu}\hat{\Psi}_{n,\nu}+\hat{\Psi}_{n+1,\nu}^{\dagger}\hat{h}_{s,\nu}\hat{\Psi}_{n,\nu}\right)$
is the Hamiltonian of the TSs, described by the spinless Kitaev Hamiltonian
Kitaev (2001), where
$\hat{\Psi}_{n,\nu}=\left(c_{n,\nu},c_{n,\nu}^{\dagger}\right)^{T}$ is the
Nambu spinor, with $c_{n,\nu}$ ($c_{n,\nu}^{\dagger}$) being the annihilation
(creation) operators on site $n$ of electrode $\nu=L,R$. The first term
describes the on-site energy, $\hat{h}_{0,\nu}=-\mu\hat{\tau}_{z}/2$. The
second term contains information about the hopping between neighboring sites
and p-wave superconducting correlations,
$\hat{h}_{s,\nu}=-t_{0}\hat{\tau}_{z}/2+i\Delta\hat{\tau}_{y}/2$, with $t_{0}$
the normal hopping between neighbors and $\Delta$ the induced superconducting
gap, taken to be the same in both electrodes for simplicity. The Hamiltonian
of the spinless QD is given by
$H_{QD}=\hat{\Psi}^{\dagger}_{d}\hat{h}_{0}\hat{\Psi}_{d}$, where
$\hat{h}_{0}=\epsilon_{0}(t)\hat{\tau}_{z}/2$ and
$\hat{\Psi}_{d}=\left(d,d^{\dagger}\right)^{T}$. The time-dependent QD level
energy, $\epsilon_{0}(t)$, evolves during the considered operation from the
initial value $\epsilon_{i}$ to the final one $\epsilon_{f}$ (with
$|\epsilon_{i}|,|\epsilon_{f}|\gg\Delta$). For simplicity, $\epsilon_{0}(t)$
is assumed to evolve linearly in time close to the superconducting gap with a
slope $r$, as illustrated in Fig. 1 c). Finally,
$H_{T}=\sum_{\nu}(\hat{\Psi}^{\dagger}_{0,\nu}\hat{h}_{T_{\nu}}\hat{\Psi}_{d}+\mbox{H.C.})$
describes the tunneling of electrons between the QD and the closest site of
the two TSs with
$\hat{h}_{T_{\nu}}=t_{\nu}\hat{\tau}_{z}e^{i\hat{\tau}_{z}\phi_{\nu}/2}$,
where $\phi=\phi_{L}-\phi_{R}$ determines the superconducting phase difference
between the leads. The tunneling rates are defined as
$\Gamma_{\nu}=\pi(t_{\nu})^{2}\rho_{F}$, with $\Gamma=\Gamma_{L}+\Gamma_{R}$
and $\rho_{F}$ being the normal density of states at the Fermi level, taken as
$\rho_{F}=1/\Delta$.

The dynamics of the system during an adiabatic operation is accurately
described by a low energy model, which only considers the MBSs in the leads.
It is described by the Hamiltonian

$H_{LEM}=H_{QD}+H_{T,MBS}\,,$ (2)

where
$H_{T,MBS}=V_{L}\gamma_{L}^{A}e^{i\phi_{L}/2}d+V_{R}\gamma_{R}^{B}e^{i\phi_{R}/2}d+\mbox{H.C.}$
is the tunneling Hamiltonian, with $V_{\nu}=t_{\nu}\rho_{F}\Delta$. Here,
$\gamma_{L}^{A}=c_{0,L}+c_{0,L}^{\dagger}$ and
$\gamma_{R}^{B}=i(c_{0,R}-c_{0,R}^{\dagger})$ are the MBS operators at the
closest end to the QD of the left and right TS (see Fig. 1 b)).

We use the non-equilibrium Green function (NEGF) formalism to access the
system state. In the time-dependent regime, the inverse QD NEGF is given by

$G^{-1}(t,t^{\prime})=g_{0}^{-1}(t,t^{\prime})-\Sigma(t,t^{\prime})\,,$ (3)

where $g^{-1}_{0}$ represents the inverse QD Green function in the Keldysh-
Nambu space Kamenev (2011); Souto  _et al._ (2016, 2017) and $\Sigma$ the
tunneling self-energy. The self-energy can be decomposed into two
contributions, $\Sigma=\Sigma_{M}+\Sigma_{c}$, describing the coupling to the
MBSs and the continuum of states, respectively (expressions are given in the
supplementary information (SI) SM ). For simplicity, we consider a sudden
connection between the QD and the electrodes at $t=0$, such that the charge
state of the QD and the parity state of the electrodes are initially well
defined. We have checked that the connection process does not affect to the
initial parity state of the MBSs for an initial level position
$|\epsilon_{i}|\gg\Delta$.

The problem is solved in the time domain by discretizing the Keldysh contour
and numerically inverting Eq. (3). Information about the mean properties of
the system can be extracted from the QD NEGFs. For instance, the average
parity of each MBS can be obtained as $\left\langle
p_{\nu}\right\rangle=i\left\langle\gamma_{\nu}^{A}\gamma_{\nu}^{B}\right\rangle$
(details are provided in the SI SM ).

In contrast, from the mean values obtained from the NEGFs of Eq. (3) it is not
possible to extract the probability of a successful operation. This
information can instead be obtained by projecting the number of electrons
transferred between the QD and the MBSs using a full counting statistics
analysis. This information is encoded in the generating function

$Z(\chi,t)=\left\langle
T_{C}\exp\left[-i\int_{C}dt^{\prime}\sum_{\nu}H_{T,\chi}(t^{\prime})\right]\right\rangle_{0}\,,$
(4)

where the average is taken over the decoupled system and the counting field,
$\chi$, is a phase factor used to count tunneling electrons. It enters into
the tunneling amplitudes as
$\hat{h}_{T_{\nu},\chi_{\nu}}=\hat{h}_{T_{\nu}}e^{i\tau_{z}^{K}(\hat{\tau}_{0}+\hat{\tau}_{z})\chi_{\nu}/2}$,
where $\tau_{z}^{K}$ is the Pauli matrix in Keldysh space, indicating the
change on the counting field sign between the two Keldysh branches. We
consider the counting field acting only for electrons tunneling between the QD
and the MBSs, as illustrated in Fig 1 d) (and not between the QD and the
quasiparticle states outside the gap), and take $\chi_{L}=\chi_{R}=\chi/2$,
which projects the wavefunction onto a state with well defined joint parity of
left and right MBSs.

The GF can also be written as
$Z(\chi,t)=\sum_{n}\mathcal{P}_{n}(t)e^{in\chi}$, where $\mathcal{P}_{n}$ is
the probability of transferring $n$ charges between the QD and the MBSs after
a time $t$. Note that at $\chi=\pi$ the GF describes the MBSs parity change.
In the Keldysh-Nambu space, the GF can be computed as a Fredholm determinant
Kamenev (2011); Souto  _et al._ (2016)

$Z(\chi,t)=\frac{\mbox{det}[g^{-1}_{0}-\Sigma(\chi)]}{\mbox{det}[g^{-1}_{0}-\Sigma(\chi=0)]}\,.$
(5)

The probability of a change of the joint MBS parity is described by the
generating function as $P(t)=[1-Z(\chi=\pi,t)]/2$, which is also the
probability for the QD charge to be transferred to the MBSs. $P$ saturates for
$|\epsilon_{0}(t)|\sim 10\Gamma$ to a value $P_{f}$, leading to a total
operation time $t\approx 20\,\Gamma/r$.

##  III Results

Figure 2: Left panel: Dependence of the inverse of the operation rate as a
function of the superconducting phase for different $P_{f}$ values. Right
panel: average parity of left and right MBSs during an operation with
$r=\Delta^{2}/4$. We consider two different phases: $\phi=\pi/2$ (solid lines)
and $\phi=\pi$ (dotted lines). In both cases we take
$\Gamma_{L}=\Gamma_{R}=0.15\Delta$ and temperature $T=0$.

In this section we analyze the success probability of the charge-transfer
based operation on the system sketched in Figs. 1 a) and b). We consider an
initially well-defined MBS parity on both sides, choosing without loss of
generality $\left|p_{L},p_{R}\right\rangle_{i}=\left|1,-1\right\rangle$ as the
initial MBS parity state. A successful operation in which the QD charge is
efficiently transferred to the MBSs (solid arrows in Fig. 1 d)) leads to a
change of the total MBS parity state (from odd to even in our case), leading
to a final state
$\left|p_{L},p_{R}\right\rangle_{f}=(V_{R}e^{i\phi_{R}/2}\left|1,1\right\rangle+V_{L}e^{i\phi_{L}/2}\left|-1,-1\right\rangle)/\sqrt{V_{L}^{2}+V_{R}^{2}}$.
As discussed below, this is only true for $\phi=(2n+1)\pi$.

In the left panel of Fig. 2 we show the dependence of the inverse manipulation
rate ($1/r$) on the superconducting phase difference for different values of
$P_{f}$. As shown, the rate needed for a given $P_{f}$ depends strongly on
$\phi$, becoming optimal (thus, minimizing operation times) for
$\phi=(2n+1)\pi$. At $\phi=2n\pi$ the time of the operation diverges due to
the formation of a dark state preserving the total MBS parity state for
$V_{L}=V_{R}$ and for any $\epsilon_{0}$ value, setting a limit $P_{f}=0.5$
for adiabatic operations. The dark state is given by
$(\left|1,-1\right\rangle+i\left|-1,1\right\rangle)/\sqrt{2}$ for the odd MBS
parity sector and
$(\left|1,1\right\rangle+i\left|-1,-1\right\rangle)/\sqrt{2}$ for the even
one. For $V_{L}\neq V_{R}$ the even and odd MBS parity sectors are no longer
decoupled, although the value of $r$ needed for reaching a $P_{f}$ close to
unity becomes strongly dependent on the asymmetry between the left and right
tunneling rates close to $\phi=2n\pi$.

In the right panel of Fig. 2 we show the average parity of the left and right
MBSs for an adiabatic $r$ value where $P_{f}\approx 1$ and two different
superconducting phases. As shown, for $\phi=\pi$ (mod $2\pi$) $\left\langle
p_{L}\right\rangle$ and $\left\langle p_{R}\right\rangle$ tend to $0$ at long
times, consistent with the convergence to the expected final state after the
operation. In contrast, for $\phi\neq(2n+1)\pi$ the average parities exhibit
oscillations during the manipulation, which leads to a dependence of the final
state on the details of the operation. These oscillations are due to the
breaking of degeneracy between the even and odd parity states of the non-local
fermion formed by the left and the right MBSs, as shown in the SI SM . For
$\phi=(2n+1)\pi+\delta\phi$ the period of the oscillations is given by
$\sqrt{\epsilon^{2}_{0}+4(V^{2}_{L}+V^{2}_{R})}/(4V_{L}V_{R}\delta\phi)$ with
$\delta\phi\ll 1$. This illustrates the importance of having an accurate
control on the superconducting phase difference. Additional oscillations are
observed after the operation (for $|\epsilon_{0}|\gg\Delta$) with a period
given by $\epsilon_{0}/[4V_{L}V_{R}\cos(\phi/2)]$. It is worth commenting that
the same behavior is observed in the case the QD is coupled to the same
Majorana operators (either $\gamma^{A}$ or $\gamma^{B}$) at the left and right
side, as considered in Ref. Flensberg (2011), by shifting the superconducting
phase difference value by $\pi$. In the following we will focus on the
$\phi=(2n+1)\pi$ situation, where the parity oscillations are absent and
$P_{f}$ quantifies the success probability of the charge-transfer operation.

Figure 3: Temperature dependence of the MBSs parity change probability,
showing the time evolution (left panel) and the long time limit as a function
of the rate (right panel). Parameters are the same as in Fig. 2 with
$\phi=\pi$.

The analysis performed above would indicate that the choice of slower rates
tends to improve the success probability. However, some additional processes
can affect the operation fidelity for adiabatic rates, such as the decaying of
excited quasiparticles into the MBSs, which lead to uncontrolled parity
changes. First estimations have shown that these events happen in the ms time
scale in a trivial wire, i.e. without MBSs Higginbotham  _et al._ (2015).
Processes involving the decaying of quasiparticles directly into the MBSs will
be disregarded in the following. Instead we consider the time-scales for
quasiparticles tunneling between the continuum and the MBSs mediated by the QD
during the charge-transfer based operation which, as it turns out, can be much
shorter, see Fig. 3. At a finite $T$, there is a density of quasiparticles
excited above the superconducting gap. For small $T$, the number of
quasiparticles is exponentially suppressed and the manipulation can be
performed with a high success probability, as illustrated by the blue curves
in the left panel of Fig. 3. However, when the temperature increases, $P_{f}$
drops for adiabatic rates. This is better illustrated in the right panel of
Fig. 3 where we show that $P_{f}$ exhibits a maximum, decreasing for small $r$
values, due to the tunneling of thermally excited quasiparticles to the QD.

For small temperatures ($T\lesssim 0.2\Delta$), the system exhibits a range of
$r$ values where $P_{f}$ is close to unity. We observe that the decay point of
$P_{f}$ for decreasing $r$ values scales linearly with the density of
thermally excited quasiparticles. It allows us to estimate an optimal window
for the rate using experimentally relevant parameters where $k_{B}T/\Delta\sim
0.1$, finding $r/\Delta\Gamma\sim 10^{-4}-10^{-1}$. This leads to an estimated
manipulation time scale of the order of $0.1\,\mu\mbox{s}$ to $0.1\,\mbox{ns}$
for $V_{L}$ and $V_{R}$ smaller but of the same order of magnitude as
$\Delta$. The upper bound has been estimated considering an equilibrium
distribution of excited quasiparticles with energies larger than the
superconducting gap. It can be significantly reduced if a higher density of
these quasiparticles is found in the TSs.

Figure 4: Results for a double charge-transfer operations where the QD level
returns to its initial value at the final time. The solid curves describe the
coherent dynamics while the dashed ones illustrate the effect of a randomly
distributed phase, $\xi\in[-\pi/2,\pi/2]$, introduced in the quantum state
after the first manipulation, using the low energy Hamiltonian of Eq. (2).
Upper panel: probability of total MBS parity change. Lower panel: left and
right MBS parity. The parameters are the same as in Fig. 2 with $\phi=\pi$ and
$r=\Delta^{2}/2$.

While Figs. 2 and 3 describe the probability of changing the parity of the
MBSs, they do not contain information about dephasing or the accumulation of
dynamical phases. These effects can be generated by high order processes
involving the tunneling of electrons between the QD and the continuum of
states. In order to quantify the dephasing, we suggest two charge-transfer
operations, where the QD level energy is swept from $\epsilon_{i}$ to
$\epsilon_{f}$ and then back to $\epsilon_{i}$. The results of this protocol
are shown in Fig. 4 for a situation where a high $P_{f}$ is observed in the
right panel of Fig. 3 (solid lines). In the top panel of Fig. 4 we show the
change of the joint MBS parity, which evolves to almost $1$ after the first
manipulation and returns back to almost $0$ when the QD level energy returns
to its original value (solid line). The lower panel of Fig. 4 shows the
average parity values of the left and right MBS pairs during the operation,
confirming that the parity of each electrode returns back to its original
value after the second operation (solid lines). We have also verified that the
final state of the electrodes does not degrade if different adiabatic rates
are considered for the two manipulation processes, indicating the absence of
uncontrolled dynamical phases for $\phi=\pi$ (mod $2\pi$).

The dashed lines in Fig. 4 illustrate the effect of an accumulation of
uncontrolled phase factors after the first operation, which we simulate using
a randomly distributed phase $\xi$ in a given interval. Therefore, the state
after a successful first operation is
$\propto(V_{R}e^{i\phi_{R}/2}\left|1,1\right\rangle+V_{L}e^{i(\phi_{L}/2+\xi)}\left|-1,-1\right\rangle)$.
This is analyzed using the low energy model described in Eq. (2), which
accurately describes the system adiabatic evolution. While the total MBS
parity change is not affected by the inclusion of randomly distributed phase
$\xi$ (top panel of Fig. 4), the individual parities of the electrodes do not
return back to their original values. Instead, they they approach
$\left\langle p_{\nu}\right\rangle=0$ in the limit the introduced phase factor
is completely random. Therefore, the difference between the initial and final
parity states, $\delta(\left\langle p_{\nu}\right\rangle)=\left\langle
p_{\nu}\right\rangle_{f}-\left\langle p_{\nu}\right\rangle_{i}$, quantifies
the accumulated error in the whole process. The error on a single manipulation
can be estimated as $1-\sqrt{1-|\delta(\left\langle p_{\nu}\right\rangle)|}$
in the regime where no other errors occur between the first and the second
operation.

##  IV Conclusions

We have analyzed the efficiency of the charge-transfer based operations of a
QD coupled to two topological superconductors, setting bounds to its optimal
time scales. We have found the optimal parameters where the final state after
an adiabatic operation does not depend on the details of how it is performed.
We have also analyzed the effects of imperfections in the system that affect
the adiabatic operations, studying the effect of the excited quasiparticles
above the superconducting gap at finite temperature, which leads to a lower
bound to the manipulation rate. In the SI SM  we furthermore investigate the
effects of an overlap between the MBS wavefunctions within a wire. We show
that this leads to an upper bound on the operation time scale determined by
the inverse of the difference between the overlap strength on both sides. Our
results establish charge-transfer based operations as a realistic alternative
to experimentally probe the nonabelian nature of MBSs.

##  V Acknowledgements

We acknowledge valuable contributions from A. Levy Yeyati and A. Martín-Rodero
on the code development. We acknowledge funding from the Danish National
Research Foundation. RSS and ML acknowledge funding from QuantERA project “2D
hybrid materials as a platform for topological quantum computing” and from
NanoLund.

## References

  * Alicea (2012) J. Alicea, Reports on Progress in Physics 75, 076501 (2012).
  * Leijnse and Flensberg (2012) M. Leijnse and K. Flensberg, Semiconductor Science and Technology 27, 124003 (2012).
  * Beenakker (2013) C. Beenakker, Annual Review of Condensed Matter Physics 4, 113 (2013).
  * Aguado (2017) R. Aguado, Riv. Nuovo Cimento 40, 523 (2017).
  * Lutchyn  _et al._ (2018) R. M. Lutchyn, E. P. A. M. Bakkers, L. P. Kouwenhoven, P. Krogstrup, C. M. Marcus, and Y. Oreg, Nature Reviews Materials 3, 52 (2018).
  * Nayak  _et al._ (2008) C. Nayak, S. H. Simon, A. Stern, M. Freedman, and S. Das Sarma, Rev. Mod. Phys. 80, 1083 (2008).
  * Mourik  _et al._ (2012) V. Mourik, K. Zuo, S. M. Frolov, S. R. Plissard, E. P. A. M. Bakkers, and L. P. Kouwenhoven, Science 336, 1003 (2012).
  * Nichele  _et al._ (2017) F. Nichele, A. C. C. Drachmann, A. M. Whiticar, E. C. T. O’Farrell, H. J. Suominen, A. Fornieri, T. Wang, G. C. Gardner, C. Thomas, A. T. Hatke, P. Krogstrup, M. J. Manfra, K. Flensberg, and C. M. Marcus, Phys. Rev. Lett. 119, 136803 (2017).
  * Zhang  _et al._ (2018) H. Zhang, C.-X. Liu, S. Gazibegovic, D. Xu, J. A. Logan, G. Wang, N. van Loo, J. D. S. Bommer, M. W. A. de Moor, D. Car, R. L. M. Op het Veld, P. J. van Veldhoven, S. Koelling, M. A. Verheijen, M. Pendharkar, D. J. Pennachio, B. Shojaei, J. S. Lee, C. J. Palmstrøm, E. P. A. M. Bakkers, S. D. Sarma, and L. P. Kouwenhoven, Nature 556, 74 EP (2018).
  * (10) A. M. Whiticar, A. Fornieri, E. C. T. O’Farrell, A. C. C. Drachmann, T. Wang, C. Thomas, S. Gronin, R. Kallaher, G. C. Gardner, M. J. Manfra, C. M. Marcus, and F. Nichele, arXiv.1902.07085 .
  * Albrecht  _et al._ (2016) S. M. Albrecht, A. P. Higginbotham, M. Madsen, F. Kuemmeth, T. S. Jespersen, J. Nygård, P. Krogstrup, and C. M. Marcus, Nature 531, 206 EP (2016).
  * Deng  _et al._ (2016) M. T. Deng, S. Vaitiekenas, E. B. Hansen, J. Danon, M. Leijnse, K. Flensberg, J. Nygård, P. Krogstrup, and C. M. Marcus, Science 354, 1557 (2016).
  * Alicea  _et al._ (2011) J. Alicea, Y. Oreg, G. Refael, F. von Oppen, and M. P. A. Fisher, Nature Physics 7, 412 (2011).
  * Sau  _et al._ (2011) J. D. Sau, D. J. Clarke, and S. Tewari, Phys. Rev. B 84, 094505 (2011).
  * Hyart  _et al._ (2013) T. Hyart, B. van Heck, I. C. Fulga, M. Burrello, A. R. Akhmerov, and C. W. J. Beenakker, Phys. Rev. B 88, 035121 (2013).
  * Aasen  _et al._ (2016) D. Aasen, M. Hell, R. V. Mishmash, A. Higginbotham, J. Danon, M. Leijnse, T. S. Jespersen, J. A. Folk, C. M. Marcus, K. Flensberg, and J. Alicea, Phys. Rev. X 6, 031016 (2016).
  * Flensberg (2011) K. Flensberg, Phys. Rev. Lett. 106, 090503 (2011).
  * Kitaev (2001) A. Y. Kitaev, Physics-Uspekhi 44, 131 (2001).
  * Kamenev (2011) A. Kamenev,  _Field Theory of Non-Equilibrium Systems_ (Cambridge University Press, 2011).
  * Souto  _et al._ (2016) R. S. Souto, A. Martín-Rodero, and A. L. Yeyati, Phys. Rev. Lett. 117, 267701 (2016).
  * Souto  _et al._ (2017) R. S. Souto, A. Martín-Rodero, and A. L. Yeyati, Phys. Rev. B 96, 165444 (2017).
  * (22) See Supplemental Material for details on the numerical methods used in this work, which includes Refs. Martín-Rodero and Yeyati (2011); Zazunov  _et al._ (2016); Bondyopadhaya and Roy (2019) .
  * Higginbotham  _et al._ (2015) A. P. Higginbotham, S. M. Albrecht, G. Kirsanskas, W. Chang, F. Kuemmeth, P. Krogstrup, T. S. Jespersen, J. Nygård, K. Flensberg, and C. . M. Marcus, Nature Physics 11, 1017 EP (2015).
  * Martín-Rodero and Yeyati (2011) A. Martín-Rodero and A. L. Yeyati, Advances in Physics 60, 899 (2011).
  * Zazunov  _et al._ (2016) A. Zazunov, R. Egger, and A. Levy Yeyati, Phys. Rev. B 94, 014502 (2016).
  * Bondyopadhaya and Roy (2019) N. Bondyopadhaya and D. Roy, Phys. Rev. B 99, 214514 (2019).

## Supplementary information on “Time scales for charge transfer based
operations on Majorana systems”

##  Appendix A Green functions formalism

In this section of the supplementary information (SI) the main theoretical
tools are introduced, summarizing the most important expressions describing
the system time evolution. We employ a Green functions formalism on the
Keldysh-Nambu contour. In this framework, the inverse QD Green function is
given by Eq. (3) of the main text. In order to describe the time dynamics, the
Keldysh contour is discretized in time with a time step, $\delta t$, smaller
than any other inverse energy (see Fig. 5). The expression for the bare
inverse QD Green function on the discretized Keldysh contour is given by

$i{\bf g}^{-1}_{e}=\left(\begin{array}[]{cccc|cccc}-1&&&&&&&-\rho\\\
h_{1}^{-}&-1&&&&&&\\\ &\ddots&\ddots&&&&&\\\ &&h_{N-1}^{-}&-1&&&&\\\
\hline\cr&&&1&-1&&&\\\ &&&&h_{N-1}^{+}&-1&&\\\ &&&&&\ddots&\ddots&\\\
&&&&&&h_{1}^{+}&-1\end{array}\right)_{2N\times 2N}\;,$ (6)

where $h^{\pm}_{n}(t)=1\mp i\delta t[\epsilon_{0}(t)+\epsilon_{0}(t+\delta
t)]/2$ and the matrix dimension is given by $N=t/\delta t$, with $t$ the final
time. The boldphase letter is used to denote Green functions on the
discretized Keldysh contour. In Eq. (6) the initial QD charge, $n_{e}$, which
enters the expression through $\rho=n_{e}(0)/[1-n_{e}(0)]$, is set either to
$n_{e}(0)=0$ or $1$, depending on the sign of the initial level position
($|\epsilon_{i}|\gg\Delta$). The Nambu structure of the inverse QD Green
function can be written as

${\bf g}^{-1}_{0}=\left(\begin{array}[]{cc}g^{-1}_{e}&0\\\
0&g^{-1}_{h}\end{array}\right),$ (7)

where the hole part is given by
$g^{-1}_{h}=g^{-1}_{e}[-\epsilon_{0}(t),(1-n_{e}(0))]$.

The tunneling self-energy of Eq. (3) of the main text describes the coupling
to the TS electrodes, which are considered to be infinitely long Kitaev chains
in the topological regime, described by the Hamiltonian

$\displaystyle
H_{\nu}=-t_{0}\sum_{n}(c_{n+1,\nu}^{\dagger}c_{n,\nu}-\mbox{H.C.})-\mu\sum_{n}c_{n,\nu}^{\dagger}c_{n,\nu}+\Delta(c_{n,\nu}^{\dagger}c_{n+1,\nu}+\mbox{H.C.})\,,$
(8)

where $c_{n,\nu}$ is the annihilation operator acting on site $n$ of electrode
$\nu$. In Eq. (8) $t_{0}$ is the hopping inside the chain, $\mu$ is the
chemical potential, taken to zero for simplicity, and $\Delta$ is the
superconducting gap. For simplicity, $\Delta$ will be taken real and positive,
and the superconducting phase factors are introduced in the superconducting
phase factors introduced in the tunneling Hamiltoninan. The retarded/advanced
(r/a) components of the electrodes Green function are given in the wideband
limit by (derivation details can be found in Ref. Zazunov  _et al._ (2016))

$\hat{g}_{L,R}^{r}(\omega)=\frac{2}{|t_{0}|}\frac{\sqrt{\Delta^{2}-(\omega+i\eta)^{2}}\hat{\tau}_{0}\pm\Delta\hat{\tau}_{x}}{(\omega+i\eta)}\,,$
(9)

with $\eta$ being a positive infinitesimal and the Pauli matrices are acting
in the Nambu space, represented by $\hat{}$. The $\pm$ sign originates from
the fact that the QD is attached to the rightmost (leftmost) site of the left
(right) TS (see Fig. 1 b of the main text). Using general relations in the
equilibrium situation Martín-Rodero and Yeyati (2011), the Keldysh off-
diagonal components of the self-energy in time domain are given by

$\hat{g}^{+-}_{\nu}(t,t^{\prime})=-\int
d\omega\left[\hat{g}_{\nu}^{a}(\omega)-\hat{g}_{\nu}^{r}(\omega)\right]n_{F}(\omega)e^{-i\omega(t-t^{\prime})}\,,$
(10)

where $\hat{g}_{\nu}^{a}=(\hat{g}_{\nu}^{r})^{*}$ and $n_{F}$ is the Fermi
function. A similar expression can be obtained for the $-+$ components, by
replacing $n_{F}$ by $n_{F}-1$. The self-energy can be obtained from the lead
Green functions as

$\hat{\Sigma}^{+-}_{\nu}(t,t^{\prime})=\theta(t)\theta(t^{\prime})|V_{\nu}|^{2}e^{-i\hat{\tau}_{z}\phi_{\nu}/2}\hat{g}^{+-}_{\nu}(t,t^{\prime})e^{i\hat{\tau}_{z}\phi_{\nu}/2}\,.$
(11)

In order to integrate Eq. (10) we use the property $1/(\omega\pm i\eta)=\mp
i\pi\delta(\omega)+\mbox{PV}(1/\omega)$, which divides the self-energy into
two contributions. The first one, involving the Dirac-delta functional,
describes the tunneling between the QD and the MBSs ($\Sigma_{MBS}$). The
second part, which is related to the integral of the principal value, contains
information about the continuum degrees of freedom ($\Sigma_{c}$). The total
self-energy is then given by

$\hat{\Sigma}(t,t^{\prime})=\sum_{\nu}\left[\hat{\Sigma}_{MBS;\nu}(t,t^{\prime})+\hat{\Sigma}_{c;\nu}(t,t^{\prime})\right]\,.$
(12)

The contribution from the MBSs can be integrated exactly, giving

$\hat{\Sigma}_{MBS;\nu}^{+-}(t,t^{\prime})=-\hat{\Sigma}_{MBS;\nu}^{-+}(t,t^{\prime})=-i\Gamma_{\nu}(\hat{\tau}_{0}\pm\hat{\tau}_{x})\,,$
(13)

where $\Gamma_{\nu}=\pi|V_{\nu}|^{2}\rho_{F}$ and $\rho_{F}=2/\pi|t_{0}|$ is
the normal density of states at the Fermi level. The contribution from the
continuum comes from the Fourier transform of

$\hat{\Sigma}_{c;\nu}^{r/a}(\omega)=\Gamma_{\nu}\,e^{-i\hat{\tau}_{z}\phi_{\nu}/2}\frac{\sqrt{\Delta^{2}-\omega^{2}}}{\omega}\hat{\tau}_{0}e^{i\hat{\tau}_{z}\phi_{\nu}/2}\,,$
(14)

which describes the electronic states outside the superconducting gap.

Figure 5: Keldysh contour considered to analyze the transient regime. $\chi$
indicates the counting field changing sign on the two branches of the contour
and $\delta t$ corresponds to the time step in the discretized calculation of
the generating function $Z(\chi,t)$.

Finally, the Keldysh diagonal components are given by general relations

$\displaystyle\hat{\Sigma}^{++}(t,t^{\prime})$ $\displaystyle=$
$\displaystyle-\theta(t,t^{\prime})\hat{\Sigma}^{-+}(t,t^{\prime})-\theta(t^{\prime}-t)\hat{\Sigma}^{+-}(t,t^{\prime})\,,$
$\displaystyle\hat{\Sigma}^{--}(t,t^{\prime})$ $\displaystyle=$
$\displaystyle-\theta(t,t^{\prime})\hat{\Sigma}^{+-}(t,t^{\prime})-\theta(t^{\prime}-t)\hat{\Sigma}^{-+}(t,t^{\prime})\,.$
(15)

Using the self-energies derived above, Eq. (3) from the main text can be
numerically inverted, which provides access to the mean QD properties, such as
the time evolution of the population as $\left\langle
n_{d}(t)\right\rangle=\mbox{Im}[G(t,t)]^{+-}_{11}$, where the subindices
indicate the Nambu component. The average parity of each lead is given by
$\left\langle
p_{\nu}\right\rangle=i\left\langle\gamma_{\nu}^{A}\gamma_{\nu}^{B}\right\rangle$.
For non-overlapping MBSs it can be determined as

$\left\langle p_{\nu}(t)\right\rangle=\left\langle
p_{\nu}(0)\right\rangle\left\\{1-2i\Gamma_{\nu}\sum_{j,k=1,2}s_{\nu}^{j+k}e^{i\hat{\tau}_{z}\phi_{\nu}/2}\int_{0}^{t}dt_{1}\int_{0}^{t}dt_{2}\left[G^{+-}_{jk}(t_{1},t_{2})-G^{-+}_{jk}(t_{1},t_{2})\right]e^{-i\hat{\tau}_{z}\phi_{\nu}/2}\right\\}\,,$
(16)

where the sum is performed in the Nambu space and $s_{L}=1$ and $s_{R}=-1$.

##  Appendix B Full counting statistics

The full counting statistics (FCS) method, which analyzes the statistics of
the transferred electrons, is an ideal tool for extracting the probability of
successful manipulation. This information is absent in the QD Green functions,
given in Eq. (3) of the main text. While FCS has traditionally been used to
investigate the charge and current fluctuations of nanojunctions, in this
section we extend this formalism for addressing the parity change of a
topological system. The number of electrons transferred are determined using a
counting variable $\chi$, which enters as phase factors in the tunneling
amplitudes, changing sign in the Keldysh contour as indicated in Fig. 5. The
main ingredient in the theory is the so-called generating function (GF)

$Z(\chi,t)=\sum_{n}\mathcal{P}_{n}(t)e^{i\,n\,\chi}\,,$ (17)

which encodes the probability distribution of transferred charges until time
$t$, $\mathcal{P}_{n}(t)$. An interesting particular case corresponds to
taking $\chi=\pi$. In this particular case, the GF is given by
$Z(\chi,t)=\sum_{n}\mathcal{P}_{n}(t)(-1)^{n}$, which describes the
probability of a parity change (transfer of an odd number of electrons).

To analyze the parity change of the subgap states, we will include the
counting variable only in the MBS self-energies (13) as

$\hat{\bar{\Sigma}}_{M;\nu}(\chi)=e^{i\tau^{K}_{z}(\hat{\tau}_{z}+\hat{\tau}_{0})\chi_{\nu}/2}\Sigma_{M;\nu}e^{i\tau^{K}_{z}(\hat{\tau}_{z}+\hat{\tau}_{0})\chi_{\nu}/2}\,,$
(18)

where $\tau^{K}_{z}$ is the Pauli matrix acting in the Keldysh space and
$\chi_{\nu}$ the counting field variable for each electrode. The counting
field in Eq. (18) only projects the first Nambu component, which is sufficient
to determine the system state. There are two different choices for the
counting field at both sides of the junction. The first possibility, which is
used in the main text, corresponds to taking $\chi_{L}=\chi_{R}=\chi/2$. This
situation corresponds to projecting the system wavefunction onto a state with
well defined joint parity of left and right MBSs. Alternatively, the counting
field variable can be set to zero on on side and to $\chi$ on the other one.
This situation corresponds to the projection of the state of one TS onto a
state with well defined parity for $\chi=\pi$. In this case, however, the
charge-transfer operation is affected by the measurement process, since an
instantaneous projection of the state on one side will set the MBS parity
either to even or odd, avoiding the formation of quantum superpositions. As an
example, this choice will prevent the system from returning back to its
original state after the protocol described in Fig. 4 of the main text.

Independently from the choice of counting field, the GF in the discrete time
mesh can be computed as

$Z(\chi,t)=\frac{\mbox{det}\left[{\bf
g}_{0}^{-1}-{\bf\Sigma(\chi)}\right]}{\mbox{det}\left[{\bf
g}_{0}^{-1}-{\bf\Sigma}(\chi=0)\right]}\,.$ (19)

Finally, it is worth commenting that the same expression can be used to
compute the transferred charge and current cumulants by taking successive
derivatives of the GF as $\left\langle
c_{k}(t)\right\rangle=\partial^{k}/\partial(i\chi)^{k}\,\mbox{Log}[Z(\chi,t)]_{\chi=0}$
and $\left\langle I^{k}(t)\right\rangle=\partial/\partial t\,\left\langle
c_{k}(t)\right\rangle$, for $\chi_{L}=-\chi_{R}=\chi/2$.

##  Appendix C MBS parity oscillations

The charge-transfer based operations are not protected by topology. Therefore,
they can suffer from decoherence and processes affecting the MBSs parity. This
is the case for the parity oscillations shown in the right panel of Fig. 2 of
the main text. They occur for any superconducting phase difference, except for
$\phi=\pi$ (mod $2\pi$), where the final state after an adiabatic operation at
zero temperature does not depend on how it is performed. In this section of
the SI we analyze the absence of parity oscillations at this particular phase,
discussing the effect of small deviations from $\phi=\pi$ (mod $2\pi$). In the
following we will consider an adiabatic operation and focus on the zero
temperature case, i.e. no excited quasiparticles above the superconducting
gap.

We consider the effective Hamiltonian

$H_{eff}=H_{QD}+H_{c}+H_{T}\,,$ (20)

where the Hamiltonian of the continuum of states above the superconducting gap
is given by

$H_{c}=\sum_{k,\nu=L,R}\left[\xi_{k}c_{k,\nu}^{\dagger}c_{k,\nu}-\Delta\left(c_{k,\nu}c_{-k,\nu}+\mbox{H.C.}\right)\right]\,.$
(21)

This term can be diagonalized using the Bogoliuvob transformation, finding

$\tilde{H}_{c}=\sum_{k,\nu=L,R}E_{k}\gamma_{k,\nu}^{\dagger}\gamma_{k,\nu}\,,$
(22)

where $E_{k}=\sqrt{\xi_{k}^{2}+\Delta^{2}}$ and the tilde is used to denote
the transformed Hamiltonian. The Bogoliuvob quasiparticle operators are given
by
$\gamma_{-k,\nu}^{\dagger}=u_{k,\nu}^{*}c_{-k,\nu}^{\dagger}+v_{k,\nu}^{*}c_{k,\nu}$
and $\gamma_{k,\nu}=u_{k,\nu}c_{k,\nu}-v_{k,\nu}c_{-k,\nu}^{\dagger}$, with
$|u_{k}^{2}|=(1-\xi_{k}/E_{k})/2$ and $|v_{k}^{2}|=(1+\xi_{k}/E_{k})/2$.

The Hamiltonian describing electron tunneling between the QD and the TS
electrodes can be written as a sum of two contributions
$\tilde{H}_{T}=\tilde{H}_{T,MBS}+\tilde{H}_{T,c}$, describing the tunneling to
the MBSs and the continuum of states, respectively. These two contributions
are given by

$\tilde{H}_{T,MBS}=V_{L}\gamma_{L}^{A}(e^{i\phi_{L}/2}d-e^{-i\phi_{L}/2}d^{\dagger})+V_{R}\gamma_{R}^{B}(e^{i\phi_{R}/2}d-e^{-i\phi_{R}/2}d^{\dagger})\,,$
(23)

where $\gamma_{L}^{A}=c_{L}+c_{L}^{\dagger}$ and
$\gamma_{R}^{B}=i(c_{R}-c_{R}^{\dagger})$ are the MBS quasiparticle operators
and

$\tilde{H}_{T,c}=\sum_{k,\nu}V_{k,\nu}\left[e^{-i\phi_{\nu}/2}d^{\dagger}\left(u^{*}_{k,\nu}\gamma_{k,\nu}+v_{k,\nu}\gamma_{k,\nu}^{\dagger}\right)+\mbox{H.C.}\right]\,.$
(24)

The time evolution of a given initial state in the interaction picture can be
obtained through

$\left|\Psi(t)\right\rangle=\mathcal{T}e^{\int_{0}^{t}\tilde{H}_{T}(t^{\prime})dt^{\prime}}\left|\Psi(0)\right\rangle=\mathcal{T}\left[1+\int_{0}^{t}dt_{1}\tilde{H}_{T}(t_{1})+\frac{1}{2}\int_{0}^{t}\int_{0}^{t}dt_{1}dt_{2}\tilde{H}_{T}(t_{1})\tilde{H}_{T}(t_{2})+\ldots\right]\left|\Psi(0)\right\rangle$
(25)

where $\mathcal{T}$ is the time ordering operator. The different terms in the
right hand side of Eq. (25) describe all the possible tunneling events between
the QD and the TSs. The linear term in $\tilde{H}_{T}$ describes the process
in which the QD charge state is transferred to the TSs during the charge-
transfer based operation, while higher order terms describe undesired effects
such as the MBS parity oscillations shown in Fig. 2 of the main text. At
second order in Eq. (25), the only terms affecting the MBS parities are the
ones involving the transfer of an electron between the left and right MBSs. In
the expansion, two of these terms leading to the same final state are given by

$-\mathcal{T}\left\\{V_{L}V_{R}\int dt_{1}\int
dt_{2}\left[e^{i(\phi_{R}-\phi_{L})/2}\gamma^{A}_{L}(t_{1})d^{\dagger}(t_{1})\gamma^{B}_{R}(t_{2})d(t_{2})+e^{i(\phi_{L}-\phi_{R})/2}\gamma^{B}_{R}(t_{1})d^{\dagger}(t_{1})\gamma^{A}_{L}(t_{2})d(t_{2})\right]\right\\}\,.$
(26)

These processes give as a consequence an electron transferred from the left to
the right TS, changing the MBS parity at both sides of the junction. For a
phase difference $\phi=\pi$ (mod $2\pi$), the two contributions in Eq. (26)
cancel each other, negating the undesired parity changes between the MBSs. A
similar cancellation can be found for the remaining second order terms
affecting the MBSs parity state. In a similar way, for any higher order term
in $\tilde{H}_{T,MBS}$ in Eq. (25), there is always another one of the same
order cancelling its contribution for $\phi=\pi$ (mod $2\pi$).

At zero temperature, the continuum of states outside the superconducting gap
start to contribute to the MBS parity at fourth order in $\tilde{H}_{T}$ in
Eq. (25). It describes processes where electrons (or holes) coming from the
continuum of states can tunnel to the MBSs, mediated by the QD. Two of these
processes leading to the same final state are described by

$\displaystyle\mathcal{T}\left\\{V_{L}V^{3}_{R}\int dt_{1}\ldots\int
dt_{4}\left[e^{i(\phi_{R}-\phi_{L})/2}\tilde{H}_{T,c}(t_{4})\gamma^{A}_{L}(t_{3})d^{\dagger}(t_{3})\gamma^{B}_{R}(t_{2})d(t_{2})\tilde{H}_{T,c}(t_{1})+\right.\right.$
$\displaystyle\left.\left.e^{i(\phi_{R}-\phi_{L})/2}\tilde{H}_{T,c}(t_{4})\gamma^{B}_{R}(t_{3})d^{\dagger}(t_{3})\gamma^{A}_{L}(t_{2})d(t_{2})\tilde{H}_{T,c}(t_{1})\right]\right\\}\,,$
(27)

which cancel each other for $\phi=\pi$ (mod $2\pi$). It can be demonstrated
that, for any other higher order term affecting the MBSs parity state, there
exists another one of the same order cancelling it for this phase difference.
It implies that the states above the superconducting gap do not induce changes
on the MBSs parity state at $T=0$ for $\phi=\pi$ (mod $2\pi$). Therefore, the
main errors occurring during the operation for these parameters are due to
non-adiabatic effects. We note that dephasing is not important in the analyzed
parameter regime, as shown in Fig. 4.

For $\phi\neq(2n+1)\pi$, the higher order contributions in $\tilde{H}_{T}$ in
Eq. (25) do not cancel. They give rise to a time oscillation of the MBSs
parity as shown in Fig. 2 of the main text, leading to an oscillating current
Bondyopadhaya and Roy (2019) in time, due to the breaking of degeneracy
between the even and odd parity states of the non-local fermion formed by
$\gamma^{A}_{L}$ and $\gamma^{B}_{R}$. Because of these oscillations, the
final state depends on the details of the operation (such as sweep rate), even
in the adiabatic limit. Also, they can lead to a result similar to the fully
dephased situation when the QD energy is not far enough above the
superconducting gap, if the characteristic measurement time on MBS parity is
larger than the oscillation period.

Slightly away from the ideal condition, $\phi=(2n+1)\pi+\delta\phi$, the
higher order terms in the expansion of Eq. (25) start to contribute. In order
to minimize their contribution, the manipulation time should be faster than
their characteristic time scales given by
$\sqrt{\epsilon^{2}_{0}+4(V^{2}_{L}+V^{2}_{R})}/(4V_{L}V_{R}\delta\phi)$ for
$\delta\phi\ll 1$. It defines an upper limit for the operation time scale,
illustrating the importance of accurately control the phase difference between
the TSs.

Finally, it is worth commenting that this demonstration is based on several
assumptions. Firstly, we have assumed that the electrons tunneling from a
given lead have a well-defined phase. Additionally, the demonstration is based
on the assumption that adding and removing electrons from the MBSs lead to the
same final state, as there is no charging energy in the TSs. Therefore, it is
important that superconductors are grounded. Furthermore, a coupling between
the MBSs in the same TS, lifting the even-odd ground state degeneracy, can be
detrimental for the charge-based operations, as shown in the next section
using a simplified version of the effective Hamiltonian (28). Finally, a non-
zero temperature or a non-adiabatic operation can induce errors during the QD
manipulation, as discussed in the main text.

##  Appendix D Low energy model: overlap between MBSs.

In this section, we introduce a simplified model that includes only the low
energy degrees of freedom. It disregards the electronic degrees of freedom
outside the superconducting gap. The low energy Hamiltonian is given by

$H_{LEM}=H_{QD}+H_{T,MBS}+H_{o,MBS}\,,$ (28)

where $H_{QD}=\epsilon_{0}(t)d^{\dagger}d$ with $\epsilon_{0}(t)$ the time-
dependent energy level and the tunneling between the MBSs and the dot is
described by Eq. (23). Finally,
$H_{o,MBS}=\sum_{\nu=L,R}\eta_{\nu}\gamma_{\nu}^{A}\gamma_{\nu}^{B}$ describes
the overlap between MBSs at the same wire.

Using the low energy Hamiltonian of Eq. (28), the time evolution of a given
initial state, $\left|\Psi(0)\right\rangle$, is described by unitary evolution
as

$\left|\Psi(t+\delta t)\right\rangle=\exp\left(-iH_{LEM}\delta
t\right)\left|\Psi(t)\right\rangle\,,$ (29)

where $\delta t$ has to be taken much smaller than the smallest inverse energy
in the model to ensure convergence. The simplified model provided in Eq. (28)
correctly describes the time evolution of the system for adiabatic
manipulations, as shown in the top panel of Fig. 4 of the main text. However,
it does not describe the effect of thermally excited quasiparticles in the TSs
and the relaxation of QD charge to the continuum of states for non-adiabatic
manipulations.

In agreement with the full calculation, for $V_{L}=V_{R}$,
$\phi_{L}-\phi_{R}=2n\pi$ and $\eta_{\nu}\neq 0$, the Hamiltonian of Eq. (28)
describes the existence of dark states partially decoupling subspaces with
different total MBS parity states. They are given by
$(\left|1,1\right\rangle-i\left|-1,-1\right\rangle)/\sqrt{2}$ and
$(\left|1,-1\right\rangle-i\left|-1,1\right\rangle)/\sqrt{2}$ for the even and
odd MBS parities respectively. These states are decoupled from each other,
limiting the success probability to $P=1/2$ for an initial state with a well
defined MBS parity at both sides of the junction. In a more general situation
with $\phi_{L}-\phi_{R}\neq 2n\pi$, the probability can reach values close to
unity. However, the manipulation time depends strongly on the superconducting
phase difference, as shown in the right panel of Fig. 2 of the main text.

Figure C.6: Occupation of the global ground state (solid lines) and excited
state (dashed lines) of the same parity after a manipulation. Results are
showed for an asymmetric coupling between MBSs in the left and right lead,
$\eta_{L}=V_{L}/10$, $\eta_{R}=\eta_{L}/2$ and
$\delta\eta=|\eta_{L}-\eta_{R}|$. The remaining parameters are $V_{L}=V_{R}$
and $\phi=\pi$.

The model in Eq. (28) allows us to easily incorporate the coupling between
MBSs in the same wire, which lifts their ground state degeneracy. For
$\eta_{L}=\eta_{R}$ and starting from the ground state of the two TSs, an
adiabatic QD level manipulation also leads to a coherent superposition between
even and odd MBS parity states for each electrode. In contrast, for
$\eta_{L}\neq\eta_{R}$ an adiabatic manipulation leads to a convergence to the
global ground state of the system, as illustrated by the blue lines in Fig.
C.6. Therefore, $1/\delta\eta$ defines a lower bound for the manipulation
rate, with $\delta\eta=|\eta_{L}-\eta_{R}|$.

Figure C.7: Parity of the left (red curves) and right (blue curves) MBSs for
different values of a random phase introduced in the quantum state after the
first manipulation (see text for details). The parameters are
$V_{L}=V_{R}=0.39$, $\phi=\pi$ and $r=1/2$. Time units have chosen to be the
asme as in Fig. 4 of the main text.

Another question of interest that can be analyzed using the model of Eq. (28)
is related to the signatures of the quantum state degradation. This is
analyzed in Fig. C.7, where we consider an adiabatic evolution of the QD from
negative to positive energies, returning back to its original value at long
times. Given $\left|1,-1\right\rangle_{i}$ as the initial state for the MBSs,
the quantum state of the system evolves after the first manipulation to a
state $\propto
V_{L}e^{-i\phi_{L}/2}\left|-1\,-1\right\rangle+V_{R}e^{i\phi_{R}/2}\left|1,1\right\rangle$
for an adiabatic manipulation. To simulate the effect from decoherence, we
include a random phase factor in one of the terms. The state before the second
manipulation is thus given by $\propto
V_{L}e^{-i\phi_{L}/2}\left|-1,-1\right\rangle+V_{R}e^{i(\phi_{R}/2+\xi)}\left|1,1\right\rangle$.
The phase factor $\xi$ is taken as a random variable with all the values
equally distributed within an interval. The result for different ranges of
$\xi$ is shown in Fig. C.7 (in the lower panel of Fig. 4 of the main text we
have taken $\xi\in[-\pi/2,\pi/2]$), demonstrating the convergence to
$\left\langle p_{\nu}\right\rangle=0$ for a case where the system coherence is
completely lost in the process.


# Mating of discrete trees and walks in the quarter-plane

Philippe Biane<EMAIL_ADDRESS>Institut Gaspard Monge UMR CNRS - 8049
Université Gustave Eiffel 5 boulevard Descartes, 77454 Champs-Sur-Marne FRANCE

###### Abstract.

We give a general construction of triangulations starting from a walk in the
quarter plane with small steps, which is a discrete version of the mating of
trees. We use a special instance of this construction to give a bijection
between maps equipped with a rooted spanning tree and walks in the quarter
plane. We also show how the construction allows to recover several known
bijections between such objects in a uniform way.

##  1\. Introduction

Mating of polynomials originates in complex dynamics, where one can match two
Julia sets in order to build a topological sphere or a surface, see e.g. [2]
and

https://www.math.univ-toulouse.fr/ cheritat/MatMovies/

for nice pictures and movies. This includes in particular the case of Julia
sets which are topologically real trees. This construction has been introduced
in probability by Le Gall and Paulin [11] for studying the topology of the
Brownian map and then used, under the name “mating of trees” by Duplantier,
Miller and Sheffield [8] in quantum gravity, followed by many others. A
discrete version of this construction already appears in Mullin’s bijection
(see [13]) and has been further used recently by several authors, see e.g.
Gwynne, Holden and Sun [9] for a recent overview. The basic idea is to
consider a walk in the quarter plane $x,y\geq 0$, with steps in the set
$\\{(1,0),(-1,0),(0,1),(0,-1)\\}$, starting and ending at $0$, and to write
the vertical and horizontal coordinates of the walk as two opposite Motzkin
paths running vertically. See below, with one Motzkin path on the left for the
horizontal coordinate and one on the right for the vertical coordinate:

then mate the two Motzkin paths by drawing horizontal lines between vertices:

The Motzkin paths are then contracted into trees in the usual way, while the
upper and lower boundaries of the rectangle are identified. The resulting map
is a planar triangulation. I will give a more detailed explanation in the
following sections.

In this note I use a generalization of these ideas to walks with small steps,
i.e. with steps taken in the set
$\\{(1,0),(-1,0),(0,1),(0,-1),(-1,-1),(1,-1),(-1,1),(1,1)\\}$, which involves
constructing a map with faces of degrees three and four then contracting the
faces of degree four. As we shall see, the generality of the construction and
the many variants one can produce from it make it a versatile tool for
producing bijections between specific classes of walks and of maps. Again, the
precise definitions will be given in the next section. Using this I give a
bijection between a certain class of walks in the quarter plane (which I call
reversed $Y$-walks, see below) and maps equipped with a rooted spanning tree
in which the degrees of the vertices are encoded by the length of the steps of
the walk. This bijection is quite different from Mullin’s bijection but bears
some connection with blossoming bijections [13]. These ideas also allow us to
reinterpret several known bijections between walks and triangulations, or more
general planar maps. In particular we will show how the following bijections
fit into this framework:

  * •

The bijection of Mullin, between walks in the quarter plane with straight
steps and triangulations having a Hamiltonian cycle.

  * •

A bijection of Bernardi between Kreweras walks and triangulations with a
spanning tree.

  * •

A bijection of Kenyon, Miller, Sheffield and Wilson between walks and maps
with a bipolar orientation.

  * •

A bijection of Li, Sun and Watson between tandem walks satisfying some further
conditions and Schnyder woods.

Rather than the particular results which are obtained, we think that the main
interest of this paper is its general philosophy and its potential to produce
a wealth of bijections between walks and maps.

This paper is organized as follows. In the next section I give a general
algorithm for producing planar triangulations, starting from a walk with small
steps in the quarter plane. In order to obtain precise bijections one needs to
specify a number of parameters in this construction. In section 3 I introduce
reversed $Y$-walks in the quarter plane and I give a new bijection between
these walks and planar maps equipped with a spanning tree. Then, in section 4,
I show how to recover the bijections listed above using similar
considerations.

##  2\. Associating a triangulation to a walk in the quarter plane

###  2.1. Trees and Dyck paths

There is a well known way to associate a rooted planar tree to a Dyck path by
matching up and down steps:

One can think that one cuts out from the plane the striped area under the Dyck
path and sews the up and down steps to produce the tree embedded into the
plane. One can generalize this construction to Motzkin paths by shrinking each
horizontal step to a point.

### 2.2.

One can also consider paths which do not start or end at $0$ and build a
forest of trees, rooted on a $V$-shaped path:

Some down steps (before the minimum of the path is reached) or upward steps
(after the minimum) are left unmatched and are indicated in red on the
picture. They form the “$V$” on which the forest is rooted.

###  2.3. The basic construction

We consider walks in the quarter plane with small steps: the coordinates of
the steps belong to $\\{-1,0,1\\}$, thus we get $8$ distinct non zero steps:

We can distinguish straight steps: $(1,0),(0,1),(-1,0),(0,-1)$

from oblique steps:

The problem of enumerating such walks has been considered in many papers,
starting from the seminal work [7].

Consider a two-dimensional walk with small steps, starting and ending at the
origin, which remains in the quarter plane $x,y\geq 0$. Here is an example
with twelve steps, ten of which are straight and two oblique:

$(1,0);(0,1);(-1,1);(1,0);(0,-1);(1,0);(0,-1);(0,1);(-1,0);(-1,0);(1,0);(-1,-1).$

The walk is shown below:

The projections of this walk on the coordinate axes are two Motzkin paths with
respective steps $1;0;-1;1;0;1;0;0;-1;-1;1;-1$ and
$0;1;1;0;-1;0;-1;1;0;0;0;-1$:

We draw the two paths vertically in an opposite way, with the horizontal
coordinate on the left and the vertical coordinate on the right, the paths
running from bottom to top.

The mating consists in drawing horizontal lines between the vertices of the
two paths, as below:

Between the two Motzkin paths we have then a succession of quadrilaterals,
each one corresponding to a step of the walk. These quadrilaterals have
several types, some of them, corresponding to straight steps, have one of
their side vertical, while the others, corresponding to oblique steps, have
tilted sides. Here are the straight steps, numbered from bottom to top, and
the shaded oblique steps.

We now contract the two Motzkin paths into two trees as in section 2.1. Again
we can imagine that we cut out the area below each Motzkin path and sew the
boundaries. In this contraction the quadrilaterals corresponding to straight
steps become triangles as, for example:

Once we have made these contractions we obtain a planar map whose faces are
triangles (corresponding to straight steps), quadrilaterals (corresponding to
oblique steps) and an external face with two sides, the two horizontal sides
of the initial rectangle. If we identify these two sides by contracting the
external face, we obtain a planar map, with a distinguished edge, the one
corresponding to the two sides of the rectangle, on which two trees are drawn,
namely the images of the two Motzkin paths. Figure 1 shows the map obtained
from the above walk, where the triangles are numbered and the two
quadrilaterals are shaded, while the two trees are depicted in red and blue
and the distinguished edge (corresponding to the upper and lower boundaries of
the rectangle) is dashed.

Figure 1. Contraction of the Motzkin paths.

In order to obtain a planar triangulation we will contract the quadrilaterals
corresponding to oblique steps: again imagine that one cuts out one of these
quadrilaterals from the plane, then identifies two opposite vertices, pairs
the edges correspondingly and sews them. More precisely, consider such a
quadrilateral:

There are two ways to contract this quadrilateral along one of its diagonals
to produce two segments, either like this by identifying opposite vertices $v$
and $w$ and accordingly sewing the edge $uv$ with $uw$ and the edge $vz$ with
$wz$:

or like this, identifying $u$ and $z$:

Let $o$ be the number of oblique steps in the walk. From the map corresponding
to the walk we can obtain $2^{o}$ triangulations by removing the
quadrilaterals and, for each one, sewing its boundaries according to the two
possibilites. Figure 2 shows the result of a choice of such contractions on
the map of Figure 1.

Figure 2. Contracting the quadrilaterals of Figure 1.

The construction presented above is very general, but not one-to-one. Indeed
one can associate to each path $2^{o}$ triangulations, moreover some
triangulations may be obtained by more than one of these constructions.

In the following I will consider specific instances of the construction, where
one restricts the class of steps which are available for the walk and one
gives an explicit algorithm to decide, for each quadrilateral, which of the
two contractions is made. In order to visualize the maps obtained by these
constructions we will find it useful to depict also the dual map as in Figure
3, where we indicate the way we contract the quadrilateral by drawing a dashed
line between the opposite vertices which have been identified, then draw edges
connecting the dual vertices.

Figure 3. The triangulation and its dual cubic map

Before going into the description of the examples, I describe some possible
variations on this construction.

###  2.4. Variations

####  2.4.1. Changing the end point

It is possible to generalize the construction to paths which do not start or
end at zero. Also one can relax the condition that the walk remains in the
quarter plane. In this case the two paths are contracted as explained in
section 2.2 and there remain edges which are not matched. Together with the
upper and lower horizontal sides, they form an external boundary. Here is an
example, where we show vertical lines between matched edges of the paths.
There remains three unmatched edges on the left and two on the right:

At this point, one can either keep the unmatched edges and consider that they
bound an exterior face, or idenfity these edges pairwise, if there is an even
number of them. We will see some examples in the following.

####  2.4.2. Changing the set of steps

It is also possible to use other types of steps. If one uses steps of type
$(i,j)$ then one can consider the path obtained by replacing the step $(i,j)$
by a sequence of $|i|$ steps of type $(\operatorname{sgn}(i),0)$ and $|j|$
steps of type $(0,\operatorname{sgn}(j))$, then erase the horizontal lines in
the polygon thus formed to get a face with $|i|+|j|+2$ edges on the boundary.
For example here, in the case $i=3,j=4$, we get the following picture:

When we erase the internal edges we get a face with nine edges

There are four edges on the right, three on the left, and two horizontal ones
(remember that vertical edges are contracted into points when we contract the
paths). Observe that one can change the order in which the $|i|+|j|$ steps are
made without changing the resulting map.

One has to be careful that there is a potential conflict between such rules
and the contracting rules for oblique paths. We will nevertheless see some
interesting examples.

####  2.4.3. Other contractions

In this paper I consider only contractions of quadrilaterals, according to one
of the two non-crossing pairings of its sides. It would be possible to
consider also contractions of larger faces, as constructed in section 2.4.2.
Such contractions would be obtained from pairings of faces with an even number
of sides. With non-crossing pairings one obtains planar maps, but it would be
also possible to construct maps of higher genus by making more general
pairings. However, we will not explore such possibilities in this paper.

####  2.4.4. Pattern avoiding

If we consider the allowed steps of the walk as forming an alphabet then the
walk can be considered as a word on this alphabet. It is possible to consider
families of walks that are constrained to avoid certain patterns. Again we
will encounter such examples.

####  2.4.5. Symmetries

There are some obvious symmetries in this construction. For example one can
make a symmetry with respect to a vertical axis in pictures like Figure 3.
This corresponds to exchanging the horizontal and vertical directions of the
walks, in other words to make a reflection with respect to the diagonal line
$x=y$ in the plane. Symmetry with respect to a horizontal axis corresponds to
considering walks with opposite steps, in reverse order.

##  3\. Maps with a spanning tree

### 3.1.

In this section we consider walks with steps in the set
$\\{(0,1),(-1,-1),(1,-1)\\}$.

For convenience we will give a name to these walks and refer to them as
“reversed $Y$-walks”, or $rY$-walks (note that, for typographical reasons, the
walks with opposite steps deserve the name of $Y$-walks).

It is easy to count the number of $rY$-walks in the quarterplane, starting and
ending at $0$. Indeed the vertical coordinate of the walk gives a Dyck path,
since the vertical coordinates of steps are either $1$ or $-1$. Choose a Dyck
path of length $4n$ for the vertical coordinate and let $i_{1},\ldots,i_{2n}$
be the indices of the down steps. The horizontal coordinate moves only when a
down step in the vertical direction is made, therefore the walk is specified
by choosing another Dyck path of length $2n$, which describes the horizontal
moves at times $i_{1},\ldots,i_{2n}$. It follows that the number of such walks
is $C_{2n}C_{n}$ where $C_{l}=\frac{1}{l+1}{2l\choose l}$, the number of Dyck
paths of length $2l$, a Catalan number. There is a simple model of maps which
is counted by this number. Consider a cubic planar map (i.e. a map with
vertices of degree three) with $2n$ vertices and thus $3n$ edges. Take $n+1$
of the edges and cut them in two, in order to obtain a tree, with the half-
edges being the leaves of the tree. We call this tree a “complete” spanning
tree. If we choose one of these leaves to root the tree we get a planar binary
tree with $2n$ internal vertices and $2n+1$ leaves, plus the root leaf. This
construction is reminiscent of so-called “blossoming bijections” (see [13], or
[1] for a recent reference), except that we do not orient the leaves of the
tree. The map from which we started can be recovered by pairing these $2n+2$
leaves, to reconstruct the edges which have been cut. In Figure 4(a) I show a
cubic map and a complete spanning tree in 4(b). The root half-edge is in blue,
with an arrow pointing at it and the other half-edges are in red. In Figure
4(c) I show the planar binary tree in standard representation, with the
matching of the leaves giving back the original map.

Figure 4. A cubic map with a complete spanning tree and a marked leaf

Such objects, planar cubic maps on $2n$ vertices, with a complete spanning
tree with a marked leaf, are thus in bijection with pairs $(T,P)$ where $T$ is
a binary tree with $2n$ internal vertices and a leaf added to the root, and
$P$ is a pairing of the $2n+2$ leaves. The leaves can be ordered cyclically
from the root by going clockwise around the tree, thus the pairings are in
bijection with non-crossing pairings of $[1,2n+2]$. There are $C_{2n}$ planar
binary trees. Since there are $C_{n+1}$ non-crossing pairings we get
$C_{2n}C_{n+1}$ pairs $(T,P)$. This is not quite $C_{2n}C_{n}$, but if we add
the constraint that the root leaf has to pair with its immediate successor
then we get the right number $C_{2n}C_{n}$. We call such an object a “special”
planar cubic map on $2n$ vertices, with a complete spanning tree with a marked
leaf. For example the cubic map depicted in Figure 4 is special since the root
leaf is paired with its successor. We will see that our construction provides
a geometric realization of this bijection between walks and such maps. We will
also extend it to a walk model for “non-special” cubic maps with a complete
spanning tree rooted at some half-edge.

###  3.2. The construction

The $rY$-walks have two types of oblique steps, so we must give the rules for
contracting the associated quadrilaterals. These rules are simple, we show
them below.

######  Contraction Rules 3.1.

i.e. in both cases identify the NW and SE corners.

###  3.3. Some bijections

There is a simple and well known bijection, which we shall denote by
$\mathcal{T}$, between rooted planar binary trees with $n$ vertices and Dyck
paths with $2n$ steps, which is best described recursively. Write a Dyck path
as a sequence of up $(u)$ and down $(d)$ steps. Then $\mathcal{T}(ud)$ is the
unique rooted planar binary tree with one vertex. For any Dyck path
$\mathcal{D}$, of length $2n$, write it uniquely as
$\mathcal{D}=u\mathcal{D}_{1}d\mathcal{D}_{2}$, where $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$ are Dyck paths of lengths $2k-2$ and $2n-2k$. Here $2k$ is
the time of first return to $0$ for $\mathcal{D}$. Then
$\mathcal{T}(\mathcal{D})$ is the binary tree whose left branch is
$\mathcal{T}(\mathcal{D}_{1})$ and whose right branch is
$\mathcal{T}(\mathcal{D}_{2})$. This tree can be obtained easily from our
construction as follows: write the Dyck path on the right but leave the left
extremities of the quadrilaterals unfinished, so that we do not make the
identifications on the left of the picture. This is shown in Figure 5(a). The
cut dual map is a tree and it is obvious that its construction satisfies the
same recursion as the bijection $\mathcal{T}$. Observe that the leaves of the
tree (in red in the picture) appear ordered on the left of the picture (except
the root leaf and its immediate successor). There is also a simple and well
known bijection between Dyck paths and noncrossing pairings which consists in
pairing up and down steps. For example, the non-crossing pairing
$(1,8),(2,3),(4,7),(5,6)$ corresponds to the Dyck path $uuduuddd$;

Figure 5. $rY$-walks and their associated maps.
(a) Construction of the spanning tree using the vertical coordinates.
(b) Matching the leaves using the horizontal coordinates.

When we complete the picture on the left, as in Figure 5(b) the Dyck path
corresponding to the horizontal coordinate determines the non-crossing pairing
of the leaves. It remains to pair the root leaf with the leaf going through
the upper side of the rectangle to obtain a special cubic map. Conversely,
given a special cubic map with a complete, rooted spanning tree, the spanning
tree gives us the vertical coordinate of an $rY$-walk, while the pairing of
the leaves gives us the horizontal coordinate. Finally one has the following.

######  Theorem 3.2.

The construction with Contraction Rules 3.1 gives a bijection between
$rY$-walks in the quarter plane, starting and ending at $0$, with $4n$ steps,
and special cubic maps with a complete spanning tree, rooted at some half-
edge, with $2n$ vertices.

We have seen that, in this construction, the root leaf is paired with its
immediate successor. In order to obtain all possible pairings, let us instead
consider walks starting at $0$ but ending at the point $(2,0)$. Making the
contractions of paths as in section 2.2 we end up with Figure 6(a), where
there are four half-edges unmatched in the dual map: the half-edges
corresponding to the upper and lower sides of the rectangle and two half-edges
coming from the two up steps on the left which are not matched with a down
step. We then pair these half-edges so that the upper and lower horizontal
sides are not matched, as in Figure 6(b) This gives a cubic map with a
complete spanning tree, in which the root is not paired with its immediate
successor.

Figure 6. Non special maps.
(a) Map with four unpaired leaves.
(b) Matching the remaining leaves .

Putting this together with the preceding construction, we get:

######  Theorem 3.3.

The construction with Contraction Rules 3.1 gives a bijection between
$rY$-walks on the quarter plane starting at $0$ and ending at $0$ or $(2,0)$,
with $4n$ steps, and cubic maps with a rooted complete spanning tree, with
$2n$ vertices.

###  3.4. Variants

Instead of the step $(0,1)$ we could consider $(0,2)$. Again it is easy to
enumerate all walks with step set $\\{(-1,-1),(1,-1),(0,2)\\}$ which start and
end at $0$: in the vertical direction we have a walk with steps $2$ and $-1$
and an application of the cycle lemma give the number of such walks with $3n$
steps, which is $\frac{1}{2n+1}{3n\choose n}=C^{(2)}_{n}$, a Fuss-Catalan
number (see e.g. [5]). On the set of $2n$ negative steps we have to choose a
Dyck path of length $2$ which gives a Catalan number $C_{n}$. The final count
is $C^{(2)}_{n}C_{n}$. Again our construction gives a bijection between walks
with step set $\\{-1,2\\}$ and ternary trees, as in Figure 7(a), which we can
complete as in Figure 7(b).

Figure 7. Quartic maps.

######  Theorem 3.4.

The construction with Contraction Rules 3.1 gives a bijection between walks on
the quarter plane with step set

$\\{(0,2),(-1,-1),(1,-1)\\}$

starting and ending at $0$, with $3n$ steps, and special quartic maps with a
complete spanning tree, with $3n$ vertices. When extending to walks ending at
$(2,0)$, we get a bijection with quartic maps with a complete rooted spanning
tree.

Obviously this can be further extended to a bijection between planar maps
equipped with a spanning tree and a marked leaf, with walks whose steps belong
to the infinite set

$\\{(-1,-1),(1,-1),(0,k);k\geq 0\\}$

starting at $0$ and ending at $0$ or $(2,0)$. Observe that the vertical
component of such a walk is a Łukasiewicz path. Applying the same algorithm as
above recovers a well known bijection between Łukasiewicz paths and trees (see
e.g. [15]), which extends the bijection between Dyck paths and binary trees.

######  Theorem 3.5.

The construction with Contraction Rules 3.1 gives a bijection between walks on
the quarter plane with step set

$\\{(-1,-1),(1,-1),(0,k),k\geq 0\\}$

starting at $0$ and ending at $0$ or $(2,0)$, and planar maps with vertices of
degree $\geq 2$, with a complete spanning tree. In this bijection, steps of
type $(0,k)$ of the walk correspond to vertices of degree $k+2$ of the map.

Mullin’s construction (as explained in Schaeffer [14]) also provides a
bijection between maps equipped with a spanning tree and walks in the quarter
plane but this is a quite different bijection, for example the set of steps
allowed in Mullin’s bijection is the set of straight steps.

##  4\. Recovering other bijections

###  4.1. Triangulations with a Hamiltonian cycle on the faces

We consider a planar triangulation equipped with a Hamiltonian cycle of its
dual graph. This amounts to choosing an ordering $f_{1},f_{2},\ldots,f_{n}$ of
the faces of the triangulation such that, for all $i$, the faces $f_{i}$ and
$f_{i+1}$ are adjacent (where $i+1$ is taken modulo $n$) and for each $i$ one
chooses an edge $e_{i}$ in the common boundary of $f_{i}$ and $f_{i+1}$. Here
is an example where the Hamiltonian cycle is in red, the faces are numbered
from $1$ to $8$ and the edges $e_{i}$ are the edges crossed by the red path.

The graph formed from the vertices of the triangulation and the edges which do
not belong to the set $e_{1},e_{2},\ldots,e_{n}$ is made of two disjoint trees
and the Hamiltonian cycle goes around each of them, one of them being on its
right and the other one on its left. Here is the picture:

We go around the cycle and record the successive triangles. Each such triangle
has exactly one side in one of the trees. If this side is in the left tree we
record a $(1,0)$ step, if the path goes up in the tree and a $(-1,0)$ step if
it goes down. If the side is in the right tree we record similarly a $(0,\pm
1)$ step. The final picture is

where we draw the Hamiltonian cycle in red, but not the whole dual map. It is
immediate to see that we obtain in this way a walk in the quarter plane, with
straight steps, starting and ending at $0$. This construction yields a
bijection between walks with straight steps in the quarter plane, starting and
ending at $0$, and planar triangulations equipped with a Hamiltonian cycle of
the dual graph. This is well known and occurs in Mullin’s bijection between
maps with a spanning tree and walks on the quarter plane, see e.g. [14],
section 1.2. See also [9] for a recent overview of applications of this kind
of bijections to random maps. In the remaining sections we will obtain
examples with more flexibility by looking at classes of walks having oblique
steps.

###  4.2.  Kreweras walks and Bernardi’s bijection

We now consider a bijection of Bernardi [5] (also used in [6]). A Kreweras
walk has steps in the set $\\{a,b,c\\}$ where $a=(1,0),$ $b=(0,1)$ and
$c=(-1,-1)$.

It can be shown that Kreweras walks with $3n$ steps, which remain in the
quarter plane, starting and ending at $0$, are enumerated by the formula
$\frac{2^{n}}{2n+1}{3n\choose n}$. This formula is explained in a bijective
way in Bernardi [5]. We will see how to recover his bijection using our
construction.

We thus consider a Kreweras walk, which remains in the quarter plane, starting
and ending at $0$, When we do the construction of section 2.3 the steps of
types $a$ or $b$ give triangles when we contract the Motzkin paths. The steps
of type $c$ give rise to quadrilaterals as below:

######  Contraction Rules 4.1.

Consider the sides $uw$ and $vz$ of the quadrilateral corresponding to a step
of type $c$. In the contraction of the two Motzkin paths, each of these sides
is matched with another segment below it, moreover this segment belongs to a
step of type $a$ (for the $uw$ segment) and to a step of type $b$ (for the
$vz$ segment). In the enumeration $x_{1},x_{2},\ldots,x_{n}$ of the steps of
the walk let $i$ and $j$, respectively, be the indices of these steps, thus
$x_{i}=a$ and $x_{j}=b$ . If $i<j$ then we identify $u$ and $z$ in the
contraction of the quadrilateral $uvwz$. If $i>j$ then we identify $v$ and
$w$.

Here is the case of the path with sequence of steps $aabbccbac$, with the dual
cubic map in green:

Observe that the triangulation (and the dual cubic map) are loopless. Indeed a
loop in the construction could be obtained only if, just after an $a$ or $b$
step, the $c$ step is contracted so that it has two sides in common with the
preceding step:

but the rules of contraction prevent this.

Each vertex of the dual map has three half-edges, which we orient so that the
half-edge corresponding to the base of the triangle is incoming and the ones
corresponding to the other sides of the triangle are outgoing:

If we keep only the edges of the dual map having half-edges with matching
orientations we obtain a spanning tree like this:

We will now see that the data of the loopless triangulation and the spanning
tree of the dual are exactly the ones obtained from Bernardi’s bijection. The
tree is a special kind of tree, called depth tree in [5], but we will not need
to go into this here. Let us sketch Bernardi’s construction and check that it
is the same as this one. More details can be found in [5]. The construction is
done step by step, by growing the dual cubic map and a spanning tree, using
three mappings denoted $\varphi_{a},\varphi_{b},\varphi_{c}$. Observe that in
[5] the Kreweras walk has in fact opposite steps as the ones used in this
paper, but since Bernardi scans the steps of the walk in reverse order, the
result is the same. The algorithm starts with a vertical arrow pointing
outside the root:

At each step a growing map (which we depict by a circle) is constructed, with
half-edges pointing outside, one of them being endowed with an arrow pointing
upwards:

The mapping $\varphi_{a}$ consists in transforming the half-edge containing
the arrow into an edge and adding on top of this edge a pair of half-edges,
with the right half-edge carrying the arrow like this:

In case of a step $b$ the mapping $\varphi_{b}$ is similar but the arrow is on
the left.

Among all half-edges pointing out of the growing map there exists some on the
right of the arrow and some on the left, in particular if there are at least
one half-edge on each side we can single out the ones which are closest to the
arrow.

Bernardi shows that in his construction one of them is an ancestor of the
other in the growing tree. Let us call $s$ this ancestor and $t$ the other
half-edge.

In case of a step $c$ the mapping $\varphi_{c}$ consists in joining the half-
edge containing the arrow to $s$ in order to make an edge of the growing map
and taking $t$ to carry the new arrow.

After the last step has been made, the remaining arrow is linked to the root
vertex. The algorithm is illustrated below for the Kreweras walk $aabbccbac$.
We denote the final step by $f$.

It is now a simple matter to check that Bernardi’s bijection corresponds
exactly to our construction. Indeed by going up in the diagram associated to
the walk we see that application of $\varphi_{a}$ corresponds to a step of
type $a$, similarly for $\varphi_{b}$. For steps of type $c$ we have to check
that our rule is the same as for Bernardi’s map $\varphi_{c}$. This follows
from the fact proved by Bernardi that the two half-edges candidates for a
pairing with the arrow are ordered in the tree: then the one that is closest
to the root must be the one that has lowest numbering in the walk.

###  4.3. Tandem walks, prographs and maps with a bipolar orientation

####  4.3.1. A bijection between prographs and tandem walks

We consider oriented planar graphs made of “products” with two inputs and one
output (from bottom to top)

and “coproducts” with one input and two outputs

The terminology comes from the theory of operads, cf Borie [3]. One can use
outputs as new inputs and get in this way configurations which are oriented
from bottom to top. Prographs are such planar configurations with one input
and one output. For example here is the only configuration with one product
and one coproduct. A more complex example is given in Figure 8(a).

One can connect the input and the output to $\infty$ and one obtains in this
way a planar cubic graph, dual to a triangulation of the sphere. Prographs can
be enumerated (see [3]), they are equinumerous with tandem walks i.e. walks in
the quarter plane, starting and ending at $0$, with steps in the set
$a=(0,1),\ b=(1,-1),\ c=(-1,0)$,

A tandem walk is a word in the alphabet $a,b,c$ and the condition to stay in
the quarter plane is that $\sharp a\geq\sharp b\geq\sharp c$ for any prefix.
This corresponds to the natural two dimensional generalization of the ballot
problem. There is a simple bijection going from tandem walks in the quarter
plane, starting and ending at $0$, to the set of standard Young tableaux with
rectangular shape, having three rows of the same length, the numbers in the
first line being the positions of the $a$ letters in the word, of the $b$
letters in the second line and of the $c$ letters in the third line. They can
thus be counted using the hook formula: there are
$\frac{2(3n)!}{n!(n+1)!(n+2)!}$ tandem walks, starting and ending at $0$, with
$3n$ steps. Tandem walks can be realized as a subset of $rY$-walks. Indeed, if
in a tandem walk we replace each occurence of the step $c=(-1,0)$ by a step
$(0,1)$ immediately followed by a step $(-1,-1)$, we obtain an $rY$-walk. Thus
we can refer to tandem walks as $rY$ walks with some forbidden patterns : no
step $(0,1)$ is followed by a step $(0,1)$ or a step $(-1,1)$.

Consider a tandem walk in the quarter plane, starting and ending at $0$. Using
the construction of section 2 there are three types of cells:

Quadrilaterals such as $a$ and $c$ give triangles, while, in case $b$ we will
smash the quadrilateral according to its natural bent:

######  Contraction Rules 4.2.

These rules form a subset of the Contraction Rules 3.1, moreover the other
Contraction Rule for $rY$-walks is compatible with the interpretation of a
step $c$ as formed by a step $(0,1)$ followed by a step $(-1,-1)$. The left
hand of the following picture shows the steps $(0,1)$ and $(-1,-1)$ and the
right hand shows the $c$ step. Clearly the two are equivalent.

The construction using Contraction Rules 4.2 associates to a tandem walk in
the quarter plane, starting and ending at $0$, a prograph, obtained as the
dual of the triangulation. Indeed it is easy to see that in the construction
each $a$ step corresponds to a coproduct while a $c$-step corresponds to a
product. Here is an example with the word $abacbc$:

The corresponding Young tableau is

4 | 6
---|---
2 | 5
1 | 3

This correspondance between tandem walks and prographs is in fact a bijection
and the inverse bijection is readily obtained from the connection, referred to
above, with $rY$-walks. It can be explicitly described as follows. Given a
prograph, cut the left input of each coproduct. The resulting graph is a
complete spanning tree. Let us call a corner the region just above a coproduct
(between its two outputs). Make a depth first search of the tree and order the
vertices and corners according to their first appearance. Make an $a$-step the
first time you go through a coproduct, a $b$-step the first time you go
through a product, and a $c$-step for each corner, this gives the tandem walk
corresponding to the prograph. The construction is shown in Figure 8.

Figure 8. From prographs to tandem walks.
(a) A prograph.
(b) Cutting left inputs and exploring the tree.
(c) The resulting path, recovering the prograph as the dual of the
triangulation.

####  4.3.2. Connections with bipolar maps and the bijection of Kenyon,
Miller, Sheffield and Wilson

As in section 2.4, one can extend the previous construction to walks which do
not start or end at zero and to walks with more general step set. Here we will
consider walks starting at a point of the type $(0,n)$ and ending at $(m,0)$
for some $m,n\geq 0$. We will also consider the infinite step set

$\mathcal{S}=\\{(1,-1),(-i,j);i,j\geq 0,i+j>0\\}$

The contruction using Contraction Rules 4.2 provides a map from walks with
step set $\mathcal{S}$ to some set of “generalized prographs”, which are made
of vertices with $i$ inputs and $j$ outputs, as shown below, with 3 inputs and
2 outputs:

Instead of looking at these generalized prographs and trying to characterize
the ones that we obtain, we will instead look at the dual maps. A vertex of a
generalized prograph corresponds to a face in the dual map. The face
associated with a step of the form $(-i,j)$ will have $i+j+2$ sides. We will
orient the sides of such a face from west to east, e.g. for $i=3,j=2$ :

For a quadrilateral corresponding to a step $(-1,1)$ :

Clearly these orientations are compatible with the identifications between
sides made when contracting the Motzkin paths or the quadrilaterals. The
orientation of the map produced in this way is acyclic, has a unique source
(the west-most point) and a unique sink (the east-most point). We claim that
the oriented maps that we obtain are exactly the bipolar oriented maps as
defined in [10] and, up to some minor twists, our construction recovers their
bijection with walks in the quarter plane. In [10] this bijection proceeds
inductively by looking at the steps of a walk and building an associated map
by sewing faces. More precisely a face with $i+j+2$ sides is associated with
every step of the form $(-i,j)$. It is easy to check that the sewing algorithm
corresponds exactly to our construction. Instead of giving full proofs we will
just check the example of [10], section 2.2 and leave the details to the
reader.

In Figure 9(a) the picture corresponding to this example is drawn.

Figure 9. (a) The example of [10] with steps
$\scriptstyle(1,-1);(0,2);(-1,0);(0,1);(1,-1);(1,-1);(-1,1);(0,1);(1,-1);(1,-1);(1,-1);(1,-1);(-1,0);(-2,1);(1,-1)$.
(b) After a reflection through the main diagonal.
(c) The map drawn as in [10].

In order to recover the map of [10], Figure 4, we make a reflection with
respect to the $x=y$ axis, as shown in Figure 9(b). After contractions the
result is shown in Figure 9(c).

###  4.4. Schnyder woods

We now describe a bijection betwen walks and Schnyder woods, originated in Li,
Sun and Watson [12]. A Schnyder wood is a planar triangulation in which the
three vertices of the external face are coloured, in clockwise order, in
green, red and blue. The internal edges are also coloured so that they form
three trees, one of each colour, rooted on the external vertex of its own
colour and containing all internal vertices. These trees are oriented towards
their roots. The edges have to satisfy the Schnyder condition at each internal
vertex: in clockwise order around the vertex, we have successively the
outgoing blue edge, incoming red edges, outgoing green edge, incoming blue
edges, outgoing red edge and incoming green edges.

It will be convenient for us to also colour in blue the external edge between
the blue and red vertices. Here I take as running example the same as Bernardi
and Bonichon [4], see Figure 10 below.

Figure 10. A Schnyder wood.

To such a Schnyder wood I will associate a tandem walk in the quarter plane,
closely related to the one described in [12]. Since the bijection is studied
in extensively in [12], I will only sketch the proof and leave the details to
the reader.

We start from a Schnyder wood and construct a tandem walk. Recall that the
steps of a tandem walk belong to the set $\\{a=(1,0),\ b=(-1,1),\ c=(0,-1)\\}$
and the condition to remain in the quarter plane is that $\sharp a\geq\sharp
b\geq\sharp c$ for all prefix. We make a contour exploration of the blue tree,
from left to right, starting from the root. The first time we encounter a blue
edge we make a $a$-step in the walk and when we go down this blue edge we make
a $b$ step. At each vertex we may cross several red edges. Each time we cross
an incoming red edge we make a $c$-step in the walk. Finally, after we went up
the last blue edge, we do not go back to the origin, so we do not make the
last $b$-step. Observe that, by the Schnyder condition, a $c$ step can never
occur immediately after a $b$ step. The word obtained in the running example
is:

$aabbacabaccabacbbaacbbbacccc$

Let us check that the walk that we obtain is a tandem walk, starting from
$(0,0)$ and ending at $(1,0)$. Consider the subword of $a$ and $b$ letters. If
we replace the $a$ and $b$ letters by $u$ and $v$ respectively, we obtain the
Dyck path corresponding to the blue tree (with its last step missing),
therefore, for any prefix in the word the number of $a$’s is larger than the
number of $b$’s. Consider the map obtained by erasing the green edges and the
green vertex. In this map construct the tree dual to the red tree and root it
on the external face. It is shown in black in Figure 11. One can see that the
subword formed by the $b$ and $c$ letters gives, upon substituting $u$ for $b$
and $v$ for $c$, the Dyck path of the exploration of this tree from left to
right, therefore, for each prefix in the word, the number of $b$’s is larger
than the number of $c$’s. It follows that the word on the letters $a,b,c$ that
we obtain from the Schnyder wood gives a tandem walk, from $(0,0)$ to $(1,0)$.

Figure 11. A dual tree

Conversely, let $p$ be a tandem walk on the quarter plane from $(0,0)$ to
$(1,0)$ satisfying the condition on steps $b$ and $c$ that the pattern $bc$ is
forbidden. We associate to this walk the mating of trees, as in section 2.1,
using Contraction Rules 4.2, but we do not identify the top and bottom sides
of the rectangle. These two sides, together with the last $a$-step, which has
not been matched with a $b$-step, form the boundary of the external triangle.
The blue tree is obtained from the right blue path. It remains to construct
the red and green trees. They are obtained by colouring some horizontal edges.
We colour red the bottom edge of each triangle of type $c$. Some of the other
horizontal edges are sewed to some blue edges and therefore will be coloured
in blue. The remaining horizontal edges are coloured in green. We orient the
red edges from west to east and the green edges from east to west. Here is the
diagram we obtain in our example.

We have to check that the coloured triangulation that we have constructed is a
Schnyder wood. We can identify the vertices of the triangulation, namely they
are either the vertices of the blue tree, the green vertex corresponding to
the left side of the picture and the red vertex corresponding to the last $c$
steps. The three external edges are the blue edge from the path, corresponding
to the last $a$ step and the upper and lower sides of the picture, as depicted
below:

The vertices of the left tree which are not the root are all matched to a
vertex of the blue tree by the contraction of a quadrangle. It remains to
check the Schnyder condition at each internal vertex. In figure 12 we consider
a typical such vertex. The blue points all correspond to the vertex and the
successive edges and faces traversed when going clockwise around the vertex
are shown on the path with arrows. It is easy to check, using the fact that
the pattern $bc$ is forbidden, that these edges follow the Schnyder condition.

Figure 12. The Schnyder condition around an internal vertex.

Finally, here is the picture of the original Schnyder wood, with the faces
numbered as above.

## References

  * [1] M. Albenque, D. Poulalhon, A generic method for bijections between blossoming trees and planar maps. Electron. J. Combin. 22 (2015), no. 2, Paper 2.38, 44 pp.
  * [2] X. Buff, A.L. Epstein, S. Koch, D. Meyer, K. Pilgrim, M. Rees, T. Lei, Questions about polynomial matings. Ann. Fac. Sci. Toulouse Math. (6) 21 (2012), no. 5, 1149–1176.
  * [3] N. Borie,  Three-dimensional Catalan numbers and product-coproduct prographs. FPSAC 29, Séminaire Lotharingien de combinatoire 76B (2017) Article $\sharp 39$.
  * [4] O. Bernardi, N. Bonichon, Intervals in Catalan lattices and realizers of triangulations. J. Combin. Theory Ser. A 116 (2009), no. 1, 55–75.
  * [5] O. Bernardi, Bijective counting of Kreweras walks and loopless triangulations. J. Combin. Theory Ser. A 114 (2007), no. 5, 931–956.
  * [6] O. Bernardi, N. Holden, X. Sun, Bijective path to quantum gravity.  https://arxiv.org/abs/1807.01684
  * [7] M. Bousquet-Mélou, M. Mishna, Walks with small steps in the quarter plane. Algorithmic probability and combinatorics, 1–-39, Contemp. Math., 520, Amer. Math. Soc., Providence, RI, 2010.
  * [8] B. Duplantier, J. Miller; S. Sheffield; Liouville quantum gravity as a mating of trees, https://arxiv.org/abs/1409.7055
  * [9] E. Gwynne, N. Holden, X. Sun, Mating of trees for random planar maps and Liouville quantum gravity: a survey, https://arxiv.org/abs/1910.04713
  * [10] R. Kenyon; J. Miller; S. Sheffield; D. Wilson; Bipolar orientations on planar maps and $SLE_{12}$, Ann. Probab. 47 (2019), no. 3, 1240–1269.
  * [11] J. F. Le Gall, F. Paulin, Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geom. Funct. Anal. 18 (2008), no. 3, 893–918.
  * [12] Y. Li, Yiting; X. Sun, S.S. Watson, Schnyder woods, $SLE_{16}$, and Liouville quantum gravity. https://arxiv.org/abs/1705.03573
  * [13] G. Schaeffer, Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees. Electron. J. Combin. 4 (1997), no. 1, Research Paper 20, 14 pp.
  * [14] G. Schaeffer, Planar maps. Handbook of enumerative combinatorics, 335–395, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2015. G. Schaeffer, Planar maps.
  * [15] R.P. Stanley. Enumerative combinatorics, vol. 2. Cambridge University Press 1999.