\section{Introduction}
\label{sec:intro}
At the heart of quantum technologies lies the fact that quantum mechanical systems show features, with no classical counterpart, that may be employed as resources to perform specific tasks better or faster than within the classical realm~\cite{NC10}.
In the context of quantum optics, genuine quantum traits of optical systems have led to the emergence of the concept of  \emph{nonclassicality}, which characterizes states whose effects are not achievable with classical light~\cite{MW95}. In particular, \textit{linear} models (here intended as systems that induce linear transformations of the bosonic mode operators) have attracted much attention in the past decades, due to the development of experimental platforms able to implement them. In fact, the generation of non-classical light, especially in the form of squeezed beams, has proven to be an enabling resource for a variety of  quantum technological applications \cite{L14}.

Recently, alternative experimental platforms have been developed that can also be coherently controlled and described as single-mode bosonic systems --- including trapped ions \cite{L03}, optomechanical systems \cite{AKM14}, atoms in optical lattices \cite{LSA13}, and hybrid systems \cite{R+14}. The latter naturally embody a playground to discuss and test the generation and  characterization of genuine quantum features. In particular, they offer the unique opportunity to consider \textit{nonlinear} (or anharmonic) models, given that the possibility to host non-linearities is within reach of current technologies, in particular for trapped ions \cite{H+11} and optomechanical systems \cite{S+09}. Interestingly, it has been shown that the inclusion of nonlinearities in the oscillator potential uncovers new possibilities to generate nonclassical states \cite{DIVINCENZO, ONG, PEANO, KOLKIRAN, ANDERSSON,RIPS,Vacanti2013,MFB14}. However, a general framework that encompasses these possibilities remains elusive and in particular a thorough quantitative assessment of the link between nonlinearity and nonclassicality still lacks.

The aim of this work is to investigate in details the idea that
nonlinearity is a general resource to generate nonclassicality in
single-mode bosonic systems constituted of anharmonic oscillators. In
particular, we will focus on a quantitative assessment of the
phenomenon, as we critically consider specific quantifiers of
nonclassicality and nonlinearity. In fact, identifying proper measures
of these quantities is crucial by itself and, in particular, different
figures of merit exist that  capture different features associated to
nonclassicality
\cite{H87,Lee1991,RV02,Kenfack2004,Asboth2005,Mari2011,FP12}. The
quantitative connection of the nonlinear behaviour of an oscillatory
system and the appearance of nonclassicality has recently been tested,
in the context of nano-mechanical resonators, for the Duffing oscillator
model \cite{Teklu2015}. Here we extend such connection and assess its
validity for more general scenarios, including three families of exactly
solvable non-linear oscillators and a generic sixth order potential.
\par
The remainder of this paper is structured as follows.  In Sec.~\ref{sec:nonclassnonlin}
we review the main conceptual tools and establish our notation and formalism. First, we
introduce and discuss the two quantitative measures of nonclassicality
that will be used throughout the paper, namely entanglement potential
and the volume of the negative part of the Wigner function. Then, we
review a recently introduced measure to quantify the nonlinearity of a
quantum oscillator \cite{Paris2014}, which in turn is based on an
entropic measure of non-Gaussianity~\cite{Genoni2010}.  In Section
\ref{sec:potentials} we analyse the quantitative connection between
nonclassicality and nonlinearity for three different nonlinear
potentials having an exact solution. We also highlight
some differences between the two measures of nonclassicality (see also
Ref.~\cite{Li2010}). In Sec.~\ref{sec:harmoscpert} we address
generic (symmmetric) anharmonic potential by considering
fourth- and sixth-order perturbations to the harmonic one.
In Sec.~\ref{sec:out} we draw our conclusions.

\section{Nonclassicality of a state and Nonlinearity of a potential}
\label{sec:nonclassnonlin}

\subsection{Nonclassicality of a Single-mode Bosonic State}
We consider a bosonic system with a single degree of freedom,
such as a one-dimensional oscillator or a single-mode of
a bosonic field. Since we deal with single-mode systems, we will not discuss
any notion related to entanglement or other nonclassical correlations.

In the most general terms, a quantum state is said to be nonclassical if
the methods of classical statistics fail to describe its properties and
phenomenology.  In the context of quantum optics this definition is made
precise by using quasiprobability distributions in phase space.
Here we are not only interested in \emph{criteria} for
nonclassicality, but we seek for a \emph{quantitative characterization}.
An excellent summary on this topic can
be found in the introduction of Ref. \cite{Miranowicz2015}.

\subsubsection{P-nonclassicality and Entanglement Potential}
\label{subsec:ep}
According to Titulaer and Glauber~\cite{Glauber1963,Titulaer1965,Mandel1986}, a quantum state is
nonclassical when its $P$ function fails to be interpreted as a
probability distribution in the phase space (see also Refs.~\cite{Vogel2006,Johansen2004,Spekkens2007}).
It has been recently emphasized~\cite{Kiesel2013} that the $P$ function
is the only quasiprobability distribution which can give a description
that can be completely modelled using classical electrodynamics,
therefore supporting the idea that to identify a classical state it is
necessary to use the $P$ function. In this paper we dub such
fundamental notion as {\it P-nonclassicality}.

The best known way to quantify P-nonclassicality is the nonclassical
depth~\cite{Lee1991}: It quantifies, operationally, the amount of thermal noise
that is needed in order to render the $P$ function of a given state a well-behaved probability
distribution and the corresponding state classical.  This measure
however is not fully suited for our purposes: in fact, while we will be interested in establishing a quantitative hierarchy
of pure non-Gaussian states in terms of their nonclassicality at a set nonlinearity of a given potential, it has been proven
that such states all saturate the nonclassical depth~\cite{Lutkenhaus1995},
i.e. they are equally and maximally nonclassical according to this measure.

This obstacle can be overcome by considering the following. It has long been
known that coherent states are the only pure states
that produce uncorrelated outputs when mixed by a passive linear-optics
device~\cite{Aharonov1966}. Specifically, P-nonclassicality has been
identified as a necessary condition for having entangled states at the output of
a beam splitter~\cite{Kim2002,Xiang-bin2002} and quantitative relations have
been identified between non-classicality and entanglement
\cite{WEP:03,Asboth2005,oli09,oli11,JLC:13,VS:14,B+15} or discord-like
correlations more in general \cite{B+15}. The idea of quantifying
nonclassicality of a single mode state as the
two mode entanglement at the output of a linear optic device was
introduced by Asb\'oth et al.~\cite{Asboth2005}. In particular, it was shown
that the optimal entangler is just a (50:50)
beam splitter with vacuum as an auxiliary state. By restricting to this setup,
nonclassicality of the input state becomes a necessary and
sufficient condition for output entanglement. As a consequence,
entanglement at the output of a beam splitter may be used as a
faithful quantitative measure of P-nonclassicality. This measure
is usually referred to as entanglement potential ${\cal E}(\rho)$ and it is defined as
\begin{equation}
\label{eq:EntPotDef}
{\cal E}[\rho]=E\left[ \hat{B} \left( \rho  \otimes |0 \rangle \langle 0 | \right) \hat{B}^{\dag} \right],
\end{equation}
where $\rho$ is the density matrix of the state under scrutiny,
$|0\rangle$ is the vacuum state at the ancillary port of the beam
splitter, $\hat B$ is the beam splitter operator, and $E[\rho]$ is a
suitable measure of entanglement.
Our analysis will be concerned with the ground state of a given
Hamiltonian model. By dealing with pure states, $E[\rho]$ can be chosen,
with no ambiguity, as the the entanglement entropy. This choice
corresponds to the \emph{entropic entanglement potential} defined in
Ref.~\cite{Asboth2005}, which has been evaluated by truncating the
dimension of the Hilbert space to a suitable dimensione, ensuring
the normalization of the state before and after the beam-splitter.

\subsubsection{$W$-nonclassicality}
\label{subsec:negwig}
While the $P$ function can be a singular object,
the Wigner function is always well behaved, even if it can attain negative values.
Negativities of the Wigner function associated with a given state defines the so-called {\it $W$-nonclassicality},
which is, however, only a sufficient condition for P-nonclassicality.
It follows that there are W-classical states which are P-nonclassical:
displaced squeezed states are a remarkable example. The notion of $W$-nonclassicality has gained an operational
meaning as follows: the evolution of a system which is in a $W$-nonclassical state
cannot be efficiently simulated with classical resources~\cite{Mari2012,Veitch2013}. In order to quantify $W$-nonclassicality we use the volume
of the negative part of the Wigner function~\cite{Kenfack2004}
\begin{equation}
\label{eq:def_delta}
\delta =
\left( \int \! \mathrm{d}x\,dp \, |W(x,p)| \right)  - 1,
\end{equation}
where $x$ and $p$ are phase-space variables, and $W(x,p)$ is the Wigner function of the state under scrutiny. We will make use of the following normalized version of this measure
\begin{equation}
\label{eq:def_nu}
\nu = \frac{\delta}{1+\delta},
\end{equation}
which gives $\nu\in[0,1]$.

Let us stress that the $W$ and $P$-nonclassicality single out different quantum features. In particular, the Hudson theorem~\cite{Hudson1974} guarantees that the sole pure states with a positive Wigner function are Gaussian ones, i.e. squeezed coherent states. Hence, there exist pure states that have zero $W$-nonclassicality (\textit{e.g.}, squeezed states) but non-zero $P$-nonclassicality. In this sense the entanglement potential can reveal more detailed features of quantumness, as we will see below. Note that measures of $W$-nonclassicality based on the geometric distance between quantum states have also been introduced \cite{H87,Mari2011}.

\subsection{Quantifying the Nonlinearity of a One-dimensional Potential Using Its Ground State}
\label{subsec:nonlin}
The first idea to quantify the nonlinearity (inteded as the
\emph{anharmonicity character}) of a potential would be defining a
distance between potential functions and the reference harmonic
potential. However, this is in general not feasible, since
potentials do not need to be integrable functions. A different approach
follows from the fact that ground states and equilibrium states
of anharmonic potentials are not Gaussian,
as opposed to those of a quantum harmonic oscillator. We can
thus choose to quantify nonlinearity by the non-Gaussianity of the ground
state of a given Hamiltonian model~\cite{Paris2014}. The measure of non-Gaussianity
used for this goal is the entropic measure introduced in
\cite{Genoni2008,Genoni2010}. Here we shall briefly review these
measures.

\subsubsection{Non-Gaussianity of a Quantum State}

The covariance matrix of a single-mode bosonic system prepared in a state $\rho$ is defined as~\cite{Ferraro2005}
\begin{equation}
\label{eq:def_covmat}
\sigma_{jk}[\rho] = \frac{1}{2} \langle \{ \hat R_j,\hat R_k \} \rangle_\rho - \langle \hat R_j \rangle_\rho \langle \hat R_k \rangle_\rho,
\end{equation}
where $\hat{\vec{R}}=(\hat{x},\hat{p})^T$  is the vector of single-mode quadrature operators $\hat x$ and $\hat p$, and the subscript implies that expectation values are calculated over state $\rho$. We also define the displacement vector $\vec{\bar{X}}[\rho]$ with components $X_k[\rho] = \langle \hat R_k \rangle_\rho$.
A Gaussian state has a Gaussian Wigner function.

To quantify non-Gaussianity of a generic state $\rho$, a reference Gaussian state $\tau$ should be defined. This is identified as the Gaussian state having the same covariance matrix and displacement vector  as $\rho$. That is
\begin{equation}
\label{eq:RefGaussianState}
\vec{\bar X}[\tau]= \vec{\bar X}[\rho], \qquad\sigma[\tau]=\sigma[\rho].
\end{equation}

Non-Gaussianity can now be defined as the distance
between $\rho$ and $\tau$ calculated using, for instance,
the quantum relative entropy
\begin{equation}
S\left( \rho \middle\| \tau \right) = \Tr \left[ \rho ( \ln \rho - \ln \tau ) \right].
\end{equation}
We have that $S\left( \rho \middle\| \tau \right)=0$ iff
$\rho = \tau$. Although $S\left( \rho \middle\| \tau \right)$ is not symmetric in its arguments, and thus does not embody a proper metric,
it has been used widely to quantify the distinguishability of two states.
This leads to the definition of the entropic measure of non-Gaussianity
\begin{equation}
\delta_{\text{E}} (\rho) =  S\left( \rho \middle\| \tau \right) =  \Tr \left[ \rho \ln \rho \right] - \Tr \left[ \rho \ln \tau \right] = S(\tau) - S(\rho),
\end{equation}
where $S$ denotes the von Neumann entropy and, owing the way $\tau$ is defined, we have that $S(\tau)=-\Tr \left[ \tau \ln \tau \right] = -\Tr \left[ \rho \ln \tau \right]$.
This measure satisfies a series of quite useful properties~\cite{Genoni2010}: it is additive under the tensor product
operation, and
invariant under symplectic transformations, which are both very useful for the sake of our analysis.

