Recently, Gunn, Ju, Ma and Zhandry give a systematic treatment on
$\qsc$~[18]. They propose a new characterization of binding
termed \emph{swap-binding}. They show a striking hiding-binding
\emph{duality} theorem for (non-interactive) quantum commitment:
binding holds if the \emph{opening} register held by the sender hides
the input state. This significantly simplifies proving binding. They
then construct binding commitment schemes which in addition are
\emph{succinct}, where the register containing the commitment has a
\emph{smaller} size than the message state.\footnote{Note that hiding
is not required in these succinct schemes.}

\paragraph{Succinct $\qsc$ from $\prss$.} The succinct $\qsc$ schemes
by~[18] are based on post-quantum one-way functions or the
potentially weaker primitive of pseudorandom unitary operators
(\pru). We show below the viability of building succinct commitment on
\prss. This further \emph{weakens} the assumption, given the oracle
separation between $\prss$s and one-way functions and that $\pru$
implies $\prss$ (in a black-box fashion) but the converse is unknown.

\begin{theorem}
Assuming a succinct $\prss$, i.e., $|\K| < 2^\dimin$, there exists a
succinct $\qsc$.
\label{thm:sqsc-prss}
\end{theorem}

\begin{proof} This follows from a generic claim in~[18]. They
show that any one-time secure quantum encryption scheme with
\emph{succinct} keys, where the key is shorter than the state to be
encrypted, readily gives a succinct \qsc. A $\prss$ is a secure
quantum encryption as discussed above. Succinctness translates if
$\prss$'s key length is shorter than the size of the input
state. This is stated below. We choose not to fully spelled out the
syntax and definitions of the involved primitives for the sake of
clarity, and refer the readers to~[18].
\end{proof}

\begin{lemma}
Assuming a succinct $\prss$, i.e., $|\K| < 2^\dimin$, there exists a
succinct one-time quantum encryption scheme.
\label{lemma:otqenc-prss}
\end{lemma}

How to instantiate a succinct $\prss$? Our construction
is not immediately succinct, because the key length
$\Omega(\secpar\cdot\dimin)$. We can remedy this by using a
pseudorandom generator to expand a key shorter than $\dimin$ into
pseudorandom keys for each iteration (\qprf~and \qprp).

%------------------dispersing rss------------------%
\section{Dispersing \rss~and Dispersing \prss}
\label{sec:srss}
%\sect{const1} demonstrates the construction of two ensembles of unitary operators,
%which are \rss s over real space and complex space respectively.
%%These ensembles are able to scramble an arbitrary state to a random state that is close to Haar random state in terms of trace distance.
%In fact, they possess a dispersing property, which is stronger compared to the closeness in trace distance.
%This strong property is a consequence of the rapid mixing property (in terms of total variation distance rather than Wasserstein $1$-distance) exhibited by the parallel Kac's walk.

We first give the formal definitions
of a random scrambler and a pseudorandom scrambler with a dispersing property in \sect{drss}.
Then, \sect{tvmixing} analyses the total variation mixing time of the parallel Kac's walk on both real and complex Hilbert space.
Lastly in \sect{provedrss}, we utilize this rapid mixing property to demonstrate that the ensembles of unitary operators we construct in \sect{const1} do exhibit a dispersing property.

\subsection{Definitions}
\label{sec:drss}

We introduce the concept of \emph{dispersing random state scramblers} (\srss),
which ensure the approximation of Haar randomness with respect to Wasserstein distance.

\begin{definition}[Dispersing Random State Scrambler]
\label{def:trssb}
Let $\hspacein$ and $\hspaceout$ be Hilbert spaces of dimensions
$2^{\dimin}$ and $2^\dimout$ respectively with
$\dimin, \dimout \in\N$ and $\dimin \leq \dimout$. Let
$\K=\bit{\klen}$ be a key space, and $\secpar$ be a security
parameter. A \emph{dispersing random state scrambler} (\srss) is an
ensemble of isometric operators
$\SG{}{\dimin,\dimout} := \{ \SG{}{\dimin,\dimout,\secpar}
\}_\secpar$ with
$\SG{}{\dimin,\dimout,\secpar} : = \{\SG{k}{\dimin,
\dimout,\secpar}: \hspacein \to \hspaceout \}_{k\in \K}$ satisfying:

\begin{itemize}

\item \textbf{Wasserstein Approximation of Haar randomness.}  There
exist $\epsilon, \delta, \delta' = \negl{\secpar}$ such that for any $\ket{\phi}\in\Sin$,

\begin{itemize}
\item The family of states $\{\SG{k}{n,m}\!\ket{\phi}\}_{k\in\K}$
forms an $\epsilon$-net of $\Sout$.

\item Let $\nu$ be the distribution of $\SG{k}{n,m}\!\ket{\phi}$
with uniformly random $k \gets \K$, and $\mu$ be the Haar
measure on $\Sout$.  Then, there exists a distribution
$\widetilde{\nu}$ such that

\[
\tv{\mu-\tilde{\nu}}\leq \delta, \quad \text{and} \quad
W_{\infty}(\tensorsrss, \widetilde{\nu}) \le \delta' .\]

\end{itemize}

\item \textbf{Uniformity}. $\scram^{n,m}$ can be uniformly computed in
polynomial time. That is, there is a deterministic Turing machine
that, on input $(1^{\dimin}, 1^{\dimout},1^\secpar,1^\klen)$,
outputs a quantum circuit $Q$ in
$\poly{\dimin,\dimout,\secpar,\klen}$ time such that for all
$k\in \K$ and $\ket{\phi}\in\Sin$
\[ Q\ket{k}\!\ket{\phi} = \ket{k}\!\ket{\phi_k}\, , \] where
$\ket{\phi_k} := \SG{k}{n,m,\secpar}\! \ket{\phi}$.
\end{itemize}
\end{definition}

In particular, small Wasserstein distance
implies small trace distance between the average states drawn from the
two distributions.

%\paragraph{Strong Random State Scrambler implies Random State Scrambler.}

\begin{proposition}
A \srss~is an \rss~with the same parameters.
\end{proposition}
\begin{proof}
It suffices to prove that Wasserstein approximation of Haar
randomness implies statistical pseudorandomness. Let $\nu$ and $\mu$
be the distribution of the output states of a \srss~and the Haar
measure, respectively. By the assumption, there exists a
distribution $\widetilde{\nu}$ on $\Sout$ and a coupling $\gamma$ of
$\nu$ and $\widetilde{\nu}$ such that
\[\prob{(\ket{\psi},\ket{\psi'})\sim\gamma}{\norm{\ket{\psi}-\ket{\psi'}}_2}\le\negl{\secpar}.\]
Notice that $\ell$ is polynomial in $\lambda$. By the triangle inequality,
\[\td\br{\expect{\ket{\psi}\sim \nu}{ \ketbra{\psi}^{\otimes \ncopy}},
\expect{\ket{\psi}\sim \widetilde{\nu}}{ \ketbra{\psi}^{\otimes \ncopy}}}\le\negl{\secpar}.\]
By \cref{lem:h3h4}, the condition that $\tv{\mu-\widetilde{\nu}}\leq \negl{\secpar}$ implies
\[\td\br{\expect{\ket{\psi}\sim \widetilde{\nu}}{ \ketbra{\psi}^{\otimes \ncopy}},
\expect{\ket{\psi}\sim \haar}{ \ketbra{\psi}^{\otimes \ncopy}}}
\le \negl{\secpar}.\]
The result follows from the triangle inequality.
\end{proof}

By weakening the pseudorandomness condition in \srss, we define \emph{dispersing pseudorandom state scrambler} (\sprss), as the pseudorandom counterpart for \srss.

\begin{definition}[Dispersing PseudoRandom State Scrambler]
\label{def:sprss}
Let $\hspacein$ and $\hspaceout$ be Hilbert spaces of dimensions
$2^{\dimin}$ and $2^\dimout$ respectively with
$\dimin, \dimout \in\N$ and $\dimin \leq \dimout$. Let
$\K=\bit{\klen}$ be a key space, and $\secpar$ be a security
parameter. A \emph{dispersing pseudorandom state scrambler} (\sprss)
is an ensemble of isometric operators
$\SG{}{\dimin,\dimout} := \{ \SG{}{\dimin,\dimout,\secpar}
\}_\secpar$ with
$\SG{}{\dimin,\dimout,\secpar} : = \{\SG{k}{\dimin,
\dimout,\secpar}: \hspacein \to \hspaceout \}_{k\in \K}$

\begin{itemize}

\item \textbf{Computational Wasserstein Approximation of Haar
randomness.}  There exist
$\epsilon, \delta, \delta' = \negl{\secpar}$ such that for any
$\ket{\phi}\in \Sin$, there exists an $\epsilon$-net $\enet$ on
$\Sout$ and a distribution $\nu$ over $\enet$ satisfying

\begin{itemize}
\item Let $\mu$ be the Haar measure on
$\Sout$. Then, there exists a distribution $\widetilde{\nu}$
such that

\[
\tv{\mu-\tilde{\nu}}\leq \delta, \quad \text{and} \quad
W_{\infty}(\tensorsrss, \widetilde{\nu}) \le \delta' .\]

\item For any $\ncopy = \poly{\secpar}$
and any non-uniform poly-time quantum adversary $\A$,

\[\abs{\prob{k\gets \K}{\A\!\br{\ket{\phi_k}^{\otimes \ncopy
}}=1} -\prob{\ket{\psi}\gets
\nu}{\A\!\br{\ket{\psi}^{\otimes \ncopy}}=1}} =
\negl{\secpar}\, ,\]

where $\ket{\phi_k} := \SG{k}{n,m,\secpar} \ket{\phi}$ and
$\ket{\psi} $ is sampled from the distribution $\nu$.

\end{itemize}

\item \textbf{Uniformity}. $\scram^{n,m}$ can be uniformly computed in
polynomial time. That is, there is a deterministic Turing machine
that, on input $(1^{\dimin}, 1^{\dimout},1^\secpar,1^\klen)$,
outputs a quantum circuit $Q$ in
$\poly{\dimin,\dimout,\secpar,\klen}$ time such that for all
$k\in \K$ and $\ket{\phi}\in\Sin$
\[ Q\ket{k}\!\ket{\phi} = \ket{k}\!\ket{\phi_k}\, , \] where
$\ket{\phi_k} := \SG{k}{n,m,\secpar}\! \ket{\phi}$.

\item \textbf{Polynomially-bounded key length}.
$\klen = \log |\K| = \poly{\dimout,\secpar}$. As a result,
$\SG{}{\dimin,\dimout}$ can be computed efficiently in time
\end{itemize}
\end{definition}

Moreover, we introduce a continuous version of random state scrambler, where continuous randomness is allowed.

\begin{definition}[Continuously Random State Scrambler]
\label{def:ctrss}

Let $\hspacein$ and $\hspaceout$ be Hilbert spaces of dimensions
$2^{\dimin}$ and $2^\dimout$ respectively with
$\dimin, \dimout \in\N$ and $\dimin \leq \dimout$. Let $\K$ be a
(continuous) key space, and $\secpar$ be a security parameter. A
\emph{continuously random state scrambler} (\csrss) is an ensemble
of isometric operators
$\SG{}{\dimin,\dimout} := \{ \SG{}{\dimin,\dimout,\secpar}
\}_\secpar$ with
$\SG{}{\dimin,\dimout,\secpar} : = \{\SG{k}{\dimin,
\dimout,\secpar}: \hspacein \to \hspaceout \}_{k\in \K}$ satisfying:

\begin{itemize}

\item \textbf{Total-Variation Approximation of Haar randomness.} Let $\ket{\phi}\in\Sin$ be an arbitrary pure state. Let
$\tensorsrss$ be the distribution of $ \SG{k}{n,m,\secpar}\ket{\phi}$ with uniformly
random $k\gets \K$, and $\mu$ be the Haar measure on $\Sout$. Then
there exists $\delta = \negl{\secpar}$ such that the total
variation distance between $\nu$ and $\mu$ is at most $\delta$,
i.e., $\norm{\nu-\mu}_{\mathrm{TV}}\leq \delta$.
\end{itemize}

\end{definition}

\subsection{Total Variation Mixing Time of the Parallel Kac's Walk}
\label{sec:tvmixing}

We assume $n=2m$ for some $m\in\N$ throughout this section.

\subsubsection{Background: Two-Phase Proof Strategy in [37]}
It is proved in [37] that the total variation mixing time
of Kac's walk on $\SR^{n}$ is $\Theta\!\br{n\log n}$.

\begin{theorem}[Theorem 1, [37]]
Let $\st{X_t\in\SR^{n}}_{t\geq 0}$
be a Markov chain that evolves
according to Kac's walk.
Then, for sufficiently large $n$, and $T > 200 n \log n$,
\sup_{X_0\in \SR^n}\! \norm{\mathcal{L}\!\br{X_{T}}-\mu}_{\mathrm{TV}} = O\!\br{\frac{1}{\poly{n}}}\enspace,
where $\mu$ is the normalized Haar measure on $\SR^n$.
\end{theorem}

We informally revisit their proof approach that
utilizes the famous coupling lemma
(see \lem{coupling_lemma}).
The coupling lemma offers a practical approach to estimate
the mixing time of a Markov chain by comparing the behavior
of two coupled random walks.
The total variation distance at time $T$ is bounded by
the probability that two coupled random walks are distinct at time $T$.
Through a two-phase coupling of
$\st{X_t}_{t\geq 0}$ and $\st{Y_t}_{t\geq 0}$,
they show that the probability that two copies are not equal at time $T$,
i.e., $\Pr\!\Br{X_T\neq Y_T}$, approaches zero when $n$ is sufficiently large and $T > 200 n \log n$.
Specifically, the two-step coupling consists of
an initial \emph{contracting phase}
followed by a subsequent \emph{coalescing phase}.
%\sout{This two-step approach is widely employed to establish the convergence
%of Metropolis-Hastings chains operating on continuous state spaces.}
The contracting phase aims to sufficiently reduce the distance
between two copies of Kac's walk
so that during the coalescing phase, they can be
further fine-tuned to coalesce.
These two phases are described below, with a focus on
how the random angles are coupled.

\textbf{Contracting Phase (from $t=0$ to $T_0$).}
The contracting phase starts from time $0$
and continues until time $T_0$.
In this phase,
$\st{X_t}$ and $\st{Y_t}$ undergo the \emph{proportional coupling}.
which aims at reducing the distance
between two copies of Kac's walk.
The proportional coupling is introduced in \sect{kac}.

\textbf{Coalescing Phase (from $t = T_0$ to $T_0+T_1$).}
This phase employs a non-Markovian coupling\footnote{
The non-Markovian coupling refers to a situation
where the transition between states depend
not only on the current state but also on the future states,
violating the memoryless property of a standard Markov process.}
starting from a close-by pair $X_{T_0}$ and $Y_{T_0}$.
Let $T_1$ be determined later.
the coupling independently and identically samples $T_1$ pairs of coordinates
$\st{\br{i_t,j_t}}_{t=T_0}^{T_0+T_1-1}$ all at once,
which are subsequently used to generate $T_1+1$ partitions of $[n]$,
denoted by $\set{\PP_t}_{t=T_0}^{T_0+T_1}$.
The construction of these partitions is done inductively in reverse order.
The last partition is enforced to be
$\PP_{T_0+T_1} = \{\{1\}, \{2\}, \ldots, \{n\}\}$.
Starting from $t=T_1+T_0-1$ and decrementing down to $T_0$,
the construction of partition $\PP_{t}$ uses the
chosen coordinate pair $(i_t,j_t)$ as a guide.
Specifically, it is generated by merging two sets in $\PP_{t+1}$:
one set includes $i_t$, and the other includes $j_t$;
while leaving other sets untouched.
Then, the value of $T_1$ is determined such that $\PP_{T_0}=\set{[n]}$ with high probability.

The aim of this phase is to ultimately coalesce $X$ and $Y$.
To see how to achieve this, we introduct the event $\A_t$ in which, at time $t$,
\sum_{i\in S} X_t [i]^2 = \sum_{i\in S} Y_t [i]^2,\quad \forall S\in \PP_{t}\enspace
\[X_t[k]Y_t[k]\geq0,\quad k\in\set{i_{t-1},j_{t-1}}.\]
Intuitively, event $\A_t$ states that if we partition $X_t$ and $Y_t$ based on $\PP_{t}$,
then both $X_t$ and $Y_t$ carry equal significance
within each segment $S$ at time $t$;
and meanwhile the corresponding updated subvectors share the same sign at time $t-1$.
It is not hard to verify that
$\A_{T_0}$ occurs if $\PP_{T_0} = \st{\st{1,\cdots,n}}$, which holds with high probability;
$\cap_{t=T_0}^{T_0+T_1}\A_{t}$ implies that the corresponding entries
in vectors $X_{T_0+T_1}$ and $Y_{T_0+T_1}$ are equal.
Thus, to prove that $X$ and $Y$ are identical by the end of this phase, it suffices to prove that all events occur with a high probability during the process.

the non-Markovian coupling aims to ensure that
$\A_{t+1}$ takes place with a high probability,
conditioned on all previous events occur.
This is achieved by sampling $\theta$ and $\theta'$ from a ``good'' joint distribution,
which makes sure that both marginal distributions are uniformly distributed on $[0,2\pi)$.
Such a desirable distribution is made possible by the entry-wise closeness achieved during the first phase.

Intuitively, the parallel Kac's walk is expected
to have a mixing time that is only on the order of $O(\log n)$,
saving factor of $n$ in the
mixing time of the original Kac's walk.
%However, the $n/2$ pairs being rotated in the parallel Kac's walk are distinct, and thus not independent.
%By the birthday paradox, this occurs in a classical Kac's walk with exponentially small probability.
However, the mixing time for the parallel Kac's walk cannot be derived from the mixing time for the original Kac's walk, directly.
Fortunately, through careful modifications to the two-phase coupling approach above, we have discovered a logarithmic mixing time for the parallel Kac's walk, resulting in exponential speedup compared to the original random walk.

\subsubsection{Real Case}
The total variation distance
between the output distribution of
a parallel Kac's walk after $T$ steps
and the normalized Haar measure on $\SR^n$
decays exponentially as $T$ grows. Formally,

\begin{theorem}\label{thm:mixing_time}
Let $\st{X_t\in\SR^{n}}_{t\geq 0}$
be a Markov chain that evolves
according to the parallel Kac's walk.
Then, for sufficiently large $n$, $c>515$ and $T = c\log n$,
\sup_{X_0\in \SR^n}\! \norm{\mathcal{L}\!\br{X_{T}}-\mu}_{\mathrm{TV}} \leq  \frac{1}{2^{\br{c/515-1}\log n-1}}\enspace,
where $\mu$ is the normalized Haar measure on $\SR^n$.
\end{theorem}

To prove \thm{mixing_time}, we will use the coupling lemma
(see \lem{coupling_lemma})
and extend the two-phase coupling method described in [37]
to accommodate parallel Kac's walks.
We have already extended the proportional coupling
used in the contracting phase in \sect{propc}.
We now introduce the non-Markovian coupling
employed in the coalescing phase to ensure that
$X$ and $Y$ converge to an identical state,
and integrate these two couplings into
a comprehensive two-phase coupling
to establish the mixing time of the parallel Kac's walk.

\paragraph{Coalescing Phase: the Non-Markovian Coupling}
The non-markovian coupling is defined in \defi{non_mark_cpl}.
As we will see later,
if the initial vectors of two parallel Kac's walks,
namely $X_{T_0}$ and $Y_{T_0}$,
are close,
this coupling guarantees
a high probability of
collision between $X_T$ and $Y_T$,
when $T$ is sufficiently large.

\begin{definition}[Non-Markovian Coupling]\label{def:non_mark_cpl}
Fix $T_0\leq T\in\N$. We couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ in the following way:
\begin{enumerate}
\item For each $T_0\leq t < T$, choose a perfect matching $P_t = \st{\br{i^{(t)}_1, j^{(t)}_1},\dots,\br{i^{(t)}_m, j^{(t)}_m}}$ uniformly at random.

\item Set $\PP_{T,1} = \st{\st{1},\dots,\st{n}}$, and define a sequence of partitions $\st{\PP_{t,k}}_{T_0\leq t<T,~ 1\leq k\leq m+1}$ of $[n]$ inductively by the process:
\begin{enumerate}
\item If $k=m+1$, let $\PP_{t,k}=\PP_{t+1,1}$.
\item If $1\leq k\leq m$, write $\PP_{t,k+1}=\st{S_1(t,k+1),\dots, S_{l_{t,k+1}}(t,k+1)}$ with $S_r(t,k+1)\subseteq [n]$ for $1\leq r\leq l_{t,k+1}$. Let $u_{t,k},~ v_{t,k}$ be the indices such that
$$i^{(t)}_{k}\in S_{u_{t,k}}(t,k+1)\quad \text{and}\quad j^{(t)}_{k}\in S_{v_{t,k}}(t,k+1)\enspace.$$
\begin{enumerate}
\item If $u_{t,k}= v_{t,k}$, set $\PP_{t,k}=\PP_{t,k+1}$.
\item If $u_{t,k}\neq v_{t,k}$, construct $\PP_{t,k}$ by merging $S_{u_{t,k}}(t,k+1)$ and $S_{v_{t,k}}(t,k+1)$ in $\PP_{t,k+1}$.
\end{enumerate}
\end{enumerate}

\item If $\PP_{T_0,1}=\st{[n]}$, we couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ in the following way:
\begin{itemize}
\item Define the set
\begin{equation}\label{eq:H}
H=\st{(t,k):T_0\leq t<T,~1\leq k\leq m,~\PP_{t,k}\neq\PP_{t,k+1}} \enspace.
\end{equation}

\item Fix $T_0\leq t<T$, $X_{t}$ and $Y_{t}$, and we couple $X_{t+1}$ and $Y_{t+1}$ in the following way:
\begin{enumerate}
\item Set $X_{t,1}=X_t$ and $Y_{t,1}=Y_t$.
\item For $1\leq k\leq m$,
\begin{enumerate}
\item If $(t,k)\notin H$, uniformly choose $\agl{t}{k}\in[0,2\pi)$. Let $$X_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},\agl{t}{k},X_{t,k})\quad\text{and}\quad Y_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},{\aglp{t}{k}},Y_{t,k})$$ where $G(\cdot)$ is defined in \cref{eq:kaconestep} and ${\aglp{t}{k}}$ is obtained in the same way as the proportional coupling defined in \defi{prop_cpl}.