The von Neumann entropy of a single mode Gaussian state takes the very simple form
\begin{equation}
S(\rho_{\text{G}}) = h\left( \sqrt{\det \vec{\sigma }} \right),
\end{equation}
where $h(x)=(x+\frac{1}{2}) \ln (x+\frac{1}{2}) - (x-\frac{1}{2}) \ln (x-\frac{1}{2})$. Thanks to this form, the entropic non-Gaussianity becomes
\begin{equation}
\delta_{\text{E}} (\rho) =  h\left( \sqrt{\det \vec{\sigma }} \right) - S(\rho),
\end{equation}
which is further simplified for pure states, as $S(\rho)=0$.

\subsubsection{Nonlinearity of a Potential}

We consider a generic potential $V(x)$ and denote with $| \phi \rangle$ the ground state of the corresponding Hamiltonian. The first idea to quantify nonlinearity would be again using the
geometrical distance between the ground state of the potential and a
reference harmonic state, in particular for this purpose the Bures
metric has also been employed \cite{Paris2014}. This way of reasoning
has a downside because we have to choose a value for the frequency
$\omega$ of the reference harmonic oscillator. The most natural choice
is expanding the potential near its minimum and finding $\omega$ as a
function of the nonlinear parameters of the potential. However,
determining this frequency is not always straightforward and for some
potentials exhbiting more than one minimum it may be even be misleading.

Instead of using a metric we choose to quantify nonlinearity using the entropic non-Gaussianity $\delta_{\text{E}}$, so that the measure of nonlinearity is defined as
\begin{equation}
\label{eq:DefGaussianNonLin}
\eta_{\text{NG}} [V]= \delta_{\text{E}} \left( |\phi\rangle \langle \phi | \right) = h \left(\sqrt{\det \vec{\sigma}}\right),
\end{equation}
this equality holds because the ground state is pure and $\vec{\sigma}$ is the covariance matrix of the ground state (we drop the dependence from the state when obvious).

This definition is more appealing than a geometric one because it does not require the determination of a reference potential for $V(x)$, but just the reference Gaussian state for the ground state of $V(x)$. This makes $\eta_{\text{NG}}$ independent of the specific features of the potential, since we do not need to know the behavior of $V(x)$ near its minimum to compute the reference frequency.

Moreover, $\eta_{\text{NG}}$ inherits the property of the non-Gaussianity measure and is invariant under symplectic transformations~\cite{Ferraro2005}. This means that $\delta_{\text{NG}}$ assigns the same nonlinearity to oscillators which are displaced, rotated in phase space or squeezed, which is a reasonable property for a measure of nonlinearity.

\section{Exactly Solvable Nonlinear Oscillators}
\label{sec:potentials}
We now analyze quantitatively the relation between the figures of merit introduced in the previous Section, considering three exactly solvable anharmonic oscillators.
\subsection{Modified Harmonic Oscillator}
The Modified Harmonic Oscillator (MHO) potential is defined as~\cite{Bund2000} (throughout this manuscript we choose units such that $\hbar = m= 1$)
\begin{equation}
\label{eq:MHOpot}
V_{\text{MHO}}(x) = \frac{\alpha ^2 x^2}{2}- \alpha \beta  x \tanh (\beta  x).
\end{equation}
Here $\alpha$ is a parameter corresponding to the frequency of the unmodified harmonic oscillator, while $\beta$ determines the deformation of the harmonic potential. The effects of this parameter on the shape of the potential is appreciated from Fig.~\ref{fig:MHOpot}, where $V_{\text{MHO}}(x)$ is plotted at a set value of $\alpha$ for different choices of $\beta$, showing that an increasing deformation parameter transforms a harmonic potential into a double-well one whose well-depth and separation both increase with $\beta$.
\begin{figure}[b]
	\centering
	\includegraphics[width=.5\textwidth]{MHOpot.pdf}
	\caption{(Color online) The MHO potential $\alpha=1$ and $\beta = 3$ (solid blue), $2$ (dotted yellow), $1$ (dashed green) and the harmonic potential with unitary frequency and mass (dot-dashed orange). The inset represent the same graph at a larger scale, where we see the resemblance to the harmonic potential.}
	\label{fig:MHOpot}
\end{figure}

The normalized wave-function of the ground-state of this potential can be found to read~\cite{Bund2000}
\begin{equation}
\label{eq:MHOground}
\phi_{\text{MHO}}(x) = \frac{\sqrt{2} e^{-\frac{1}{2} \alpha  x^2} \cosh (\beta  x)}{\sqrt[4]{\frac{\pi}{\alpha}} \sqrt{1+\exp[{\beta^2}/{\alpha }]}}.
\end{equation}
The associated energy is $E_0 = (\alpha - \beta^2)/{2}$. The covariance matrix of such least-energy state can be computed straightforwardly to be
\begin{equation}
\label{eq:MHOcorrmat}
 \vec{\sigma}^{\text{MHO}} =
\begin{pmatrix}
 \frac{1}{2\alpha}+\frac{\beta^2}{\alpha^2} \frac{\exp[{\beta^2}/\alpha]}{1+\exp[{\beta^2}/\alpha]} & 0 \\
 0 & \frac{\alpha }{2}-\frac{\beta ^2}{1+\exp[{\beta ^2}/{\alpha }]}
\end{pmatrix}.
\end{equation}
Its determinant is
\begin{equation}
\det{\vec{\sigma}^{\text{MHO}}} =\frac{1}{4}  - \frac{\tau^2}{2} \frac{\left(  2 \tau^2  e^{\tau^2}-  e^{2\tau^2}+1\right)}{(e^{\tau^2}+1)^2}
\end{equation}
with $\tau=\sqrt{{\beta^2}/{\alpha}}$. Such dependence on $\tau$, rather than $\alpha$ and $\beta$ independently, is common to $\eta_{\text{NG}} = h(\det{\sigma})$ and the measure of nonlinearity based on the Bures distance (for the latter, we should choose the unmodified harmonic oscillator with frequency $\alpha$ as a reference). Both measures of nonlinearity increase monotonically with $\tau$.

The Wigner function associated with $\phi_{\rm MHO}$ can be written in terms of the suitably rescaled phase-space variables $q = \beta x$ and $p = \frac{\beta}{\alpha} y$ as~\cite{Bund2000}
\begin{equation}
\label{eq:MHOwig}
W_{\text{MHO}}(q,p) = e^{-\frac{q^2+p^2}{\tau^2}} \frac{\cosh (2 q)+
e^{\tau^2}\cos (2p)}{\pi\tau^2(1+e^{\tau^2})},
\end{equation}
which shows again the key role played by $\tau$ and, in turn, that the non-classicality measure based on the volume of the negative part of $W_{\rm MHO}(q,p)$ is  determined by such parameter.

In order to understand how $W$-nonclassicality and nonlinearity are
related to each other, we have studied both quantities against $\tau$. In Fig.~\ref{fig:MHOdelta} we report the resulting parametric plot,
showing that $\nu$ monotonically increases with $\eta_{\text{NG}}$, thus
supporting the idea that a growing degree of anharmonicity of the potential results in increased nonclassicality of the corresponding ground state.
\begin{figure}[!t]
\centering
\includegraphics[width=.5\textwidth]{MHOdng.pdf}
\caption{(Color online) Parametric plot of the $W$-nonclassicality measure
$\nu(\tau)$ versus the degree of nonlinearity for the MHO potential and for $\tau\in[0.1,6]$.} \label{fig:MHOdelta}
\end{figure}

However, the picture changes significantly as soon as we consider
P-nonclassicality quantified by the entanglement potential which, as
said, can single out more detailed features of quantumness. Indeed, at
variance with what has been found above, such figure of merit turns out
to depend on $\alpha$  and $\beta$ independently. The reason for such a
difference in behavior should be ascribed to the fact that entanglement
at the output of a beam splitter can be originated either by a
non-Gaussian input state or by Gaussian single-mode squeezing.
In other words, nonlinearity is needed to generate
W-nonclassicality, while P-nonclassicality may be obtained using just
squeezing.

In order to illustrate this clearly, in Fig.~\ref{fig:MHOsqueezingvsEP} we show the entanglement
potential and squeezing for the MHO both as a function of $\beta$ for fixed
values of $\tau$, and as a function of $\tau$ at set values of
$\alpha$.
The squeezing  in Fig.~\ref{fig:MHOsqueezingvsEP} is shown in terms of
the ratios
\begin{equation}
r_x=\frac{\sigma^{\rm MHO}_{11}}{\sigma^0_{11}}=2\sigma^{\rm MHO}_{11},\quad r_p=\frac{\sigma^{\rm MHO}_{22}}{\sigma^0_{22}}=2\sigma^{\rm MHO}_{22}
\end{equation}
 with $\sigma^{0}_{11}=\sigma^{0}_{22}=1/2$ the variances of position and momentum calculated over the vacuum state of the harmonic potential.
Squeezing is found in the ground state of the MHO for either $r_x<1$ or $r_p<1$.
As it is apparent from Fig.~\ref{fig:MHOsqueezingvsEP}, the behavior of ${\cal E}$ is rather
different from $\nu$, and its features may be understood looking at
squeezing. In particular, we see that ${\cal E}$ grows when
the ground state exhibits squeezing.
\begin{figure}[t!]
\centering
{\bf (a)}\hskip0.5\columnwidth{\bf (b)}\\
\includegraphics[width=.49\columnwidth]{MHOsqueezingVSepT1.pdf}
\includegraphics[width=.49\columnwidth]{MHOsqueezingVSepT3.pdf}\\
{\bf (c)}\hskip0.5\columnwidth{\bf (d)}\\
\includegraphics[width=.49\columnwidth]{MHOsqueezingVSepA3.pdf}
\includegraphics[width=.49\columnwidth]{MHOsqueezingVSepA5.pdf}
\caption{(Color online) Entanglement potential and squeezing for the
MHO. In panels {\bf (a)} and {\bf (b)} [{\bf (c)} and {\bf (d)}] we plot $r_x$ (dashed blue curve),
$r_p$ (dotted orange curve), the entanglement potential (P-nonclassicality)
${\cal E}$ (black dots), and $W$-nonclassicality $\nu$ (red dots) against $\beta$ [$\tau$] for $\tau=1$ and $\tau=3$ [$\alpha=3$ and $\alpha=5$]. Squeezing is observed for either $r_x<1$ or $r_p<1$ (i.e. variances of the perturbed ground state below the values of the vacuum state of a harmonic oscillator).}
\label{fig:MHOsqueezingvsEP}
\end{figure}

\subsection{Morse potential}
The Morse potential has been introduced as an
approximation to the potential energy of diatomic molecules as it
provides a better description of the vibrational structure than the
(quantum) harmonic oscillator~\cite{Morse1929}. The form of the potential is
\begin{equation}
\label{eq:MorsePot}
V_{\text{M}} = D \left( e^{-2 \alpha x} - 2 e^{-\alpha x} \right),
\end{equation}
where $x$ is the distance from the minimum of the
potential, the parameter $D > 0$ determines the depth of the well, while
$\alpha$ controls its width. Expanding the two exponentials for $\alpha
\to 0$ at fixed $D$ we get the harmonic limit, which is an oscillator
with frequency $\omega_{\text{M}} = \sqrt{2D} \alpha$. The
potential is plotted in Fig.~\ref{fig:MorsePot} for different values of the
parameters.

\begin{figure}[!t]
	\centering
	\includegraphics[width=.5\textwidth]{MorsePot.pdf}
	\caption{(Color online) The Morse potential $V_{\rm M}(x)$ for $D = 1$ and $\alpha = 1$ (solid blue), $2$ (dashed orange), $3$ (dotted green). The inset shows the potential for $\alpha=1$ and $D = 1$ (solid blue), $2$ (dashed orange), $3$ (dotted green).}
	\label{fig:MorsePot}
\end{figure}

The  Schr\"odinger equation associated with this potential
can be solved analytically, the energy eigenvectors being labelled by two
quantum numbers, which we label here $N$ and $\nu$. The first is related to the parameters
of the potential as $N = -{1}/{2} +
{\sqrt{2D}}/{\alpha}$. The second, which can take values $\nu=0,1,2,..,\lfloor{N}\rfloor$, counts the number of anharmonic excitations of the system. As we want at least one bound state, we require $N>0$. We thus have the constraint $\alpha < 2 \sqrt{2 D}$. The limiting case where we
have just one bound state (the ground state) is achieved for
$\alpha \to 2\sqrt{2D}$. The wave-function of the ground state is
\begin{equation}
\label{eq:MorseGS}
\phi_{\text{M}} (x) = (2 N + 1)^N \sqrt{\frac{\alpha}{(N-1)!}} e^{-\alpha x N - (N + \frac{1}{2})e^{-\alpha x}}
\end{equation}
with associated energy $E=-\alpha N^2/2$.
The behavior of the nonlinearity of the Morse potential can be understood by looking at the form of
the potential in Fig.~\ref{fig:MorsePot}, as opposed to the harmonic
one~\cite{Paris2014}: For any fixed value of $D$ [$\alpha$] we expect an increase [decrease] of nonlinearity
for increasing $\alpha$ [$D$].

The covariance matrix associated with the ground state in Eq.~\eqref{eq:MorseGS} is
\begin{equation}
\label{eq:MorseCorMat} \vec{\sigma}^{\text{M}} =
\begin{pmatrix}
\frac{\psi ^{(1)}(2 N)}{\alpha ^2} & 0 \\
0 &  \frac{\alpha ^2 N}{2}
\end{pmatrix},
\end{equation}
where $\psi^{(n)}(z)$ is the polygamma function $\psi^{(n)}(z) =
\frac{\mathrm{d}^{n+1}}{\mathrm{d}z^{n+1}} \log \Gamma (z)$, $\Gamma(Z)$
being the Euler Gamma function.
The determinant of this correlation matrix, and thus the Bures distance
from the reference harmonic oscillator, depend just on $N$ or, equivalently, on the combination
${\sqrt{2D}}/{\alpha}$. In this case both measures of nonlinearity are monotonically
decreasing functions of $N$.

The Wigner function for the ground state of the Morse potential reads as follows~\cite{Frank2000}
\begin{equation}
W_{\text{M}}(x,p)= \frac{2(2N + 1 )^{2N}}{\pi \Gamma(2N)} e^{-2N\alpha x} K_{-2\I p / \alpha}\left( \left(2N + 1\right) e^{-\alpha x} \right),
\end{equation}
where $K_{\gamma}(z)$ is the Macdonald function of (non-integer) order $\gamma$. In order to calculate the measure of nonclassicality $\nu$, we rescale the phase-space variables to $q=\alpha x$ and $p=\frac{y}{\alpha}$, and evaluate
\begin{equation}
\label{eq:MorseWigInt}
\begin{split}
&\iint \! \mathrm{d}x\, \mathrm{d}y \, \left\lvert W_{\text{M}}(x,y) \right\lvert =\\
&\iint \! \mathrm{d}q\, \mathrm{d}p \left\lvert \frac{2e^{-2N q}}{\pi \Gamma(2N)} (2N + 1 )^{2N}  K_{-2\I p}\left( \left(2N + 1\right) e^{-q} \right)  \right\lvert,
\end{split}
\end{equation}
which shows that the only relevant parameter is $N$. The numerical integration of Eq.~\eqref{eq:MorseWigInt} is
challenging and was carried out with the aid of the CUBA
libraries~\cite{Hahn2005}.
The degree of $W$-nonclassicality $\nu$ is found to monotonically decreases
with $N$, and the
parametric plot of nonclassicality versus nonlinearity in
Fig.~\ref{fig:Morsenu} reveals a monotonic behavior, strengthening the link between such features and reinforcing the idea that nonlinearity might play the role of a catalyst for nonclassicality.

\begin{figure}[!h]
\centering
\includegraphics[width=.5\textwidth]{MorseDeltaVSetaNG.pdf}
\caption{(Color online) Parametric plot of the $W$-nonclassicality $\nu$
versus the degree of nonlinearity $\eta$ for a Morse potential with $D=1$ and
$\alpha\in[0.15,2.7]$, i.e. $N\in[0.0238,8.928]$.}
\label{fig:Morsenu}
\end{figure}

The situation regarding the entanglement potential is completely analogous to what we found for the MHO, as it depends on both parameters.
In Fig.~\ref{fig:MorsesqueezingvsEP} we report the same kind of graphs, both with $N$ fixed and $\alpha$ fixed,
which show that the behavior of ${\cal E}$ is explained by the squeezing of the state.

\begin{figure}[!b]
\centering
{\bf (a)}\hskip0.5\columnwidth{\bf (b)}\\
\includegraphics[width=.49\columnwidth]{MorseSqueezingVSepN1.pdf}
\includegraphics[width=.49\columnwidth]{MorseSqueezingVSepN5.pdf}
{\bf (c)}\hskip0.5\columnwidth{\bf (d)}\\
\includegraphics[width=.49\columnwidth]{MorseSqueezingVSepA1.pdf}
\includegraphics[width=.49\columnwidth]{MorseSqueezingVSepA3.pdf}
\caption{(Color online) Entanglement potential and squeezing for
the Morse oscillator. In panels {\bf (a)} and {\bf (b)} [{\bf (c)} and {\bf (d)}] we plot $r_x$ (dashed blue curve),
$r_p$ (dotted orange curve), the entanglement potential (P-nonclassicality)
${\cal E}$ (black dots), and $W$-nonclassicality $\nu$ (red dots) against $\alpha$ [$1/N$] for $N=1$ and $N=5$ [$\alpha=1$ and $\alpha=3$]. Squeezing is observed for either $r_x<1$ or $r_p<1$ (i.e. variances of the perturbed ground state below the values of the vacuum state of a harmonic oscillator).}
\label{fig:MorsesqueezingvsEP}
\end{figure}

\subsection{Pöschl-Teller potential}
The modified P\"oschl-Teller potential (PT) is defined as
\begin{equation}
\label{eq:PTpot}
V_{\text{PT}}(x)=-{A_{\rm PT}}{\cosh ^{-2}(\alpha  x)},
\end{equation}
where $A_{\rm PT}>0$ is the depth of the potential and $\alpha$ is
connected to its range. The harmonic limit is obtained at fixed $A_{\rm PT}$ for
$\alpha \to 0$ and the frequency of the reference harmonic oscillator is $\omega_{\rm PT} = \sqrt{2A_{\rm PT}}\alpha$.
As for the Morse potential, we have a quantum number $s$ that labels the energy eigenstates and counts the anharmonic
excitations. It is related to the parameters of the potential through the relation $A_{\rm PT}=\frac{1}{2} \alpha^2 s ( s + 1)$. Therefore, the
request for the existence of at least one bound state translates into $s = \frac{1}{2}\left( -1 + \sqrt{1 + 8 A_{\rm PT} / \alpha^2} \right)
>0$. Fig.~\ref{fig:PTpot} shows the dependence of the PT potential on the position coordinate.
\begin{figure}[t!]
\centering
\includegraphics[width=.5\textwidth]{PTpot.pdf}
\caption{(Color online) The Posh-Teller potential with $A_{\rm PT}=1$ and $\alpha=1/2$ (solid blue), $1$ (dotted orange) and $3$ (dashed green).}
	\label{fig:PTpot}
\end{figure}

The ground state of  the system reads
\begin{equation}
\label{eq:PTground}
\phi_{\text{PT}}(x) = \frac{1}{\pi^{\frac{1}{4}} } \sqrt{\frac{\alpha  \Gamma \left(s+\frac{1}{2}\right)}{\Gamma (s)}} {\cosh^{-s}(\alpha  x)},
\end{equation}
with associated energy $E=-\alpha^2 s^2/2$.

Differently from the previous cases, the covariance matrix of the ground state is rather involved and will not
be reported here. In line with the case of the previous two anharmonic potentials studied here, its determinant depends only on $s$ (or, equivalently, on $A_{\rm PT}/{\alpha^2}$). Again, both $\eta_{\text{NG}}$ and the Bures nonlinearity are
monotonically decreasing function of $s$ only.

The Wigner function of state $\phi_{\rm PT}(x)$ in Eq.~\eqref{eq:PTground} is known
analytically for the case of $A_{\rm PT}=\alpha^2$ \cite{Bund2000}. In
this case, the measure $\nu$ is an $s$-dependent constant, as it can be seen by rescaling the relevant variables as $p'=\frac{p}{\alpha}$, $x'=\alpha x$, $y'=\alpha y$ and evaluating the integral
\begin{equation}
W_{\text{PT}}(x,p) = \int\! \mathrm{d}y  \, \phi^*_{\text{PT}}\left(x-\frac{y}{2}\right) \phi_{\text{PT}}\left(x+\frac{y}{2}\right) e^{-\I y p},
\end{equation}
which embodies the definition of Wigner function.

As for the entanglement potential, this turns out to depend on both $\alpha$ and $s$. Plots similar to those valid for the MHO and Morse potential are presented in Fig.~\ref{fig:PTsqueezingvsEP} (without the $W$-nonclassicality $\nu$).
\begin{figure}[t]
\centering
{\bf (a)}\hskip0.5\columnwidth{\bf (b)}\\
\includegraphics[width=.49\columnwidth]{PTsqueezingVSepS1.pdf}
\includegraphics[width=.49\columnwidth]{PTsqueezingVSepS5.pdf}
{\bf (c)}\hskip0.5\columnwidth{\bf (d)}\\
\includegraphics[width=.49\columnwidth]{PTsqueezingVSepA1.pdf}
\includegraphics[width=.49\columnwidth]{PTsqueezingVSepA3.pdf}
\caption{(Color online) Entanglement potential and squeezing for
the PT oscillator. Panels {\bf (a)} and {\bf (b)} [{\bf (c)} and {\bf (d)}] show $r_x$ (dashed blue curve),
$r_p$ (dotted orange curves), and the entanglement potential ${\cal E}$ (black dots)against $\alpha$ [$1/s$] for $s=1$ and
$s=5$ [$\alpha=1$ and $\alpha=3$].} \label{fig:PTsqueezingvsEP}
\end{figure}

\section{Oscillators with polynomial perturbations}
\label{sec:harmoscpert}
So far we have studied exactly solvable potentials with two parameters
and revealed a common behavior: the nonlinearity and the $W$-nonclassicality
$\nu$ have the same behavior and depend just on a single effective
parameter.  On the other hand, the entanglement potential carries a
dependence on both the parameters and its different behavior may be
understood in terms of the squeezing of the state.

Now we want to address the case of a generic two-parameter perturbation,
so we study a physical system composed of a one-dimensional harmonic oscillator
with perturbations proportional to $x^4$ and $x^6$ respectively.
The Hamiltonian of this system thus reads
\begin{equation}
\label{eq:H}
H = \frac{1}{2} (p^2 + \omega^2 x^2) + \epsilon_4 x^4 +
\epsilon_6 x^6\,.
\end{equation}
As the model is not exactly solvable, the properties of the system will be studied using perturbation theory.
We notice that Eq.~\eqref{eq:H} may also serve as an approximation
for any symmetric (even) potential. We do not consider
odd powers of $x$, as they give rise to known problems in the
convergence of the perturbative series. A remark is in order: terms proportional to $x$ and to $x^2$ could in
principle be treated in a perturbative way as well. However, they do not give rise to
truly anharmonic behavior, and will not be considered in this context.

\label{subsec:PHOApproxSol}
\label{sec:pertstates}
In order to get insight into the ground states for these Hamiltonians we use
first-order time-independent perturbation theory~\cite{Sakurai2011}.
The state takes the form
\begin{equation}
\label{eq:psi}
|\psi\rangle=\sum^3_{n=0}\gamma_{2n}|2n\rangle,
\end{equation}
where $|k\rangle$ denotes a Fock number state of the harmonic oscillator
and the coefficients $\gamma_k$ are in given Appendix~\ref{app:states}.

First-order perturbation theory returns the ground as a finite
superposition of Fock states, which makes the
Wigner function and the nonlinearity easy to compute.
In order to assess the validity of the first order approximation,
we compare such ground state to the state obtained by numerically diagonalizing
the Hamiltonian of the system within a truncated Fock space
of suitable size. Convergence of the results  of such numerical calculations appear to be ensured by
using $61$ harmonic levels. The corresponding ground state $|\phi\rangle$ is then compared to $|\psi\rangle$ using the
state fidelity
$|\langle \phi | \psi \rangle |^2$. In Fig.~\ref{fig:OverlapContourPert60} we present a contour plot of
the overlap as a function of both $\epsilon_4$ and $\epsilon_6$.
\begin{figure}[t!]\centering
\includegraphics[width=.5\textwidth]{ContourOverlap2.pdf}
\caption{(Color online) Contour plot of the overlap between the
perturbative ground states of Eq.~(\ref{eq:psi}) and the numerically calculated one (for $\omega = 1$).}
\label{fig:OverlapContourPert60}
\end{figure}
For values of $\epsilon_4$ up to 0.1 and $\epsilon_6$ up to 0.03 the fidelity is at least $\approx 0.976$.

\subsection{Nonclassicality and Nonlinearity}
\label{sec:PHOnonlin}
From the perturbed ground state in Eq.~\eqref{eq:psi} we compute the nonlinearity of the perturbing potential. The covariance matrix associated with $|\psi\rangle$ can be thus written as
\begin{equation}
\sigma^{\rm pol}=
\begin{pmatrix}
\frac{(1 + 2 \langle \hat{a}^2 \rangle + 2 \langle \hat{a}^\dag a \rangle - 4 {\langle \hat{a} \rangle}^2 )}{2\omega} & 0 \\
0 & \frac{\omega}{2}(1 + 2 \langle \hat{a}^\dag \hat{a} \rangle - 2 \langle \hat{a}^2 \rangle)
\end{pmatrix},
\end{equation}
with $\hat a$ and $\hat a^\dag$ the annihilation and creation operators of the oscillator and
\begin{equation}
\label{eq:meanvalues}
\begin{split}
\langle  \hat{a}^\dag \rangle &=  \langle  \hat{a} \rangle = 0, \\
\langle  \hat{a}^\dag a \rangle &= 2 |\gamma_2|^2 + 4 |\gamma_4|^2 + 6  |\gamma_4|^2, \\
\langle  \hat{a}^2  \rangle &= \sqrt{2} \gamma _2 \gamma _0{}^*+2 \sqrt{3} \gamma _4 \gamma _2{}^*+\sqrt{30} \gamma _6 \gamma _4{}^*, \\
\langle  \hat{a}^{\dag2}  \rangle &= \langle  \hat{a}^2  \rangle^* = \sqrt{2} \gamma _0 \gamma _2{}^*+2 \sqrt{3} \gamma _2 \gamma _4{}^*+\sqrt{30} \gamma _4 \gamma _6{}^*.
\end{split}
\end{equation}
An explicit calculation shows that the determination of $\sigma^{\rm pol}$, and in turn
the nonlinearity $h(\sqrt{\det \vec{\sigma}})$, depends on both the perturbative parameters and on the frequency $\omega$. No single-parameter rescaling can be identified in this case, thus entailing the double-dependence highlighted above, which is passed to the $W$-nonclassicality $\nu$
[cf. Appendix~\ref{app:states}].