\item If $(t,k)\in H$, let $\theta_0$ be the angle satisfies
$\theta_0'$ be the angle satisfies
and then choose the best distribution $\nu$ among all joint distributions on $[0,2\pi)\times [0,2\pi)$ with both marginal distributions uniformly distributed on $[0,2\pi)$ which maximizes the probability of the following events when $(\theta,\theta')\sim\nu$:
\begin{align*}
\sum_{i\in S_{r}(t,k+1)} X_{t,k+1} [i]^2 &= \sum_{i\in S_{r}(t,k+1)} Y_{t,k+1} [i]^2\enspace, \enspace1\leq r\leq l_{t,k+1}\\
X_{t,k+1} [i]\cdot Y_{t,k+1}[i]&\geq 0\enspace, \enspace i\in\st{i_{k}^{(t)},j_{k}^{(t)}}\enspace,
\end{align*}
$$X_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},\theta-\theta_0,X_{t,k})\quad\text{and}\quad Y_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},\theta'-\theta_0',Y_{t,k})\enspace.$$
Then choose $(\agl{t}{k},{\aglp{t}{k}})\sim \nu$, and set
$$X_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},\agl{t}{k}-\theta_0,X_{t,k})\quad\text{and}\quad Y_{t,k+1} = G(i_{k}^{(t)},j_{k}^{(t)},{\aglp{t}{k}}-\theta_0',Y_{t,k})\enspace.$$
\end{enumerate}
\item Set $X_{t+1} = X_{t,m+1}$ and $Y_{t+1} = Y_{t,m+1}$.
\end{enumerate}
\end{itemize}

\item If $\PP_{T_0,1}\neq \st{[n]}$, for $T_0\leq t\leq T$, we couple $X_{t+1}$ and $Y_{t+1}$ in the following way: choose $m$ independent angles $\agl{t}{1},\dots,\agl{t}{m}\in [0,2\pi)$ uniformly at random and set
$$X_{t+1}=F\br{P_t,\agl{t}{1},\dots,\agl{t}{m},X_t}\quad \text{and}\quad Y_{t+1}=F\br{P_t,\agl{t}{1},\dots,\agl{t}{m},Y_t}\enspace,$$
where $F(\cdot)$ is given in \cref{eq:F}.
\end{enumerate}
\end{definition}

Step 1 samples $T-T_0$ matchings,
generating all coordinate pairs
that will be updated in the succeeding process.
Step 2 utilizes this matchings to construct a series of partitions of $[n]$ in a back propagation manner.
Starting from $\PP_{T,1} = \st{ \st{1},\dots,\st{n} }$,
it sequentially construct
$$\PP_{T-1,m+1} \enspace
\enspace\PP_{T-1,m}\enspace \enspace\cdots\enspace
\enspace\PP_{T-1,1}\enspace
\enspace\PP_{T-2,m+1}\enspace \enspace\cdots\enspace
\enspace\PP_{T-2,1}\enspace \enspace\cdots\enspace
\enspace\PP_{T_0,1}\enspace.$$
$\PP_{t,m+1}$ is set equal to $\PP_{t+1,1}$ directly.
For $1\leq k\leq m$, $\PP_{t,k}$ is obtained based on $\PP_{t,k+1}$
and the $k$-th pair of coordinates in matching $P_t$.
If two coordinates of the $k$-th pair
belong to different components in partition $\PP_{t,k+1}$,
we merge these two components.
Otherwise, $\PP_{t,k}$ is set equal to $\PP_{t,k+1}$.
This series of partitions thus consists of random partitions of set $[n]$
and with high probability the first partition $\PP_{T_0,1}$
is $\st{[n]}$ (see \lem{good_start}). This follows from the argument for bounding the probability of the
connectivity of Erd\"os-R\'enyi graphs~\cite[Theorem
7.3]{Bollobas01}. The proof is deferred to \app{deferred proofs}.

\begin{lemma}\label{lem:good_start}
Fix $c>0$ and $T_0\in\N$. Let $l=5(1+c)\log n$ and $T=T_0+l$.	Then we have for $n$ sufficiently large,
\Pr\!\Br{\PP_{T_0,1}\neq\st{[n]}} \leq 2n^{-c}\enspace,
where $\PP_{T_0,1}$ is defined in \defi{non_mark_cpl}.
\end{lemma}

If $\PP_{T_0,1} = \st{[n]}$,
step 3 serves as the crucial step of
this coupling.
To provide a clearer explanation of how this coupling technique works,
\defi{AT1} introduces a series of events $\st{\A(t,k)}$.
Intuitively, $\A(t,k)$ indicates that
the $(k-1)$-th updated coordinates in both vectors have the same signs at time $t$,
both vectors have the same weight within each component of the partition $\PP_{t,k}$.

\begin{definition}\label{def:AT1}
Let $\A(T_0,1)$ denote the event
\begin{align*}
\sum_{i\in S_{r}(T_0,1)} X_{T_0,1} [i]^2 &= \sum_{i\in S_{r}(T_0,1)} Y_{T_0,1} [i]^2, 1\leq r\leq l_{T_0,1}\enspace.
\end{align*}
For other $T_0\leq t \leq T$ and
$1\leq k \leq m+1$,
we define the event $\A(t,k)$ as
\footnote{In Eq.~\eq{cond2}, if $k=1$, then $i\in\st{ i_{m}^{(t-1)},j_{m}^{(t-1)} }$.}
\begin{align}
\sum_{i\in S_{r}(t,k)} X_{t,k} [i]^2 &= \sum_{i\in S_{r}(t,k)} Y_{t,k} [i]^2\enspace, \enspace1\leq r\leq l_{t,k}\label{eq:cond1}\\
X_{t,k} [i]\cdot Y_{t,k}[i]&\geq 0\enspace, \enspace i\in\st{i_{k-1}^{(t)},j_{k-1}^{(t)}}
\enspace. \label{eq:cond2}
\end{align}
\end{definition}

It is worthy noting that under the assumption $\PP_{T_0,1} = \st{[n]}$,
$\A(T_0,1)$ occurs since the sum of squares of the components of a unit vector is equal to $1$.
And if $\{\A(t,k)\}$ take place in the entire process,
we can conclude that $X_T = Y_T$ because
$\A(T,1)$ guarantees the corresponding coordinates have the same absolute values
and \rmk{sign} together with \eq{cond2} guarantees that they have the same signs as well.
So we want to couple the rotation angles to ensure that
$\A(t,k+1)$ occurs with a high probability,
given that all previous events have already taken place.
The coupling of the rotation angles are divided into two cases:
whether the coordinate pair $\br{i^{(t)}_k, j^{(t)}_k}$ is a “merge point” in the construction process of partitions.
If not, the rotation angles are coupled using the proportional coupling (see step 3.b.i).
For non-“merge point”,
the proportional coupling does not affect the partition
and also maintain the weight within each component,
and thus $\A(t,k+1)$ must occur conditioned on $\A(t,k)$.
In the other case, we sample the rotation angles from a “good” joint distribution which maximizes the probability that $\A(t,k+1)$ occurs (see step 3.b.ii).

We next show why such a “good” joint distribution exists.
Before that, we set some notations.
For $T_0\leq t \leq T$ and $1\leq k \leq m+1$, define
\begin{align}\label{eqn:Atk}
A_{t,k}[i] = X_{t,k}[i]^2\enspace,\quad B_{t,k}[i] = Y_{t,k}[i]^2\enspace.
\end{align}
For $T_0\leq t_1,t_2\leq T$ and
$1\leq k_1,k_2\leq m+1$,
we define a partial order
$\sqsubseteq$ as
(t_1,k_1)\sqsubseteq (t_2,k_2)\quad \text{iff} \quad
\br{t_1<t_2} \vee \br{t_1=t_2 \wedge k_1\leq k_2 }\enspace.
Note that if $\br{i^{(t)}_k, j^{(t)}_k}$ is a “merge point”,
$\PP_{t,k+1}$ differs from $\PP_{t,k}$ only in
the components in which $i^{(t)}_k$ and $ j^{(t)}_k$ are,
namely $S_{u_{t,k}}(t,k+1)$ and $S_{v_{t,k}}(t,k+1)$.
To see whether $\A(t,k+1)$ occurs given $\A(t,k)$, we only need to check
whether \eq{cond1} holds for $r = u_{t,k}$, that is,
\sum_{i\in S_{u_{t,k}}(t,k+1)} X_{t,k} [i]^2
= \sum_{i\in S_{u_{t,k}}(t,k+1)} Y_{t,k} [i]^2\enspace.
A=\sum_{i\in S_{u_{t,k}}(t,k+1)\backslash i^{(t)}_k} X_{t,k}[i]^2\enspace,
\quad \quad
B=X_{t,k} [i^{(t)}_k]^2+X_{t,k} [j^{(t)}_k]^2\enspace,
C=\sum_{i\in S_{u_{t,k}}(t,k+1)\backslash i^{(t)}_k} Y_{t,k}[i]^2
\enspace,\quad \quad
We will have
\sum_{i\in S_{u_{t,k}}(t,k+1)} X_{t,k} [i]^2  = A + B\cos({\agl{t}{k}})^2
\enspace,\quad \quad
\sum_{i\in S_{u_{t,k}}(t,k+1)} Y_{t,k} [i]^2 = C + D\cos({\aglp{t}{k}})^2\enspace.
The following lemma states that $\abs{A-C}$ and $\abs{B-D}$ are bounded by the initial distance of two vectors. Its proof is the same as Lemma 4.4 in [37].
\begin{lemma}
\label{lem:never_drift}
Fix $T_0<T$, and couple two chains $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ using the non-Markovian coupling defined in \defi{non_mark_cpl}.
Fix $T_0\leq t_0 \leq T$ and $1\leq k_0 \leq m+1$.
Then, on the event $\bigcap _{(t,k)\sqsubseteq (t_0,k_0)}\A(t,k)\cap\st{\PP_{T_0,1}=\st{[n]}}$, we have
\norm{A_{t,k}-B_{t,k}}_{1,S}\leq \norm{A_{T_0,1}-B_{T_0,1}}_{1}
for all $(t,k)\sqsubseteq(t_0,k_0)$
%such that $T_0\leq t\leq t$
and $S\in\PP_{t,k}$.
Moreover, for all $(t,k)\sqsubseteq(t_0,k_0)$
%such that $T_0\leq t\leq t_0$
\norm{A_{t,k}-B_{t,k}}_{1}\leq n\norm{A_{T_0,1}-B_{T_0,1}}_{1}\enspace.
\end{lemma}

Knowing that $A,B$ and $C,D$ are close,
the following lemma states the existence of a good distribution $\nu$ for ${\agl{t}{k}}$ and ${\aglp{t}{k}}$ such that
$\sum_{i\in S_{u_{t,k}}(t,k+1)} X_{t,k} [i]^2
$ agrees with $\sum_{i\in S_{u_{t,k}}(t,k+1)} Y_{t,k} [i]^2$ with high probability.

\begin{lemma}[Lemma 4.6 in [37]] \label{lem:good_dist}
Fix positive reals $1<p<q'<q/2$. Let $\theta,\theta'\sim\mathrm{Unif}[0,2\pi)$ and let
S=A+B\cos(\theta)^2 \quad\text{ and }
\quad S'=C+D\cos(\theta')^2
for some $0\leq A,B,C,D\leq 1$ that satisfy
\abs{A-C},\abs{B-D}\leq n^{-q}\quad \text {and}\quad B,D\geq n^{-p}\enspace.
Then for sufficiently large $n$, there exists a coupling of $\theta,\theta'$ so that
\Pr\!\Br{S=S'}\geq 1-6\times 10^3n^{-c}
\cos(\theta)\cos(\theta')\geq 0 \quad\text{ and } \quad
\sin(\theta)\sin(\theta')\geq 0
where $c=\min\br{\frac{q'}{2},q-2q'}>0$.
\end{lemma}

\paragraph{Proof of the Total Variation Mixing Time}
\begin{proof}[Proof of \thm{mixing_time}]
Let $a=66,~b=24,~ T_0=500\log n, ~ T_1=15\log n,~ T=T_0+T_1 = 515\log n$. We construct a coupling of two copies $\st{X_t}_{t\geq 0}$ and $\st{Y_t}_{t\geq 0}$ of the parallel Kac's walk with starting points $X_0=x\in \SR^n$ and $Y_0\sim \mu$. The coupling is as follows:
\begin{enumerate}
\item couple $\st{X_t}_{0\leq t\leq T_0}, \st{Y_t}_{0\leq t\leq T_0}$ by using the proportional coupling defined in \defi{prop_cpl},
\item couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ by using the non-Markovian coupling defined in \defi{non_mark_cpl}.
\end{enumerate}
Define the events
\begin{align*}
\EE_1 &= \st{\norm{A_{T_0}-B_{T_0}}_1\geq n^{-a}}\enspace,\\
\EE_2 &= \st{\PP_{T_0,1}\neq \st{\st{1,\dots,n}}}\enspace,\\
\EE_3 &= \st{X_{T}\neq Y_{T}}\enspace.
\end{align*}
By \lem{coupling_lemma},
\begin{align}
\sup_{X_0\in \SR^n} \norm{\mathcal{L}\!\br{X_{T}}-\mu}_{\mathrm{TV}}
\leq \sup_{X_0\in \SR^n}\Pr\!\Br{\EE_3}\leq \sup_{X_0\in \SR^n}
\br{\Pr\!\Br{\EE_1}+\Pr\!\Br{\EE_2}+\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}}\enspace.\label{eq:tv}
\end{align}
By Markov's inequality, we have
\begin{align}
\Pr\!\Br{\EE_1} &= \Pr\!\Br{\norm{A_{T_0}-B_{T_0}}_1\geq n^{-a}}\nonumber\\
&\leq \Pr\!\Br{\norm{A_{T_0}-B_{T_0}}_2\geq n^{-a-1/2}}\nonumber\\
\text{(\lem{contraction_lemma})}&\leq n^{2a+1}\cdot2\cdot\br{\frac{3}{4}}^{T_0}\leq \frac{1}{n^2}\enspace. \label{eq:event1}
\end{align}
Moreover, by \lem{good_start}, we have
\begin{align}
\Pr\!\Br{\EE_2}\leq 2n^{-2}\enspace.\label{eq:event2}
\end{align}
In order to bound $\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}$,
recall the definition of $\A(t,k)$ in \defi{AT1}.
It is evident that $\bigcap_{(t,k)\sqsubseteq (T,1)}\A(t,k)$ implies $\EE_3^c$. Thus, $\EE_3\cap \EE_1^c \cap \EE_2^c$ implies $\bigcup_{(t,k)\sqsubseteq (T,1)}\A(t,k)^c \cap \EE_1^c \cap \EE_2^c$. So, we have
\begin{align}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}
\Pr\!\Br{\bigcup_{(t,k)\sqsubseteq (T,1)}\A(t,k)^c \cap \EE_1^c \cap \EE_2^c} \nonumber\\
\sum_{t=T_0}^{T-1} \sum_{k=1}^{m} \Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \EE_1^c \cap \EE_2^c}\nonumber\\
&\quad \quad + \Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c}\enspace.\label{eq:e3}
\end{align}
Notice that if $\EE_2^c$ happens, we have
\sum_{i\in [n]} X_{T_0,1} [i]^2 = \sum_{i\in [n]} Y_{T_0,1} [i]^2 = 1\enspace,\\
and the proportional coupling forces $X_{T_0,1} [i]\cdot Y_{T_0,1} [i] = X_{T_0} [i]\cdot Y_{T_0} [i]\geq 0$ for all $1\leq i\leq n$.
Therefore, $A(T_0,1)$ must occur, i.e.,
\begin{align}
\Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c}=0\enspace.\label{eq:imps}
\end{align}
Combining \eq{e3} and \eq{imps}, we have
\begin{equation}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}\leq
\sum_{t=T_0}^{T-1} \sum_{k=1}^{m} \Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \EE_1^c \cap \EE_2^c}	\enspace.\label{eq:e3final}
\end{equation}

We are now left to find a upper bound for $\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \EE_1^c \cap \EE_2^c}$ when $T_0\leq t\leq T-1$ and $1\leq k\leq m$. To this end, we define
\B(t,k) = \st{\min_{(t',k')\sqsubseteq (t,k):t'\leq t}\min_{1\leq i\leq n} Y_{t',k'}[i]^2\geq n^{-b}}\enspace.
Note that
\begin{align}\label{eq:e3single}
&\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \EE_1^c \cap \EE_2^c}\nonumber\\
\leq &\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} + \Pr\!\Br{\B(t,k)^c}\enspace.
\end{align}
By \lem{marg_of_haar} and a union bound over all $(t',k')$ such that $(t',k')\sqsubseteq (t,k)$ and $t'\leq t$, we have for sufficiently large $n$,
\begin{equation}\label{eq:e3single2}
\Pr\!\Br{\B(t,k)^c} \leq 15n^{3-\frac{b}{3}}\log(n)\enspace.
\end{equation}

Next, we consider two cases of the term
$$\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c}$$
in \eq{e3single}: $(t,k)\notin H$ and $(t,k)\in H$,
where $H$ is defined in \defi{non_mark_cpl}.
In the case that $(t,k)\notin H$, we have $\PP_{t,k} = \PP_{t,k+1}$ and we apply the proportional coupling. Thus
$\A(t,k)$ implies $\A(t,k+1)$ which means
\begin{align}\label{eq:e3single11}
\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c}=0\enspace.
\end{align}