As our aim is to highlight the role played by the perturbative parameters, in the remainder of our analysis we set $\omega=1$ and
generate random pairs of values $(\epsilon_4,\epsilon_6)$ (within the appropriate range of validity of the first-order perturbative approach discussed above) that are then used to compute both the nonclassicality and nonlinearity indicators.

The results shown in Figs.~\ref{fig:PHOdng46} and~\ref{fig:PHOepng46} showcase a non-monotonic relation between nonlinearity and nonclassicality: the points corresponding to the randomly taken pairs of values for the parameters are distributed within a (narrow) region comprised within four curves, each associated with an extremal value of $\epsilon_{4,6}$.
\begin{figure}[t!]
	\centering
	\includegraphics[width=.5\textwidth]{PHOnung46.pdf}
	\caption{(Color online) Random scatter plot of the $W$-nonclassicality $\nu$ versus the nonlinearity $\eta_{\text{NG}}$ for the perturbed harmonic oscillator when both parameters $\epsilon_4$ and $\epsilon_6$ are are varied in the range given in Fig.~\ref{fig:OverlapContourPert60}; 1000 random points were generated. The dark blue curve below the points represents $\epsilon_6 = 0$, while the one above the points is the curve for $\epsilon_6 = 0.03$. The light red curve below the points is the one for $\epsilon_4 = 0.1$, while the one above the points is for $\epsilon_4 =0$. }
	\label{fig:PHOdng46}
\end{figure}
\begin{figure}[t!]
	\centering
	\includegraphics[width=.5\textwidth]{PHOepng46.pdf}
	\caption{(Color online) Random scatter plot of the entanglement potential (P-nonclassicality) ${\cal E}$ versus the nonlinearity $\eta_{\text{NG}}$ for the perturbed harmonic oscillator when both parameters $\epsilon_4$ and $\epsilon_6$ are varied in the range given in Fig.~\ref{fig:OverlapContourPert60}; 10000 random points were generated. The dark blue curve above the points represents $\epsilon_6 = 0$, while the one below the points is the curve for $\epsilon_6 = 0.03$. The light red curve above the points is the one for $\epsilon_4 = 0.1$, while the one below the points is for $\epsilon_4 =0$.}
	\label{fig:PHOepng46}
\end{figure}
Nonclassicality and nonlinearity are thus strongly dependent on the
details of the system under consideration and are, strictly speaking,
non equivalent notions.
On the other hand, the regions in Fig.~\ref{fig:PHOdng46}
and~\ref{fig:PHOepng46} are concentraded enough to suggest
that the intuitive link between such two features is, in
fact, correct. Notice also that upon fixing the value of
one of the parameters (either $\epsilon_4$ or
$\epsilon_6$) the behaviour of both nonclassicality measures
becomes monotonic with nonlinearity.

Digging into the details of the phenomenological behavior identified by
our analysis, it appears that $W$-nonclassicality
(Fig.~\ref{fig:PHOdng46}) is favoured by the $x^6$-like nonlinearity. On
the other hand,
P-nonclassicality, appears to benefit from a $\hat x^4$-type of nonlinear effects:
in Fig.~\ref{fig:PHOepng46} the roles of the dark blue and light red
curves are inverted with respect to Fig.~\ref{fig:PHOdng46}, showing
that, after choosing the parameters $\epsilon_4$ and $\epsilon_6$ in
such a way that the entropic nonlinearity is fixed, the ground state
obtained with the maximum value of $\epsilon_4$ generates more
entanglement than any other one.

\section{Conclusions}
\label{sec:out}
We have addressed in details the role played by the nonlinearity of
anharmonic potentials in the generation of nonclassicality in their
ground states. In particular, we have shown that nonlinearity plays
a crucial role in the generation of W-nonclassicality, while
P-nonclassicality may be also obtained by potential inducing just
squeezing.

Our results support the expectation, put forward in
Ref.~\cite{Teklu2015}, that the nonlinearity of a potential is
quantitatively related to the nonclassicality of its ground state and
thus the former feature may be regarded as a resource to generate the
latter one. The strict validity of such expectation, which appears to be
conceptually quite intuitive, is however strongly linked to the specific
details of the Hamiltonian model being addressed. Anharmonic potentials
that can be reduced to a single-parameter dependence give rise, in fact,
to a monotonic relation between nonlinearity and W-nonclassicality.
Such a correspondence breaks down for effectively
multi-parameter potentials: set values of nonlinearity bound the
possible degrees of nonclassicality of the ground state of a given
anharmonic potential, albeit without {\it determining} it unambiguously.

Our investigation opens up a series of questions, all linked to the
effective role that non-harmonic oscillators might have in the quantum
technology arena: it would be interesting, for instance, to investigate
whether the enhanced non-classicality achieved, in general, for a
non-null degree of nonlinearity is accompanied by an equally enhanced
degree of coherence in the ground state of the oscillator. Equally
interesting is the question on the actual use that can be made of the
sought nonlinearity in protocols of practical quantum estimation.

\section*{Acknowledgements}
This work was supported by the UK
EPSRC (EP/M003019/1), the John Templeton Foundation (grant ID
43467), the EU through the Collaborative
Projects QuProCS (Grant
Agreement 641277) and TherMiQ (Grant Agreement 618074), and by UniMI through the H2020 Transition
Grant 15-6-3008000-625.

\begin{widetext}


\section{Introduction}

Grover's algorithm \cite{Grover1996} famously searches a ``database'' of size $N$ for a ``marked'' item by querying an oracle $O(\sqrt{N})$ times. This unstructured search assumes that there is no structure to the database, so one can move from querying any item to querying any other, and information about the location of the marked vertex can only come from querying the oracle. As such, it is natural to formulate Grover's algorithm as a quantum walk \cite{Kempe2003} on the complete graph of $N$ vertices \cite{FG1998a,CG2004,Wong2015b}, since every vertex is connected to every other, and the goal is to find a marked vertex by querying an oracle.

Physically, however, structure may exist that prevents one from arbitrarily traversing the database. Such spatial search problems can also be modeled as searches on graphs \cite{AA2005,CG2004,AKR2005}. Although spatial search algorithms using quantum walks have been around for roughly a decade, there is still no complete theory as to what structures support fast quantum search \cite{MeyerWong2015}.

One graph that has recently provided several new insights into the role of structure in spatial search is the ``simplex of complete graphs,'' an example of which is shown in Fig.~\ref{fig:simplex_weighted}. This graph is an arrangement of $M+1$ complete graphs of $M$ vertices such that each vertex in a complete graph is connected to a different cluster. Formally, it is a first-order truncated $M$-simplex lattice \cite{Dhar1977}, and it contains $N = M(M+1)$ vertices and $M^2(M+1)/2$ edges.

This graph has enough structure to yield interesting results, but enough symmetry to lend itself to analysis. It was first introduced for quantum search in \cite{MeyerWong2015} as a structure with high connectivity, but on which search is unexpectedly slow. It has also been studied with various spatial distributions of multiple marked vertices \cite{Wong2015a}. Finally, search for a completely marked cluster causes the standard continuous-time quantum walk search algorithm to beat the typical discrete-time one \cite{WongAmbainis2015}. In each of these, the graph was unweighted (\textit{i.e.}, each edge had weight $1$).

\begin{figure}
\begin{center}
	\includegraphics{simplex_weighted}
	\caption{\label{fig:simplex_weighted} A 5-simplex with each vertex replaced by the complete graph of 5 vertices. Solid edges have weight $1$, and dotted edges have weight $w$. A vertex is marked, indicated by a double circle. Identically evolving vertices are identically colored and labeled.}
\end{center}
\end{figure}

In this paper, we also focus on search on the simplex of complete graphs, except now we consider a weighted version where the edges within clusters still have weight $1$, but edges between clusters have weight $w \in \mathbb{R}_{+}$. This is denoted by the solid and dotted edges in Fig.~\ref{fig:simplex_weighted}, respectively. Although quantum walks on weighted graphs have been investigated for universal mixing \cite{CFHRTW2007} and utilized for quantum state transfer \cite{CDEL2004} and quantum transport \cite{ZFKWLB2013}, they have not been explored for search (apart from the context of time-reversal symmetry breaking \cite{Wong2015d}, which yielded no speedup).

With this choice of weights, the graph remains vertex-transitive, so regardless of which vertex is marked, the system will evolve the same. As we explain later, weights defined this way on the simplex of complete graphs preserves some key properties of quantum search, and importantly, we show that search can be faster on the the weighted graph. In particular, search for a unique marked vertex on the unweighted ($w = 1$) graph takes time $\Theta(N^{3/4})$ \cite{MeyerWong2015}. We show that as $w$ increases, the runtime decreases to $\Theta(N^{3/4}/w)$. We can choose $w$ to nearly scale as $N^{1/4}$, reducing the runtime to nearly $\Theta(\sqrt{N})$.

Next, we define the quantum walk search algorithm on the graph, and we show that the system evolves in a constant $7$-dimensional subspace. Then we explain the general evolution of the algorithm, which occurs in two stages. Afterwards we analytically prove the runtime of the algorithm, which involves novelly adjusting degenerate perturbation theory \cite{JMW2014} to capture the weights of the graph. Subsequently, we give a new method of using degenerate perturbation theory to determine how precisely the jumping rate of the quantum walk must be chosen. Since degenerate perturbation theory is a useful tool in a variety of quantum search problems \cite{JMW2014,MeyerWong2015,Wong2015a,WongAmbainis2015,Novo2014}, these two extensions to the method are important apart from the graph at hand. Finally, we end with some remarks about the energy usage of the search algorithm and the connectivity of the weighted graph.

\section{Quantum Walk Search}

The vertices of the graph label computational basis states of an $N$-dimensional Hilbert space. A randomly walking quantum particle searches for a ``marked'' vertex of a regular graph by evolving by Schr\"odinger's equation with Hamiltonian
\[ H = -\gamma A - \ketbra{a}{a}, \]
where $\gamma$ is the jumping rate (\textit{i.e.}, amplitude per time), $A$ is the adjacency matrix of the graph ($A_{ij}$ equals the weight of the edge between vertices $i$ and $j$, and is zero if they are not connected), and $\ket{a}$ is a vertex that we are searching for \cite{CG2004}. Together, $-\gamma A$ effects a quantum walk, and $-\ketbra{a}{a}$ is a Hamiltonian oracle \cite{Mochon2007}.

The system $\ket{\psi(t)}$ begins in an equal superposition $\ket{s}$ over all the vertices:
\[ \ket{\psi(0)} = \ket{s} = \frac{1}{\sqrt{N}} \sum_{i=1}^N \ket{i}. \]
Not only is this a convenient initial state, but it expresses our initial lack of knowledge of where the marked vertex might be by guessing each vertex with equal probability. It is also an eigenstate of the adjacency matrix $A$ (with eigenvalue $M+w-1$) that effects the quantum walk, so if we evolve by $-\gamma A$ alone, we have no new information, and the state stays the same. It is only when we include the oracle term $-\ketbra{a}{a}$ that information changes, and the state changes with it.

Figure ~\ref{fig:simplex_weighted} shows that there are only seven kinds of vertices. For example, all the blue $b$ vertices will evolve the same way. Thus we can group identically-evolving vertices together into a 7D subspace:
\begin{align*}
	\ket{a} &= \ket{\text{red}} \\
	\ket{b} &= \frac{1}{\sqrt{M-1}} \sum_{i \in \text{blue}} \ket{i} \\
	\ket{c} &= \ket{\text{yellow}} \\
	\ket{d} &= \frac{1}{\sqrt{M-1}} \sum_{i \in \text{magenta}} \ket{i} \\
	\ket{e} &= \frac{1}{\sqrt{M-1}} \sum_{i \in \text{green}} \ket{i} \\
	\ket{f} &= \frac{1}{\sqrt{M-1}} \sum_{i \in \text{brown}} \ket{i} \\
	\ket{g} &= \frac{1}{\sqrt{(M-1)(M-2)}} \sum_{i \in \text{white}} \ket{i}.
\end{align*}
In this subspace, the initial equal superposition state is
\begin{align*}
	\ket{s} = \frac{1}{\sqrt{N}} \Big( &\ket{a} + \sqrt{M-1} \ket{b} + \ket{c} + \sqrt{M-1} \ket{d} \\ &+ \sqrt{M-1} \ket{e} + \sqrt{M-1} \ket{f} \\ &+ \sqrt{(M-1)(M-2)} \ket{g} \Big),
\end{align*}
and the search Hamiltonian is
\[ \setlength{\arraycolsep}{1pt} H = -\gamma \! \left( \! \begin{matrix}
	\frac{1}{\gamma} & \sqrt{M_1} & w & 0 & 0 & 0 & 0 \\
	\sqrt{M_1} & M_2 & 0 & 0 & w & 0 & 0 \\
	w & 0 & 0 & \sqrt{M_1} & 0 & 0 & 0 \\
	0 & 0 & \sqrt{M_1} & M_2 & 0 & w & 0 \\
	0 & w & 0 & 0 & 0 & 1 & \sqrt{M_2} \\
	0 & 0 & 0 & w & 1 & 0 & \sqrt{M_2} \\
	0 & 0 & 0 & 0 & \sqrt{M_2} & \sqrt{M_2} & M_3+w \\
\end{matrix} \! \right) \! , \setlength{\arraycolsep}{3pt} \]
where $M_k = M - k$. Thus we have reduced an $N$-dimensional problem to a 7-dimensional one.

\section{Two-Stage Algorithm}

To understand the behavior of the algorithm, let us start with the unweighted ($w = 1$) graph, which was first solved in \cite{MeyerWong2015}, and whose solution we now summarize. In Fig.~\ref{fig:overlap_w1}, we plot the probability overlaps of $\ket{s}$, $\ket{a}$, and $\ket{b}$ with the eigenvectors of $H$. When $\gamma$ is away from the critical value $\gamma_{c1} = 2/M = 0.002$, the initial state $\ket{s}$ asymptotically equals the ground or first excited state, and the system fails to evolve. So for the system to evolve at all, we must pick $\gamma$ to equal $\gamma_{c1}$, where the initial state takes the form $\ket{s} \propto \ket{\psi_0} + \ket{\psi_1}$. Thus it is half in the ground state and half in the first excited state. At $\gamma_{c1}$, note that $\ket{b}$ is also half in each of those energy eigenstates, taking the form $\ket{b} \propto \ket{\psi_0} - \ket{\psi_1}$. As proved in \cite{MeyerWong2015}, the energy gap at $\gamma_{c1}$ is $\Delta E = E_1 - E_0 = 4/M^{3/2}$, and so the system evolves from $\ket{s}$ to $\ket{b}$ in time $t_1 = \pi/\Delta E = \pi M^{3/2} / 4$.

\begin{figure*}
\begin{center}
	\subfloat[]{
		\includegraphics{overlap_w1}
		\label{fig:overlap_w1}
	} \quad \quad \quad \quad
	\subfloat[]{
		\includegraphics{overlap_w3}
		\label{fig:overlap_w3}
	}
	\caption{\label{fig:overlap} Probability overlaps of $\ket{s}$, $\ket{a}$, and $\ket{b}$ with eigenstates of $H$ for search on the weighted simplex of complete graphs with $M = 1000$ and (a) $w = 1$ (unweighted), and (b) $w = 3$.}
\end{center}
\end{figure*}

In this first stage of the algorithm, we have moved probability from being uniformly distributed throughout the graph to the correct cluster (see Fig.~\ref{fig:simplex_weighted}). Now we want the probability to move within this cluster to the marked vertex. To do this, note from Fig.~\ref{fig:overlap_w1} that when $\gamma$ equals $\gamma_{c2} = 1/M = 0.001$, $\ket{b}$ is now half in the ground and third excited states, taking the form $\ket{b} \propto \ket{\psi_0} + \ket{\psi_3}$. At $\gamma_{c2}$, we also have the marked vertex $\ket{a} \propto \ket{\psi_0} - \ket{\psi_3}$ with an energy gap of $\Delta E = E_3 - E_0 = 2/\sqrt{M}$. So for the second stage of the algorithm, the system evolves from $\ket{b}$ to $\ket{a}$ in time $t_2 = \pi/\Delta E = \pi \sqrt{M} / 2$.

We can see each distinctive stage in Figs.~\ref{fig:prob_time_b} and \ref{fig:prob_time_a}, where we plot the probability at $\ket{b}$ and $\ket{a}$, respectively, as the system evolves. The unweighted ($w = 1$) case is the solid black curves. For the first stage of the algorithm, from $t = 0$ to $t_1 = \pi\,1000^{3/2} / 4 \approx 24836.471$, probability accumulates at $\ket{b}$. Then we switch to the second stage of the algorithm, which only lasts for time $t_2 = \pi \sqrt{1000} / 2 \approx 49.673$, where the probability quickly moves from $\ket{b}$ to $\ket{a}$, achieving the search.

\begin{figure}
\begin{center}
	\includegraphics{prob_time_b}
	\caption{\label{fig:prob_time_b} Probability at $\ket{b}$ as a function of time for search on a simplex of complete graphs with $M = 1000$. The solid black curve is $w = 1$ (unweighted), and the dashed red curve is $w = 3$. Probability accumulates during the first stage of the algorithm and then it quickly leaves during the second stage (the sudden drop).}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
	\includegraphics{prob_time_a}
	\caption{\label{fig:prob_time_a} Probability at $\ket{a}$ (\textit{i.e.}, the success probability) as a function of time for search on a simplex of complete graphs with $M = 1000$. The solid black curve is $w = 1$ (unweighted), and the dashed red curve is $w = 3$. During the second stage of the algorithm, the probability quickly accumulates (the sudden spike).}
\end{center}
\end{figure}

The total runtime of the algorithm is the sum of the time for each stage: $t_1 + t_2 = \pi/\Delta E = \pi M^{3/2} / 4 + \pi \sqrt{M} / 2 = \Theta(M^{3/2}) = \Theta(N^{3/4})$. Clearly, the slow part of the algorithm is the first stage, where the probability is moving between clusters. The second stage is fast, where probability moves within the cluster containing the marked vertex. It is reasonable, then, that increasing the weights of the edges between clusters (the dotted edges in Fig.~\ref{fig:simplex_weighted}) can speed up this slow first stage. This is the idea of this paper.