In the other case that $(t,k)\in H$,
A=\sum_{i\in S_{u_{t,k}}(t,k+1)\backslash i^{(t)}_k} X_{t,k}[i]^2\enspace,
\quad \quad
B=X_{t,k} [i^{(t)}_k]^2+X_{t,k} [j^{(t)}_k]^2\enspace,
C=\sum_{i\in S_{u_{t,k}}(t,k+1)\backslash i^{(t)}_k} Y_{t,k}[i]^2
\enspace,\quad \quad
S = A + B\cos({\agl{t}{k}})^2
\enspace,\quad \quad
S'= C + D\cos({\aglp{t}{k}})^2\enspace.
On the event $\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k') \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c$, we have by \lem{never_drift}
\begin{align*}
\abs{A-C} \leq \norm{A_{t,k}-B_{t,k}}_1\leq n\norm{A_{T_0}-B_{T_0}}_1 \leq n^{1-a}\enspace.
\end{align*}
\begin{align*}
\abs{B-D} \leq \norm{A_{t,k}-B_{t,k}}_1\leq n\norm{A_{T_0}-B_{T_0}}_1 \leq n^{1-a}\enspace.
\end{align*}
Moreover, $D\geq n^{-b}$ and $B\geq D-\abs{B-D}\geq n^{-b}$ for sufficiently large $n$.
Then apply \lem{good_dist} with $p=b,~ q=a-1$ and $q'=\frac{2(a-1)}{5}$, we know there exists a distribution $\nu_0$ such that when $({\agl{t}{k}},{\aglp{t}{k}})\sim \nu_0$, we have
\cos({\agl{t}{k}})\cos({\aglp{t}{k}})\geq 0 \quad\text{ and }\quad
\sin({\agl{t}{k}})\sin({\aglp{t}{k}})\geq 0
\Pr_{({\agl{t}{k}},{\aglp{t}{k}})\sim \nu_0}
\Br{ S\neq S' | \bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k') \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \leq 6\times 10^3n^{-\frac{a-1}{5}}\enspace.
We choose the best distribution which maximizes the probability of event described in \eq{cond1} and \eq{cond2}, so
\begin{align} \label{eq:e3single12}
&\Pr\!\Br{\A(t,k+1)^c \cap \br{\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k')} \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber\\
\leq  &\Pr\!\Br{\left.\A(t,k+1)^c \right|\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k') \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber\\
\leq &\Pr_{({\agl{t}{k}},{\aglp{t}{k}})\sim \nu_0}\Br{\left.\A(t,k+1)^c \right|\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k') \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber \\
= &\Pr_{({\agl{t}{k}},{\aglp{t}{k}})\sim \nu_0}\Br{\left.S\neq S' \right|\bigcap_{(t',k')\sqsubseteq (t,k)}\A(t',k') \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \leq 6\times 10^3n^{-\frac{a-1}{5}}\enspace.
\end{align}

Combining \eq{e3final}, \eq{e3single}, \eq{e3single2}, \eq{e3single11} and \eq{e3single12}, we have for sufficiently large $n$
\begin{align} \label{eq:event3}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}\leq \sum_{t=T_0}^{T-1} \sum_{k=1}^{m} 6\times 10^3n^{-\frac{a-1}{5}} + 15n^{3-\frac{b}{3}}\log(n) \leq   \frac{1}{n^2}\enspace.
\end{align}

By \eq{tv}, \eq{event1}, \eq{event2} and \eq{event3}, we have for sufficiently large $n$ and $T=515\log n$
\begin{align*}
\sup_{X_0\in \SR^n} \norm{\mathcal{L}\br{X_{T}}-\mu}_{\mathrm{TV}} \leq \sup_{X_0\in \SR^n}\Pr\!\Br{\EE_3} \leq  \frac{1}{2n} \enspace.
\end{align*}

As for $T= c \log n$ where $c > 515$,
by \lem{fcts_tv}
we have
\begin{align*}
\sup_{X_0\in \SR^n} \norm{\mathcal{L}\br{X_{T}}-\mu}_{\mathrm{TV}}\leq 2\br{\frac{1}{n}}^{\lint{\frac{T}{515\log n}}} \leq  \frac{1}{2^{\br{c/515-1}\log n - 1}}\enspace.
\end{align*}

\end{proof}

\subsubsection{Complex Case}
The output distribution of
the parallel Kac's walk on complex vectors
after $T$ steps
approaches the Haar measure
on the complex unit sphere of $\C^n$
exponentially fast as $T$ grows.
\begin{theorem}\label{thm:mixing_time_c}
Let $\st{X_t\in\SC^{n}}_{t\geq 0}$
be a Markov chain that evolves
according to the parallel Kac's walk
on complex vectors.
Then, for sufficiently large $n$, $c>515$ and $T = c\log n$,
\sup_{X_0\in \SC^n}\! \norm{\mathcal{L}\!\br{X_{T}}-\mu}_{\mathrm{TV}} \leq  \frac{1}{2^{\br{c/515-1}\log n-1}}\enspace,
where $\mu_{\C}$ is the Haar measure on $\SC^{n}$.
\end{theorem}

We defer the complete proof to \app{deferred proofs},
as it is similar to the proof of \thm{mixing_time}.

\subsection{Construction of \srss~and \sprss}
\label{sec:provedrss}
%\sect{const1} demonstrates the construction of two ensembles of unitary operators,
%which are \rss s over real space and complex space respectively.
%These ensembles are able to scramble an arbitrary state to a random state that is close to Haar random state in terms of trace distance.
%In fact, they possess a stronger property which we call \emph{Wasserstein Approximation of Haar randomness} (see \defi{trssb}), compared to the \emph{Statistical Pseudorandomness} (see \defi{rssb}).

\subsubsection{Real Case}
The following theorem proves that the \rss~we construct over real space is also a \srss.

\begin{theorem}\label{thm:kactosrss}
Let $n\in\N$, $d = \log^2\!\secpar+\log^2\!n$ and $T = 515 (\secpar + 1) n$.
The ensemble of unitary operators
$\enssrsscons$ defined in \defi{kactorss}
is a \srss.
\end{theorem}

To prove \cref{thm:kactosrss}, recall the ensemble of unitary operators $\enscsrsscons \coloneq \st{\csrsscons }_{\secpar}$ we define in \sect{rss_in_real}.
We have the following proposition for $\enscsrsscons$.

\begin{proposition}
For $T = 515 (\secpar + 1) n $,
the ensemble of unitary operator $\enscsrsscons$
is a \csrss.
\end{proposition}

\begin{proof}
Note that a uniformly random
corresponds to a $T$-step parallel Kac's walk on $\SR^{2^n}$.
The proposition then follows from \thm{mixing_time} and the definition of the \csrss.
\end{proof}

Let $\ket{\eta}\in\S(\H)$ be an arbitrary real state.
\begin{equation}\label{eq:NN}
\NN = \st{\srsscons_{\rep{\sigma}{T},\rep{f}{T}}\!\!\ket{\eta}}
\enspace\enspace \text{and}\enspace\enspace
\widetilde{\NN} = \st{\csrsscons_{\rep{\sigma}{T},\rep{\cf}{T}}\!\!\ket{\eta}}\enspace.
\end{equation}
We need the following two lemmas. Both proofs are deferred to \app{deferred proofs}.

\begin{lemma}\label{lem:realNNfullmap}
$\widetilde{\NN}= \SR^{2^n}$.
\end{lemma}

\begin{lemma}\label{lem:realNNepsnet}
There exists an $\epsilon  = \negl{\secpar}$  such that $\NN$
is an $\epsilon$-net for real vectors in $\S(\H)$, where $\NN$ is defined in \cref{eq:NN}.
\end{lemma}

\begin{proof}[Proof of \cref{thm:kactosrss}]
It is easy to see that the uniformity condition is satisfied.
Let $\kappa$ denote the key length.
Quantum circuit $\srsscons$ applies $\srsscons_{\rep{\sigma}{T},\rep{f}{T}}$ after reading $\rep{\sigma}{T}$ and $\rep{f}{T}$.
To implement $\srsscons_{\rep{\sigma}{T},\rep{f}{T}}$, we need to realize each of
the $T = 515 (\secpar + 1) n$ unitary gates $K$.
Since each gate $K$ can be implemented in $\poly{n,\secpar,\klen}$ time,
the total construction time for $\srsscons_{\rep{\sigma}{T},\rep{f}{T}}$
is also $\poly{n,\secpar,\klen}$.

Combining with \cref{lem:realNNepsnet}, it suffices to prove that there exists a good distribution $\widetilde{\nu}$ satisfying the requirement in \defi{trssb}.
Fix $\ket{\eta}\in\S(\H)$. Define three distributions:
\begin{itemize}
\item $\nu$ be the distribution of
$\srsscons_{\rep{\sigma}{T}, \rep{f}{T}}\!\!\ket{\eta}$
with independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$
and random functions $\rep{f}{T}: \bit{n-1}\to\bit{d}$.
\item $\widetilde{\nu}$ be the distribution of
with independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$,
and random functions $\rep{\cf}{T} : \bit{n-1}\to[0,1)$.
\item $\mu$ be the Haar measure on $\SR^{2^n}$.
\end{itemize}
Note that $\widetilde{\nu}$ is the output distribution of $T$-step parallel Kac's walk. Thus by \thm{mixing_time}, we have
\begin{align}\label{eq:closetv}
\tv{\widetilde{\nu} - \mu} \leq \frac{1}{2^{\secpar n - 1}} = \negl{\secpar}\enspace.
\end{align}
We are left to show the Wasserstein $\infty$-distance between $\nu$ and $\widetilde{\nu}$ is negligible.
To this end, we construct a coupling $\gamma_0$ of $\nu$ and $\widetilde{\nu}$ by using the same permutation $\sigma_t$ and letting $f_t$ be the function satisfying $f_t(y)$ is the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$. Therefore
\begin{align}\label{eq:closewinfty}
W_{\infty} ( \nu, \widetilde{\nu}) =
~& \lim_{p\to\infty}\br{ \inf_{\gamma\in\Gamma(\nu,\widetilde{\nu})} \E_{(\ket{v},\ket{u})\sim \gamma}\!\Br{\norm{\ket{v}-\ket{u}}_2^p} }^{1/p} \nonumber\\
\leq ~& \lim_{p\to\infty}\br{ \E_{(\ket{v},\ket{u})\sim \gamma_0}\!\Br{\norm{\ket{v}-\ket{u}}_2^p} }^{1/p}
~\overset{\text{(Eq.~\eq{uvclose})}}{\leq} ~
\frac{1030\pi (\secpar+1)n}{\secpar^{\log \secpar}n^{\log n}}= \negl{\secpar} \enspace .
\end{align}
This completes the proof.
\end{proof}

In \sect{prss_in_real}, we substitute random permutations and random functions
utilized in $\enssrsscons$ with pseudorandom alternatives, resulting in $\enssgen$ which is proved to be a \prss. In fact, $\enssgen$ is also a \sprss.

\begin{theorem}\label{thm:realdprss}
Let $n\in\N$, $d = \log^2\!\secpar+\log^2\!n$ and $T = 515 (\secpar + 1) n$.
The ensemble of unitary operators
$\enssgen$ defined in \defi{kactoprss} is a \sprss.
\end{theorem}
\begin{proof}
It is easy to see the conditions of polynomial-bounded key length and uniformity are satisfied.
%The first item of "computationally Wasserstein approximation of Haar randomness" is also the same as in the proof of \thm{realprss}, and the second item is by \cref{thm:kactosrss}.
We now prove the condition of computational Wasserstein approximation of Haar randomness.
Let $\nu$ be the distribution of
$\srsscons_{\rep{\sigma}{T}, \rep{f}{T}}\!\!\ket{\eta}$
with random permutations and random functions,
and $\NN$ be the support of $\nu$.
By \thm{kactosrss}, $\NN$ is an $\epsilon$-net with $\epsilon=\negl{\secpar}$,
and there exists a distribution $\widetilde{\nu}$
such that
$\tv{\mu-\tilde{\nu}}\text{ and }
W_{\infty}(\tensorsrss, \widetilde{\nu})$ are both negligible.
Moreover, the output distribution of $\enssgen$ is computationally indistinguishable from
$\nu$ since we use \qprp s and \qprf s to replace random permutations
and random functions.
%	By the quantum-secure property of $\tau$ and $F$, the following two situations are computationally indistinguishable for any polynomial-time quantum oracle algorithm $\A$ (see \lem{twokeys}):
%	\begin{itemize}
%		\item given oracle access to
%		$\tau_{r_1},\cdots,\tau_{r_T}$ and $F_{s_1},\cdots,F_{s_T}$
%		where
%		$\rep{r}{T}\in\K_1$ and $\rep{s}{T}\in\K_2$
%		are independently and uniformly random keys.
%		\item given oracle access to
%		independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$
%		and random functions $\rep{f}{T}: \bit{n-1}\to\bit{d}$.
%	\end{itemize}
%	Thus, we have
%for any
%	polynomial-time quantum algorithm $\A$,
%	$$
%	\abs{
%		\Pr\Br{\A\br{\ket{\phi_k}^{\otimes l}} = 1} -
%		\Pr\Br{\A\br{\ket{\varphi_{\rep{\sigma}{T},\rep{f}{T}}}^{\otimes l}} = 1}
%	} = \negl{\secpar} \enspace .
%	$$
%	By \thm{kactosrss}, the condition of computationally Wasserstein approximation of Haar randomness holds.
%Thus we complete our proof.

\end{proof}

\subsubsection{Complex Case}
Likewise, the ensemble of unitary operators built over complex space in \sect{rss_in_complex} turns out to be a \srss. The proof is proved in \app{deferred proofs}.

\begin{theorem}\label{thm:kactosrssc}
Let $n\in\N$, $d = 2\br{\log^2\!\secpar + \log^2\!n}$ and $T = 515 (\secpar + 1) n$.
The ensemble of unitary operators
$ \enssrssconsc$
defined in \defi{kactosrssc}
is a \srss.
\end{theorem}

For the same reason as \thm{realdprss}, replacing the random primitives employed in $ \enssrssconsc$ with their pseudorandom counterparts yields a \sprss.
\begin{theorem}\label{thm:complexdprss}
Let $n\in\N$, $d = 2\br{\log^2\!\secpar + \log^2\!n}$ and $T = 515 (\secpar + 1) n$.
The ensemble of unitary operators
$\enssgenc$ defined in \defi{kactoprssc} is a \sprss.
\end{theorem}
%We omit the proof which is similar to that of \cref{thm:realdprss}.

% \section{Conclusions and open problems}
% \label{sec:conclusion}
% \input{conclusion}

\newpage
\begin{appendices}
\addappheadtotoc
\addtocontents{toc}{\protect\setcounter{tocdepth}{1}}
% \appendix
\section{Connections with Existing PRS variants}
\label{sec:connection}
\paragraph{(Scalable) Pseudorandom States.}
The original definition of~[26] identifies the number of
$\dimin$ with the security parameter. This is refined by~[13]
that treats $n$ and
$\secpar$ separately, and they call it \emph{scalable}
$\prsg$s. The primary benefit is to tune security when $\dimin <
\secpar$. We rephrase the scalable definition in a style that is
congruent with our definitions of new quantum pseudorandom primitives.

\begin{definition}[(Scalable) \prsg]
Let $\K=\{0,1\}^{\klen}$ be a key space,
$\H$ be a Hilbert space of dimension $2^{\dimin}$ with
$\secpar$ be a security parameter.
A \emph{(scalable) pseudorandom state generator (\prsg)}~is an ensemble of unitaries
\[\mathcal{G}^n:=\{\{\mathcal{G}^{n,\secpar}_{k}:\H\rightarrow \H\}_{k\in\K}\}_{\lambda}\]

\begin{itemize}
\item \textbf{Pseudorandomness.}  Any polynomially many $\ncopy$ copies of
$\ket{\phi_k}$ with the same random $k$ is computationally
indistinguishable from the same number of copies of a Haar random
state.  More precisely, for any $n\in\N$, any efficient quantum
algorithm $\A$ and any $\ncopy \in\poly{\lambda}$,
\[\abs{\prob{k\gets \K}{\A\!\br{\ket{\phi_k}^{\otimes \ncopy}}=1}-\prob{\ket{\psi}\gets \mu}{\A\!\br{\ket{\psi}^{\otimes \ncopy}}=1}}=\negl{\lambda} \enspace,\]
where $\ket{\phi_k}:=\mathcal{G}^{n,\lambda}_{\kappa}\!\ket{0^n}$ and $\mu$ is the Haar measure on $\S(\H)$.

\item \textbf{Uniformity.}  $\mathcal{G}^n$ can be uniformly
computed in polynomial time. That is, there is a deterministic
Turing machine that, on input $(1^{\dimin},1^\secpar,1^\klen)$,
outputs a quantum circuit $Q$ in $\poly{\dimin,\secpar,\klen}$
time such that for all $k\in \K$ and $\ket{\phi}\in\Sin$
\[ Q\ket{k}\!\ket{\phi} = \ket{k}\!\ket{\phi_k}\, , \] where
$\ket{\phi_k} := \mathcal{G}^{n,\lambda}_{k}\! \ket{\phi}$.

\item \textbf{Polynomially-bounded key length.}
$\klen = \log |\K| = \poly{\dimout,\secpar}$. As a result,
$\mathcal{G}^{\dimin}$ can be computed efficiently in time
\end{itemize}

We informally call the keyed family of quantum states
$\st{\ket{\phi_k}}_{k\in\K}$ a \emph{(scalable) pseudorandom quantum state} in $\H$.
\label{def:scalableprsg}
\end{definition}

The existence of \prss s implies
the existence of (scalable) \prsg s~[26, 13] straightforwardly by definition.

\begin{lemma}
If $\SG{}{n,m}$ is a \prss~from $\hspacein$ to $\hspaceout$
over a key space $\K$ with security parameter $\secpar$,
$\st{ \SG{k}{n,m,\secpar}\ket{\phi}}_{k\in\K}$ is a (scalable) \prs~in $\hspaceout$ for any
\label{lem:prss2prs}
\end{lemma}

%\paragraph{Scalable Pseudorandom States.}
%%Brakerski and
%%Shmueli~[13] introduced scalable pseudorandom states to
%%eliminate the dependence between the state size and the security
%%parameter. This modification aids in assuring the security when the
%%state size $n$ is much smaller than the security parameter $\secpar$
%%(e.g. $n=\log(\lambda)$).
%We recall the definition:
%\begin{definition}[Scalable \prsg~[13]]
%  Let $\K$ be a key space \wrt the security parameter $\secpar$ and
%  $\H$ be a Hilbert space with dimension
%  $2^n$. %($\lambda$ and $n$ are independent).
%  A pair of quantum algorithm $(K, G)$ is a \emph{scalable \prs~generator}
%  if the following holds:
%  \begin{itemize}
%  \item \textbf{Key Generation}.  For all $n,\secpar\in \N$,
%    $K(1^{\lambda}, 1^n)$ outputs a classical key $k\in \K$.
%  \item \textbf{State Generation.}  For all $k\in \K$, the algorithm
%    $G(1^\secpar, 1^n, k)$ outputs an $n$-qubit quantum state
%    $\ket{\phi_k}\in \S(\H)$.
%  \item \textbf{Pseudorandomness.}  For any polynomial many copies of
%    $\ket{\phi_k}$ with the same random $k$ is computationally
%    indistinguishable from the same number of copies of a Haar random
%    state.  Precisely, for any $n, \lambda\in \N$, any
%    $\poly{\lambda, n}$-time quantum algorithm
%    $\A$ %=\{\A_\lambda\}_{\lambda\in \N}$
%    and any $\ncopy\in \poly{\lambda}$,
%    \[ \abs{\prob{k\gets K(1^\secpar, 1^n)} {\A\br{\ket{\phi_k}^{\tp
%              \ncopy}}=1} - \prob{\psi\gets \haar}
%        {\A\br{\ket{\psi_k}^{\tp \ncopy}}=1} }\leq \negl{\secpar} \, ,
%		\]
%                where $\haar$ is the Haar measure on $\S(\H)$.
%   \end{itemize}
%   \label{def:scalableprs}
%  If $(K, G)$ is a PRSS from $\hspacein$ to
%  $\hspaceout$ \wrt parameters $(\secpar, n, m)$ s.t.
%  $n=m$, $\{\ket{\phi_k}\}_{k\in
%    \K}$ is a scalable PRS in $\hspaceout$ for any $\ket{\phi}\in
%  \S(\hspaceout)$.
%  \label{lem:prss2sprs}

\paragraph{Pseudorandom Function-like States.}
%\prfsg s~[3] extend \prs s by augmenting with classical inputs
%alongside the secret key. Although the security is initially based on
%pre-selected classical queries to the \prfsg~generator, the subsequent
%work[1] relaxes this to allow adversaries making adaptive
%(classical or quantum) queries resulting in three levels of security.
%We recall the definition:
We recall the definition of the pseudorandom function-like states generator
with three levels of security:
\begin{definition}[\prfsg~[3, 1]]
\label{def:prfs}
Let $\K=\bit{\secpar}$ be a key space.  Let $\CC=\bit{n}$ be a
classical input space and $\H$ be a Hilbert space of dimension
$2^m$.  A pair of $\poly{\secpar,m}$-time quantum algorithm $(K,G)$
is a \emph{pseudorandom function-like state} generator if the
following holds:
\begin{itemize}
\item \textbf{Key Generation.}  For all $\secpar\in\N$,
$K(1^\secpar)$ outputs a uniform key $k\in \K$.

\item \textbf{State Generation.}
For all $k\in \K$ and $x\in \CC$, $G(1^\secpar, k, x)$ computes
$\ket{\phi_{x,k}} \in\S(\H)$.

\item \textbf{Pseudorandomness.}  The pseudorandomness can be
defined in three different levels (from weaker to stronger):

\begin{itemize}
\item \textbf{Selective security.}  For any $\secpar\in \N$,
$s\in \poly{\secpar}, \ncopy\in \poly{\secpar }$, any efficient
quantum algorithm (non-uniform) $\A$ and a set of pre-declared
input $\{ x_1, \dots, x_{s}\}\subseteq \CC$,
\begin{align*}
\bigg|\Pr_{k\gets\K}
& \Br{\A(x_1, \dots, x_s, \ket{\phi_1}^{\tp\ncopy}, \dots, \ket{\phi_s}^{\tp\ncopy})=1} \\
& -\Pr_{\ket{\psi_1}, \dots, \ket{\psi_s}\gets\haar}
\Br{\A(x_1, \dots, x_s, \ket{\psi_1}^{\tp\ncopy}, \dots, \ket{\psi_s}^{\tp\ncopy})=1}
\bigg|\leq \negl{\secpar},
\end{align*}
where, for each $i$, $\ket{\phi_i}$ denotes $\ket{\phi_{x_i,k}}$ generated by $G$; and $\ket{\psi_i}$ is a Haar random state.

\item \textbf{Adaptive security.}
Given \emph{classical-access} to either the \prfs~oracle $\oracle_{\prfs}$
or the Haar-random oracle $\oracle_{\Haar}$,
for any $\secpar\in\N$,
any efficient quantum algorithm (non-uniform) $\A$
with polynomial length quantum advice $\rho_\secpar$,
%the following holds:
\[
\abs{
\prob{k\gets\K}{\A^{{\oracle_{\prfs}(k, \cdot)}}(\rho_\secpar)=1}
\prob{\oracle_{\Haar}}{\A^{{\oracle_{\Haar}(\cdot)}}(\rho_\secpar)=1}
\]
where on input $x\in\CC$,
$\oracle_{\prfs}(k, \cdot)$ outputs $G(1^\secpar, k, x)$;
and $\oracle_{\Haar}(\cdot)$ outputs a Haar random $\ket{\psi_x}$.
\item \textbf{Quantum-accessible adaptive security.}
Given \emph{quantum-access} to a \prfs~or Haar-random oracle,
for any $\lambda\in \N$,
for any efficient quantum algorithm (non-uniform) $\A$
with polynomial length quantum advice $\rho_\secpar$,
%the following holds:
\[
\abs{
\prob{k\leftarrow \K}{\A^{\ket{\oracle_{\prfs}(k, \cdot)}}(\rho_\secpar)=1}
\prob{\oracle_{\Haar}}{\A^{\ket{\oracle_{\Haar}(\cdot)}}(\rho_\secpar)=1}
\]
where on input a $n$-qubit register $\regx$,
$\oracle_{\prfs}(k, \cdot)$ applies a channel that controlled on the
register $\regx$ containing $x$,
and stores $G(1^\secpar, k, x)$ in the register $\regy$,
then output $(\regx, \regy)$;
instead,  $\oracle_{\Haar}(\cdot)$ stores a Haar random
$\ketbra{\psi_x}$ on the register $\regy$,
then output $(\regx, \regy)$.
\end{itemize}
\end{itemize}
\label{def:prfs}
\end{definition}

As previously mentioned, the security of our \prss~is maintained
when applied to any arbitrary initial pure state,
making it straightforward to derive a \prfsg~with selective security.

\begin{lemma}
Assume $\SG{}{n,m}$ is a \prss~from $\hspacein$ to $\hspaceout$
over a key space $\K$
with security parameter $\secpar$.
Construct $(\hat{K},\hat{G})$ in the following way:
\begin{itemize}
\item (Key generation.)
Given $s\in \poly{\secpar}$, for all $\lambda\in\N$, $\hat{K}(1^\secpar)$ generates a key
$k=\{k_1, \dots, k_s\}$ such that for $i\in[s]$,
$k_i$ is chosen uniformly and independently from $\K$;
\item (State generation.)
For all $k$ and classical queries $\{x_i\in \CC\}_{i=1}^s$,
computes $\ket{\phi_{i}}= \SG{k_i}{n,m,\lambda}\ket{x_i}$.
\end{itemize}
Then, $(\hat{K},\hat{G})$ is a \prfsg~with selective security.
\label{lem:prss2prfs-select}
\end{lemma}
\begin{proof}
The algorithm $(\hat{K},\hat{G})$ is efficient as
it essentially performs \prss~a polynomial number of times.
Meanwhile, the indistinguishability holds because all output states are obtained via independent keys.
\end{proof}

%\fnote{quantum-access case is tricky! cannot apply $\prss$ directly on
%  input superposition. we need to apply it to each $x$ in
%  superposition. Zhanry's sample indist = oracle indist.~\cite[Theorem
%  1.1]{Zhandry21_qprf} may work.}

If we restrict $n=O(\log \secpar)$ and set $s=O(2^n)\in\poly{\secpar}$,
the construction in \lem{prss2prfs-select} produces sufficient key segments
to ensure that every $x\in\CC$ has its own independent key.
As a consequence, log-input \prfsg s with adaptive security can be achieved
through the use of \prss s.
Furthermore, as demonstrated by the results in~[43],
quantum superposition queries over the input domain do not provide
any additional advantages when the output state is known for every input string,
which results in quantum-accessible adaptive security.

\begin{lemma}\label{lem:prfs-adapt}
If $\SG{}{n,m}$ is a \prss~from $\hspacein$ to $\hspaceout$
over a key space $\K$
with security parameter $\secpar$ s.t. $n=O(\log\secpar)$,
then $(\hat{K},\hat{G})$ is a \prfsg~satisfying
adaptive security and quantum-accessible adaptive security.
\end{lemma}

Prior works~[3, 1] have demonstrated that $\log$-input
$\prfsg$s can be constructed from a $\prs$, although this approach
requires a \emph{test procedure}. The test procedure involves
post-selecting among the classical input domain, which introduces
errors and incurs computation overhead. By flexibility in input
selection, our $\prss$ provides a cleaner method. We note that
$\prfsg$s on long inputs (i.e., exponentially large domain) seem
stronger and might not be possible from $\prs$s or $\prss$s in a
black-box manner. Existing constructions need to employ a post-quantum

\section{Deferred Proofs}
\label{sec:deferred proofs}
\subsection{Proof of \lem{h3h4}}
\begin{proof}[Proof of \lem{h3h4}]
We demonstrate that the real case and the complex case can be established using the same approach.

Let $\zeta^+-\zeta^-$ be the Hahn decomposition of the signed measure $\mu-\nu$. Then
\begin{align*}
\E_{\ket{\psi}\sim \mu}\!\Br{ \br{\ketbra{\psi}}^{\otimes l} }
- \E_{\ket{\varphi}\sim \nu}\!\Br{\br{\ketbra{\varphi}}^{\otimes l}}
=~&\norm{\int_{\SR^{2^n}}\br{\ketbra{u}}^{\otimes l}\br{\mu-\nu}\br{\d\ket{u}}}_1\\
=~&\norm{\int_{\SR^{2^n}}\br{\ketbra{u}}^{\otimes l}\br{\zeta^+-\zeta^-}\br{\d\ket{u}}}_1\\
\leq~&\norm{\int_{\SR^{2^n}}\br{\ketbra{u}}^{\otimes l}\zeta^+\br{\d\ket{u}}}_1+\norm{\int_{\SR^{2^n}}\br{\ketbra{u}}^{\otimes l}\zeta^-\br{\d\ket{u}}}_1\\
\leq~&\int_{\SR^{2^n}}\norm{\br{\ketbra{u}}^{\otimes l}}_1\zeta^+\br{\d\ket{u}}+\int_{\SR^{2^n}}\norm{\br{\ketbra{u}}^{\otimes l}}_1\zeta^-\br{\d\ket{u}}\\
\end{align*}
\end{proof}

\subsection{Proof of \lem{twokeys}}
\begin{proof}[Proof of \lem{twokeys}] We first prove the case that $F: \K_1 \times \X_1 \to \Y_1$ and $G: \K_2 \times \X_2 \to \Y_2$ are both \qprf s. We prove the lemma by contradiction.
Suppose there exists a polynomial-time quantum oracle algorithm $\A$ who queries $q$ times such that
\begin{align*}
\abs{
\prob{ k_1\gets\K_1, k_2\gets \K_1 }{\A^{F_{k_1}, G_{k_2}}\!\br{1^\lambda}=1}-\prob{f\gets\Y_1^{\X_1},g\gets\Y_2^{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}
} = \dfrac{1}{\poly{\lambda}} \enspace .
\end{align*}
By the triangle inequality,
\begin{align*}
\prob{ k_1\gets\K_1, k_2\gets \K_1 }{\A^{F_{k_1}, G_{k_2}}\!\br{1^\lambda}=1}-\prob{k_1\gets\K_1, g\gets\Y_2^{\X_2}}{\A^{F_{k_1},g}\!\br{1^\lambda}=1}
} \\
&~~~~~~+~~~~~ \abs{
\prob{k_1\gets\K_1, g\gets\Y_2^{\X_2}}{\A^{F_{k_1},g}\!\br{1^\lambda}=1}-\prob{f\gets\Y_1^{\X_1},g\gets\Y_2^{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}
} \geq  \dfrac{1}{\poly{\lambda}} \enspace .
\end{align*}
Without loss of generality, we assume
\begin{align*}
\abs{
\prob{k_1\gets\K_1, g\gets\Y_2^{\X_2}}{\A^{F_{k_1},g}\!\br{1^\lambda}=1}-\prob{f\gets\Y_1^{\X_1},g\gets\Y_2^{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}
} \geq  \dfrac{1}{2\cdot \poly{\lambda}}\enspace.
\end{align*}

Thus we can define a polynomial-time quantum oracle algorithm
$\A'$ that is able to distinguish $F_{k_1}$ from a random
function $f$.  Once $\A'$ gets an oracle access to some
function $h\in\st{F_{k_1},f}$, it simulates the execution of
$\A$ with oracle access to $h$ and a random function $g$.
Since $\A$ makes at most $q$ queries, $\A'$ can efficiently
simulate a random oracle using $2q$-wise independent function
(see~\cite[Theorem 6.1]{Zhandry15_ibe}).  This contradicts the
quantum-security property of $F$.

To prove the case that $F: \K_1 \times \X_1 \to \Y_1$ is a \qprf~and $G: \K_2 \times \X_2 \to \X_2$ is a \qprp, we may assume as above that there exists a polynomial-time quantum oracle algorithm $\A$ who queries $q$ times such that
\begin{align*}
\abs{
\prob{k_1\gets\K_1, g\gets S_{\X_2}}{\A^{F_{k_1},g}\!\br{1^\lambda}=1}-\prob{f\gets \Y_1^{\X_1},g\gets S_{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}
} \geq  \dfrac{1}{2\cdot \poly{\lambda}}\enspace.
\end{align*}
Then we define the following efficient algorithm $\A''$ to distinguish a \qprf~from a random function:
\begin{enumerate}
\item Given $h\in\st{F_{k_1},f}$,
it chooses a permutation $g$ uniformly at random from a $2q$-wise almost independent family of permutations to simulate a random permutation oracle.
This sampling procedure can be done in polynomial time
(see~\cite[Theorem 5.9]{KNR09}).
\item It simulates $\A$ with oracle access to $h$ and $g$, and outputs what $\A$ returns.
\end{enumerate}
This breaks the quantum-security property of \qprf s.

%To prove the case that $F: \K_1 \times \X_1 \to \Y_1$ are QPRPs and $G: \K_2 \times \X_2 \to \Y_2$ are QPRFs, we introduce some notations to keep the expressions short.
%  \item $p(\mathrm{PRP},\mathrm{PRF})=\prob{ k_1\gets\K_1, k_2\gets \K_1 }{\A^{F_{k_1}, G_{k_2}}\!\br{1^\lambda}=1}$;
%  \item $p(\mathrm{RP},\mathrm{PRF})=\prob{ f\gets\mathrm{Perm}(\X_1), k_2\gets \K_1 }{\A^{f, G_{k_2}}\!\br{1^\lambda}=1}$;
%  \item $p(\mathrm{RF},\mathrm{PRF})=\prob{ f\gets\Y_1^{\X_1}, k_2\gets \K_1 }{\A^{f, G_{k_2}}\!\br{1^\lambda}=1}$;
%  \item $p(\mathrm{RF},\mathrm{RF})=\prob{ f\gets\Y_1^{\X_1}, g\gets\Y_2^{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}$;
%  \item $p(\mathrm{RP},\mathrm{RF})=\prob{ f\gets\mathrm{Perm}(\X_1), g\gets\Y_2^{\X_2}}{\A^{f,g}\!\br{1^\lambda}=1}$.
%Using the triangle inequality,
%  &\abs{p(\mathrm{PRP},\mathrm{PRF})-p(\mathrm{RP},\mathrm{RF})} \\
%  \leq&\abs{p(\mathrm{PRP},\mathrm{PRF})-p(\mathrm{RP},\mathrm{PRF})}+\abs{p(\mathrm{RP},\mathrm{PRF})-p(\mathrm{RF},\mathrm{PRF})}\\
%  &+\abs{p(\mathrm{RF},\mathrm{PRF})-p(\mathrm{RF},\mathrm{RF})}
%  +\abs{p(\mathrm{RF},\mathrm{RF})-p(\mathrm{RF},\mathrm{RP})}
%We have $\abs{p(\mathrm{PRP},\mathrm{PRF})-p(\mathrm{RP},\mathrm{PRF})}=\negl{\lambda}$ by the definition of QPRP. Further notice that random functions and random permutations are computationally indistinguishable~\cite[Theorem 3.1]{Zhandry15_col}, which implies that $\abs{p(\mathrm{RP},\mathrm{PRF})-p(\mathrm{RF},\mathrm{PRF})}=\negl{\lambda}$.
%Using the same argument for the QPRFs, we have
%  +\abs{p(\mathrm{RF},\mathrm{RF})-p(\mathrm{RF},\mathrm{RP})}=\negl{\lambda}.\]
%Thus, we conclude the result.
\end{proof}

\subsection{Proof of ~\thm{mixing_time_w1_c}}
To prove \thm{mixing_time_w1_c}, we extend the the proportional coupling introduced in real case to complex case.
In the proportional coupling, the real case lets $(X_t[i], X_t[j])$ be collinear with $(Y_t[i], Y_t[j])$ so that the distance from $X_t$ to $Y_t$ is reduced by a constant factor in each step. However in complex case, $(X_t[i], X_t[j])$ is actually a two  dimensional complex vector and this makes it unsuitable to adopt the previous approach directly. To deal with this, in the complex case, we let
$(\abs{X_t[i]}, \abs{X_t[j]})$ align collinearly with $(\abs{Y_t[i]}, \abs{Y_t[j]})$ in real two dimensional real plane, and make ${X_t[i]}$ and ${Y_t[i]}$, as well as ${X_t[j]}$ and ${Y_t[j]}$, share the same argument in complex plane in the meantime. We assume $n=2m$.

\subsubsection{Proportional Coupling}

\begin{definition}[Proportional Coupling]\label{def:prop_cpl_c}
We define a coupling of two copies
$\st{X_t}_{t\geq 0}, \st{Y_t}_{t\geq 0}$
of parallel Kac's walk on complex vectors
in the following way:
Fix $X_t$, $Y_t\in \C^{n}$.
\begin{enumerate}
\item Choose a perfect matching of $[n]$, denoted by $P_t = \st{\br{i^{(t)}_1, j^{(t)}_1},\dots,\br{i^{(t)}_m, j^{(t)}_m}}$, uniformly at random.
\item Let $X_{t,1} =X_t$ and $Y_{t,1}=Y_t$. For every $1\leq k\leq m$:
\begin{enumerate}
\item let $l^{(t)}_k = \sqrt{\abs{X_{t,k}[i^{(t)}_k]}^2+\abs{X_{t,k}[j^{(t)}_k]}^2}$ and ${l'}^{(t)}_k = \sqrt{\abs{Y_{t,k}[i^{(t)}_k]}^2+\abs{Y_{t,k}[j^{(t)}_k]}^2}$. Let $U_0$ and $U_0'$ be the unitary operators in $\su\br{2}$ which satisfy
\begin{align*}
\end{matrix}} = \br{\begin{matrix}
\end{matrix}}
\text{\quad and\quad}
\end{matrix}} = \br{\begin{matrix}
\end{matrix}}\enspace.
\end{align*}
\item pick $\alpha_k^{(t)},\beta_k^{(t)}\in[0,2\pi)$ and $\zeta_k^{(t)}\in[0,1)$ uniformly at random and set

\begin{align}\label{eq:theta}
\theta_k^{(t)} = \arcsin \sqrt{\zeta_k^{(t)}}\enspace.
\end{align}
\item set
\begin{align*}
X_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k, \alpha^{(t)}_k,\beta^{(t)}_k,\theta^{(t)}_k, U_0X_{t,k}}\enspace,\\
Y_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k, \alpha^{(t)}_k,\beta^{(t)}_k,\theta^{(t)}_k, U_0'Y_{t,k}}\enspace.
\end{align*}
\end{enumerate}

\item Finally, set $X_{t+1}=X_{t,m+1}$ and $Y_{t+1}=Y_{t,m+1}$.
\end{enumerate}
\end{definition}

\begin{remark}
In step 2(a), if $l^{(t)}_k\neq 0$, $X_{t,k}[i^{(t)}_k]=r_1e^{\i\gamma}$ and $X_{t,k}[j^{(t)}_k]=r_2e^{\i\delta}$ with $r_1,r_2\in[0,1]$ and $\gamma,\delta\in[0,2\pi)$, then $U_0$ is $U\!\br{\alpha_0,\beta_0,\theta_0}$ where
\begin{align*}
\alpha_0 = -\gamma\enspace,\quad \beta_0 = \pi-\delta\enspace,\quad \theta_0 = \arccos\frac{r_1}{\sqrt{r_1^2+r_2^2}} \enspace .
\end{align*}
If $l^{(t)}_k = 0$, $U_0$ can be arbitrary matrix in $\su(2)$.
The same applies to $U_0'$.
\end{remark}

Due to the unitary invariance of Haar measures,
$UU_0$ is Haar distributed on $\su(2)$
for a random random $U$
sampled according to
Haar measure on $\su(2)$.
This guarantees that
the proportional coupling
is indeed a valid coupling.

\begin{remark}
The proportional coupling forces $X_{t+1}[i], Y_{t+1}[i]$ and the original point to be collinear in the complex plane. In other words, $X_{t+1}[i]$ and $Y_{t+1}[i]$ have the same argument.  Specifically, we can write
X_{t+1}[i] = e^{i\phi} l
\text{\quad and \quad}
Y_{t+1}[i] =  e^{i\phi}l'
for some $l,l'\in[0,1],\phi\in[0,2\pi)$.
\end{remark}

Through proportional coupling ,
$X$ and $Y$ approach each other at an exponential rate.
Formally, we have

\begin{lemma} \label{lem:contraction_lemma_c}
Let $X_0,Y_0\in \SC^{n}$. For $t\geq 0$, we couple $(X_{t+1},Y_{t+1})$ conditional on $(X_{t},Y_{t})$ according to the proportional coupling defined in \defi{prop_cpl_c}.
We define
A_{t}[i] = \abs{X_t[i]}^2\enspace,\quad B_{t}[i] = \abs{Y_t[i]}^2\enspace.
Then for any $l\in\N$, we have
\E\!\Br{\sum_{i=1}^n \br{A_l[i]-B_l[i]}^2}\leq 2\cdot\br{\frac{2}{3}}^l\enspace.
\end{lemma}

\begin{proof}[Proof of~\lem{contraction_lemma_c}]
Fix $X_t,Y_t\in \SC^n$. Let $(X_{t+1},Y_{t+1})$ obtained from $(X_{t},Y_{t})$ by applying the coupling defined in \defi{prop_cpl_c}.
Recall that $n=2m$.
Let $N=\frac{n!}{2^{m}m!}$ be the number of perfect matchings for $[n]$.
A perfect matching $\st{\br{i^{(t)}_1, j^{(t)}_1},\dots,\br{i^{(t)}_m, j^{(t)}_m}}$ of $[n]$ at step $t$ is denoted by $\br{\overrightarrow{i^{(t)}},\overrightarrow{j^{(t)}}}$.

We have
\begin{align}
&\E\!\Br{\sum_{i=1}^n \br{A_{t+1}[i]-B_{t+1}[i]}^2}=\frac{1}{N}\sum_{\br{\overrightarrow{i^{(t)}},\overrightarrow{j^{(t)}}}}\underbrace{\E\!\Br{\left.\sum_{i=1}^n \br{A_{t+1}[i]-B_{t+1}[i]}^2\right|P_t=\br{\overrightarrow{i^{(t)}},\overrightarrow{j^{(t)}}}}}_{(\star)} \enspace .\label{eqn:t1c}
\end{align}

By the definition of the parallel Kac's walk on complex vectors, we have

\begin{align}
(\star)=&\sum_{k=1}^m \E\!
\Br{\br{\br{A_{t}[i^{(t)}_k]+A_{t}[j^{(t)}_k]}\cos(\theta_k^{(t)})^2-\br{B_{t}[i^{(t)}_k]+B_{t}[j^{(t)}_k]}\cos(\theta_k^{(t)})^2}^2}\nonumber\\
&\quad\quad+\sum_{k=1}^m \E\!
\Br{\br{\br{A_{t}[i^{(t)}_k]+A_{t}[j^{(t)}_k]}\sin(\theta_k^{(t)})^2-\br{B_{t}[i^{(t)}_k]+B_{t}[j^{(t)}_k]}\sin(\theta_k^{(t)})^2}^2}\nonumber\\
\br{\br{A_{t}[i^{(t)}_k]+A_{t}[j^{(t)}_k]}-\br{B_{t}[i^{(t)}_k]+B_{t}[j^{(t)}_k]}}^2\nonumber\\
\br{\br{A_{t}[i^{(t)}_k]-B_{t}[i^{(t)}_k]}^2+\br{A_{t}[j^{(t)}_k]-B_{t}[j^{(t)}_k]}^2}}_{(\star\star)} \nonumber\\	&\quad\quad+\underbrace{\frac{2}{3}\sum_{k=1}^m2\br{A_{t}[i^{(t)}_k]-B_{t}[i^{(t)}_k]}\br{A_{t}[j^{(t)}_k]-B_{t}[j^{(t)}_k]}}_{(\star\star\star)}\enspace,\label{eqn:t2c}
\end{align}
where the second equality is by $\E\!\Br{\cos(\theta_k^{(t)})^4}=\E\!\Br{\sin(\theta_k^{(t)})^4}=1/3.$

As $\st{\br{i^{(t)}_1, j^{(t)}_1},\dots,\br{i^{(t)}_m, j^{(t)}_m}}$ is a perfect matching, we have
\begin{equation}\label{eqn:t3c}
(\star\star)=\frac{2}{3}\sum_{i=1}^{n}\br{A_t[i]-B_t[i]}^2 \enspace .
\end{equation}
Combing Eqs.~\eqref{eqn:t1c}\eqref{eqn:t2c}\eqref{eqn:t3c}, we obtain
\begin{align}\label{eqn:t4c}
&\E\!\Br{\sum_{i=1}^n \br{A_{t+1}[i]-B_{t+1}[i]}^2}= \frac{2}{3}\sum_{i=1}^{n}\br{A_t[i]-B_t[i]}^2+\underbrace{\frac{1}{N}\sum_{\br{\overrightarrow{i^{(t)}},\overrightarrow{j^{(t)}}}}(\star\star\star)}_{(4\star)} \enspace .
\end{align}
Using the same calculation in \cref{eqn:t5}, we have
\begin{align}
\end{align}

Combining Eqs.~\eqref{eqn:t4c}\eqref{eqn:t5c}, we have
\begin{align*}
\E\!\Br{\sum_{i=1}^n \br{A_{l}[i]-B_{l}[i]}^2} &= \E\!\Br{\E\!\Br{\left.\sum_{i=1}^n \br{A_{l}[i]-B_{l}[i]}^2 \right|X_{l-1},Y_{l-1} } }\\
&\leq \frac{2}{3}\E\!\Br{\sum_{i=1}^{n}\br{A_{l-1}[i]-B_{l-1}[i]}^2}\\
&\leq \br{\frac{2}{3}}^l \sum_{i=1}^{n}\br{A_{0}[i]-B_{0}[i]}^2\leq 2\cdot\br{\frac{2}{3}}^l\enspace.
\end{align*}
\end{proof}

\subsubsection{Proof of the Mixing Time}
\label{sec:mixing_time_w1_c}

\begin{proof}[Proof of \thm{mixing_time_w1_c}]
Let $T=10(c+1)\log n$ for $c>0$. We couple two copies $\st{X_t}_{t\geq 0}$ and $\st{Y_t}_{t\geq 0}$ of the parallel Kac's walk with starting points $X_0=x\in \SC^n$ and $Y_0\sim \mu$, by applying the proportional coupling. We have
\begin{equation*}
\wone{\mathcal{L}\!\br{X_{T}}}{\mu} = \wone{\mathcal{L}\!\br{X_{T}}}{\mathcal{L}\!\br{Y_{T}}} \leq \expec{\norm{X_T-Y_T}_2} \leq \br{\expec{\norm{X_T-Y_T}_2^4}}^{1/4}\enspace.
\end{equation*}
Then by Cauthy-Schwarz inequality, we have
\begin{equation}\label{eq:w11_c}
\wone{\mathcal{L}\!\br{X_{T}}}{\mu} \leq \br{n\expec{\norm{X_T-Y_T}_4^4}}^{1/4}\enspace.
\end{equation}
Note that the proportional coupling forces $X_T[i]$ and $Y_T[i]$ share the same argument for all $i\in[n]$. Therefore, for all $i\in[n]$
\abs{X_T[i]-Y_T[i]} = \abs{\abs{X_T[i]}-\abs{Y_T[i]}} \leq \abs{X_T[i]}+\abs{Y_T[i]} \enspace .
This gives us
\begin{equation}\label{eq:w12_c}
\norm{X_T-Y_T}_4^4 = \sum_{i=1}^n\abs{X_T[i]-Y_T[i]}^4 \leq \sum_{i=1}^n\br{\abs{X_T[i]}^2-\abs{Y_T[i]}^2}^2\enspace .
\end{equation}
Combing Eqs. \eq{w11_c} and \eq{w12_c}, we have
\begin{align*}
\wone{\mathcal{L}\!\br{X_{T}}}{\mu}
\leq &\br{n\expec{\sum_{i=1}^n\br{\abs{X_T[i]}^2-\abs{Y_T[i]}^2}^2}}^{1/4}\\
\leq &\br{2n\br{\frac{2}{3}}^{T}}^{1/4}
\leq \frac{1}{2^{c\log n}} \enspace.
\end{align*}
\end{proof}

\subsection{Proof of \thm{kactorssc}}\label{sec:proof_rssc}
To prove \thm{kactorssc}, we first introduce a new ensemble of (infinitely many) unitary operators
$\enscsrssconsc \coloneq \st{\csrssconsc }_{\secpar}$ with
$$\csrssconsc \coloneq \st{\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}:\H\to\H}
_{\rep{\sigma}{T} \in S_{2^n},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}: \bit{n-1}\to [0,1)}$$
\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}
= \widetilde{L}_{\tau_{T},\cf_{T},\cg_{T},\ch_{T}}\cdots
\widetilde{L}_{\tau_{2},\cf_{2},\cg_{2},\ch_{2}}
\widetilde{L}_{\tau_{1},\cf_{1},\cg_{1},\ch_{1}} \enspace
= U_{\sigma^{-1}} \widetilde{Q}_{\cf,\cg,\ch} U_{\sigma}$
$\widetilde{Q}_{\cf,\cg,\ch}$ is defined to be
\begin{align}\label{eq:widetildeq}
\widetilde{Q}_{\cf,\cg,\ch} =
\sum_{y\in\bit{n-1}}
\otimes\ketbra{y}\enspace,
\end{align}
in which $U(\alpha,\beta,\theta)$ is defined in \eq{parhaar} and for any $y\in\bit{n-1}$
\[
\widetilde{\theta}_y=\arcsin\br{\sqrt{\cf(y)}}\enspace, \enspace
\widetilde{\alpha}_y=2\pi\cdot\cg(y)\enspace , \enspace
\widetilde{\beta}_y=2\pi\cdot\ch(y)\enspace .
\]
Similar to the real case,
$\widetilde{L}_{\sigma,\cf,\cg,\ch}$ represents one step of parallel Kac's walk in complex space
for independently and uniformly random $\sigma,\cf,\cg$ and $\ch$.

\begin{lemma} \label{lem:ltildelclose}
Let $\sigma\in S_{2^n}$
and $\cf,\cg,\ch:\bit{n-1}\to[0,1)$.
Let $f:\bit{n-1}\to \bit{d}$ be the function satisfying for any $y\in\bit{n-1}$,
$f(y)$ is the $d$ digits after the binary point in $\widetilde{f}(y)$. The same applies to $g$ and $h$.
\norm{ L_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}
}_\infty }
\leq 2^{6-\frac{d}{2}} \enspace ,
where $L_{\sigma,f,g,h}=U_{\sigma^{-1}} Q_{f,g,h} U_{\sigma}$
is defined in \eq{normalq} and
= U_{\sigma^{-1}} \widetilde{Q}_{\cf,\cg,\ch} U_{\sigma}$
is defined in \eq{widetildeq}.
\end{lemma}

\begin{proof}[Proof of \lem{ltildelclose}]
Recall the unitary $\widehat{L}_{\sigma,f,g,h}=U_{\sigma^{-1}} \widehat{Q}_{f,g,h} U_{\sigma}$ defined in \eq{widehatq}.
We will prove
\begin{itemize}
\item $\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty \leq 2^{3-d}\pi \enspace.$
\item $ \norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty \leq 2^{4-\frac{d}{2}} \enspace.$
\end{itemize}
The claim then follows from the triangle inequality.

\paragraph{Proof of the first bound}
Fix a $y\in\bit{n-1}$, we have
\begin{align*}
\norm{
\begin{pmatrix}
\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
\end{pmatrix} -
\begin{pmatrix}
\cos\br{\frac{\pi}{2}\xi_{y}}&-\sin\br{\frac{\pi}{2}\xi_{y}}\\
\sin\br{\frac{\pi}{2}\xi_{y}}&\cos\br{\frac{\pi}{2}\xi_{y}}
\end{pmatrix}
&= ~2\abs{\sin\br{\frac{\theta_y-\frac{\pi}{2}\xi_y}{2}}} \leq \abs{\frac{\pi}{2}\xi_y-\theta_y}\leq 2^{-d-1}\pi\enspace,\\
\norm{\left(
\begin{matrix}
e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
\end{matrix}
\right) -
\left(
\begin{matrix}
e^{\i2\pi\gamma_y^{+}} & 0\\
0 & e^{-\i2\pi\gamma_y^{+}}
\end{matrix}
\right)
&\leq ~\abs{2\pi\gamma_y^{+}-\frac{\alpha_y+\beta_y}{2}} \leq 2^{1-d}\pi\enspace,\\
\norm{\left(
\begin{matrix}
e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
\end{matrix}
\right) -
\left(
\begin{matrix}
e^{\i2\pi\gamma_y^{-}} & 0\\
0 & e^{-\i2\pi\gamma_y^{-}}
\end{matrix}
\right)
&\leq ~\abs{2\pi\gamma_y^{-}-\frac{\alpha_y-\beta_y}{2}} \leq 2^{1-d}\pi\enspace.
\end{align*}
Thus, by the triangle inequality and the decomposition for matrix $U\!\br{\alpha,\beta,\theta}$, we have for any $y\in\bit{n-1}$
\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{2\pi(\gamma_y^{+}+\gamma_y^{-}),2\pi(\gamma_y^{+}-\gamma_y^{-}),\frac{\pi}{2}\xi_y}}_\infty \leq 2^{3-d}\pi\enspace.
Therefore we have
\begin{align*}
\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty &= \norm{Q_{f,g,h} - \widehat{Q}_{f,g,h}}_\infty \\
& = \max_{y\in\bit{n-1}} \norm{U\!\br{2\pi(\gamma_y^{+}+\gamma_y^{-}),2\pi(\gamma_y^{+}-\gamma_y^{-}),\frac{\pi}{2}\xi_y} - U\!\br{\alpha_y,\beta_y,\theta_y}}_\infty\\
& \leq 2^{3-d}\pi\enspace.
\end{align*}

\paragraph{Proof of the second bound}
Fix a $y\in\bit{n-1}$, we have
$\abs{\alpha_y-\widetilde{\alpha}_y}\leq 2^{1-d}\pi$, and
$\abs{\beta_y-\widetilde{\beta}_y}\leq 2^{1-d}\pi$.
\begin{align}
\norm{\left(
\begin{matrix}
e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
\end{matrix}
\right) -
\left(
\begin{matrix}
e^{\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}}
\end{matrix}
\right)
&\leq \abs{\frac{\alpha_y+\beta_y}{2}-\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}\leq 2^{1-d}\pi\enspace, \label{eq:m1}\\
\norm{\left(
\begin{matrix}
e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
\end{matrix}
\right) -
\left(
\begin{matrix}
e^{\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} } & 0\\
0 & e^{-\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}}}
\end{matrix}
\right)
&\leq \abs{\frac{\alpha_y-\beta_y}{2}-\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} \leq 2^{1-d}\pi\enspace. \label{eq:m2}
\end{align}
Moreover, we have $\abs{\val{f(y)}-\widetilde{f}(y)}\leq 2^{-d}$ and thus
\begin{align}
\begin{pmatrix}
\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
\end{pmatrix} -
\begin{pmatrix}
\cos\br{\widetilde{\theta}_y}&-\sin\br{\widetilde{\theta}_y}\\
\sin\br{\widetilde{\theta}_y}&\cos\br{\widetilde{\theta}_y}
\end{pmatrix}
}_\infty \nonumber \\
= ~	&\norm{
\begin{pmatrix}
\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
\end{pmatrix}
}_\infty \nonumber \\
\leq ~&\norm{
\begin{pmatrix}
\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
\end{pmatrix}
}_2 \nonumber \\
= ~& \sqrt{2\br{\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}}^2+2\br{\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)}}^2}
\leq  2^{-\frac{d}{2}+\frac{3}{2}}\enspace \label{eq:m3},
\end{align}
where the last inequality is by the following fact.
\begin{fact}
For $a,b\in[0,1]$ and $d\in\N$, if $\abs{a-b}\leq 2^{-d}$, then $\abs{\sqrt{a}-\sqrt{b}}\leq 2^{-\frac{d}{2}+\frac{1}{2}}.$
\end{fact}
\begin{proof}
Let $\delta = 2^{-d+1}$. If $a\leq \delta$ and $b\leq \delta$, we have $\abs{\sqrt{a}-\sqrt{b}} \leq \max\st{\sqrt{a},\sqrt{b}}\leq \sqrt{\delta} = 2^{-\frac{d}{2}+\frac{1}{2}}$. If $a>\delta$ or $b>\delta$, we will have $a>\delta/2$ and $b>\delta/2$, and therefore
\abs{\sqrt{a}-\sqrt{b}} \leq \frac{1}{\sqrt{2\delta}}\cdot \abs{a-b} \leq 2^{-\frac{d}{2}-1} \enspace.
%	Note that for unitary matrices $A,B$ and $C$,
%	$$\norm{ABC-A'B'C'}_\infty\leq \norm{A-A'}_\infty+\norm{B-B'}_\infty+\norm{C-C'}_\infty\enspace.$$
Hence, we have by \eq{m1}, \eq{m2} and \eq{m3}, for any $y\in\bit{n-1}$,
\begin{align*}
\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty \leq 2^{4-\frac{d}{2}}\enspace.
\end{align*}
\begin{align*}
\norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty
~& =~ \norm{\widehat{Q}_{f,g,h} - \widetilde{Q}_{\cf,\cg,\ch}}_\infty \\
& = ~\max_{y\in\bit{n-1}}
\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty\\
& \leq ~2^{4-\frac{d}{2}}\enspace .
\end{align*}