Let us see how increasing the weights affects the algorithm. Fig.~\ref{fig:overlap_w3} shows the probability overlap plots with $w = 3$. From this, we see that the algorithm is still a two-stage evolution, except $\gamma_{c1}$ has shifted to the left. What is more striking, however, are the evolution plots in Figs.~\ref{fig:prob_time_b} and \ref{fig:prob_time_a}. Running each stage for the appropriate amount of time so that the probability moves from $\ket{s}$ to $\ket{b}$ to $\ket{a}$, we see that the runtime has been cut in half (actually, the first stage's runtime has been cut in half, and the second stage is the same).

So we indeed get a speedup by increasing the weights of the edges between the complete graph clusters. To prove this, and to show just how much of a speedup is possible, we use degenerate perturbation theory \cite{JMW2014}.

\section{Adjusted Degenerate Perturbation Theory}

\begin{figure}
\begin{center}
	\subfloat[]{
		\includegraphics{diagram_H}
		\label{fig:diagram_H}
	}

	\subfloat[]{
		\includegraphics{diagram_H_stage1}
		\label{fig:diagram_H_stage1}
	}

	\subfloat[]{
		\includegraphics{diagram_H_adjusted}
		\label{fig:diagram_H_adjusted}
	}

	\subfloat[]{
		\includegraphics{diagram_H_perturbed}
		\label{fig:diagram_H_perturbed}
	}

	\subfloat[]{
		\includegraphics{diagram_H_stage2}
		\label{fig:diagram_H_stage2}
	}

	\caption{Apart from a factor of $-\gamma$, the (a) Hamiltonian for search on the weighted simplex of complete graphs, (b) typical first-stage leading-order terms, (c) adjusted first-stage leading-order terms, (d) first-stage leading-order terms plus a perturbation, and (e) second-stage leading-order terms. Note (b) is also the second-stage leading-order terms plus a perturbation.}
\end{center}
\end{figure}

To begin, we interpret the search Hamiltonian (in the 7-dimensional subspace) as an adjacency matrix, which we express diagrammatically \cite{Wong2014} in Fig.~\ref{fig:diagram_H}. Finding the eigenvalues and eigenvectors of this Hamiltonian is too complicated given all the connections between the basis states. To simplify it, we treat the Hamiltonian as a leading-order term $H^{(0)}$ plus a perturbation $H^{(1)}$. Assuming that $w$ scales less than $\sqrt{M}$ throughout this paper, we can drop it with all other terms that scale less than $\sqrt{M}$, yielding the leading-order Hamiltonian shown in Fig.~\ref{fig:diagram_H_stage1}. This is precisely the leading-order Hamiltonian for the unweighted ($w = 1$) graph, and its eigenvalues and eigenvectors are given in \cite{MeyerWong2015}. While we have made the leading-order Hamiltonian tractable, we have lost all dependence on the weight $w$.

We need to introduce some dependence on $w$ back, but not so much that the problem becomes intractable. To do this, consider the original simplex of complete graphs in Fig.~\ref{fig:simplex_weighted}. There are $M(M+1)/2$ edges with weight $w$. Some of them connect $a$ with $c$, some $b$ with $e$, some $d$ with $f$, and some $g$ with $g$. Just how many is shown in Table~\ref{table:weighted}. Thus the edges of weight $w$ are dominated by those connecting $g$ vertices with other $g$ vertices. So we add this back into the leading-order Hamiltonian.

\begin{table}
	\caption{\label{table:weighted}The number of edges of weight $w$ based on what kinds of vertices they connect.}
	\begin{ruledtabular}
	\begin{tabular}{cc}
		Connection & Number of Edges \\
		\colrule
		$a \sim c$ & $1$ \\
		$b \sim e$ & $M-1$ \\
		$d \sim f$ & $M-1$ \\
		$g \sim g$ & $\frac{(M-1)(M-2)}{2}$ \\
	\end{tabular}
	\end{ruledtabular}
\end{table}

For consistency, we should also do this for the edges with weight $1$. There is a total of $M(M+1)(M-1)/2$ such edges, and their connections are as shown in Table~\ref{table:unweighted}. These are dominated by $g \sim g$, followed by $b \sim b$, $d \sim d$, $e \sim g$, and $f \sim g$. Note that $e \sim g$ and $f \sim g$ are already included in Fig.~\ref{fig:diagram_H_stage1}, but we should add the other terms in.

\begin{table}
	\caption{\label{table:unweighted}The number of edges of weight $1$ based on what kinds of vertices they connect}
	\begin{ruledtabular}
	\begin{tabular}{cc}
		Connection & Number of Edges \\
		\colrule
		$a \sim b$ & $M-1$ \\
		$b \sim b$ & $\frac{(M-1)(M-2)}{2}$ \\
		$c \sim d$ & $M-1$ \\
		$d \sim d$ & $\frac{(M-1)(M-2)}{2}$ \\
		$e \sim f$ & $M-1$ \\
		$e \sim g$ & $(M-1)(M-2)$ \\
		$f \sim g$ & $(M-1)(M-2)$ \\
		$g \sim g$ & $\frac{(M-1)(M-2)(M-3)}{2}$ \\
	\end{tabular}
	\end{ruledtabular}
\end{table}

Including these additional contributions, we get the adjusted leading-order Hamiltonian in Fig.~\ref{fig:diagram_H_adjusted}. This now has dependence on $w$, but is still simple enough to solve analytically. In particular, there are two eigenstates of it that we are interested in:
\begin{gather*}
	u = \frac{1 + 2\gamma - M\gamma + \sqrt{R_u}}{2\sqrt{M}\gamma} \ket{a} + \ket{b} \\
	v = \frac{2 \sqrt{M}}{-3 + M + w + \sqrt{R_v}} \left( \ket{e} + \ket{f} \right) + \ket{g},
\end{gather*}
with respective eigenvalues
\begin{gather*}
	E_u = \frac{1-2 \gamma +M \gamma +\sqrt{R_u}}{2 \gamma} \\
	E_v = \frac{1}{2} \left(-3+M+w+\sqrt{R_v}\right),
\end{gather*}
where
\begin{gather*}
	R_u = 1 + 4\gamma - 2M\gamma + 4\gamma^2 + M^2\gamma^2 \\
	R_v = 9 + 2M + M^2 - 6w + 2Mw + w^2
\end{gather*}
are the radicands in the expressions. These two eigenstates are of interest because $\ket{u} \approx \ket{b}$ and $\ket{v} \approx \ket{g} \approx \ket{s}$ to leading order, and recall from Fig.~\ref{fig:overlap} that we want to choose $\gamma$ so that the ground and first excited states are each half $\ket{b}$ and half $\ket{s}$. If the eigenvalues $E_u$ and $E_v$ are nondegenerate, then even with the perturbation, $\ket{u}$ and $\ket{v}$ will remain approximate eigenstates. But when they are degenerate, then linear combinations of them
\[ \ket{\psi} = \alpha_u \ket{u} + \alpha_v \ket{v}, \]
will be eigenstates of the perturbed system, which is what we want. Setting their unperturbed eigenvalues $E_u$ and $E_v$ equal, solving for $\gamma$, and taking the leading-order term for large $M$, we get the critical $\gamma$ for the first stage of the algorithm:
\[ \gamma_{c1} = \left( 1 + \frac{1}{w} \right) \frac{1}{M}. \]
When $w = 1$, this yields the unweighted value of $2/M$, as expected from \cite{MeyerWong2015} and Fig.~\ref{fig:overlap_w1}. When $w = 3$, we get with $M = 1000$ that $\gamma_{c1} = (1 + 1/3)/1000 = 0.0013$, in agreement with Fig.~\ref{fig:overlap_w3}.

Now lets calculate the perturbed eigenstates. The perturbation $H^{(1)}$ restores terms of constant weight so that the we get Fig.~\ref{fig:diagram_H_perturbed}. This lifts the degeneracy so that, as described above, the eigenstates become $\alpha_u \ket{u} + \alpha_v \ket{v}$, and the coefficients can be found by solving
\[ \begin{pmatrix}
	H_{uu} & H_{uv} \\
	H_{vu} & H_{vv} \\
\end{pmatrix} \begin{pmatrix}
	\alpha_u \\
	\alpha_v \\
\end{pmatrix} = E \begin{pmatrix}
	\alpha_u \\
	\alpha_v \\
\end{pmatrix}, \]
where $H_{uv} = \bra{u} H^{(0)} + H^{(1)} \ket{v}$, etc. Calculating these matrix elements with $\gamma = \gamma_{c1}$, the terms $O(1/M^{3/2})$ are
\[ \begin{pmatrix}
	-\frac{1+w}{w} + \frac{1-w^2}{w} \frac{1}{M} & -\frac{1+w}{M^{3/2}} \\
	-\frac{1+w}{M^{3/2}} & -\frac{1+w}{w} + \frac{1-w^2}{w} \frac{1}{M} \\
\end{pmatrix} \begin{pmatrix}
	\alpha_u \\
	\alpha_v \\
\end{pmatrix} = E \begin{pmatrix}
	\alpha_u \\
	\alpha_v \\
\end{pmatrix}. \]
Solving this yields perturbed eigenstates
\[ \ket{\psi_{\pm}} = \frac{1}{\sqrt{2}} \begin{pmatrix} \pm 1 \\ 1 \end{pmatrix} = \frac{1}{\sqrt{2}} \left( \pm \ket{u} + \ket{v} \right) \approx \frac{1}{\sqrt{2}} \left( \pm \ket{b} + \ket{g} \right) \]
with corresponding eigenvalues
\[ E_\pm = -\frac{1+w}{w} + \frac{1-w^2}{wM} \mp \frac{1+w}{M^{3/2}}. \]
Thus to leading order, the system evolves from $\ket{s} \approx \ket{g}$ to $\ket{b}$ in time
\[ t_1 = \frac{\pi}{\Delta E} = \frac{\pi}{2(1+w)} M^{3/2}. \]
When $w = 1$, we get the unweighted graph's expected runtime of $\pi M^{3/2} / 4$ for the first stage of the algorithm. Clearly, as we increase $w$, the runtime is decreased. For example, when $w = 3$, the runtime is $\pi M^{3/2} / 8$, which is half the time of the unweighted graph; this agrees with Figs.~\ref{fig:prob_time_b} and \ref{fig:prob_time_a}, where the dashed red curve shows the probability at $\ket{b}$ and $\ket{a}$, respectively, as the system evolves with $w = 3$.

When $w$ scales larger than a constant, then the runtime scaling of $t_1$ is reduced. For example, if $w = \Theta(M^{1/4})$, then $t_1 = \Theta(M^{5/4}) = \Theta(N^{5/8})$. Recall we are assuming that $w$ scales less than $\sqrt{M}$ in order to employ our perturbative method, so $t_1$ can almost be lowered to $\Theta(M) = \Theta(\sqrt{N})$. As we will see later, there is another consideration to account for that yields this same limitation on $w$. But before focusing too much on $t_1$, we must determine how the weights affect the second stage of the algorithm.

\section{Stage 2}

Let us now analyze how the weights affect the second stage of the algorithm, where probability moves from $\ket{b}$ to $\ket{a}$. From Fig.~\ref{fig:overlap}, the critical $\gamma$ for the second stage of the algorithm is unchanged from its unweighted value of $\gamma_{c2} = 1/M$. To prove this, we again use degenerate perturbation theory. This time, there is no adjustment needed as was in the first stage to reintroduce dependence on $w$, so the results from \cite{MeyerWong2015} and \cite{Wong2014} carry over directly, and which we summarize here.

For the leading-order Hamiltonina $H^{(0)}$, we drop the terms that scale less than $M$, yielding Fig.~\ref{fig:diagram_H_stage2}. From this, we see that $\ket{a}$ and $\ket{b}$ are eigenstates of $H^{(0)}$ with respective eigenvalues $-1$ and $-\gamma M$. If these eigenvalues are nondegenerate, then even with the perturbation, $\ket{b}$ will be an approximate eigenstate of the Hamiltonian, so the system will not evolve from $\ket{b}$ apart from a global, unobservable phase. To make the system evolve, we equate the eigenvalues to create a degeneracy, yielding the critical $\gamma$ for the second stage of the algorithm:
\[ \gamma_{c2} = \frac{1}{M}. \]
Then the perturbation $H^{(1)}$, which restores edges of weight $\Theta(\sqrt{M})$ so that we have Fig.~\ref{fig:diagram_H_stage1}, cause the eigenstates to become
\[ \alpha_a \ket{a} + \alpha_b \ket{b}, \]
where the coefficients can be found by solving
\[ \begin{pmatrix}
	H_{aa} & H_{ab} \\
	H_{ba} & H_{bb} \\
\end{pmatrix} \begin{pmatrix}
	\alpha_a \\
	\alpha_b \\
\end{pmatrix} = E \begin{pmatrix}
	\alpha_a \\
	\alpha_b \\
\end{pmatrix}, \]
where $H_{ab} = \bra{a} H^{(0)} + H^{(1)} \ket{b}$, etc. With $\gamma = \gamma_{c2}$, this is
\[ \begin{pmatrix}
	-1 & \frac{-1}{\sqrt{M}} \\
	\frac{-1}{\sqrt{M}} & -1 \\
\end{pmatrix} \begin{pmatrix}
	\alpha_a \\
	\alpha_b \\
\end{pmatrix} = E \begin{pmatrix}
	\alpha_a \\
	\alpha_b \\
\end{pmatrix}. \]
Solving this yields perturbed eigenstates and eigenvalues
\[ \frac{1}{\sqrt{2}} \left( \pm \ket{a} + \ket{b} \right), \quad -1 \mp \frac{1}{\sqrt{M}}. \]
Thus during the second stage of the algorithm, the system evolves from $\ket{b}$ to $\ket{a}$ in time
\[ t_2 = \frac{\pi}{\Delta E} = \frac{\pi \sqrt{M}}{2}. \]
So adding weights to the graph does not change the runtime of the second stage of the algorithm. Thus we can speed up the first stage of the algorithm by making the graph weighted without harming the second stage of the algorithm, and the total runtime is
\[ t_1 + t_2 = \frac{\pi M^{3/2}}{2(1+w)} + \frac{\pi \sqrt{M}}{2}. \]
This agrees with Figs.~\ref{fig:prob_time_b} and \ref{fig:prob_time_a}, where for $w = 3$ and $M = 1000$, the system evolves for time $t_1 = \pi 1000^{3/2} / 2(1+3) \approx 12418.235$, and then for an additional time of $t_2 = \pi \sqrt{1000}/2 \approx 49.673$.

Thus to reduce the overall runtime, we want to increase $w$ to be as large as possible. Recall that these results assume that $w$ scales less than $\sqrt{M}$, so we can almost decrease the overall runtime to $\Theta(M) = \Theta(\sqrt{N})$. But for this to be possible, there is one more matter to consider regarding the critical $\gamma$'s.

\section{Convergence of Critical Gammas}

Recall the critical $\gamma$'s for the first and second stages of the algorithm:
\[ \gamma_{c1} = \left( 1 + \frac{1}{w} \right) \frac{1}{M}, \quad \gamma_{c2} = \frac{1}{M}. \]
Then as $w$ increases, $\gamma_{c1}$ converges to $\gamma_{c2}$. This can also be seen in Fig.~\ref{fig:overlap}; as $w$ increases, the overlap crossing at $\gamma_{c1}$ moves to the left until it collides with the stationary crossing at $\gamma_{c2}$. This causes the distinct evolution of the two stages to meld together in a way that is unpredictable by our current method of degenerate perturbation theory.

So how big can $w$ be such that the two-stage algorithm holds? This equates to finding the ``width'' around each critical $\gamma$ in which the algorithm evolves correctly. For example, for the complete graph of $N$ vertices, an explicit calculation in \cite{Wong2015c} shows that when $\gamma$ is within $O(1/N^{3/2})$ of its critical value of $1/N$, then the system searches in Grover's $\Theta(\sqrt{N})$ time. When $\gamma$ is outside of this region, the system asymptotically starts in an eigenstate and fails to evolve apart from a global, unobservable phase. So there is a region around the critical $\gamma$ in which the algorithm is relevant, and outside of which it is not. For our weighted graph, we want the $\gamma_c$'s to be outside of each other's region of influence.

To find the relevant region around each $\gamma_c$, an explicit calculation as in \cite{Wong2015c} is prohibitive. Instead, we introduce a new approach to finding such precision bounds on how close $\gamma$ must be to its critical value using degenerate perturbation theory. To demonstrate it, let us start with the second stage, which is easier and will yield the relevant region. Recall from the last section that $\ket{a}$ and $\ket{b}$ are eigenstates of the leading-order Hamiltonian in Fig.~\ref{fig:diagram_H_stage2} with respective eigenvalues $-1$ and $-\gamma M$. Then if $\gamma$ is $\epsilon$ away from its critical value, \textit{i.e.}, $\gamma = \gamma_{c2} + \epsilon = 1/M + \epsilon$, then $\ket{b}$'s unperturbed eigenvalue becomes $-1 - \epsilon M$. If $\epsilon$ is small so that $\ket{a}$ and $\ket{b}$ are near-degenerate, then with the perturbation, the eigenstates become linear combinations $\alpha_a \ket{a} + \alpha_b \ket{b}$, and we solve an eigenvalue problem for the coefficients. The eigenvalue problem contains a term $H_{bb} = \langle b | H^{(0)} + H^{(1)} | b \rangle$, which contains a term scaling as $\epsilon M$ that is the leading-order term in $\epsilon$. For the system to evolve with the correct scaling, $\epsilon M$ must scale no greater than the energy gap $\Theta(1/\sqrt{M})$. Thus $\epsilon = O(1/M^{3/2})$. This gives the precision with which $\gamma$ must equal its second critical value.

Since the first stage's energy gap $\Theta(w/M^{3/2})$ is smaller than the second stage's $\Theta(1/\sqrt{M})$, the first stage has a smaller range of $\gamma$'s that will work for it. This can also be seen in Fig.~\ref{fig:overlap_w3}, where $\gamma_{c1} = 0.0013$ has a thinner crossing than $\gamma_{c2} = 0.001$'s crossing. Thus when the $\gamma_c$'s ``collide,'' it is when they are within $O(1/M^{3/2})$ of each other, having entered the second stage's region of influence.

Back to our original question of how big $w$ can be before the first stage ``collides'' with the second stage. We want
\[ \gamma_{c1} = \frac{1}{M} + \frac{1}{wM} = \gamma_{c2} + \frac{1}{wM} \]
to stay outside of the range of the second stage. Taking $1/wM$ to be $\epsilon$ in the previous calculation, we want it to scale bigger than $1/M^{3/2}$, which yields
\[ w = o(\sqrt{M}). \]
That is, the weight must scale less than $\sqrt{M}$ for the two stages of the algorithm to be distinct. Since this is the assumption throughout our paper for the perturbative calculations to work, our algorithm works in all values of $w$ considered in this work, and it allows the runtime to be reduced to nearly $\Theta(\sqrt{N})$.

\section{Energy and Connectivity}

We end with some remarks about the energy usage of the algorithm, as well as the connectivity of the weighted graph. First regarding energy, the operator norm of the Hamiltonian gives some sense of the energy being used. By making the graph weighted, we have only changed $\gamma$ and the adjacency matrix while leaving the oracle term $\ketbra{a}{a}$ alone. The operator norm of the adjacency matrix is $M + w - 1 = \Theta(M)$, and both the critical $\gamma$'s scale as $\Theta(1/M)$. Thus the operator norm of $\gamma A$ is $\Theta(1)$, and so to leading order, the search algorithm on the weighted graph does not use more energy than on the unweighted graph.

Now for connectivity. Since the (unweighted) simplex of complete graphs was first introduced for quantum computing as a graph with high connectivity, but on which search is slow \cite{MeyerWong2015}, we comment on the connectivity of our weighted version. The vertex connectivity is unchanged, since $M$ vertices must be removed to disconnect the graph. Thus it does not capture the weights and is a poor indicator of connectivity for weighted graphs. The edge connectivity is also unsatisfactory. While $M$ edges must be removed, should the weights of the edges be accounted for? For example, a cluster can be disconnected from the rest of the graph by removing the $M$ edges of weight $w$ connecting to the cluster. Or a single vertex can be disconnected by removing its $M$ edges, of which $M-1$ have weight $1$ and one has weight $w$. As such, it is better to consider algebraic connectivity \cite{Fiedler1973} for weighted graphs, which is the second smallest eigenvalue of the graph Laplacian $L = D - A$, where $D$ is a diagonal matrix with the degree of each vertex. For the weighted simplex of complete graphs, it is
\[ \lambda_1 = \frac{1}{2} \left( M + 2w - \sqrt{M^2 - 4w + 4w^2} \right) \approx w. \]
Clearly, making the weight $w$ larger increases the algebraic connectivity, as expected. We can further improve this with a normalized algebraic connectivity \cite{Chung1997}, which for a regular graph is simply its algebraic connectivity divided by its degree, in this case yielding roughly $w / M$. As expected, this connectivity is higher when the weight $w$ increases. When $w$ almost scales as $\sqrt{M}$ so that the runtime is nearly reduced to $\Theta(\sqrt{N})$, the algebraic connectivity is almost that of an eight-dimensional cubic lattice, on which search is fast \cite{CG2004}.

This does not contradict the conclusion of \cite{MeyerWong2015}, of course. That the weighted simplex of complete graphs has high connectivity and yields fast search does not take away from the counterexample of the unweighted graph searching slower than its connectivity would suggest. Furthermore, by changing the weights, we have changed the graph.

\section{Conclusion}

We have modified the simplex of complete graphs to have different weights on the edges between clusters from the edges within clusters. This defines a reasonable search structure that is vertex-transitive, and whose equal superposition over the vertices is an eigenstate of its adjacency matrix. By adjusting degenerate perturbation theory, we proved that the runtime on this weighted graph can be reduced from the unweighted $\Theta(N^{3/4})$ to nearly $\Theta(\sqrt{N})$. Thus we have novelly demonstrated that faster quantum search is possible on a weighted graph.

It is very possible that our work can be extended to fully reduce the runtime to Grover's $\Theta(\sqrt{N})$. For example, we have left open the case when $w$ scales greater than or equal to $\sqrt{M}$. One could also consider changing the weights differently, moving away from our model where edges between clusters have one weight while edges within clusters have another. Finally, different graphs could be considered altogether.

\begin{acknowledgments}
	Thanks to a referee of \cite{Wong2015a} for suggesting search on the weighted simplex of complete graphs. This work was supported by the European Union Seventh Framework Programme (FP7/2007-2013) under the QALGO (Grant Agreement No.~600700) project, and the ERC Advanced Grant MQC.
\end{acknowledgments}


\section{Introduction}

Since its discovery, Pauli-spin blockade (PSB)\cite{Ono02} has been a valuable tool for probing fundamental physics.  Its use in spin to charge conversion has led to investigations of spin $T_1$ relaxation times\cite{Petta05B,Hu12}, electron spin couplings to lattice nuclear spins\cite{Johnson05A}, and spin-orbit effects\cite{Nadj10}.  PSB has also received a lot of attention from the quantum information community due to its use in read-out and initialization of various electron spin states\cite{Petta05,Koppens06,Nowack07}.  The majority of studies involving PSB have focused on the low magnetic field regime. In this manuscript we investigate the qualitative behavior of PSB at all magnetic fields. In doing so we identify experimentally accessible regimes where PSB has yet to be studied and new physics is likely to be found.

In a typical double quantum dot (DQD) device two quantum dots are coupled to each other as well as to two electron reservoirs (see figure~1(a)). The dots are also capacitively coupled to one or more gate electrodes which can be used to control the dot potentials. The charge configuration of the system is characterized by a pair of numbers $(n,m)$ corresponding to the number of electrons on the left and right dot, respectively. Transport through quantum dots can be understood by considering the chemical potentials of the quantum dots, $\mu_{l}(n,m) \equiv E(n,m) - E(n-1,m)$ and $\mu_{r}(n,m) \equiv E(n,m)-E(n,m-1)$, where $E$ denotes the total energy of the system. When the appropriate chemical potentials form a energetically downhill path between the Fermi levels of the two leads, $\mu_{LL(RL)}$, electron tunnelling through the device is energetically favorable and leads to current flow\cite{VDW02}. Near the \ensuremath{(1,1) \leftrightarrow (0,2)~} charge transition, where PSB typically occurs, this condition can be expressed as $\mu_{LL} \geq \mu_l(1,1) \geq\mu_r(0,2) \geq \mu_{RL}$ for transport in the forward \ensuremath{(1,1) \rightarrow (0,2)~} direction and $\mu_{LL} \leq \mu_l(1,1) \leq\mu_r(0,2) \leq \mu_{RL}$ for transport in the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction.  These conditions describe regions of transport known as bias triangles, with sizes proportional to the applied bias voltage, $V_{bias}$.\cite{VDW02}

For a more complete picture of transport through a DQD near the \ensuremath{(1,1) \leftrightarrow (0,2)~} charge degeneracy we now also consider the spin state of the electrons.  For transport in the forward (left to right) direction current flows via tunneling events that cycle through the $(0,1) \rightarrow (1,1) \rightarrow (0,2) \rightarrow (0,1)$ charge configurations. In the reverse direction it occurs via $(0,1) \rightarrow (0,2) \rightarrow (1,1) \rightarrow (0,1)$.  In both cases the first tunneling event brings an electron from a lead onto the DQD forming a two-electron system.  These electrons can form one of four possible spin states, the $s=0$ spin singlet $\left|S\right\rangle~\equiv~\left(\left|\uparrow\downarrow\right\rangle - \left|\downarrow\uparrow\right\rangle\right)/\sqrt{2}$, or one of the three $s=1$ triplet states $\left|T_0\right\rangle~\equiv ~\left(\left|\uparrow\downarrow\right\rangle + \left|\downarrow\uparrow\right\rangle\right)/\sqrt{2}$, $\left|T_+\right\rangle~\equiv~\left|\uparrow\uparrow\right\rangle$, $\left|T_-\right\rangle~\equiv~\left|\downarrow\downarrow\right\rangle$. In zero magnetic field, the \ket{S} state is typically the ground state and the three degenerate triplet states are higher in energy by the exchange energy $J$\cite{AshcroftMermin}. Since $J$ scales with the wavefunction overlap between the two electrons, the charge configuration of the electrons will have a large influence on the magnitude of $J$. When in the (0,2) charge configuration, the overlap is large so $J(0,2)$ is as well, whereas in the (1,1) configuration the overlap is minimal as is $J(1,1)$\footnote{In this paper we take $J(1,1) = 0$ for simplicity. Including a finite value would not significantly affect the results of this work.}. This difference in exchange between the two charge configurations is the cornerstone of PSB.  It leads to a situation where although the forward \ensuremath{(1,1) \rightarrow (0,2)~} interdot transition is allowed for the \ket{S} ground states, current does not flow.  This occurs because, with $J(1,1) < J(0,2)$, it is possible that even though conduction through the singlet states is allowed, {\emph{i.e.}} $\mu_{LL}\geq\mu_l^{\left|S\right\rangle}(1,1) \geq \mu_r^{\left|S\right\rangle}(0,2)\geq \mu_{RL}$, the interdot transition for the triplet states is forbidden, $\mu_l^{\left|T_x\right\rangle}(1,1)\leq\mu_r^{\left|T_x\right\rangle}(0,2)$.  Thus, once loaded, the \ket{(1,1)T_x} can tunnel neither forward nor back until it has relaxed into a singlet state. Since the spin relaxation from a \ket{T_x} state to a \ket{S} state is typically long relative to the tunneling times, the measured current in the PSB region is near or below the noise floor of the measurement system. This situation truncates the size of the bias triangles in the forward bias direction, as shown in figure~1c, while leaving the triangles measured in the reverse bias direction at ``full size'', as in figure~1b. This size difference is the most basic signature of PSB and has been measured by several groups in various material systems\cite{Johnson05B,Lai11,Yamahata12,Simmons10,Koppens05,Shaji08,Churchill09A,Weber14,Liu08,Pfund07,Nadj10}.

\begin{figure}
	\centering

	\includegraphics[width = 0.9\columnwidth]{./Figure1.png}

	\caption{{\bf{Traditional forward Pauli-spin blockade, B = 0 T}} Bias triangles at the $(1,1) \leftrightarrow (0,2)$ charge transition with no applied magnetic field, $V_{bias} = \pm 1~{\rm{mV}}$ and $J(0,2) = 0.3~{\rm{meV}}$. (a) Schematic of a typical double quantum dot. A bias applied between the left and right leads can lead to electrons tunneling through the device. The potentials of the dots are controlled with two capacitively coupled gates. (b) and (c) are voltage space pictures of current measurements in the \ensuremath{(0,2) \rightarrow (1,1)~} and \ensuremath{(1,1) \rightarrow (0,2)~} biasing directions using typical voltage and capacitance values. Filled regions of color correspond to non-zero current. (d) is the chemical potential space picture for the same transitions. Triangles below the $\Delta\mu_{l}(1,1) = 0$ axis are for \ensuremath{(1,1) \rightarrow (0,2)~} biasing and those above are for \ensuremath{(0,2) \rightarrow (1,1)~} biasing. Chemical potential diagrams for certain regions of interest in (b), (c) and (d) are also shown. The \ensuremath{\mu}-space~ origin is determined by the Fermi level of the left lead which we take to be at the ground potential for all measurements.  The PSB region is labelled with the blue diamond.\label{fig1}}
\end{figure}

For a more intuitive presentation of the voltage space measurements depicted in figure~1(b) and (c) one can convert them to chemical potential space, or \ensuremath{\mu}-space~\cite{Perron15}, where triangles from both bias polarities can be shown on a single plot. Plotted in figure~1(d) is the \ensuremath{\mu}-space~ equivalent to what is shown in both panels~(b) and (c), where the axes are defined as $\Delta\mu_l(1,1) \equiv \mu_l^{\left|S\right\rangle}(1,1) - \mu_{LL}$ and $\Delta\mu_r(0,2) \equiv \mu_r^{\left|S\right\rangle}(0,2) -\mu_{LL}$.  Also shown in this plot are outlines of the ``state triangles'', which correspond to the conditions $\mu_{LL} \geq \mu_{l}^{state}(1,1) \geq \mu_{r}^{state}(0,2) \geq \mu_{RL}$, in the forward biased direction and $\mu_{RL} \geq \mu_{r}^{state}(0,2) \geq \mu_{l}^{state}(1,1) \geq \mu_{LL}$, with $\mu_{LL} \equiv 0$,  in the reverse direction, where $state$ refers to the spin state, \ket{S} or \ket{T_x}, of the two electron system. In figure~1(c) and (d), the region labeled with the blue diamond corresponds to the region where PSB occurs, as shown in the corresponding chemical potential diagram.

When a magnetic field $B$, is applied, several effects can occur depending on the direction of the applied field. If applied perpendicular to the two-dimensional electron gas (2DEG) there can be a significant change in the spatial wavefunctions of the electrons. This will in turn affect the magnitudes of $J(1,1)$ and $J(0,2)$ leading to a change in size of the PSB region\cite{Johnson05B}. At higher fields, the \ket{T_x} states can fall below the \ket{S} states leading to PSB in the \ensuremath{(1,1) \rightarrow (0,2)~} direction caused by singlet states rather than the triplet states\cite{Sun12}. When $B$ is applied in the plane of the 2DEG the spatial effect on the wave functions is negligible and observed effects are due to the Zeeman splitting of the triplet levels. This in-plane magnetic field dependence will be the focus of the remainder of this manuscript.

When considering the in-plane $B$, we make the following assumptions for $B$-dependence of the chemical potentials
\begin{align}
	\left. \mu^{\left|S\right\rangle}\left(n,m\right)\right|_{B\neq0} &= \left.\mu^{\left|S\right\rangle}\left(n,m\right)\right|_{B=0}, \\
	\left. \mu^{\left|T_0\right\rangle}\left(n,m\right)\right|_{B\neq0} &=\left. \mu^{\left|S\right\rangle}\left(n,m\right)\right|_{B=0} + J(n,m), \\
	\left.	\mu^{\left|T_\pm\right\rangle}\left(n,m\right)\right|_{B\neq0} &=\left. \mu^{\left|S\right\rangle}\left(n,m\right)\right|_{B=0} + J(n,m) \pm g\mu_BB.
\end{align}
\noindent When $B$ is increased from zero, the first notable effect is the change in size of the bias triangles. As reported in reference~\cite{Lai11}, the triangles in the forward \ensuremath{(1,1) \rightarrow (0,2)~} biasing direction grow in size proportional to the Zeeman energy $E_Z = g\mu_B B$, with $g$ the electron g-factor, and $\mu_B$ the Bohr magneton.  However, we predict a concomitant reduction in size of the triangles measured in the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction.  Both of these effects are illustrated in figure~2.

Figure~2(a) shows the \ensuremath{\mu}-space~ picture of the changing triangles (see supplemental material for details on using the \ensuremath{\mu}-space~ picture to determine the regions of allowed current).  The origin is defined by the point where $\mu_l^{\left|S\right\rangle}(1,1) =\mu_r^{\left|S\right\rangle}(0,2) = \mu_{LL} = 0$. Since $\mu^{\left|S\right\rangle}(n,m)$ has no magnetic field dependence, our definition of the origin relates it to a single point in voltage space, at all magnetic fields. This has the advantage that the direction the growth/contraction occurs along is clarified. The triangles for both biasing directions change size along the $\Delta\mu_{l}(1,1)$ axis. This is understood by considering the process which determines the edge of the triangles in each case.  For the forward \ensuremath{(1,1) \rightarrow (0,2)~} direction, the crucial process is the loading of an electron from the left lead onto the left dot.  As $B$ is increased, the \ket{(1,1)T_-} level is lowered by the Zeeman energy meaning that the loading of that state can occur at larger $\Delta\mu_l(1,1)$ values. This is shown in the chemical potential diagrams at the top of figure~2a for the point labelled with the blue triangle. In this region, since the only accessible (1,1) state is \ket{T_-}, conduction is spin-polarized. In the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction, the crucial process is the Coulomb blockade of current due to loading of the \ket{(1,1)T_-} level below $\mu_{LL}$. Again, as $B$ is increased this level drops below $\mu_{LL}$ at a higher $\Delta\mu_l(1,1)$. This is depicted in the chemical potential diagrams at the bottom of figure~2a for the point labeled with the red square. In both biasing directions, when viewed in this \ensuremath{\mu}-space~ picture, the direction the triangles are changing is clear, and we can then easily generate the correct gate voltage space picture. This is done in figure~2(b)~ through~(d), using typical capacitance and voltage parameters, which show bias triangles for the forward \ensuremath{(1,1) \rightarrow (0,2)~} direction growing with magnetic field in roughly the $-V_{lg}$ direction (as compared to the detuning direction i.e. perpendicular to the base of the triangles). This prediction is clearly observed in reference~\cite{Lai11} and validates the assumptions made in equations~1 through 3.

\begin{figure}
	\centering

	\includegraphics[width = 0.9\columnwidth]{./Figure2.png}

	\caption{{\bf{Magnetic field dependence for $\mathbf{B \leq B_{ST}}$}}: (a) \ensuremath{\mu}-space~ picture of bias triangles in both biasing directions with $V_{bias}~=~\pm1~\rm{mV}$, $J(0,2) = 0.3$~meV at three $B$ values corresponding to $E_Z = 0.0$, 0.125 and 0.25~meV respectively. The triangles outlined with consecutively thicker lines correspond to higher $B$. As $B$ is increased, the triangles in the forward \ensuremath{(1,1) \rightarrow (0,2)~} direction (left set of triangles) grow along the $\mu_l(1,1)$ direction while the reverse \ensuremath{(0,2) \rightarrow (1,1)~} biased triangles shrink in the same direction.  The change in triangle size is due to the Zeeman splitting of the \ket{(1,1)T_-} level as shown in the chemical potential diagrams corresponding to the points labeled with the blue triangle and the red square respectively.  (b) through (d) are gate voltage space bias triangles in the forward \ensuremath{(1,1) \rightarrow (0,2)~} biasing direction at the same magnetic fields as (a). The vertex labeled with the star occurs at the same position at all magnetic fields in both \ensuremath{\mu}-space~ and gate voltage space. The growth direction we predict is clear and agrees with the data in Figure~4 of reference~\cite{Lai11}.\label{fig1}}
\end{figure}

As $B$ is increased further there will be a crossover from PSB in the forward \ensuremath{(1,1) \rightarrow (0,2)~} direction, as discussed above and in previous works\cite{Ono02,Nadj10,Liu08,Lai11,Yamahata12,Johnson05B,Koppens05,Simmons10,Shaji08,Churchill09A,Churchill09B,Weber14,Liu08,Pfund07,Sun12}, to PSB in the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction.  The onset of this reverse PSB is accompanied by the development of a tail-like feature in the regions of allowed current\footnote{These tail features are qualitatively similar to those associated with lifetime enhanced transport\cite{Shaji08,Simmons10} but arise from very different physical mechanisms.} and occurs at a magnetic field $B_{ST}$ where $E_Z = J(0,2)$.

\begin{figure}
	\centering

	\includegraphics[width = 0.9\columnwidth]{./Figure3.png}
	\caption{$\mathbf{B \geq B_{ST}}$ \ensuremath{\mu}-space~ picture of transport in the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction with an applied magnetic field $g \mu_B B = 0.5~\rm{meV}$, $J(0,2) = 0.3~\rm{meV}$ and $V_{bias} = -1~\rm{mV}$. The region of allowed current (red) is no longer triangular.  The tail-like feature, indicated with the star, consists of current through only the \ket{T_-} levels and therefore is a spin polarized current upon exiting the DQD.  The regions identified with the diamond and square symbols define the area of PSB. Unlike the typical PSB, this high-field PSB is caused by the loading of the \ket{(0,2)S} level rather than the \ket{(1,1)T} level. This means that any leakage current measured in this region is due to relaxing from the \ket{(0,2)S} and \ket{(0,2)T_-} states. In the region identified by the black circle current is allowed through both the  \ket{S} and \ket{T_-} states.  Below the \ensuremath{\mu}-space~ plot are chemical potential diagrams for the indicated positions with key transitions indicated with arrows.\label{fig3}}
\end{figure}

Both of the high field features can be understood by considering figure~3, a \ensuremath{\mu}-space~ picture of a transport measurement in the reverse \ensuremath{(0,2) \rightarrow (1,1)~} direction with $E_Z > J(0,2)$. Included are the state triangles for the various singlet and triplet chemical potential levels. The regions labeled with the blue diamond and square correspond to the region of PSB.  The physics of this PSB is similar to the traditional low field \ensuremath{(1,1) \rightarrow (0,2)~} PSB, but with the \ket{(0,2)S} state filling the role of the trapped state and the \ket{T_-} levels contributing to current.  This is shown in the corresponding chemical potential diagrams. Throughout the PSB region, although current is allowed through the ground state \ket{T_-} levels, the \ket{(0,2)S} state can load from the right lead and, since the \ket{(0,2)S}$\rightarrow$\ket{(1,1)T_-} tunneling event is not allowed, it will block current until it relaxes to a \ket{T_-} state. Much like how the leakage current in the low field \ensuremath{(1,1) \rightarrow (0,2)~} PSB region was used to probe the \ket{(1,1)T}$\rightarrow$\ket{(1,1)S} relaxation\cite{Lai11,Koppens05,Yamahata12,Churchill09A,Churchill09B,Pfund07,Nadj10}, leakage currents in this reverse PSB region can be used to probe the \ket{(0,2)S}$\rightarrow$\ket{(0,2)T_-} relaxation.

Figure~3 has another distinct feature, the tail region labeled with the star.  This feature also develops when the \ket{T_-} state becomes the ground state in the (0,2) configuration. The feature can be understood by considering the border between the tail and the PSB region. To the left of this border no current is measured because the \ket{(0,2)S} can load and prevent current flow as previously discussed. To the right of the border the \ket{(0,2)S} level is above $\mu_{RL}$ and is therefore unable to load (compare the chemical potential diagrams labelled with the diamond and the star).  Since the \ket{(0,2)T_-} state is the only state that can load, the current measured in the tail region will be spin polarized upon exiting the DQD, which suggests a potential use as a polarized spin current source.\footnote{The current is polarized upon exiting the double quantum dot, however, the spin relaxation process of the electrons once in the Fermi sea of the lead is likely to be fast, quickly diminishing the polarization of the current.}

By thoroughly considering the \ensuremath{\mu}-space~ picture typically used to explain PSB, we have identified several interesting and unexplored features involved in the \ensuremath{(1,1) \leftrightarrow (0,2)~} transition of a double quantum dot at both low and high magnetic fields.  The boundary between the two field regimes occurs at $B_{ST}$ where the Zeeman energy of \ket{(0,2)T_-} equals $J(0,2)$.  With $g=2$ and exchange energies reported\cite{Lai11,Shaji08,Liu08} in the range of 0.24 to 1.4~meV, $B_{ST}$ in Si should be in the range of 2 to 12~Tesla, accesible with standard cryomagnetics.  This suggests that Si offers an opportunity to test our predictions.  Simple validation can be achieved by performing measurements of the type reported in \cite{Lai11} for both biasing directions and comparing with our predictions of changing triangle size.  Following that, the high-field tail feature we predict should be a clear signature that the reverse PSB regime has been reached.  This naturally leads to experiments involving the leakage current in the PSB regime. Similar to low-field PSB leakage current investigations\cite{Lai11,Koppens05,Yamahata12,Churchill09A,Churchill09B,Pfund07,Nadj10,Johnson05A}, these measurements would probe singlet-triplet relaxation mechanisms but in the (0,2) charge configuration rather than the (1,1). This removes any spin-orbit interaction and nuclear field gradients between the two electrons, both of which were previously shown as the dominant coupling mechanisms between the \ket{S} and \ket{T_x} states in certain material systems\cite{Churchill09A,Nadj10,Pfund07,Yamahata12,Danon09,Nadj10,Pfund07,Churchill09A,Churchill09B,Koppens05}.  Thus, measurements of this type will deepen our understanding of higher order spin relaxation mechanisms.

\begin{acknowledgements}
	We are grateful for the many useful discussions with Josh Pomeroy, Garnett Bryant, Mark Stiles and Michael Gullans.
\end{acknowledgements}

\section{Allowed Current when $J(0,2) \geq E_{Z}$}

In figure~2 of the main text we show the region of allowed current in a \ensuremath{\mu}-space~ picture for low magnetic fields. Here, we elaborate on the details of where and why current is allowed. The process of making chemical potential space plots is rather straightforward. For each state, one right-angle triangle is formed with horizontal and vertical sides of length $eV_{bias}$. The singlet triangle has the appropriate vertex positioned at the origin while the other state triangles are shifted according to their appropriate exchange and Zeeman energies. This is shown in figure~S1 with $V_{bias} = -1$~mV, $J(0,2) = 0.3$~meV, and $E_Z = 0.15$~meV.

\renewcommand{\thefigure}{S\arabic{figure}}
\begin{figure}
	\centering

	\includegraphics[width = 0.8\columnwidth]{./Supp.png}
	\caption{{\bf{Low field state triangles:}} State triangles in the \ensuremath{(1,1) \rightarrow (0,2)~} direction in \ensuremath{\mu}-space~ with  $J(0,2) = 0.3$~meV, $E_{Z} = 0.15$~meV, and $V_{bias}~=~-1~\rm{mV}$. The singlet triangle always lies at the origin by definition, and all other state triangles are shifted along the two axis according to the appropriate energy splittings.}
\label{figs1}
\end{figure}

To determine the regions of allowed current one can draw the state triangles for the magnetic field of interest and then examine the different regions they define. By counting the conduction paths formed by transitions that are both energetically favorable and allowed through spin conservation one can determine how many channels are allowed in a given region. Secondly, one must determine if there are any partial channels, that is states that can be loaded onto the double dot but not contribute to further tunneling, such as the \ket{(1,1)T_x} levels in traditional PSB. If one of these states exists current is not expected. Figure~S2 shows this process for the \ensuremath{\mu}-space~ plot in figure~S1. The filled regions are colored according to the number of channels conduction can occur through.  The red region is the PSB region, where, although conduction is allowed through the singlet channel, no current is expected to flow due to the loading of the \ket{(1,1)T_-} state.  In the green region all four states contribute to conduction.  The cyan region corresponds to where the \ket{(1,1)T_+} level cannot be loaded but all other states contribute to current.  Finally, the yellow region corresponds to where there are no blocking partial channels and only the \ket{T_-} levels contribute to conduction.

\renewcommand{\thefigure}{S\arabic{figure}}
\begin{figure}
	\centering

	\includegraphics[height = \columnwidth]{./Supp1.png}
	\caption{{\bf{Low field state triangles:}} State triangles in the \ensuremath{(1,1) \rightarrow (0,2)~} direction in \ensuremath{\mu}-space~ with  $J(0,2) = 0.3$~meV, $E_{Z} = 0.15$~meV, and $V_{bias}~=~-1~\rm{mV}$. Colors in the filled region correspond the number of allowed conduction channels. The red region is the Pauli-spin blockade region with one allowed channel but one blocking partial channel. In the green region conduction is allowed through all four states, \ket{S}, \ket{T_0}, \ket{T_+} and \ket{T_-}. In the cyan region the \ket{T_+} level cannot load so it is not involved in conduction whereas in the yellow region only the \ket{T_-} level can load. Thus, current is polarized. Also shown are chemical potential diagrams corresponding to various points in the plot, which indicate whether or not current is allowed.}
\label{figs2}
\end{figure}

\section{Internal Structure}
Looking at figure S1, one might expect some current dependence relating to the number of conduction channels allowed.  Any dependence would likely depend heavily on any state dependent tunnel rates and very device specific.

\end{document}