\end{proof}

\begin{proof}[Proof of \thm{kactorssc}]
It is easy to see that the uniformity condition is satisfied.
Let $\kappa$ denote the key length.
Quantum circuit $\srssconsc$ applies $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$ after reading $\rep{\sigma}{T},\rep{f}{T},\rep{g}{T}$ and $\rep{h}{T}$.
To implement $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$, we need to realize each of
the $T = 10 (\secpar + 1) n$ unitary gates $L$.
Since each gate $L$ can be implemented in $\poly{n,\secpar,\klen}$ time,
the total construction time for $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$
is also $\poly{n,\secpar,\klen}$.

%%%%%%%%%%%%%%%%%%%%%%% trace distance %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Thus, it suffices to prove the requirement of \emph{Statistical Pseudorandomness} is satisfied.
Fix $\ket{\eta}\in\S(\H)$. Define three distributions:
\begin{itemize}
\item $\nu$ be the distribution of
with independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$,
and random functions $\rep{f}{T},\rep{g}{T},\rep{h}{T}: \bit{n-1}\to\bit{d}$.
\item $\widetilde{\nu}$ be the distribution of
with independent and uniformly random permutations
$\rep{\sigma}{T}\in S_{2^n}$,
and random functions
$\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}: \bit{n-1}\to[0,1)$.
\item $\mu$ be the Haar measure on $\S(\H)$.
\end{itemize}

%%%%%%%%%%%%%%%%%% H1 and H2 %%%%%%%%%%%%%
We first proof the trace distance between $\nu$ and $\widetilde{\nu}$ is negligible.
To this end, we construct a coupling $\gamma_0$ of $\nu$ and $\widetilde{\nu}$ by using the same permutation $\sigma_t$ and letting $f_t$ be the function satisfying $f_t(y)$ is the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$ (The same applies to $g_t$ and $h_t$).
Therefore, for any $\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0$,
we have
\begin{align}
\norm{\ket{\phi} - \ket{\varphi}}_2 ~
=	~& \norm{
\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
\!\!\ket{\eta}-
\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}
}_2 \nonumber\\
\leq  ~& \norm{
\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
- \csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}
}_\infty \nonumber\\
\leq ~& 2^{6-\frac{d}{2}} T = \frac{640 (\lambda+1)n}{\lambda^{\log \lambda}\cdot n^{\log n}}
\enspace, \nonumber
\end{align}
where the last inequality is from \fct{uprod} and \lem{ltildelclose}.
Thus, for any $l\in\poly{\secpar,n}$
\begin{align} \label{eq:h1_h2_rssc}
\E_{\ket{\phi}\sim \nu}\!\Br{\br{\ketbra{\phi}}^{\otimes l}}
\E_{\ket{\varphi}\sim \widetilde{\nu}}\!\Br{\br{\ketbra{\varphi}}^{\otimes l}}
}_1 \nonumber\\
\leq ~& \E_{\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0}\!\Br{
\norm{
\br{\ketbra{\phi}}^{\otimes l}
\br{\ketbra{\varphi}}^{\otimes l}
}_1} \nonumber\\
\leq ~& l \E_{\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0}\!\Br{
\norm{
\ketbra{\phi}
\ketbra{\varphi}
}_1} \nonumber\\
\leq ~& l
\br{\E_{\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0}\!\Br{
\norm{
\ket{\phi}\br{ \bra{\phi} - \bra{\varphi}}
}_1} + \E_{\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0}\!\Br{
\norm{
\br{ \ket{\phi} - \ket{\varphi}}\bra{\varphi}
\leq ~& 2l
\E_{\br{\ket{\phi}, \ket{\varphi}}\sim \gamma_0}\!\Br{
\norm{ \ket{\phi} - \ket{\varphi} }_2 } \leq \frac{1280 (\lambda+1)nl}{\lambda^{\log \lambda}\cdot n^{\log n}} \enspace.
\end{align}
%%%%%%%%%%%%%%%%%% H2 and H3 %%%%%%%%%%%%%
As for the trace distance between $\widetilde{\nu}$ and $\mu$, note that $\widetilde{\nu}$ is the output distribution of $T$-step parallel Kac's walk. Thus by \thm{mixing_time_w1_c}, we have
\begin{align*}
\wone{\widetilde{\nu}}{\mu} \leq \frac{1}{2^{\lambda n}} \enspace.
\end{align*}
So there exists a coupling of $\widetilde{v}$ and $\mu$, denoted by $\gamma_1$, that achieves
\begin{align*}
\E_{\br{\ket{\varphi}, \ket{\psi}}\sim \gamma_1}
\!\Br{ \norm{\ket{\varphi}-\ket{\psi}}_2 }\leq \frac{3}{2^{\lambda n}} \enspace .
\end{align*}
Therefore, similar to Eq. \eq{h1_h2_rssc}, we have for any $l\in\poly{\secpar,n}$
\begin{align} \label{eq:h2_h3_rssc}
\norm{
\E_{\ket{\varphi}\sim \widetilde{\nu}}\!\Br{\br{\ketbra{\varphi}}^{\otimes l}}
\E_{\ket{\psi}\sim \mu}\!\Br{\br{\ketbra{\psi}}^{\otimes l}}
\leq 2l
\E_{\br{\ket{\varphi}, \ket{\psi}}\sim \gamma_1}\!\Br{
\norm{ \ket{\varphi} - \ket{\psi} }_2 } \leq \frac{6l}{2^{\lambda n}}\enspace .
\end{align}
Finally, by the triangle inequality, Eqs.~\eq{h1_h2_rssc} and \eq{h2_h3_rssc}, we have
\begin{align*}
\norm{
\E_{\ket{\phi}\sim \nu}\!\Br{\br{\ketbra{\phi}}^{\otimes l}} -
\E_{\ket{\psi}\sim \mu}\!\Br{\br{\ketbra{\psi}}^{\otimes l}} }_1 \leq
\frac{1280 (\lambda+1)nl}{\lambda^{\log \lambda}\cdot n^{\log n}} +
\frac{6l}{2^{\lambda n}} = \negl{\secpar} \enspace.
\end{align*}
This establishes the \emph{Statistical Pseudorandomness} property.

\end{proof}

\subsection{Proof of \thm{complexprss}}
\begin{proof}[Proof of \thm{complexprss}]
The key length is bounded by $4T\cdot\poly{n,d} = \poly{n,\secpar}$
since $\tau$ and $F$ are efficient. Thus the condition of polynomial-bounded key length is satisfied.
To implement $\sgenc_k$, we need to realize each of
the $T = 10 (\secpar + 1) n$ unitary gates $L$
that compose $\sgenc_k$.
Since each gate $L$ can be implemented in $\poly{n,\secpar}$ time
due to the efficiency of $\tau$ and $F$,
the total construction time for $\sgenc_k$
is also $\poly{n,\secpar}$. Thus the uniformity is also satisfied.

We now prove the pseudorandomness property.
To this end, we consider three hybrids for an arbitrary $\ket{\phi}\in\S(\H)$ and $l\in\poly{\secpar,n}$:
\begin{itemize}
\item[H1:] \label{itm:h1c}
$\ket{\phi_k}^{\otimes l}$ for
$\ket{\phi_k} = \sgenc_k\!\ket{\phi}$
is chosen uniformly at random.

\item[H2:] \label{itm:h2c}
$\ket{\varphi_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}}^{\otimes l}$ for
\ket{\varphi_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}}
= \srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}\!\!\ket{\phi}
with independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$
and random functions $\rep{f}{T},\rep{g}{T},\rep{h}{T}: \bit{n-1}\to\bit{d}$.
is defined in \defi{kactosrssc}.

\item[H3:] \label{itm:h3c}
$\ket{\psi}^{\otimes l}$ for $\ket{\psi}$ chosen according to the Haar measure $\mu$ on $\S(\H)$.
\end{itemize}

We first prove that \itm{h1c}{H1} and \itm{h2c}{H2}
are computationally indistinguishable.
By the quantum-secure property of $\tau$ and $F$,
we know the following two situations are computationally indistinguishable for any polynomial-time quantum oracle algorithm $\A$ (see \lem{twokeys}):
\begin{itemize}
\item given oracle access to
$\tau_{r_1},\cdots,\tau_{r_T}$ and $F_{u_1},\cdots,F_{u_T},F_{s_1},\cdots,F_{s_T},F_{t_1},\cdots,F_{t_T}$
$\rep{r}{T}\in\K_1$ and $\rep{u}{T},\rep{s}{T},\rep{t}{T}\in\K_2$
are independent and uniformly random keys.

\item given oracle access to
independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$
and random functions
$\rep{f}{T},\rep{g}{T},\rep{h}{T}: \bit{n-1}\to\bit{d}$.
\end{itemize}
Thus, we have for any
polynomial-time quantum algorithm $\A$,
\abs{
\Pr\Br{\A\br{\ket{\phi_k}^{\otimes l}} = 1} -
\Pr\Br{\A\br{\ket{\varphi_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}}^{\otimes l}} = 1}
} = \negl{\secpar} \enspace .

For \itm{h2c}{H2} and \itm{h3c}{H3},
they are statistically indistinguishable since $\enssrssconsc$ defined in \defi{kactosrssc}
is an \rss~by \thm{kactorssc}.
Finally, by the triangle inequality we establish \itm{h1c}{H1} and \itm{h3c}{H3}
are computationally indistinguishable.
This accomplishes the proof.
\end{proof}

\subsection{Proof of \lem{good_start}}
\begin{proof}[Proof of \lem{good_start}]
Let graph $G_0=(V=[n],E_0=\emptyset)$.
We recursively define $G_1,\dots,G_l$ as follows:
given $G_i=([n],E_i)$,
choose a perfect matching $M_i$ of $[n]$
uniformly at random,
and set
$$G_{i+1}=\br{[n],E_{i+1}=E_i\cup M_i}\enspace.$$

\begin{align*}
&=\Pr\!\Br{G_l\text{ is disconnected}}\\
&=\Pr\!\Br{\exists ~S\subseteq [n]\text{ such that there is no edge between }S\text{ and }[n]\backslash S \text{ in } G_l}\\
&\leq \sum_{i\in[m],~ i\text{ is even}} \sum_{S\in \binom{[n]}{i}}\Pr\!\Br{\text{There is no edge between }S\text{ and }[n]\backslash S \text{ in } G_l}\\
&\leq \sum_{i\in[m],~ i\text{ is even}} \sum_{S\in \binom{[n]}{i}}
\br{\frac{\frac{i!}{2^{i/2}(i/2)!}\cdot\frac{(n-i)!}{2^{(n-i)/2}((n-i)/2)!}}{\frac{n!}{2^{n/2}(n/2)!}}	}^l\\
&=\sum_{i\in[m],~ i\text{ is even}} \sum_{S\in \binom{[n]}{i}}
\br{\frac{(n-i)(n-i-1)\cdots((n-i)/2+1)}{n(n-1)\cdots ((n+i)/2+1)}\cdot \frac{i(i-1)\cdots(i/2+1)}{((n+i)/2)\cdots(n/2+1)}}^l\\
&\leq \sum_{i\in[m],~ i\text{ is even}} \sum_{S\in \binom{[n]}{i}}
\br{\frac{i(i-1)\cdots(i/2+1)}{((n+i)/2)\cdots(n/2+1)}}^l\\
&\leq \sum_{i\in[m],~ i\text{ is even}} \sum_{S\in \binom{[n]}{i}}
\br{\frac{2i}{n+i}}^{il/2}\\
&\leq \sum_{i\in[m],~ i\text{ is even}} \binom{n}{i}\br{\frac{2}{3}}^{il/2}
\leq \br{1+\br{\frac{2}{3}}^{l/2}}^n-1
\leq n\br{\frac{2}{3}}^{l/2}\br{1+\br{\frac{2}{3}}^{l/2}}^{n-1}\enspace.
\end{align*}
When $l=5(1+c)\log n$ and $n$ is sufficiently large,
n\br{\frac{2}{3}}^{l/2}\leq n^{-c}
\quad\text{and}\quad
\br{1+\br{\frac{2}{3}}^{l/2}}^{n-1}\leq 2\enspace.
\end{proof}

\subsection{Proof of ~\thm{mixing_time_c}}
To prove \thm{mixing_time_c}, we extend the two-stage coupling introduced in real case to complex case. We have introduced the proportional coupling of complex space in \defi{prop_cpl_c}. We now extend the the non-Markovian coupling and then prove the mixing time. We assume $n=2m$.

%	Let $Y\sim \mu_{\C}$ where $\mu_{\C}$ is the Haar measure on $\C^{n}$. Then for all $1<c<\infty$ and any $1\leq i\leq n$,
%	$$
%	\Pr\!\Br{\abs{Y[i]}^2\leq \br{2n}^{-3c}}\leq 2\cdot \br{2n}^{1-c} \enspace.
%	$$

%	Let $g_1,\dots,g_{2n}$ be $2n$ i.i.d. real random variable with $\nd{0,1}$ distribution. We have
%	\begin{align*}
%		\Pr\!\Br{\abs{Y[i]}^2\leq \br{2n}^{-3c}} &= \Pr\!\Br{\frac{g_1^2+g_2^2}{\sum_{k=1}^{2n} g_k^2}\leq \br{2n}^{-3c}} \\
%		&\leq \Pr\!\Br{\frac{g_1^2}{\sum_{k=1}^{2n} g_k^2}\leq \br{2n}^{-3c}}\\
%		&\leq 2\cdot \br{2n}^{1-c} \enspace.
%	\end{align*}
%	The last inequality follows from \lem{marg_of_haar}.

\subsubsection{Non-Markovian Coupling}

\begin{definition}[Non-Markovian Coupling]\label{def:non_mark_cpl_c}
Fix $T_0\leq T\in\N$. We couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ in the following way:
\begin{enumerate}
\item For each $T_0\leq t < T$, choose a perfect matching $P_t = \st{\br{i^{(t)}_1, j^{(t)}_1},\dots,\br{i^{(t)}_m, j^{(t)}_m}}$ uniformly at random.

\item Set $\PP_{T,1} = \st{\st{1},\dots,\st{n}}$, and define a sequence of partitions $\st{\PP_{t,k}}_{T_0\leq t<T,~ 1\leq k\leq m+1}$ of $[n]$ in the same way as \defi{non_mark_cpl}.

\item If $\PP_{T_0,1}=\st{\st{1, \dots, n}}$, we couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ in the following way:
\begin{itemize}
\item Define the set
$$ H=\st{(t,k):T_0\leq t<T,~1\leq k\leq m,~\PP_{t,k}\neq\PP_{t,k+1}} \enspace.$$

\item Fix $T_0\leq t<T$, $X_{t}$ and $Y_{t}$, and we couple $X_{t+1}$ and $Y_{t+1}$ in the following way:
\begin{enumerate}
\item Set $X_{t,1}=X_t$ and $Y_{t,1}=Y_t$.
\item For $1\leq k\leq m$,
\begin{enumerate}
\item If $(t,k)\notin H$, we obtained $X_{t,k+1}$ and $Y_{t,k+1}$ in the same way as the proportional coupling defined in \defi{prop_cpl_c}.

\item If $(t,k)\in H$, let $$l^{(t)}_k = \sqrt{\abs{X_{t,k}[i^{(t)}_k]}^2+\abs{X_{t,k}[j^{(t)}_k]}^2}$$ and $${l'}^{(t)}_k = \sqrt{\abs{Y_{t,k}[i^{(t)}_k]}^2+\abs{Y_{t,k}[j^{(t)}_k]}^2}.$$ Let $U_0$ and $U_0'$ be the unitary operators which satisfy
\begin{align*}
\end{matrix}} = \br{\begin{matrix}
\end{matrix}}
\text{\quad and\quad}
\end{matrix}} = \br{\begin{matrix}
\end{matrix}}\enspace.
\end{align*}
Then we choose the best distribution $\nu$ among all joint distributions on $[0,1)\times [0,1)$ with both marginal distributions uniformly distributed on $[0,1)$ which maximizes the probability of the following events when $(\zeta,\zeta')\sim\nu$ and $\alpha, \beta$ are uniformly sample from $[0,2\pi)$:
\begin{align*}
\sum_{i\in S_{r}(t,k+1)} \abs{ X_{t,k+1} [i]}^2 &= \sum_{i\in S_{r}(t,k+1)} \abs{Y_{t,k+1} [i]}^2, \enspace 1\leq r\leq l_{t,k+1}
\end{align*}
\begin{align*}
X_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k,\alpha,\beta,\arcsin \sqrt{\zeta}, U_0X_{t,k}}\enspace,\\
Y_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k,\alpha,\beta,\arcsin \sqrt{\zeta'}, U_0'Y_{t,k}}\enspace.
\end{align*}
Then choose $(\zeta^{(t)}_k,{\zeta'}^{(t)}_k)\sim\nu$ and $\alpha^{(t)}_k, \beta^{(t)}_k$ uniformly from $[0,2\pi)$, and set
\begin{align*}
X_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k,\alpha^{(t)}_k,\beta^{(t)}_k,\arcsin \sqrt{\zeta^{(t)}_k}, U_0X_{t,k}}\enspace,\\
Y_{t,k+1} = G_{\C}\!\br{i^{(t)}_k,j^{(t)}_k,\alpha^{(t)}_k,\beta^{(t)}_k,\arcsin \sqrt{{\zeta'}^{(t)}_k}, U_0'Y_{t,k}}\enspace.
\end{align*}
\end{enumerate}
\item Set $X_{t+1} = X_{t,m+1}$ and $Y_{t+1} = Y_{t,m+1}$.
\end{enumerate}
\end{itemize}

\item If $\PP_{T_0,1}\neq \st{\st{1, \dots, n}}$, for $T_0\leq t\leq T$, we couple $X_{t+1}$ and $Y_{t+1}$ in the following way:
choose $2m$ independent angles
uniformly at random.
Additionally, $m$ independent real numbers $\zeta_1^{(t)}\dots,\zeta_m^{(t)}\in[0,1)$ are selected uniformly at random and compute
\theta_k^{(t)}=\arcsin\br{\sqrt{\zeta_k^{(t)}}}
for all $k\in\st{1,\dots,m}$.
We set
$$X_{t+1}=F_{\C}\!\br{P_t,\st{\alpha_k^{(t)}}_{k=1}^m,\st{\beta_k^{(t)}}_{k=1}^m,\st{\theta_k^{(t)}}_{k=1}^m,X_t} \enspace,$$
$$Y_{t+1}=F_{\C}\!\br{P_t,\st{\alpha_k^{(t)}}_{k=1}^m,\st{\beta_k^{(t)}}_{k=1}^m,\st{\theta_k^{(t)}}_{k=1}^m,Y_t} \enspace.$$

\end{enumerate}
\end{definition}

For $T_0\leq t \leq T$, $1\leq k \leq m+1$ and $1\leq i\leq n$ we define
A_{t,k}[i] = \abs{X_{t,k}[i]}^2\enspace,\quad B_{t,k}[i] = \abs{Y_{t,k}[i]}^2\enspace,
and define the event $\A(t,k)$ by
\A(t,k) = \st{\text{Eq. \eq{cond1_c} are satisfied for all $(t',k')\sqsubseteq (t,k)$ such that $T_0\leq t' \leq t$}}.
\begin{align}
\sum_{i\in S_{r}(t',k')}A_{t',k'}[i] &= \sum_{i\in S_{r}(t',k')} B_{t',k'}[i]\enspace, \quad 1\leq r\leq l_{t',k'}\enspace.\label{eq:cond1_c}
\end{align}

Similarly, we have the following two lemmas as \lem{never_drift} and \lem{good_dist} before.

\begin{lemma}
\label{lem:never_drift_c}
Fix $T_0<T$ and two chains $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ are coupled using the non-Markovian coupling defined in \defi{non_mark_cpl_c}.
Fix $T_0\leq t \leq T$ and $1\leq k \leq m+1$.
Then, on the event $\A(t,k)\cap\st{\PP_{T_0,1}=\st{1, \dots, n}}$, we have
\norm{A_{t',k'}-B_{t',k'}}_{1,S}\leq \norm{A_{T_0}-B_{T_0}}_{1}
for all $(t',k')\sqsubseteq(t,k)$ such that $T_0\leq t'\leq t$ and $S\in\PP_{t',k'}$. Moreover, for all $(t',k')\sqsubseteq(t,k)$ such that $T_0\leq t'\leq t$,
\norm{A_{t',k'}-B_{t',k'}}_{1}\leq n\norm{A_{T_0}-B_{T_0}}_{1}\enspace.
\end{lemma}
The proof of above lemma is the same as Lemma 4.4 in [37].

\begin{lemma} \label{lem:good_dist_c}
Fix positive reals $1<p<q$. Let $\zeta,\zeta'\sim\mathrm{Unif}[0,1)$ and let
S=A+B\zeta \quad\text{ and }
\quad S'=C+D\zeta'
for some $0\leq A,B,C,D\leq 1$ that satisfy
\abs{A-C},\abs{B-D}\leq n^{-q}\quad \text {and}\quad B,D\geq n^{-p}\enspace.
Then for sufficiently large $n$, there exists a coupling of $\zeta,\zeta'$ so that
\Pr\!\Br{S=S'}\geq 1-3 n^{-(q-p)}\enspace.
\end{lemma}

\begin{proof}
Without loss of generality, we assume $B\geq D$. The total variation distance between $S$ and $S'$ is
\begin{align*}
\norm{S-S'}_{\mathrm{TV}} &\leq 1 - \int_{\br{A,A+B}\cap \br{C,C+D}} \frac{1}{B}~ \de{x}\\
& \leq 1 - \int_{A+n^{-q}} ^{A+B-2n^{-q}}  \frac{1}{B}~ \de{x}\\
& = 1 - \br{B-3n^{-q}}\frac{1}{B}\\
& = \frac{3n^{-q}}{B} \leq 3 n^{-(q-p)}\enspace.
\end{align*}
This implicitly defines a coupling of $\zeta,\zeta'$ that satisfies $
\Pr\!\Br{S=S'}\geq 1-3 n^{-(q-p)}.
\end{proof}

\subsubsection{Proof of \thm{mixing_time_c}}
Let $a=30,~b=24,~ T_0=500\log n, ~ T_1=15\log n,~ T=T_0+T_1 = 515\log n$. We construct a coupling of two copies $\st{X_t}_{t\geq 0}, \st{Y_t}_{t\geq 0}$ with starting point $X_0\in \SC^{n}$ and $Y_0\sim \mu_{\C}$. The coupling is as follows:
\begin{enumerate}
\item Couple $\st{X_t}_{0\leq t\leq T_0}, \st{Y_t}_{0\leq t\leq T_0}$ by using the proportional coupling defined in \defi{prop_cpl_c}.
\item Couple $\st{X_t}_{T_0\leq t\leq T}, \st{Y_t}_{T_0\leq t\leq T}$ by using the non-markovian coupling defined in \defi{non_mark_cpl_c}.
\end{enumerate}
Define the event
\begin{align*}
\EE_1 &= \st{\norm{A_{T_0}-B_{T_0}}_1\geq n^{-a}}\enspace,\\
\EE_2 &= \st{\PP_{T_0,1}\neq \st{\st{1,\dots,n}}}\enspace,\\
\EE_3 &= \st{X_{T}\neq Y_{T}}\enspace.
\end{align*}
By \lem{coupling_lemma},
\begin{align}
\sup_{X_0\in \SC^{n}} \norm{\mathcal{L}\br{X_{T}}-\mu_{\C}}_{\mathrm{TV}}
&\leq \sup_{X_0\in \SC^{n}}\Pr\!\Br{\EE_3}\nonumber\\
&\leq \sup_{X_0\in \SC^{n}}
\br{\Pr\!\Br{\EE_1}+\Pr\!\Br{\EE_2}+\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}}\enspace.\label{eq:tv_c}
\end{align}
By \lem{contraction_lemma_c} and Markov's inequality, we have
\begin{align}
\Pr\!\Br{\EE_1} &= \Pr\!\Br{\norm{A_{T_0}-B_{T_0}}_1\geq n^{-a}}\nonumber\\
&\leq \Pr\!\Br{\norm{A_{T_0}-B_{T_0}}_2\geq n^{-a-1/2}}\nonumber\\
&\leq n^{2a+1}\cdot2\cdot\br{\frac{2}{3}}^{T_0}\leq \frac{1}{n^2}\enspace. \label{eq:event1_c}
\end{align}
Moreover, by \lem{good_start}, we have
\begin{align}
\Pr\!\Br{\EE_2}\leq 2n^{-2}\enspace.\label{eq:event2_c}
\end{align}
In order to bound $\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}$,
recall the definition of $\A(t,k)$ in \eq{cond1_c}.
If $\A(T,1)$ occurs, we have $\abs{X_t[i]}=\abs{Y_t[i]}$ for all $i\in\st{1,\dots,n}$.
Meanwhile, our coupling ensures $X_t[i]$ and $Y_t[i]$ have the same argument. This means $\A(T,1)$ implies $\EE_3^c$. As a result, $\EE_3\cap \EE_1^c \cap \EE_2^c$ implies $\A(T,1)^c \cap \EE_1^c \cap \EE_2^c$. So, we have
\begin{align}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}
\Pr\!\Br{\A(T,1)^c \cap \EE_1^c \cap \EE_2^c} \nonumber\\
\sum_{t=T_0}^{T-1} \Pr\!\Br{\A(t+1,1)^c \cap \A(t,1) \cap \EE_1^c \cap \EE_2^c} + \Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c} \nonumber \\
\sum_{t=T_0}^{T-1} \Pr\!\Br{\A(t,m+1)^c \cap \A(t,1) \cap \EE_1^c \cap \EE_2^c} + \Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c} \nonumber \\
\sum_{t=T_0}^{T-1} \sum_{k=1}^{m} \Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \EE_1^c \cap \EE_2^c} + \Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c}\enspace.\label{eq:e3_c}
\end{align}
Notice that if $\EE_2^c$ happens, we have
\sum_{i\in \st{1, \dots, n}} \abs{X_{T_0,1} [i]}^2 = \sum_{i\in \st{1, \dots, n}} \abs{Y_{T_0,1} [i]}^2 = 1\enspace .\\
\begin{align}
\Pr\!\Br{\A(T_0,1)^c \cap \EE_1^c \cap \EE_2^c}=0\enspace.\label{eq:imps_c}
\end{align}
Combining \eq{e3_c} and \eq{imps_c}, we have
\begin{equation}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}\leq \sum_{t=T_0}^{T-1} \sum_{k=1}^{m} \Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \EE_1^c \cap \EE_2^c}\enspace.\label{eq:e3final_c}
\end{equation}

We are now left to find a upper bound for $\Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \EE_1^c \cap \EE_2^c}$ when $T_0\leq t\leq T-1$ and $1\leq k\leq m$. To this end, we define
\B(t,k) = \st{\min_{(t',k')\sqsubseteq (t,k):t'\leq t}\min_{1\leq i\leq n} \abs{Y_{t',k'}[i]}^2\geq (2n)^{-b}}\enspace.
Note that
\begin{align}
&\Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \EE_1^c \cap \EE_2^c}\nonumber\\
&\hspace{2cm}\leq \Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} + \Pr\!\Br{\B(t,k)^c}\enspace.	\label{eq:e3single_c}
\end{align}
By \lem{marg_of_haar_c} and a union bound over all $(t',k')$ such that $(t',k')\sqsubseteq (t,k)$ and $t'\leq t$, we have for sufficiently large $n$,
\begin{equation}\label{eq:e3single2_c}
\Pr\!\Br{\B(t,k)^c} \leq 15\cdot 2^{1-\frac{b}{3}}\cdot n^{3-\frac{b}{3}}\log(n)\leq \frac{1}{n^4}\enspace.
\end{equation}

Next, we consider two cases of the term $\Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c}$ in \eq{e3single_c}: $(t,k)\notin H$ and $(t,k)\in H$,
where $H$ is defined in \defi{non_mark_cpl_c}.
In the case that $(t,k)\notin H$, we have $\PP_{t,k} = \PP_{t,k+1}$ and we apply the proportional coupling. Thus
$\A(t,k)$ implies $\A(t,k+1)$ which means
\begin{align}\label{eq:e3single11_c}
\Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c}=0\enspace.
\end{align}

In the other case that $(t,k)\in H$,
A=\sum_{i\in S_{v_{t,k}}(t,k+1)\backslash j^{(t)}_k} \abs{X_{t,k}[i]}^2\enspace,
\quad \quad
B= \abs{X_{t,k} [i^{(t)}_k]}^2+\abs{X_{t,k} [j^{(t)}_k]}^2\enspace,

C=\sum_{i\in S_{v_{t,k}}(t,k+1)\backslash j^{(t)}_k} \abs{Y_{t,k}[i]}^2
\enspace,\quad \quad
D= \abs{Y_{t,k}[i^{(t)}_k]}^2+\abs{Y_{t,k}[j^{(t)}_k]}^2\enspace,

S = A + B\zeta^{(t)}_k
\enspace,\quad \quad
S'= C + D{\zeta'}^{(t)}_k\enspace.
On the event $\A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c$, we have by \lem{never_drift}
\begin{align*}
\abs{A-C} \leq \norm{A_{t,k}-B_{t,k}}_1\leq n\norm{A_{T_0}-B_{T_0}}_1 \leq n^{1-a}\enspace.
\end{align*}
\begin{align*}
\abs{B-D} \leq \norm{A_{t,k}-B_{t,k}}_1\leq n\norm{A_{T_0}-B_{T_0}}_1 \leq n^{1-a}\enspace.
\end{align*}
Moreover, $D\geq n^{-(b+1)}$ and $B\geq D-\abs{B-D}\geq n^{-(b+1)}$ for sufficiently large $n$.
Then apply \lem{good_dist_c} with $p=b+1,~ q=a-1$, we know there exists a distribution $\nu_0$ such that when $\br{\zeta^{(t)}_k,{\zeta'}^{(t)}_k}\sim \nu_0$, we have
\Pr_{\br{\zeta^{(t)}_k,{\zeta'}^{(t)}_k}\sim \nu_0}\!
\Br{ S\neq S' | \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \leq 3 n^{-(a-b-2)}\enspace.
We choose the best distribution which maximizes the probability of event described in \eq{cond1_c} , so
\begin{align} \label{eq:e3single12_c}
&\Pr\!\Br{\A(t,k+1)^c \cap \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber\\
\leq  &\Pr\Br{\left.\A(t,k+1)^c \right| \A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber \\
\leq &\Pr_{\br{\zeta^{(t)}_k,{\zeta'}^{(t)}_k}\sim \nu_0}\Br{\left.\A(t,k+1)^c \right|\A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \nonumber \\
= &\Pr_{\br{\zeta^{(t)}_k,{\zeta'}^{(t)}_k}\sim \nu_0}\Br{\left.S\neq S' \right|\A(t,k) \cap \B(t,k) \cap \EE_1^c \cap \EE_2^c} \leq 3 n^{-(a-b-2)}\enspace.
\end{align}

Combining \eq{e3final_c}, \eq{e3single_c}, \eq{e3single11_c}, \eq{e3single12_c} and \eq{e3single2_c}, we have for sufficiently large $n$
\begin{align} \label{eq:event3_c}
\Pr\!\Br{\EE_3\cap \EE_1^c \cap \EE_2^c}\leq \sum_{t=T_0}^{T-1} \sum_{k=1}^{m} 3 n^{-(a-b-2)} + n^{-4} \leq  \frac{1}{n^2}\enspace.
\end{align}

By \eq{tv_c}, \eq{event1_c}, \eq{event2_c} and \eq{event3_c}, we have for sufficiently large $n$ and $T=515\log n$
\begin{align*}
\sup_{X_0\in \SC^{n}} \norm{\mathcal{L}\br{X_{T}}-\mu_{\C}}_{\mathrm{TV}} \leq {\frac{1}{2n}}\enspace.
\end{align*}

As for $T\geq 515\log n$,
by \lem{fcts_tv}
we have
\begin{align*}
\sup_{X_0\in \SC^{n}} \norm{\mathcal{L}\br{X_{T}}-\mu_{\C}}_{\mathrm{TV}}\leq 2\br{{\frac{1}{n}}}^{\lint{\frac{T}{515\log n}}} \leq \frac{1}{2^{\br{c/515-1}\log n-1}}\enspace.
\end{align*}

\subsection{Proof of \lem{realNNfullmap}}\label{app:proofofrealnnfullmap}
\begin{proof}[Proof of \lem{realNNfullmap}]
To see why $\widetilde{\NN}= \SR^{2^n}$, we prove $\SR^{2^n}\subseteq \widetilde{\NN}$ since $\widetilde{\NN} \subseteq \SR^{2^n}$ is trivial.
Given $\ket{\xi}\in\SR^{2^n}$, we prove
$\ket{\xi}\in \widetilde{\NN} $
by constructing a series of
$(\sigma_t,\cf_t)$ for $t\leq n$ such that
(we let $\KK_{\sigma_t,\cf_t} = \id$ for $t>n$).

The idea is to bisect $\KK_{\sigma_t,\cf_t}\cdots\KK_{\sigma_1,\cf_1}\ket{\eta}$ and $\ket{\xi}$ accordingly and recursively, always keeping the 2-norm of each part of the two vectors equal.

To illustrate the process in detail, we begin with indexing the entries of a vector in $\SR^{2^n}$ by a bit string of length $n$. In step $t\in[n]$, we divide the index set $\bit{n}$ into $2^t$ sets based on the first $t$ bits. For $y\in\bit{t}$, we define $S_y$ to be the set of all elements in $\bit{n}$ with prefix $y$. We then split $\ket{\eta}$ and $\ket{\xi}$ into $2^t$ sub-vectors, according to $S_y$ where $y\in\bit{t}$. Let $L_y$ be the function from $\SR^{2^n}$ to $\R$ that gives the length of the  sub-vector corresponding to $S_y$. Let
\ket{\eta_0}=\ket{\eta},\quad\ket{\eta_t}=\KK_{\sigma_t,\cf_t}\ket{\eta_{t-1}}\quad\text{for}\enspace t\in[n]\enspace.
Our goal is to construct $(\sigma_t,\cf_t)$ at each step $t\in[n]$, such that $L_y\!\br{\ket{\eta_t}}=
L_y\!\br{\ket{\xi}}$ for every $t\in[n-1],y\in\bit{t}$ and that $\ket{\eta_n}=\ket{\xi}$.

To accomplish this, we first define $\sigma_t \in S_{2^n}$ to be
$$\sigma_t(x)=\overline{x_tx_1\dots x_{t-1}x_{t+1}\dots x_n}\quad \text{for all }x\in\bit{n}\enspace.$$
For any $y\in\bit{t-1}$,
$\sigma_t$ matches every index in $S_{\overline{y0}}$
with another index in $S_{\overline{y1}}$
that shares a common suffix of length $n-t$.

Next, we move to construct $\cf_t$.
Define $\alpha_y$ for each $y\in\bit{t-1}$ as
$$\alpha_y=\begin{cases}\arccos\frac{L_{\overline{y0}}\br{\ket{\xi}}}{L_{y}\br{\ket{\xi}}}&\text{if }L_{y}\br{\ket{\xi}}\ne0\text{ and }t<n\enspace,\\
0&\text{if }L_{y}\br{\ket{\xi}}=0\text{ and }t<n\enspace.
\end{cases}$$
When $t=n$, we define $\alpha_y$ for $y\in\bit{n-1}$ to be any angle satisfying
\begin{align*}
\br{\ket{\xi}}_{\overline{y0}}&=L_y\br{\ket{\xi}}\cos\alpha_y \enspace,\\
\br{\ket{\xi}}_{\overline{y1}}&=L_y\br{\ket{\xi}}\sin\alpha_y \enspace.
\end{align*}
We want to design $\cf_{t}$ which controls the rotation of each index pair
to let each pair of indices between $S_{\overline{y0}}$ and $S_{\overline{y1}}$ (induced by $\sigma_t$) form an angle $\alpha_y$
with the $x$-axis in a two-dimensional Cartesian coordinate system.
To this end, for each $y\in\bit{t-1}$ and $z\in\bit{n-t}$,
we define $\beta_y(z)$ to be any angle satisfying
\begin{align*}
\br{\ket{\eta_{t-1}}}_{\overline{y0z}}&=\sqrt{\br{\ket{\eta_{t-1}}}_{\overline{y0z}}^2+\br{\ket{\eta_{t-1}}}_{\overline{y1z}}^2}\cos\beta_y(z) ,\\
\br{\ket{\eta_{t-1}}}_{\overline{y1z}}&=\sqrt{\br{\ket{\eta_{t-1}}}_{\overline{y0z}}^2+\br{\ket{\eta_{t-1}}}_{\overline{y1z}}^2}\sin\beta_y(z) ,
\end{align*}
and we define $\cf_t$ to be
\cf_t(\overline{yz})=\br{\alpha_y-\beta_y(z)}/(2\pi)
for all $y\in\bit{t-1}$ and $z\in\bit{n-t}$. It can be easily verified that
$$L_y\br{\ket{\eta_t}}=L_y\br{\ket{\xi}}\enspace\text{ for }\enspace t\in[n-1] \enspace\text{and} \enspace y\in\bit{t} ,$$
and $\ket{\eta_n}=\ket{\xi}$.
\end{proof}

\subsection{Proof of \lem{realNNepsnet}}
\begin{proof}[Proof of \lem{realNNepsnet}]
Let $\ket{u} = \csrsscons_{\rep{\sigma}{T},\rep{\cf}{T}}\!\!\ket{\eta}\in\widetilde{\NN}$ for some $\rep{\sigma}{T} \in S_{2^n}$ and $\rep{\cf}{T}: \bit{n-1}\to [0,1)$.
For every $t\in[T]$, we define $f_t$ by letting $f_t(y)$ be the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$.
It is evident that $\ket{v} = \srsscons_{\rep{\sigma}{T},\rep{f}{T}}\!\!\ket{\eta}\in\NN$.
\begin{align}
\norm{\ket{u} - \ket{v}}_2 ~
=	~& \norm{
\csrsscons_{\rep{\sigma}{T},\rep{\cf}{T}}\!\!\ket{\eta} -
\srsscons_{\rep{\sigma}{T},\rep{f}{T}}\!\!\ket{\eta}
}_2 \nonumber\\
\leq  ~& \norm{
\csrsscons_{\rep{\sigma}{T},\rep{\cf}{T}} -
\srsscons_{\rep{\sigma}{T},\rep{f}{T}}
}_\infty \leq  2^{1-d}\pi T = \frac{1030\pi (\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}} \enspace, \label{eq:uvclose}
\end{align}
where the last inequality is from \fct{uprod} and \lem{k_hk_close}.
This proves that $\NN$ is indeed an $\epsilon$-net
for $\widetilde{\NN}$ where $\epsilon  = \frac{1030\pi (\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}} =  \negl{\secpar}$. Combining with \cref{lem:realNNfullmap}, we conclude the result.
\end{proof}

\subsection{Proof of \thm{kactosrssc}}
To prove \thm{kactosrssc}, recall the ensemble of (infinitely many) unitary operators
$\enscsrssconsc \coloneq \st{\csrssconsc }_{\secpar}$ defined in \sect{proof_rssc}.

\begin{proposition}
For $T = 515 (\secpar + 1) n $,
the ensemble of unitary operator $\enscsrssconsc$
is a \csrss.
\end{proposition}

\begin{proof}
Note that a uniformly random
corresponds to a $T$-step parallel Kac's walk on $\SC^{2^n}$.
The proposition then follows from \thm{mixing_time_c} and the definition of \csrss.
\end{proof}

Let $\eta\in\S(H)$ be an arbitrary state. Denote
\NN = \st{
\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
\!\!\ket{\eta} }
\enspace \text{and}\enspace
\widetilde{\NN} = \st{\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}}\enspace.
We prove the following two lemmas.

\begin{lemma}\label{lem:complexNNfullmap}
$\widetilde{\NN}= \S(\H)$ .
\end{lemma}
\begin{proof}
We prove $\SC^{2^n}\subseteq \widetilde{\NN}$ since $\widetilde{\NN} \subseteq \SC^{2^n}$ is trivial.
Given $\ket{\xi}\in\SC^{2^n}$, we prove
$\ket{\xi}\in \widetilde{\NN} $
by constructing a series of
$(\sigma_t,\cf_t,\cg_t,\ch_t)$ for $t\leq n+1$ such that
(we let $\LL_{\sigma_t,\cf_t,\cg_t,\ch_t} = \id$ for $t>n+1$).

The proof idea is similar to Appendix \ref{app:proofofrealnnfullmap}. For any $t\in[n]$ and $y\in\bit{t}$, we use the definition of $S_y$, $L_y$ (change the domain to $\SC^{2^n}$), and $\ket{\eta_t}$ (change $\KK_{\sigma_t,\cf_t}$ to $\LL_{\sigma_t,\cf_t,\cg_t,\ch_t}$) there. Our goal is to construct $(\sigma_t,\cf_t,\cg_t,\ch_t)$ at each step $t\in[n+1]$, such that
L_y\!\br{\ket{\xi}}$ for every $t\in[n-1],y\in\bit{t}$ and that $\ket{\eta_{n+1}}=\ket{\xi}$.
That is, after $n-1$ steps, for every $y\in\bit{n-1}$, the two-dimensional sub-vectors of $\ket{\eta_n}$ and $\ket{\xi}$ induced by $S_y$ have the same length. In the final two steps, we adjust the two sub-vectors to be equal.

For any $t\in[n]$, let $\sigma_t$ be defined as in Appendix \ref{app:proofofrealnnfullmap}. We now construct $\cf_t,\cg_t,\ch_t$.

For any $t\in[n],y\in\bit{t-1},z\in\bit{n-t}$, suppose that
where $\theta^\eta_{y,0,z},\theta^\eta_{y,1,z},\theta^\xi_{y,0,z},\theta^\xi_{y,1,z}\in[0,2\pi),r^\eta_{y,0,z},r^\eta_{y,1,z},r^\xi_{y,0,z},r^\xi_{y,1,z}\in[0,1].$

For $t\in[n-1]$, define
$$\alpha_y=\begin{cases}\arccos\frac{L_{\overline{y0}}\br{\ket{\xi}}}{L_{y}\br{\ket{\xi}}}&\text{if }L_{y}\br{\ket{\xi}}\ne0\enspace,\\
\end{cases}$$
$$\rho_y(z)=\begin{cases}\arccos\frac{r^\eta_{y,0,z}}{\sqrt{\br{r^\eta_{y,0,z}}^2+\br{r^\eta_{y,1,z}}^2}}&\text{if }\br{r^\eta_{y,0,z}}^2+\br{r^\eta_{y,1,z}}^2>0\enspace,\\
\end{cases}$$

We then define $\cf_t,\cg_t,\ch_t$ to be
\begin{align*}
\cf_t(\overline{yz})&=\sin^2\br{\alpha_y-\rho_y(z)},\\
\cg_t(\overline{yz})&=\theta^\eta_{y,1,z}/(2\pi),\\
\ch_t(\overline{yz})&=\theta^\eta_{y,0,z}/(2\pi),
\end{align*}
for all $y\in\bit{t-1}$ and $z\in\bit{n-t}$. It can be easily verified that
$$L_y\br{\ket{\eta_t}}=L_y\br{\ket{\xi}}\enspace\text{ for }\enspace t\in[n-1] \enspace\text{and} \enspace y\in\bit{t} .$$
For $t=n$, we set the second entry of the sub-vector of $\ket{\eta_{n-1}}$ induced by $S_y$ to zero for all $y\in\bit{n-1}$. That is, define
\begin{align*}
\cf_n(y)&=\begin{cases}
\frac{\br{r^\eta_{y,1}}^2}{\br{r^\eta_{y,0}}^2+\br{r^\eta_{y,1}}^2}&\text{if }\br{r^\eta_{y,0}}^2+\br{r^\eta_{y,1}}^2>0,\\
\end{cases}\\
\cg_n(y)&=-\theta^\eta_{y,0}/(2\pi),\\
\ch_n(y)&=\br{\pi-\theta^\eta_{y,1}}/(2\pi),
\end{align*}
for all $y\in\bit{n-1}$. We then have $$L_y\br{\ket{\eta_n}}=L_y\br{\ket{\eta_{n-1}}}=L_y\br{\ket{\xi}}\text{ for all }y\in\bit{n-1}.$$ For the final step, we let $\sigma_{n+1}=\sigma_n$, and define
\begin{align*}
\cf_{n+1}(y)&=\begin{cases}
\frac{\br{r^\xi_{y,1}}^2}{\br{r^\xi_{y,0}}^2+\br{r^\xi_{y,1}}^2}&\text{if }\br{r^\xi_{y,0}}^2+\br{r^\xi_{y,1}}^2>0,\\
\end{cases}\\
\cg_{n+1}(y)&=\theta^\xi_{y,0}/(2\pi),\\
\ch_{n+1}(y)&=-\theta^\xi_{y,1}/(2\pi),
\end{align*}
for all $y\in\bit{n-1}$. It can be easily verified that $\ket{\eta_{n+1}}=\ket{\xi}$.
\end{proof}

\begin{lemma}\label{lem:complexNNepsnet}
There exists an $\epsilon  = \negl{\secpar}$ such that
is an $\epsilon$-net for
$\S(\H)$ .
\end{lemma}

\begin{proof}
By \lem{complexNNfullmap}, it suffices to prove that
there exists an $\epsilon  = \negl{\secpar}$ such that
$\NN$ is an $\epsilon$-net for $\widetilde{\NN}$.

Let $\ket{u} = \csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}\in\widetilde{\NN}$ for some $\rep{\sigma}{T} \in S_{2^n}$ and $\rep{\cf}{T}$,
$\rep{\ch}{T}: \bit{n-1}\to [0,1)$.
For every $t\in[T]$, we define $f_t$ by letting $f_t(y)$ be the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$.
We define $g_t$ and $h_t$ for $t\in[T]$ in the same way.
It is evident that $\ket{v} = \srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
\!\!\ket{\eta}\in\NN$.
\begin{align}
\norm{\ket{u} - \ket{v}}_2 ~
=	~& \norm{
\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
\!\!\ket{\eta}-
\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}
}_2 \nonumber\\
\leq  ~& \norm{
\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
- \csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}
}_\infty \nonumber\\
\leq ~& 2^{6-\frac{d}{2}} T = \frac{32960(\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}}
\enspace, \label{eq:uvclosec}
\end{align}
where the last inequality is from \fct{uprod} and \lem{ltildelclose}.
This proves that $\NN$ is indeed an $\epsilon$-net
for $\widetilde{\NN}$ where $\epsilon  = \frac{32960(\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}} = \negl{\secpar}$.
\end{proof}

\begin{proof}[Proof of \thm{kactosrssc}]
It is easy to see that the uniformity condition is satisfied.
Let $\kappa$ denote the key length.
Quantum circuit $\srssconsc$ applies $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$ after reading $\rep{\sigma}{T},\rep{f}{T},\rep{g}{T}$ and $\rep{h}{T}$.
To implement $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$, we need to realize each of
the $T = 515 (\secpar + 1) n$ unitary gates $L$.
Since each gate $L$ can be implemented in $\poly{n,\secpar,\klen}$ time,
the total construction time for $\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}$
is also $\poly{n,\secpar,\klen}$.

In conjunction with \lem{complexNNepsnet}, it suffices to prove the existence of a good distribution $\widetilde{\nu}$ meeting the requirement in \defi{trssb}. Fix $\ket{\eta}\in\S(\H)$.
Define three distributions:
\begin{itemize}
\item $\nu$ be the distribution of
with independent and uniformly random permutations $\rep{\sigma}{T}\in S_{2^n}$,
and random functions $\rep{f}{T},\rep{g}{T},\rep{h}{T}: \bit{n-1}\to\bit{d}$.
\item $\widetilde{\nu}$ be the distribution of
with independent and uniformly random permutations
$\rep{\sigma}{T}\in S_{2^n}$,
and random functions
$\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}: \bit{n-1}\to[0,1)$.
\item $\mu$ be the Haar measure on $\S(\H)$.
\end{itemize}
Note that $\widetilde{\nu}$ is the output distribution of $T$-step parallel Kac's walk in $\SC^{2^n}$. Thus by \thm{mixing_time_c}, we have
\begin{align}\label{eq:closetvc}
\tv{\widetilde{\nu} - \mu} \leq \frac{1}{2^{\secpar n - 1}} = \negl{\secpar}\enspace.
\end{align}
We are left to show the Wasserstein $\infty$-distance between $\nu$ and $\widetilde{\nu}$ is negligible.
To this end, we construct a coupling $\gamma_0$ of $\nu$ and $\widetilde{\nu}$ by using the same permutation $\sigma_t$ and letting $f_t$ be the function satisfying $f_t(y)$ is the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$ (The same applies to $g_t$ and $h_t$).
\begin{align}
W_{\infty} ( \nu, \widetilde{\nu}) =
~& \lim_{p\to\infty}\br{ \inf_{\gamma\in\Gamma(\nu,\widetilde{\nu})} \E_{(\ket{v},\ket{u})\sim \gamma}\!\Br{\norm{\ket{v}-\ket{u}}_2^p} }^{1/p} \nonumber\\
\leq ~& \lim_{p\to\infty}\br{ \E_{(\ket{v},\ket{u})\sim \gamma_0}\!\Br{\norm{\ket{v}-\ket{u}}_2^p} }^{1/p}
~\overset{\text{(Eq.~\eq{uvclosec})}}{\leq} ~
\frac{32960(\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}}= \negl{\secpar} \label{eq:closewinftyc}\enspace .
\end{align}
Thus we conclude the result.
\end{proof}

%\begin{proof}[Proof of \lem{complexNNepsnet}]
%	By \lem{complexNNfullmap}, it suffices to prove that
%	there exists an $\epsilon  = \negl{\secpar}$ such that
%	$\NN$ is an $\epsilon$-net for $\widetilde{\NN}$.
%	Let $\ket{u} = \csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}\in\widetilde{\NN}$ for some $\rep{\sigma}{T} \in S_{2^n}$ and $\rep{\cf}{T}$,
%		$\rep{\cg}{T}$,
%		$\rep{\ch}{T}: \bit{n-1}\to [0,1)$.
%	For every $t\in[T]$, we define $f_t$ by letting $f_t(y)$ be the $d$ digits after the binary point in $\widetilde{f}_t(y)$ for all $y\in\bit{n-1}$.
%	We define $g_t$ and $h_t$ for $t\in[T]$ in the same way.
%	It is evident that $\ket{v} = \srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
%		\!\!\ket{\eta}\in\NN$.
%	And
%	\begin{align}
%		\norm{\ket{u} - \ket{v}}_2 ~
%	 =	~& \norm{
%			\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
%		\!\!\ket{\eta}-
%			\csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}\!\!\ket{\eta}
%		}_2 \nonumber\\
%	\leq  ~& \norm{
%			\srssconsc_{\rep{\sigma}{T},\rep{f}{T},\rep{g}{T},\rep{h}{T}}
%			- \csrssconsc_{\rep{\sigma}{T},\rep{\cf}{T},\rep{\cg}{T},\rep{\ch}{T}}
%		}_\infty \nonumber\\
%	\leq ~& 2^{6-\frac{d}{2}} T = \frac{32960(\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}}
%	\enspace, \label{eq:uvclosec}
%	\end{align}
%	where the last inequality is from \fct{uprod} and \clm{ltildelclose}.
%	This proves that $\NN$ is indeed an $\epsilon$-net
%	for $\widetilde{\NN}$ where $\epsilon  = \frac{32960(\secpar+1)n}{\secpar^{\log \secpar} n^{\log n}} = \negl{\secpar}$.
%	\begin{claim} \label{clm:ltildelclose}
%	Let $\sigma\in S_{2^n}$
%	and $\cf,\cg,\ch:\bit{n-1}\to[0,1)$.
%	Let $f:\bit{n-1}\to \bit{d}$ be the function satisfying for any $y\in\bit{n-1}$,
%	$f(y)$ is the $d$ digits after the binary point in $\widetilde{f}(y)$. The same applies to $g$ and $h$.
%	Then
%	$$
%	{
%		\norm{ L_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}
%	}_\infty }
%	\leq 2^{6-\frac{d}{2}} \enspace ,
%	$$
%	where $L_{\sigma,f,g,h}=U_{\sigma^{-1}} Q_{f,g,h} U_{\sigma}$
%	is defined in \eq{normalq} and
%	$\widetilde{L}_{\sigma,\cf,\cg,\ch}
%	= U_{\sigma^{-1}} \widetilde{Q}_{\cf,\cg,\ch} U_{\sigma}$
%	is defined in \eq{widetildeq}.
%	\end{claim}
%	\begin{proof}[Proof of \clm{ltildelclose}]
%		Recall the unitary $\widehat{L}_{\sigma,f,g,h}=U_{\sigma^{-1}} \widehat{Q}_{f,g,h} U_{\sigma}$ defined in \eq{widehatq}.
%		We will prove
%		\begin{itemize}
%			\item $\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty \leq 2^{3-d}\pi \enspace.$
%			\item $ \norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty \leq 2^{4-\frac{d}{2}} \enspace.$
%		\end{itemize}
%		The claim then follows from the triangle inequality.
%		\paragraph{Proof of the first bound}
%		Fix a $y\in\bit{n-1}$, we have
%	\norm{
%	\begin{pmatrix}
%		\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
%		\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
%	\end{pmatrix} -
%	\begin{pmatrix}
%		\cos\br{\frac{\pi}{2}\xi_{y}}&-\sin\br{\frac{\pi}{2}\xi_{y}}\\
%		\sin\br{\frac{\pi}{2}\xi_{y}}&\cos\br{\frac{\pi}{2}\xi_{y}}
%	\end{pmatrix}
%	}_\infty
%	&= ~2\abs{\sin\br{\frac{\theta_y-\frac{\pi}{2}\xi_y}{2}}} \leq \abs{\frac{\pi}{2}\xi_y-\theta_y}\leq 2^{-d-1}\pi\enspace,\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i2\pi\gamma_y^{+}} & 0\\
%			0 & e^{-\i2\pi\gamma_y^{+}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq ~\abs{2\pi\gamma_y^{+}-\frac{\alpha_y+\beta_y}{2}} \leq 2^{1-d}\pi\enspace,\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i2\pi\gamma_y^{-}} & 0\\
%			0 & e^{-\i2\pi\gamma_y^{-}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq ~\abs{2\pi\gamma_y^{-}-\frac{\alpha_y-\beta_y}{2}} \leq 2^{1-d}\pi\enspace.
%Thus, by the triangle inequality and the decomposition for matrix $U\!\br{\alpha,\beta,\theta}$, we have for any $y\in\bit{n-1}$
%\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{2\pi(\gamma_y^{+}+\gamma_y^{-}),2\pi(\gamma_y^{+}-\gamma_y^{-}),\frac{\pi}{2}\xi_y}}_\infty \leq 2^{3-d}\pi\enspace.
%Therefore we have
%	\begin{align*}
%		\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty &= \norm{Q_{f,g,h} - \widehat{Q}_{f,g,h}}_\infty \\
%		& = \max_{y\in\bit{n-1}} \norm{U\!\br{2\pi(\gamma_y^{+}+\gamma_y^{-}),2\pi(\gamma_y^{+}-\gamma_y^{-}),\frac{\pi}{2}\xi_y} - U\!\br{\alpha_y,\beta_y,\theta_y}}_\infty\\
%		& \leq 2^{3-d}\pi\enspace.
%	\end{align*}
%	\paragraph{Proof of the second bound}
%	Fix a $y\in\bit{n-1}$, we have
%	$\abs{\alpha_y-\widetilde{\alpha}_y}\leq 2^{1-d}\pi$, and
%	$\abs{\beta_y-\widetilde{\beta}_y}\leq 2^{1-d}\pi$.
%	Therefore,
%	\begin{align}
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq \abs{\frac{\alpha_y+\beta_y}{2}-\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}\leq 2^{1-d}\pi\enspace, \label{eq:m1}\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq \abs{\frac{\alpha_y-\beta_y}{2}-\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} \leq 2^{1-d}\pi\enspace. \label{eq:m2}
%	\end{align}
%	Moreover, we have $\abs{\val{f(y)}-\widetilde{f}(y)}\leq 2^{-d}$ and thus
%	\begin{align}
%	&\norm{
%	\begin{pmatrix}
%		\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
%		\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
%	\end{pmatrix} -
%	\begin{pmatrix}
%		\cos\br{\widetilde{\theta}_y}&-\sin\br{\widetilde{\theta}_y}\\
%		\sin\br{\widetilde{\theta}_y}&\cos\br{\widetilde{\theta}_y}
%	\end{pmatrix}
%	}_\infty \nonumber \\
%	= ~	&\norm{
%	\begin{pmatrix}
%		\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
%		\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
%	\end{pmatrix}
%	}_\infty \nonumber \\
%	\leq ~&\norm{
%	\begin{pmatrix}
%		\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
%		\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
%	\end{pmatrix}
%	}_2 \nonumber \\
%	= ~& \sqrt{2\br{\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}}^2+2\br{\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)}}^2}
%	\leq  2^{-\frac{d}{2}+\frac{3}{2}}\enspace \label{eq:m3},
%	\end{align}
%	where the last inequality is by the following fact.
%	\begin{fact}
%		For $a,b\in[0,1]$ and $d\in\N$, if $\abs{a-b}\leq 2^{-d}$, then $\abs{\sqrt{a}-\sqrt{b}}\leq 2^{-\frac{d}{2}+\frac{1}{2}}.$
%	\end{fact}
%	\begin{proof}
%	Let $\delta = 2^{-d+1}$. If $a\leq \delta$ and $b\leq \delta$, we have $\abs{\sqrt{a}-\sqrt{b}} \leq \max\st{\sqrt{a},\sqrt{b}}\leq \sqrt{\delta} = 2^{-\frac{d}{2}+\frac{1}{2}}$. If $a>\delta$ or $b>\delta$, we will have $a>\delta/2$ and $b>\delta/2$, and therefore
%	$$
%	\abs{\sqrt{a}-\sqrt{b}} \leq \frac{1}{\sqrt{2\delta}}\cdot \abs{a-b} \leq 2^{-\frac{d}{2}-1} \enspace.
%	$$\end{proof}
%%	Note that for unitary matrices $A,B$ and $C$,
%%	$$\norm{ABC-A'B'C'}_\infty\leq \norm{A-A'}_\infty+\norm{B-B'}_\infty+\norm{C-C'}_\infty\enspace.$$
%	Hence, we have by \eq{m1}, \eq{m2} and \eq{m3}, for any $y\in\bit{n-1}$,
%	\begin{align*}
%		\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty \leq 2^{4-\frac{d}{2}}\enspace.
%	\end{align*}
%	Therefore,
%	\begin{align*}
%		\norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty
%		~& =~ \norm{\widehat{Q}_{f,g,h} - \widetilde{Q}_{\cf,\cg,\ch}}_\infty \\
%		& = ~\max_{y\in\bit{n-1}}
%		\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty\\
%		& \leq ~2^{4-\frac{d}{2}}\enspace .
%	\end{align*}
%	\end{proof}

%\subsection{Proof of \clm{ltildelclose}}
%\begin{proof}[Proof of \clm{ltildelclose}]
%		Recall the unitary $\widehat{L}_{\sigma,f,g,h}=U_{\sigma^{-1}} \widehat{Q}_{f,g,h} U_{\sigma}$ defined in \eq{widehatq}.
%		We will prove
%		\begin{itemize}
%			\item $\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty \leq 2^{3-d}\pi \enspace.$
%			\item $ \norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty \leq 2^{5-d} \enspace.$
%		\end{itemize}
%		The claim then follows from the triangle inequality.
%		\paragraph{Proof of the first bound}
%		Fix a $y\in\bit{n-1}$, we have
%	\norm{
%	\begin{pmatrix}
%		\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
%		\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
%	\end{pmatrix} -
%	\begin{pmatrix}
%		\cos\br{\xi_{y}}&-\sin\br{\xi_{y}}\\
%		\sin\br{\xi_{y}}&\cos\br{\xi_{y}}
%	\end{pmatrix}
%	}_\infty
%	&= ~2\abs{\sin\br{\frac{\theta_y-\xi_y}{2}}} \leq \abs{\xi_y-\theta_y}\leq 2^{-m-1}\pi\enspace,\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\gamma_y^{+}} & 0\\
%			0 & e^{-\i\gamma_y^{+}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq ~\abs{\gamma_y^{+}-\frac{\alpha_y+\beta_y}{2}} \leq 2^{1-m}\pi\enspace,\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\gamma_y^{-}} & 0\\
%			0 & e^{-\i\gamma_y^{-}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq ~\abs{\gamma_y^{-}-\frac{\alpha_y-\beta_y}{2}} \leq 2^{1-m}\pi\enspace.
%Thus, by the triangle inequality and the decomposition for matrix $U\!\br{\alpha,\beta,\theta}$, we have for any $y\in\bit{n-1}$
%\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\gamma_y^{+}+\gamma_y^{-},\gamma_y^{+}-\gamma_y^{-},\xi_y}}_\infty \leq 2^{3-m}\pi\enspace.
%Therefore we have
%	\begin{align*}
%		\norm{L_{\sigma,f,g,h} - \widehat{L}_{\sigma,f,g,h}}_\infty &= \norm{Q_{f,g,h} - \widehat{Q}_{f,g,h}}_\infty \\
%		& = \max_{y\in\bit{n-1}} \norm{U\!\br{\gamma_y^{+}+\gamma_y^{-},\gamma_y^{+}-\gamma_y^{-},\xi_y} - U\!\br{\alpha_y,\beta_y,\theta_y}}_\infty\\
%		& \leq 2^{3-m}\pi\enspace.
%	\end{align*}
%	\paragraph{Proof of the second bound}
%	Fix a $y\in\bit{n-1}$, we have
%	$\abs{\alpha_y-\widetilde{\alpha}_y}\leq 2^{1-m}\pi$, and
%	$\abs{\beta_y-\widetilde{\beta}_y}\leq 2^{1-m}\pi$.
%	Therefore,
%	\begin{align}
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y+\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y+\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq \abs{\frac{\alpha_y+\beta_y}{2}-\frac{\widetilde{\alpha}_y+\widetilde{\beta}_y}{2}}\leq 2^{1-m}\pi\enspace, \label{eq:m1}\\
%	\norm{\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\alpha_y-\beta_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\alpha_y-\beta_y}{2}}}
%		\end{matrix}
%	\right) -
%	\left(
%		\begin{matrix}
%			e^{\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} } & 0\\
%			0 & e^{-\i\br{\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}}}
%		\end{matrix}
%	\right)
%	}_\infty
%	&\leq \abs{\frac{\alpha_y-\beta_y}{2}-\frac{\widetilde{\alpha}_y-\widetilde{\beta}_y}{2}} \leq 2^{1-m}\pi\enspace. \label{eq:m2}
%	\end{align}
%	Moreover, we have $\abs{\val{f(y)}-\widetilde{f}(y)}\leq 2^{-m}$ and thus
%	\begin{align}
%	&\norm{
%	\begin{pmatrix}
%		\cos\br{\theta_{y}}&-\sin\br{\theta_{y}}\\
%		\sin\br{\theta_{y}}&\cos\br{\theta_{y}}
%	\end{pmatrix} -
%	\begin{pmatrix}
%		\cos\br{\widetilde{\theta}_y}&-\sin\br{\widetilde{\theta}_y}\\
%		\sin\br{\widetilde{\theta}_y}&\cos\br{\widetilde{\theta}_y}
%	\end{pmatrix}
%	}_\infty \nonumber \\
%	= ~	&\norm{
%	\begin{pmatrix}
%		\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
%		\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
%	\end{pmatrix}
%	}_\infty \nonumber \\
%	\leq ~&\norm{
%	\begin{pmatrix}
%		\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)} & -\sqrt{\val{f(y)}}+\sqrt{\widetilde{f}(y)}\\
%		\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)} & \sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}
%	\end{pmatrix}
%	}_2 \nonumber \\
%	= ~& 2\br{\sqrt{1-\val{f(y)}}-\sqrt{1-\widetilde{f}(y)}}^2+2\br{\sqrt{\val{f(y)}}-\sqrt{\widetilde{f}(y)}}^2
%	\leq  2^{-m+3}\enspace \label{eq:m3},
%	\end{align}
%	where the last inequality is by the following claim.
%	\begin{claim}
%		For $a,b\in[0,1]$ and $m\in\N$, if $\abs{a-b}\leq 2^{-m}$, then $\abs{\sqrt{a}-\sqrt{b}}\leq 2^{-\frac{m}{2}+\frac{1}{2}}.$
%	\end{claim}
%	\begin{proof}
%	Let $\delta = 2^{-m+1}$. If $a\leq \delta$ and $b\leq \delta$, we have $\abs{\sqrt{a}-\sqrt{b}} \leq \max\st{\sqrt{a},\sqrt{b}}\leq \sqrt{\delta} = 2^{-\frac{m}{2}+\frac{1}{2}}$. If $a>\delta$ or $b>\delta$, we will have $a>\delta/2$ and $b>\delta/2$, and therefore
%	$$
%	\abs{\sqrt{a}-\sqrt{b}} \leq \frac{1}{\sqrt{2\delta}}\cdot \abs{a-b} \leq 2^{-\frac{m}{2}-1} \enspace.
%	$$\end{proof}
%%	Note that for unitary matrices $A,B$ and $C$,
%%	$$\norm{ABC-A'B'C'}_\infty\leq \norm{A-A'}_\infty+\norm{B-B'}_\infty+\norm{C-C'}_\infty\enspace.$$
%	Hence, we have by \eq{m1}, \eq{m2} and \eq{m3}, for any $y\in\bit{n-1}$,
%	\begin{align*}
%		\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty \leq 2^{5-m}\enspace.
%	\end{align*}
%	Therefore,
%	\begin{align*}
%		\norm{\widehat{L}_{\sigma,f,g,h} - \widetilde{L}_{\sigma,\cf,\cg,\ch}}_\infty
%		~& =~ \norm{\widehat{Q}_{f,g,h} - \widetilde{Q}_{\cf,\cg,\ch}}_\infty \\
%		& = ~\max_{y\in\bit{n-1}}
%		\norm{U\!\br{\alpha_y,\beta_y,\theta_y}-U\!\br{\widetilde{\alpha}_y,\widetilde{\beta}_y,\widetilde{\theta}_y}}_\infty\\
%		& \leq ~2^{5-m}\enspace .
%	\end{align*}

%\subsection{{Proof of~\cref{lem:h1h2_c}}}
%\begin{proof}[Proof of~\cref{lem:h1h2_c}]
% For $i\in\set{0,1,\dots,l}$, denote
%	 \[A_i=\E\!\Br{ \br{\ketbra{{\phi}_k}}^{\otimes l-i}\br{\ketbra{\widetilde{\phi}_k}}^{\otimes i} }\enspace.\]
%	 By the triangle inequality, it suffices to prove for $i\in[l]$,
%	 $$\norm{A_{i-1}-A_{i}}_1 \leq 2^{4-m}\pi T \enspace .$$
%	 For $k = \br{r_1,u_1,s_1,t_1,r_2,u_2,s_2,t_2,\dots,r_T,u_T,s_T,t_T} \in \br{\K_1\times\K_2\times\K_2\times\K_2}^T$ and $w\in [T]$, denote
%	 \begin{align*}
%	 	\ket{\widetilde{\phi}^w_k} = \widetilde{L}_{\tau_{r_w},F_{u_w},F_{s_w},F_{t_w}}\cdots \widetilde{L}_{\tau_{r_2},F_{u_2},F_{s_2},F_{t_2}}\widetilde{L}_{\tau_{r_1},F_{u_1},F_{s_1},F_{t_1}}\ket{\eta}\enspace,\\
%	 	\ket{\phi^w_k} = L_{\tau_{r_w},F_{u_w},F_{s_w},F_{t_w}}\cdots L_{\tau_{r_2},F_{u_2},F_{s_2},F_{t_2}}L_{\tau_{r_1},F_{u_1},F_{s_1},F_{t_1}}\ket{\eta}\enspace.
%	 \end{align*}
%	 We have
%	 \begin{align*}
%		\norm{A_{i-1}-A_{i}}_1
%		\leq~&\expec{\norm{ \br{\ketbra{{\phi}^T_k}}^{\otimes l-i}\otimes\br{\ketbra{{\phi}^T_k}-\ketbra{\widetilde{\phi}^{~T}_k}}\otimes\br{\ketbra{\widetilde{\phi}^{~T}_k}}^{\otimes i-1} }_1}\\
%		=~&\E\!\Br{\norm{\ketbra{{\phi}^T_k}-\ketbra{\widetilde{\phi}^{~T}_k} }_1}\\
%		\leq
%		~&\expec{\norm{ L_{\tau_{r_T},F_{u_T},F_{s_T},F_{t_T}}
%		\ketbra{{\phi}^{T-1}_k}
%		\br{ L_{\tau_{r_T},F_{u_T},F_{s_T},F_{t_T}} -
%			 \widetilde{L}_{\tau_{r_T},F_{u_T},F_{s_T},F_{t_T}} }
%		}_1 }\\
%		&+\expec{\norm{
%		L_{\tau_{r_T},F_{u_T},F_{s_T},F_{t_T}}
%		\br{\ketbra{{\phi}^{T-1}_k} - \ketbra{\widetilde{\phi}^{~T-1}_k}}
%		\widetilde{L}_{\tau_{r_T},F_{u_T},F_{s_T},F_{t_T}}
%		}_1}\\
%		&+\expec{\norm{