The distribution state sequence $\Psi$ associated with a distributional
unitary synthesis problem in $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ is
required to be in $\mathsf{stateBQP}$, instead of some notion of
$\mathsf{stateSZK}_{{\mathrm{HV}}}$. In the definition of
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ we require that the simulator can
output the state between an honest verifier and honest prover after each
round. It is easy to see that any reasonable definition of
$\mathsf{stateSZK}_{{\mathrm{HV}}}$ results in the same class as
$\mathsf{stateBQP}$.

###### Honest-verifier versus general zero knowledge.

A natural question is whether this definition of zero knowledge can be
meaningfully generalized to the _malicious verifier_ setting, where the
interaction between the honest prover and verifier can be efficiently
simulated even if the verifier deviates from the protocol. This is typically
the notion of zero knowledge that is useful in the cryptographic setting. It
is known that in both the classical and quantum settings, the malicious
verifier and honest verifier definitions of statistical zero knowledge proofs
yield the same complexity classes (i.e.,
$\mathsf{SZK}=\mathsf{SZK}_{\mathrm{HV}}$ and
$\mathsf{QSZK}=\mathsf{QSZK}_{\mathrm{HV}}$) [Oka96, GSV98, Wat06]. We leave
studying stronger notions of zero knowledge protocols for unitary synthesis to
future work:

######  Open Problem 8.

Is there a meaningful notion of malicious verifier zero knowledge for unitary
synthesis problems, and how is that related to the honest verifier setting
that we considered here?

##  Part II Uhlmann Transformation Problem: Definitions and Structural Results

###  5 Definition of the Uhlmann Transformation Problem

In this section we formally define the Uhlmann Transformation Problem as a
unitary synthesis problem. We also define a “succinct” version of it, in which
the two input states $\ket{C},\ket{D}$ that specify an instance of the Uhlmann
Transformation Problem, while exponentially complex, nonetheless have a
polynomial-size description.

####  5.1 Uhlmann’s theorem and canonical isometries

We begin by recalling Uhlmann’s theorem.

######  Theorem 5.1 (Uhlmann’s theorem).

Let $\ket{\psi}_{\mathsf{AB}}$ and $\ket{\varphi}_{\mathsf{AB}}$ be pure
states on registers $\mathsf{AB}$ and denote their reduced states on register
$\mathsf{A}$ by $\rho_{\mathsf{A}}$ and $\sigma_{\mathsf{A}}$, respectively.
Then, there exists a unitary $U_{\mathsf{B}}$ acting only on register
$\mathsf{B}$ such that

$\mathrm{F}(\rho_{\mathsf{A}},\sigma_{\mathsf{A}})=|\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
U_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}|^{2}\,.$

We now would like to define a unitary synthesis problem $(U_{x})_{x}$
corresponding to Uhlmann’s theorem. Intuitively, whenever the string $x$
represents a pair of bipartite states $\ket{\psi},\ket{\varphi}$ (by
specifying circuits for them, for example), the unitary $U_{x}$ should satisfy
the conclusion of Uhlmann’s theorem. However are several subtleties that
arise. First, the unitary $U_{\mathsf{B}}$ in Theorem 5.1 is not unique;
outside of the support of $\rho_{\mathsf{B}}=\mbox{\rm
Tr}_{\mathsf{A}}\left(\ket{\psi}\\!\\!\bra{\psi}_{\mathsf{AB}}\right)$,
$U_{B}$ can act arbitrarily. This motivates defining a _canonical_ Uhlmann
transformation $W$ corresponding to a pair of bipartite states
$\ket{\psi}_{\mathsf{A}\mathsf{B}},\ket{\varphi}_{\mathsf{A}\mathsf{B}}$. A
natural candidate is
$W=\operatorname{sgn}(\mathrm{Tr}_{\mathsf{A}}(\ket{\varphi}\\!\\!\bra{\psi}))$
where for any linear operator $K$ with singular value decomposition $U\Sigma
V^{\dagger}$, we define
$\operatorname{sgn}(K)=U\operatorname{sgn}(\Sigma)V^{\dagger}$ with
$\operatorname{sgn}(\Sigma)$ denoting replacing all the nonzero entries of
$\Sigma$ with $1$ (which is the same as the usual sign function since all
singular values are non-negative). A proof that $W$ is a partial isometry
satisfying $\mathrm{F}(\rho,\sigma)=|\bra{\varphi}\textnormal{id}\otimes
W\ket{\psi}|^{2}$ can be found in [MY23, Lemma 7.6]. This Uhlmann
transformation is also _minimal_ in the sense that any other partial isometry
$\tilde{W}$ that achieves the same guarantee satisfies
$W^{\dagger}W\leq\tilde{W}^{\dagger}\tilde{W}$.

However, this definition of canonical Uhlmann transformation is not robust in
the sense that arbitrarily small changes to the states
$\ket{\psi},\ket{\varphi}$ could result in arbitrarily large changes in $W$ as
measured by, say, the operator norm. Consider the following two-qutrit
example:

$\displaystyle\ket{\psi}$
$\displaystyle=\sqrt{1-\epsilon}\ket{00}+\sqrt{\epsilon/2}\ket{11}+\sqrt{\epsilon/2}\ket{22}\,,$
$\displaystyle\ket{\tilde{\psi}}$
$\displaystyle=\sqrt{1-\epsilon}\ket{00}+\sqrt{\epsilon/2}\ket{12}+\sqrt{\epsilon/2}\ket{21}\,,$
$\displaystyle\ket{\varphi}$ $\displaystyle=\ket{\psi}\,.$

The Uhlmann isometry $W$ corresponding to $(\ket{\psi},\ket{\varphi})$ is
simply the identity operator on $\mathbb{C}^{3}$. On the other hand, the
Uhlmann isometry $\tilde{W}$ corresponding to
$(\ket{\tilde{\psi}},\ket{\varphi})$ can be computed as

$\tilde{W}=\ket{0}\\!\\!\bra{0}+\ket{1}\\!\\!\bra{2}+\ket{2}\\!\\!\bra{1}\,.$

In other words, it swaps $\ket{1}$ with $\ket{2}$ and keeps $\ket{0}$
unchanged. The difference $W-\tilde{W}$ has operator norm at least $2$, but
the difference $\ket{\psi}-\ket{\tilde{\psi}}$ has norm at most $\epsilon$,
which can be arbitrarily small. We would like a definition of the canonical
Uhlmann isometry that is insensitive to extremely small changes in the states
$\ket{\psi},\ket{\varphi}$.

Finally, for convenience, we only focus on bipartite states that have the same
number of qubits on each side. This is not a severe assumption as we can
always pad the smaller register with ancilla zero qubits, which does not
affect the existence of an Uhlmann transformation.

These points motivate the following definition of canonical Uhlmann isometry.
First, some notation: for $\eta\in\mathbb{R}$ and an operator $K$ with
singular value decomposition $U\Sigma V^{\dagger}$, we define
$\operatorname{sgn}_{\eta}(K)$ to be the operator

$\operatorname{sgn}_{\eta}(K)=U\operatorname{sgn}_{\eta}(\Sigma)V^{\dagger}$

where $\operatorname{sgn}_{\eta}(\Sigma)$ denotes the projection onto the
eigenvectors of $\Sigma$ with eigenvalue greater than $\eta$. In other words,
$\operatorname{sgn}_{\eta}$ is the scalar function that behaves like the usual
$\operatorname{sgn}$ function on inputs $|x|>\eta$, and maps inputs
$|x|\leq\eta$ to 0; this scalar function is applied to the diagonal matrix
$\Sigma$ in the usual way. We also write $\operatorname{sgn}(K)$ to denote
$\operatorname{sgn}_{0}(K)$. Using $\operatorname{sgn}_{\eta}$ instead of
$\operatorname{sgn}$ in the definition of the Uhlmann partial isometry removes
the sensitivity to arbitrarily small changes to the input states discussed
above. The parameter $\eta$ can be thought of as a cutoff below which changes
in the input states are ignored.

######  Definition 5.2 (Canonical Uhlmann partial isometry).

The _canonical Uhlmann partial isometry with cutoff $\eta$_ corresponding to a
pair of pure states $(\ket{\psi}_{\mathsf{AB}},\ket{\varphi}_{\mathsf{AB}})$
is defined as

$W=\operatorname{sgn}_{\eta}(\mathrm{Tr}_{\mathsf{A}}(\ket{\varphi}\\!\\!\bra{\psi}))\,.$
(5.1)

For brevity we call $W$ the _canonical $\eta$-Uhlmann isometry_.

We verify several basic properties of the canonical $\eta$-Uhlmann isometry.

######  Proposition 5.3.

The map $W$ defined in Equation 5.1 is a partial isometry, and satisfies the
following. Let $\rho,\sigma$ denote the reduced density matrices of
$\ket{\psi},\ket{\varphi}$, respectively, on register $\mathsf{A}$.

  1. 1.

(Approximate Uhlmann transformation) The isometry $W$ approximately maps
$\ket{\psi}$ to $\ket{\varphi}$, i.e.,

$|\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
W_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}|^{2}\geq\mathrm{F}(\rho_{\mathsf{A}},\sigma_{\mathsf{A}})-2\eta\dim(\mathsf{B})\,,$

  2. 2.

(Minimality) For all partial isometries $R_{\mathsf{B}}$ satisfying

$\mathrm{F}(\rho_{\mathsf{A}},\sigma_{\mathsf{A}})=|\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
R_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}|^{2}\,,$

we have $W^{\dagger}W\leq R^{\dagger}R$.

###### Proof.

Let $X,Y$ be unitary operators acting on register $\mathsf{B}$ such that

$\displaystyle\ket{\psi}=\sqrt{\rho}\otimes X\ket{\Omega}$
$\displaystyle\ket{\varphi}=\sqrt{\sigma}\otimes Y\ket{\Omega}$

where $\ket{\Omega}=\sum_{i}\ket{i}_{\mathsf{A}}\ket{i}_{\mathsf{B}}$ is the
unnormalized maximally entangled state in the standard basis. Let $U\Sigma
V^{\dagger}$ denote the singular value decomposition of
$(\sqrt{\rho}\sqrt{\sigma})^{\top}$, the transpose of
$\sqrt{\rho}\sqrt{\sigma}$ with respect to the standard basis. Then the proof
of [MY23, Lemma 7.6] shows that

$W=YU\operatorname{sgn}_{\eta}(\Sigma)V^{\dagger}X^{\dagger}\,.$ (5.2)

The fact that $W$ is a partial isometry is clear: since the matrices $X,U,V,Y$
are unitary and $\operatorname{sgn}_{\eta}(\Sigma)$ is a projection, it can be
written in the form $W=\Pi F$ where
$\Pi=XU\operatorname{sgn}_{\eta}(\Sigma)U^{\dagger}X^{\dagger}$ is a
projection and $F=XUV^{\dagger}Y^{\dagger}$ is a unitary. To show the
approximate transformation statement, we note that the proof of [MY23, Lemma
7.6] shows that

$\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
W_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}=\mathrm{Tr}(\sqrt{\sigma}\sqrt{\rho}\operatorname{sgn}_{\eta}(\sqrt{\rho}\sqrt{\sigma}))$

where $\operatorname{sgn}_{\eta}(K)$ for an arbitrary operator $K$ with
singular value decomposition $R\Sigma Q^{\dagger}$ is defined to be
$R\operatorname{sgn}_{\eta}(\sigma)Q^{\dagger}$. The preceding centered
equation is equal to

$\displaystyle\mathrm{Tr}(\sqrt{\sigma}\sqrt{\rho}\operatorname{sgn}(\sqrt{\rho}\sqrt{\sigma}))-\mathrm{Tr}\Big{(}\sqrt{\sigma}\sqrt{\rho}\,\big{(}\operatorname{sgn}(\sqrt{\rho}\sqrt{\sigma})-\operatorname{sgn}_{\eta}(\sqrt{\rho}\sqrt{\sigma}\big{)}\,)\Big{)}$
$\displaystyle\qquad\geq\sqrt{\mathrm{F}(\sigma,\rho)}-\mathrm{Tr}\Big{(}\sqrt{\sigma}\sqrt{\rho}\,\big{(}\operatorname{sgn}(\sqrt{\rho}\sqrt{\sigma})-\operatorname{sgn}_{\eta}(\sqrt{\rho}\sqrt{\sigma}\big{)}\,)\Big{)}$
(5.3)

where in the last line we used that
$\mathrm{F}(\sigma,\rho)=\mathrm{Tr}(|\sqrt{\sigma}\sqrt{\rho}|)^{2}$ and that
$\mathrm{Tr}(K\operatorname{sgn}(K^{\dagger}))=\mathrm{Tr}(|K|)$ for all
operators $K$. Letting $U\Sigma V^{\dagger}$ denote the singular value
decomposition of $(\sqrt{\rho}\sqrt{\sigma})^{\top}$, we have that
$\overline{U}\Sigma V^{\top}$ is the singular value decomposition of
$\sqrt{\sigma}\sqrt{\rho}$. Thus Equation 5.3 is equal to

$\sqrt{\mathrm{F}(\sigma,\rho)}-\mathrm{Tr}(\Sigma(\operatorname{sgn}(\Sigma)-\operatorname{sgn}_{\eta}(\Sigma)))\geq\sqrt{\mathrm{F}(\sigma,\rho)}-\eta\dim(\mathsf{B})$

where we used that
$\operatorname{sgn}(\Sigma)-\operatorname{sgn}_{\eta}(\Sigma))$ is the
projector onto the eigenvectors of $\Sigma$ with eigenvalue smaller than
$\eta$. Squaring both sides, we get:

$\Big{(}\sqrt{\mathrm{F}(\sigma,\rho)}-\eta\dim(\mathsf{B})\Big{)}^{2}=\mathrm{F}(\sigma,\rho)-2\sqrt{\mathrm{F}(\sigma,\rho)}\eta\dim(\mathsf{B})+\eta^{2}\dim(\mathsf{B})^{2}\geq\mathrm{F}(\sigma,\rho)-2\eta\dim(\mathsf{B})$

where we used that $0\leq\mathrm{F}(\sigma,\rho)\leq 1$. This shows the
approximation statement.

For the minimality statement, we note that the proof of Uhlmann’s theorem
[Wil13, Theorem 9.2.1] shows that

$|\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
R_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}|^{2}=|\mathrm{Tr}(\sqrt{\sigma}\sqrt{\rho}\,(Y^{\dagger}RX)^{\top})|^{2}=|\mathrm{Tr}((Y^{\dagger}RX)(\sqrt{\sigma}\sqrt{\rho})^{\top})|^{2}$

where in the last step we used $|\mathrm{Tr}(K)|=|\mathrm{Tr}(K^{\top})|$ for
all operators $K$. Let $Q=Y^{\dagger}RX$, and note that the singular value
decomposition of $(\sqrt{\sigma}\sqrt{\rho})^{\top}$ is $V\Sigma U^{\dagger}$.
By the Cauchy-Schwarz inequality for matrices, we have

$\displaystyle|\mathrm{Tr}((Y^{\dagger}RX)(\sqrt{\sigma}\sqrt{\rho})^{\top})|^{2}$
$\displaystyle=|\mathrm{Tr}(QV\Sigma^{1/2}\Sigma^{1/2}U^{\dagger})|^{2}\leq\mathrm{Tr}(QV\Sigma
V^{\dagger}Q^{\dagger})\,\mathrm{Tr}(U\Sigma U^{\dagger})$
$\displaystyle\qquad=\mathrm{Tr}(\Sigma
V^{\dagger}Q^{\dagger}QV)\,\mathrm{Tr}(\Sigma)\leq\mathrm{Tr}(\Sigma)^{2}$

where in the last line we used that the operator norm of
$V^{\dagger}Q^{\dagger}QV$ is at most $1$. If
$|\bra{\varphi}_{\mathsf{AB}}(\textnormal{id}_{\mathsf{A}}\otimes
R_{\mathsf{B}})\ket{\psi}_{\mathsf{AB}}|^{2}=\mathrm{F}(\rho,\sigma)^{2}=\mathrm{Tr}(|\sqrt{\sigma}\sqrt{\rho}|)=\mathrm{Tr}(\Sigma)^{2}$,
then this implies that

$\mathrm{Tr}(\Sigma V^{\dagger}Q^{\dagger}QV)=\mathrm{Tr}(\Sigma)\,.$

Since $\Sigma$ and $V^{\dagger}Q^{\dagger}QV$ are positive semidefinite, and
$V^{\dagger}Q^{\dagger}QV$ has operator norm at most $1$, this implies that
$V^{\dagger}Q^{\dagger}QV$ acts as the identity on the support of $\Sigma$; in
particular, $V^{\dagger}Q^{\dagger}QV\geq\operatorname{sgn}(\Sigma)$ in the
positive semidefinite ordering. This is equivalent to

$R^{\dagger}R\geq XV\operatorname{sgn}(\Sigma)V^{\dagger}X^{\dagger}\geq
XV\operatorname{sgn}_{\eta}(\Sigma)V^{\dagger}X^{\dagger}=W^{\dagger}W$

as desired. ∎

####  5.2 Worst-case Uhlmann transformation problem

We now define explicit and succinct descriptions of quantum circuits.

######  Definition 5.4 (Explicit and succinct descriptions of quantum
circuits).

An _explicit description_ of a unitary quantum circuit $C$ is a sequence
$(1^{n},g_{1},g_{2},\ldots)$ where $1^{n}$ represents in unary the number of
qubits that $C$ acts on, and $g_{1},g_{2},g_{3},\ldots$ is a sequence of
unitary gates.

A _succinct description_ of a quantum circuit $C$ is a pair $(1^{n},\hat{C})$
where $\hat{C}$ is a description of a classical circuit111111Here, we think of
$\hat{C}$ as being a list of AND, OR, and NOT gates. that takes as input an
integer $t$ in binary and outputs the description a unitary gate $g_{t}$
coming from some universal gate set, as well as the (constant-sized) set of
qubits that $g_{t}$ acts on. Together, the gates $g_{1},\ldots,g_{T}$ describe
a circuit $C$ acting on $n$ qubits; we will always denote the classical
circuit with a hat (e.g. $\hat{C}$) and use the same latter without a hat
(e.g. $C$) for the associated quantum circuit.

We make a few remarks about the definitions of explicit and succinct
descriptions of quantum circuits:

  1. (i)

The length of an explicit description of a quantum circuit is polynomial in
the number of qubits it acts on as well as the number of gates in the circuit.

  2. (ii)

In a succinct description of a quantum circuit $C$, the size of the circuit
may be exponentially larger than the length of the description
$(1^{n},\hat{C})$. However, the number of qubits that $C$ acts on is
polynomial (in fact, at most linear) in the description length.

  3. (iii)

For a succinct description, we provide the number of qubits $n$ in the quantum
circuit explicitly in unary because given only the classical circuit $\hat{C}$
it may be difficult to compute the the number of qubits that the quantum
circuit $C$ acts on.

We now define two variants of the Uhlmann Transformation Problem. In the
first, the two bipartite states are described by explicit circuit
descriptions, and in the second they are described by succinct circuit
descriptions.

######  Definition 5.5 (Valid Uhlmann instances).

We say that a string $x\in\\{0,1\\}^{*}$ is a _valid Uhlmann instance_ if it
encodes a tuple $(1^{n},C,D)$ where $C,D$ are explicit descriptions of
_unitary_ circuits that each act on $2n$ qubits. We say that $x$ is a _valid
succinct Uhlmann instance_ if $x=(1^{n},\hat{C},\hat{D})$ is a succinct
description of a pair $(C,D)$ of unitary circuits that each act on $2n$ qubits
for some $n$.

We further say that a valid (possibly succinct) Uhlmann instance $x$ is a
_fidelity- $\kappa$ instance_ if the reduced states $\rho,\sigma$ of the
states $\ket{C}=C\ket{0^{2n}}$, $\ket{D}=D\ket{0^{2n}}$ on the first $n$
qubits satisfy $\mathrm{F}(\rho,\sigma)\geq\kappa$.

######  Definition 5.6 (Uhlmann Transformation Problem).

Let $\kappa,\eta:\mathbb{N}\to[0,1]$ be functions. The _$(\kappa,\eta)$
-Uhlmann Transformation Problem_ is the unitary synthesis problem
$\textsc{Uhlmann}_{\kappa,\eta}=(U_{x})_{x\in\\{0,1\\}^{*}}$ where whenever
$x$ is a fidelity-$\kappa(n)$ Uhlmann instance specifying a pair $(C,D)$ of
unitary circuits that each act on $2n$ qubits for some $n$, then $U_{x}$ is
the canonical $\eta$-Uhlmann isometry for the states $\ket{C}=C\ket{0^{2n}}$
and $\ket{D}=D\ket{0^{2n}}$, with $U_{x}$ acting on the last $n$ qubits.
Otherwise if $x$ is not a valid Uhlmann instance, then we define $U_{x}=0$
(i.e., a partial isometry with zero-dimensional support).

The _$(\kappa,\eta)$ -Succinct Uhlmann Transformation Problem_, denoted by
$\textsc{SuccinctUhlmann}_{\kappa,\eta}$, is the sequence $(U_{x})_{x}$ where
whenever $x$ is a valid fidelity-$\kappa(n)$ succinct Uhlmann instance
specifying a pair $(C,D)$ of unitary circuits that each act on $2n$ qubits for
some $n$, then $U_{x}$ is the canonical $\eta$-Uhlmann isometry for the states
$\ket{C}=C\ket{0^{2n}}$ and $\ket{D}=D\ket{0^{2n}}$, with $U_{x}$ acting on
the last $n$ qubits; if $x$ is not a valid succinct Uhlmann instance, then we
define $U_{x}=0$.

Although we defined the Uhlmann and SuccinctUhlmann problems as parameterized
by the cutoff parameter $\eta$ for the sake of robustness of the definitions,
we will see next that when we focus on _distributional_ versions of these
problems the $\eta$ parameter can be without loss of generality set to $0$.
The cutoff parameter $\eta$ only really matters for complexity results about
solving Uhlmann or SuccinctUhlmann in the _worst-case_.

####  5.3 Distributional Uhlmann transformation problem

To define average case versions of the Uhlmann Transformation Problems we
specify a distribution state $\ket{\psi_{x}}$ for every valid (succinct or
non-succinct) Uhlmann instance $x$. If $x$ specifies a pair of circuits
$(C,D)$ on $2n$ qubits each, the distribution state $\ket{\psi_{x}}$ is also
on $2n$ qubits. As we argue below, a natural choice of distribution state is
$\ket{\psi_{x}}=C\ket{0^{2n}}$. When $x$ represents a fidelity-$1$ Uhlmann
instance the Uhlmann transformation $U_{x}$ by definition maps
$\ket{\psi_{x}}$ to $D\ket{0^{2n}}$.

######  Definition 5.7 (Distributional Uhlmann Transformation Problems).

We define a state sequence
$\Psi_{\textsc{Uhlmann}}=(\ket{\psi_{x}})_{x\in\\{0,1\\}^{*}}$ as follows: for
all $x\in\\{0,1\\}^{*},$

$\ket{\psi_{x}}=\begin{cases}\ket{C}&\text{if $x=(1^{n},C,D)$ is valid Uhlmann
instance,}\\\ 0&\text{otherwise.}\end{cases}$

Then, the _distributional $(\kappa,\eta)$-Uhlmann Transformation Problem_ is
the distributional unitary synthesis problem
$\textsc{DistUhlmann}_{\kappa,\eta}=(\textsc{Uhlmann}_{\kappa,\eta},\Psi_{\textsc{Uhlmann}})$.

Analogously, we define the state family
$\Psi_{\textsc{SuccinctUhlmann}}=(\ket{\psi_{x}})_{x}$ as follows: for all
$x\in\\{0,1\\}^{*},$

$\ket{\psi_{x}}=\begin{cases}\ket{C}&\text{if $x=(1^{n},\hat{C},\hat{D})$ is
valid succinct Uhlmann instance,}\\\ 0&\text{otherwise.}\end{cases}$

The _distributional $(\kappa,\eta)$-Succinct Uhlmann Transformation Problem_
is the distributional unitary synthesis problem
$\textsc{DistSuccinctUhlmann}_{\kappa,\eta}=(\textsc{SuccinctUhlmann}_{\kappa,\eta},\Psi_{\textsc{SuccinctUhlmann}})$.

We now argue that this choice of distribution state is natural for the Uhlmann
Transformation Problems: being able to solve the distributional Uhlmann
Transformation Problems in the average-case essentially coincides with being
able to perform the Uhlmann transformation corresponding to a pair of
(succinctly or non-succinctly described) states. The next proposition captures
this equivalence in the _high $\kappa$ regime_, where $\kappa$ is close to
$1$.

######  Proposition 5.8.

Let $M=(M_{x})_{x}$ be a quantum algorithm where for each valid
fidelity-$\kappa(n)$ Uhlmann (resp. Succinct Uhlmann) instance $x=(1^{n},C,D)$
(resp. $x=(1^{n},\hat{C},\hat{D})$),

$\mathrm{F}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\ket{D}\\!\\!\bra{D}\Big{)}\geq\kappa(n)-\delta(n)$
(5.4)

for some error function $\delta(n)$, where $M_{x}$ acts on the second $n$
qubits of $\ket{C}$. Then $M$ implements $\textsc{DistUhlmann}_{\kappa,0}$
(resp. $\textsc{DistSuccinctUhlmann}_{\kappa,0}$) with average-case error
$6\sqrt{1-\kappa(n)}+\sqrt{\delta(n)}$.

Conversely, suppose that a (uniform or nonuniform) quantum algorithm
$M=(M_{x})_{x}$ implements $\textsc{DistUhlmann}_{\kappa,0}$ (resp.
$\textsc{DistSuccinctUhlmann}_{\kappa,0}$) with average-case error $\delta$.
Then for all valid fidelity-$\kappa(n)$ Uhlmann (resp. Succinct Uhlmann)
instances $x=(1^{n},C,D)$ (resp. $x=(1^{n},\hat{C},\hat{D})$), the following
holds:

$\mathrm{F}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\ket{D}\\!\\!\bra{D}\Big{)}\geq\Big{(}1-\delta(n)-5\sqrt{1-\kappa(n)}\Big{)}^{2}\,.$

###### Proof.

We will prove this proposition for the case of Uhlmann instances; the case of
succinct Uhlmann instances is entirely analogous. Throughout the proof we
abuse notation slightly and write $\delta=\delta(n)$ and $\kappa=\kappa(n)$.

We begin with the first part of the proposition. Fix a valid
fidelity-$\kappa(n)$ Uhlmann instance $x=(1^{n},C,D)$. Let $\eta=0$ and let
$W$ denote the canonical $\eta$-Uhlmann partial isometry corresponding to
$(\ket{C},\ket{D})$. Let $U=W+(\textnormal{id}-W^{\dagger}W)$, which is a
(non-partial) isometry. Let $\Phi(K)=UKU^{\dagger}$ and note that it is a
channel completion of the partial isometry $W$. (This is in fact the most
straightforward channel completion: it simply applies $W$ on the support of
$W$, and the identity on the orthogonal complement of the support of $W$.) We
will show that

$\mathrm{td}((\textnormal{id}\otimes\Phi)\ket{C}\\!\\!\bra{C},\ket{D}\\!\\!\bra{D})\leq
5\sqrt{1-\kappa}\,.$ (5.5)

Before proving this, let us see how this implies the first part of the
proposition. By the triangle inequality, we have

$\displaystyle\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),(\textnormal{id}\otimes\Phi)(\ket{C}\\!\\!\bra{C})\Big{)}$
$\displaystyle\qquad\leq\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\ket{D}\\!\\!\bra{D}\Big{)}+\mathrm{td}\Big{(}\ket{D}\\!\\!\bra{D},(\textnormal{id}\otimes\Phi)(\ket{C}\\!\\!\bra{C})\Big{)}$
$\displaystyle\qquad\leq\sqrt{1-\kappa+\delta}\,+5\sqrt{1-\kappa}$
$\displaystyle\qquad\leq 6\sqrt{1-\kappa}+\sqrt{\delta}$

where in the third line we applied the Fuchs-van de Graaf inequality to
Equation 5.4 and also used Equation 5.5. This shows that one the state
$\ket{C}$, $M_{x}$ behaves (approximately) like a channel completion of the
Uhlmann partial isometry. By Definition 3.5, this means that $M_{x}$
(approximately) implements the DistUhlmann problem as claimed in the first
part of the proposition.

We now prove Equation 5.5. The main issue we have to deal with is that for
$\kappa<1$, the support of the reduced state of $\ket{C}$ on the second half
of the qubits may not be contained in the support of the Uhlmann partial
isometry. As a result, taking $\Phi$ to be a channel completion of the Uhlmann
partial isometry as above, it is _not_ the case that
$\Phi(\ket{C}\\!\\!\bra{C})=(\textnormal{id}\otimes
W)\ket{C}\\!\\!\bra{C}(\textnormal{id}\otimes W^{\dagger})$. (This equation
does of course hold for $\kappa=1$.)

To deal with this issue, we need to consider the state $\ket{C}$ projected
onto the support of the Uhlmann partial isometry. To this end, let
$\Pi=W^{\dagger}W$ denote the projector onto the support of $W$. Let
$\ket{C^{\prime}}$ denote the (re-normalized) projection of $\ket{C}$ onto
$\textnormal{id}\otimes\Pi$:

$\ket{C^{\prime}}=\frac{(\textnormal{id}\otimes\Pi)\ket{C}\\!\\!\bra{C}(\textnormal{id}\otimes\Pi)}{\mathrm{Tr}((\textnormal{id}\otimes\Pi)\ket{C}\\!\\!\bra{C})}\,.$

By the Gentle Measurement Lemma [Wil13, Section 9.4], we have

$\mathrm{td}(\ket{C}\\!\\!\bra{C},\ket{C^{\prime}}\\!\\!\bra{C^{\prime}})\leq
2\sqrt{1-\mathrm{Tr}((\textnormal{id}\otimes\Pi)\ket{C}\\!\\!\bra{C})}\,.$
(5.6)

Note that since the projection $\textnormal{id}\otimes\Pi$ is at least
$(\textnormal{id}\otimes
W^{\dagger})\ket{D}\\!\\!\bra{D}(\textnormal{id}\otimes W)$ in the positive
semidefinite ordering, we have

$\mathrm{Tr}((\textnormal{id}\otimes\Pi)\ket{C}\\!\\!\bra{C})\geq\mathrm{Tr}\Big{(}(\textnormal{id}\otimes
W^{\dagger})\ket{D}\\!\\!\bra{D}(\textnormal{id}\otimes
W)\ket{C}\\!\\!\bra{C}\Big{)}=\mathrm{F}(\rho,\sigma)\geq\kappa$ (5.7)

where $\rho,\sigma$ denote the reduced density matrices of $\ket{C},\ket{D}$
respectively. Applying the triangle inequality, we have

$\displaystyle\mathrm{td}((\textnormal{id}\otimes\Phi)\ket{C}\\!\\!\bra{C},\ket{D}\\!\\!\bra{D})$
$\displaystyle\leq\mathrm{td}((\textnormal{id}\otimes\Phi)\ket{C}\\!\\!\bra{C},(\textnormal{id}\otimes\Phi)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}})+\mathrm{td}((\textnormal{id}\otimes\Phi)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}},\ket{D}\\!\\!\bra{D})$
$\displaystyle\leq\mathrm{td}(\ket{C}\\!\\!\bra{C},\ket{C^{\prime}}\\!\\!\bra{C^{\prime}})+\mathrm{td}((\textnormal{id}\otimes
W)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}}(\textnormal{id}\otimes
W^{\dagger}),\ket{D}\\!\\!\bra{D})$ $\displaystyle\leq
2\sqrt{1-\kappa}+\mathrm{td}((\textnormal{id}\otimes
W)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}}(\textnormal{id}\otimes
W^{\dagger}),\ket{D}\\!\\!\bra{D})$

where in the second line we used the monotonicity of the trace distance under
quantum channels and the fact that $\ket{C^{\prime}}$ is supported on $\Pi$,
and in the last line we used Equation 5.6 and Equation 5.7. To bound the last
term we use the triangle inequality again:

$\displaystyle\mathrm{td}((\textnormal{id}\otimes
W)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}}(\textnormal{id}\otimes
W^{\dagger}),\ket{D}\\!\\!\bra{D})$
$\displaystyle\qquad\leq\mathrm{td}(\ket{C}\\!\\!\bra{C},\ket{C^{\prime}}\\!\\!\bra{C^{\prime}})+\mathrm{td}((\textnormal{id}\otimes
W)\ket{C}\\!\\!\bra{C}(\textnormal{id}\otimes
W^{\dagger}),\ket{D}\\!\\!\bra{D})$ $\displaystyle\qquad\leq 3\sqrt{1-\kappa}$

where in the last line we applied the Fuchs-van de Graaf inequality to
$\mathrm{F}((\textnormal{id}\otimes
W)\ket{C}\\!\\!\bra{C}(\textnormal{id}\otimes
W^{\dagger}),\ket{D}\\!\\!\bra{D})\geq\kappa$. This concludes the proof of
Equation 5.5.

We now prove the “Conversely” part of the proposition. Again fix a valid
fidelity-$\kappa(n)$ Uhlmann instance $x=(1^{n},C,D)$. By Definition 3.5,
there exists a channel completion $\Phi$ of the Uhlmann transformation $W$
corresponding to the states $\ket{C},\ket{D}$ such that

$\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})\,\ket{C}\\!\\!\bra{C},(\textnormal{id}\otimes\Phi)\,\ket{C}\\!\\!\bra{C}\,\Big{)}\leq\delta\,.$
(5.8)

By the triangle inequality

$\displaystyle\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\ket{D}\\!\\!\bra{D}\Big{)}$
$\displaystyle\qquad\leq\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),(\textnormal{id}\otimes\Phi)\,\ket{C}\\!\\!\bra{C}\Big{)}+\mathrm{td}\Big{(}(\textnormal{id}\otimes\Phi)\ket{C}\\!\\!\bra{C},(\textnormal{id}\otimes\Phi)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}}\Big{)}$
$\displaystyle\qquad\qquad+\mathrm{td}\Big{(}(\textnormal{id}\otimes\Phi)\ket{C^{\prime}}\\!\\!\bra{C^{\prime}},\ket{D}\\!\\!\bra{D}\Big{)}\,.$
(5.9)

By Equation 5.8, the first term is at most $\delta$. Using the same argument
as above, by the monotonicity of trace distance under quantum channels and the
Gentle Measurement Lemma, the second term of Equation 5.9 is at most
$2\sqrt{1-\kappa}$. Similarly, the third term of Equation 5.9 is bounded by
$3\sqrt{1-\kappa}$ as shown above.

Putting everything together, we can upper bound Equation 5.9 by

$\mathrm{td}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\ket{D}\\!\\!\bra{D}\Big{)}\leq\delta+5\sqrt{1-\kappa}\,.$

Applying the Fuchs-van de Graaf inequality yields the conclusion of the
proposition. ∎

Proposition 5.8 indicates that in the average-case setting and the setting of
$\kappa$ close to $1$, the $\eta$ cutoff parameter can be without loss of
generality set to $0$, as alluded to earlier. This is because Proposition 5.8
shows that solving the distributional versions of Uhlmann or SuccinctUhlmann
is equivalent to approximately mapping $\ket{C}$ to $\ket{D}$ while acting
only on the second half of the qubits. This second statement, however, is
clearly robust to small perturbations: if a quantum algorithm $M$ can
approximately map $\ket{C}$ to $\ket{D}$, then it can also approximately map
$\ket{C^{\prime}}$ and $\ket{D^{\prime}}$ where
$\ket{C^{\prime}}\approx\ket{C}$ and $\ket{D^{\prime}}\approx\ket{D}$. Thus
the subtlety discussed at the beginning of the section about the need for a
cutoff parameter $\eta$ does not arise.

Since we mainly deal with solving Uhlmann or SuccinctUhlmann in the average
case and in the high $\kappa$ regime, we will from now omit mention of the
$\eta$ parameter and implicitly assume it is set to $0$. The only place where
we explicitly need the $\eta$ parameter is in Section 7.3, where we sketch how
$\textsc{SuccinctUhlmann}_{1,\eta}$ for exponentially small cutoff $\eta$ is a
complete problem for (worst-case) $\mathsf{unitaryPSPACE}$.

Finally, we pose a question about the tightness of Proposition 5.8.

######  Open Problem 9.

Can Proposition 5.8 be improved to give meaningful guarantees when the
fidelity parameter $\kappa$ is bounded away from $1$?

Improving it would be helpful when reasoning about Uhlmann transformations for
$\textsc{Uhlmann}_{\kappa}$ instances with small $\kappa$ (for an example of
this, see Section 8.2).

###  6 Structural Results about the Uhlmann Transformation Problem

Having defined the Uhlmann Transformation Problem and its succinct version as
unitary synthesis problems, we now prove some structural results about their
complexity. Specifically we show that the distributional Uhlmann
Transformation Problem is complete for the zero knowledge unitary complexity
class $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ defined in Section 4. We also
prove a hardness amplification result for the Uhlmann Transformation Problem,
which has cryptographic applications as we discuss in Section 8. We then
introduce a simple “padding trick” that shows that the complexity of the
distributional Uhlmann Transformation Problem is the same for all $\kappa$
that is polynomially-bounded away from $0$ or $1$. As discussed in the
previous section, since we are only dealing with the distributional Uhlmann
Transformation Problem, we set the cutoff parameter $\eta$ to $0$ and omit
reference to it.

####  6.1 Completeness for unitary zero knowledge

In this section we show that $\textsc{DistUhlmann}_{1-\mathrm{negl}}$ is
complete for the unitary complexity class
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ (see Section 4.3 for the definition
of this class). What we mean by this is that for every negligible function
$\mathrm{negl}(n)$, the distributional unitary synthesis problem
$\textsc{DistUhlmann}_{1-\mathrm{negl}}$ is contained in
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$, and every problem in
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ is polynomial-time reducible to
$\textsc{DistUhlmann}_{1-\mathrm{negl}}$ for _some_ negligible function
$\mathrm{negl}(n)$ (related to the simulation error of the problem).

We first introduce the notation employed throughout this section. A register
block $\mathsf{R}_{[i:j]}$ is an ordered collection of registers, denoted as
$\mathsf{R}_{[i:j]}\coloneqq\mathsf{R}_{i}\mathsf{R}_{i+1}\dots\mathsf{R}_{j}$,
with the size of the collection defined as, $|\mathsf{R}_{[i:j]}|\coloneqq
j-i+1$. When the first index is omitted, the collection is taken to start at
$i=1$, so $\mathsf{R}_{[m]}=\mathsf{R}_{1}\ldots\mathsf{R}_{m}$. For a
permutation $\pi$ on $|\mathsf{R}_{[0:m]}|$ elements, we use $P_{\pi}$ to
denote the unitary for a “block permutation” that permutes the registers
inside a block in the obvious way, and
$\mathcal{P}_{\pi}(\cdot)=P_{\pi}(\cdot)P_{\pi}^{\dagger}$ the associated
channel.

We first show that for all negligible functions $\mu(n)$,
$\textsc{DistUhlmann}_{1-\mu}$ is contained in
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ in Proposition 6.1. Then, in
Proposition 6.5 we show that $\textsc{DistUhlmann}_{1-\mathrm{negl}}$ is
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$-hard, i.e. that any problem in
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ polynomial-time reduces to
$\textsc{DistUhlmann}_{1-\epsilon}$ for some negligible function
$\epsilon(n)$. In Theorem 6.7, we combine these two statements to conclude
that $\textsc{DistUhlmann}_{1-\mathrm{negl}}$ is complete for
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$.

#####  6.1.1
$\textsc{DistUhlmann}_{1-\mathrm{negl}}\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$

######  Proposition 6.1.

$\textsc{DistUhlmann}_{1-\mu}\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ for
all negligible functions $\mu(n)$.

###### Proof.

Let $\mu(n)$ be a negligible function. We show that for all polynomials $q$,
$\textsc{DistUhlmann}_{1-\mu}\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1-\nu,1/2,1/q}$
for $\nu(n)=32q(n)^{2}\mu(n)$; since $\nu(n)$ is still negligible, this
suffices to show the proposition. For this, we need to design a protocol that
satisfies the conditions from Definition 4.3. Consider the following protocol
(1).

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]

######  Protocol 1.

$\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1-\nu,\frac{1}{2},1/q}$ verifier for
$\textsc{DistUhlmann}_{1-\mu}$

Input:  A valid $\textsc{Uhlmann}_{1-\mu}$ instance $x=(1^{n},C,D)$, and an
$n$ qubit quantum register $\mathsf{B}_{0}$.

  1. 1.

Let $m=32q(n)^{2}$. Prepare the state
$\bigotimes_{i=1}^{m}\ket{C}_{\mathsf{A}_{i}\mathsf{B}_{i}}$. Select a
permutation $\pi\in S_{m+1}$ uniformly at random, and apply
$\mathcal{P}_{\pi}$ to the register block
$\mathsf{B}_{[0:m]}=\mathsf{B_{0}B_{1}\dots B_{m}}$. Send the block
$\mathsf{B}_{[0:m]}$ to the prover.

  2. 2.

The verifier receives register block $\mathsf{B}$ from the prover. Then:

    1. (a)

Apply $\mathcal{P}_{\pi^{-1}}$ to $\mathsf{B}_{[0:m]}$.

    2. (b)

Apply $(D^{\dagger})^{\otimes m}$ to registers $\mathsf{AB}_{[m]}$, and
measure in the computational basis. If the outcome is the all-0 string for all
$i$, accept and output the $\mathsf{B}_{0}$ register. Otherwise, reject.

Note that all registers, $\mathsf{B_{i}}$ and $\mathsf{A_{i}}$, used in the
protocol have a dependence on the instance $x$, but as the instance $x$ if
fixed at the beginning of the protocol, we omit explicitly writing this
dependence. 1 describes the actions of the verifier. To satisfy Definition
4.3, we also need to define an honest prover $P^{*}$, who behaves as follows:
let $\Phi(\cdot)$ be an arbitrary channel completion of the canonical Uhlmann
partial isometry for $(C,D)$. Upon receipt of the registers
$\mathsf{B}_{[0:m]}=\mathsf{B_{0}\dots B_{m}}$, the honest prover $P^{*}$
applies $\Phi(\cdot)$ to each register $\mathsf{B_{i}}$ individually and sends
back the resulting state.

We will show that 1 with the honest prover $P^{*}$ satisfies the three
properties from Definition 4.3. Since the proofs are slightly involved, we
separate them out into individual lemmas, which we prove below using the same
notation and parameter settings introduced here:

  1. 1.

The honest prover $P^{*}$ needs to succeed with probability at least
$1-\nu(n)$ (Lemma 6.2).

  2. 2.

The verifier needs to satisfy the soundness condition of an
$\mathsf{avgUnitaryQIP}_{1-\nu,1/2,1/q}$ protocol (Lemma 6.3).

  3. 3.

The protocol needs to satisfy the zero-knowledge condition (Lemma 6.4).

Combined, Lemmas 6.2, 6.3 and 6.4 imply Proposition 6.1. ∎

We now prove the individual lemmas referenced in the proof of Proposition 6.1.

######  Lemma 6.2 ($\mathsf{avgUnitaryQIP}$ completeness).

For all valid $\textsc{Uhlmann}_{1-\mu}$ instances $x=(1^{n},C,D)$, for
sufficiently large $n$ the honest prover $P^{*}$ satisfies

$\Pr[V_{x}(\ket{C}_{\mathsf{A_{0}B_{0}}})\mathord{\leftrightarrows}P^{*}]\geq
1-\nu(n)\,.$

###### Proof.

We want to show that the honest prover, who applies the optimal Uhlmann
isometry, is accepted by the verifier with probability at least $1-\nu$. Let
$W_{\mathsf{B}}$ be the optimal Uhlmann partial isometry for the circuit pair
$(C,D)$. Because we are considering an $\textsc{Uhlmann}_{1-\mu}$ instance we
have that

$1-\mu(n)\leq\left|\bra{D}\left(\textnormal{id}_{\mathsf{A}}\otimes
W_{\mathsf{B}}\right)\ket{C}\right|^{2}\,.$

The honest prover action on the product state $\ket{C}^{\otimes m+1}$ is
exactly given by $W^{\otimes m+1}_{\mathsf{B}}$. Because the fidelity is
multiplicative under tensor products, the probability of the verifier
accepting is given by

$\left(\left|\bra{D}\left(\textnormal{id}_{\mathsf{A}}\otimes(W)_{\mathsf{B}}\right)\ket{C}\right|^{2}\right)^{m}\geq(1-\mu(n))^{m}\geq
1-m\cdot\mu(n)=1-\nu(n)\,.$

Additionally, after interacting with the honest prover and conditioned on
accepting, the verifier has successfully applied $W$ to the input state. ∎

######  Lemma 6.3 ($\mathsf{avgUnitaryQIP}$ soundness).

For all valid $\textsc{Uhlmann}_{1-\mu}$ instances $x=(1^{n},C,D)$, for
sufficiently large $n$, for all quantum provers $P$, there exists a channel
completion $\Phi_{x}$ of $U_{x}$ such that

$\text{if }\quad{\rm Pr}\left[V_{x}(\ket{C})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq\frac{1}{2}\qquad\text{then}\qquad\mathrm{td}(\sigma,(\Phi_{x}\otimes\textnormal{id})\ket{C}\\!\\!\bra{C})\leq
1/q(n)~{},$

where $\sigma$ denotes the output of
$V_{x}(\ket{C})\mathord{\leftrightarrows}P$, conditioned on $V_{x}$ accepting.

###### Proof.

We argue that soundness holds in three steps. We first show that by applying
the block permutation $P_{\pi}$ and inverting it after the interaction with
the prover, the verifier has forced the state after interacting with the
prover to be a symmetric state across the registers
$\mathsf{A}\mathsf{B}_{[0:m]}$. Second, we show that measuring
$\ket{D}\\!\\!\bra{D}$ on the $m$ decoy registers and accepting yields a state
close to measuring $\ket{D}\\!\\!\bra{D}$ on all $m+1$ registers. Finally we
apply the Gentle Measurement Lemma to show that, conditioned on accepting, the
verifier has a state close to the optimal Uhlmann unitary applied to the input
state.

We begin by expressing the state of the verifier’s registers after interacting
with the prover and undoing the permutation in step $2(a)$. Assume that the
verifier’s quantum input is the $\mathsf{B_{0}}$ register of
$\ket{C}_{\mathsf{A_{0}B_{0}}}$ (the distributional input). In the protocol,
the verifier will first apply a random permutation on $\mathsf{B}_{[0:m]}$;
then the prover will perform some arbitrary action on $\mathsf{B}_{[0:m]}$,
represented by a quantum channel $\Lambda_{\mathsf{B}_{[0:m]}}$; and finally
the verifier will undo the random permutation from the first step. Treating
$\mathsf{A_{0}}$ as the purification register of the verifier’s quantum input,
the state of the registers $\mathsf{B}_{[0:m]}A_{[0:m]}$ after these three
steps is given by

$\displaystyle\rho^{*}\coloneqq\mathop{\mathbb{E}}_{\pi\in
S_{m+1}}\Big{(}(\mathcal{P}_{\pi^{-1}})_{\mathsf{B}_{[0:m]}}\circ\Lambda_{\mathsf{B}_{[0:m]}}\circ(\mathcal{P}_{\pi})_{\mathsf{B}_{[0:m]}}\otimes\textnormal{id}_{\mathsf{A}_{[0:m]}}\Big{)}(\ket{C}\\!\\!\bra{C}^{\otimes
m+1})\,.$

Note that in addition to permuting the $\mathsf{B}_{[0:m]}$ registers and then
permuting them back, we can extend the permutation to include the
$\mathsf{A}_{[0:m]}$ registers, too. This is because
$(\mathcal{P}_{\pi})_{\mathsf{AB}_{[0:m]}}=(\mathcal{P}_{\pi})_{\mathsf{A}_{[0:m]}}\otimes(\mathcal{P}_{\pi})_{\mathsf{B}_{[0:m]}}$,
and since $\Lambda$ does not act on $\mathsf{A}_{[0:m]}$, the permutations on
$\mathsf{A}_{[0:m]}$ simply cancel. Therefore,

$\displaystyle\rho^{*}=\mathop{\mathbb{E}}_{\pi\in
S_{m+1}}\Big{(}(\mathcal{P}_{\pi^{-1}})_{\mathsf{AB}_{[0:m]}}\circ(\Lambda_{\mathsf{B}_{[0:m]}}\otimes\textnormal{id}_{\mathsf{A}_{[0:m]}})\circ(\mathcal{P}_{\pi})_{\mathsf{AB}_{[0:m]}}\Big{)}(\ket{C}\\!\\!\bra{C}^{\otimes
m+1})\,.$

This state is clearly permutation-invariant, i.e.
$(\mathcal{P}_{\sigma})_{\mathsf{AB}_{[0:m]}}(\rho^{*})=\rho^{*}$ for any
permutation $\sigma\in S_{m+1}$.

In the last step of the protocol, the verifier performs the projective
measurement
$\\{\Pi^{(0)}=\ket{D}\\!\\!\bra{D},\Pi^{(1)}=\textnormal{id}-\Pi^{(0)}\\}$ on
each of the systems in $\mathsf{AB}_{[m]}$ and accepts if all of them yield
outcome 0. We define random variables $X_{0},\dots,X_{m}$ with the joint
distribution

$\displaystyle{\rm Pr}\left[X_{0}=b_{0}\wedge\dots\wedge
X_{m}=b_{m}\right]=\mathrm{Tr}\left(\left(\otimes_{i=0^{m}}\Pi^{(b_{i})}_{\mathsf{A_{i}B_{i}}}\right)\rho^{*}\right)\,,$

i.e. $X_{i}$ corresponds to the verifier’s measurement on the $i$-th system.
Since we are assuming ${\rm
Pr}\left[V_{x}(\ket{C})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq\frac{1}{2}$, we have that ${\rm
Pr}\left[(X_{1},\dots,X_{m})=(0,\dots,0)\right]\geq 1/2$. Intuitively, the
“bad outcome” is that the verifier receives outcome $0$ for
$X_{1},\dots,X_{m}$, but if the verifier had measured the 0-th system, he
would have received outcome 1. We can bound the probability of this happening
as

$\displaystyle{\rm Pr}\left[X_{0}=1|(X_{1},\dots,X_{m})=(0,\dots,0)\right]$
$\displaystyle\leq 2\,{\rm
Pr}\left[X_{0}=1\wedge(X_{1},\dots,X_{m})=(0,\dots,0)\right]$
$\displaystyle\leq\frac{2}{m+1}\sum_{i=0}^{m+1}{\rm
Pr}\left[X_{i}=1\wedge(X_{j})_{j\neq i}=(0,\dots,0)\right]$
$\displaystyle\leq\frac{2}{m+1}\,.$ (6.1)

For the first inequality, we used the definition of conditional probability
and ${\rm Pr}\left[(X_{1},\dots,X_{m})=(0,\dots,0)\right]\geq 1/2$. For the
second inequality, we used the fact that due to the permutation-invariance of
$\rho^{*}$, the random variables $(X_{0},\dots,X_{m})$ are exchangeable (i.e.
their joint distribution is invariant under permutations), and for the last
inequality we used that $(X_{i}=1\wedge(X_{j})_{j\neq i}=(0,\dots,0))$ are
disjoint events, so the sum of their probabilities is at most 1.

Denoting the verifier’s output state conditioned on acceptance by $\sigma$,
Equation 6.1 tells us that

$\displaystyle\mathrm{F}(\sigma,\ket{D}\\!\\!\bra{D})=\mathrm{Tr}\left(\ket{D}\\!\\!\bra{D}\sigma\right)^{2}\geq\Big{(}1-\frac{2}{m+1}\Big{)}^{2}\geq
1-\frac{4}{m+1}\,.$

By Fuchs-van de Graaf we have

$\displaystyle\mathrm{td}(\sigma,\ket{D}\\!\\!\bra{D})\leq\sqrt{\frac{4}{m+1}}~{}.$

Then Equation 5.5 in the proof of Proposition 5.8 shows that for all channel
completions $\Phi_{x}$ of $U_{x}$, we have that

$\mathrm{td}((\Phi_{x}\otimes\textnormal{id})\ket{C}\\!\\!\bra{C},\,\ket{D}\\!\\!\bra{D})\leq
5\sqrt{\mu(n)}$

so therefore

$\mathrm{td}\Big{(}\sigma,(\Phi_{x}\otimes\textnormal{id})\ket{C}\\!\\!\bra{C}\Big{)}\leq\sqrt{\frac{4}{m+1}}+5\sqrt{\mu(n)}~{}.$

By the choice of $m=32q(n)^{2}$, since $\mu(n)$ is negligible, for
sufficiently large $n$ this is at most $1/q(n)$ as desired. This completes the
proof of Lemma 6.3.

∎

######  Lemma 6.4 ($\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ zero-knowledge).

There exists a negligible function $\mathrm{negl}$ and a polynomial-time
simulator that, on input $(x,1)$,121212Note that there is only $1$ interaction
with the prover in the protocol. outputs a state $\rho$ satisfying

$\mathrm{td}(\rho,\sigma_{x,1})\leq\mathrm{negl}(n)\,,$

where $\sigma_{x,1}$ is the reduced density matrix of $V_{x}^{*}$ immediately
after interacting with the honest prover $P^{*}$.

###### Proof.

The simulator simply outputs the state $\ket{D}^{\otimes m+1}$. Because the
fidelity is being measured between product states, the fidelity between the
simulator output and the state of the verifier after interacting with the
honest prover is

$\left(\left|\bra{D}\left(\textnormal{id}_{\mathsf{A}}\otimes
W_{\mathsf{B}}\right)\ket{C}\right|^{2}\right)^{m+1}\geq 1-(m+1)\mu(n).$

By the standard relationship between trace distance and fidelity, the trace
distance between the simulators output and the state of the verifier after
interacting with the prover is at most $\sqrt{(m+1)\mu(n)}$. Since $m$ is a
polynomial in $n$, $\sqrt{(m+1)\mu(n)}$ is also a negligible function in $n$,
so the simulator satisfies the definition of
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$. ∎

#####  6.1.2 $\textsc{DistUhlmann}_{1-\mathrm{negl}}$ is
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$-hard

Now we show that all problems in $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$
reduce to $\textsc{DistUhlmann}_{1-\nu}$ for _some_ negligible $\nu(n)$ (which
depends on the $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$-problem). We highlight
the annoying fact that it is not known if there is a single negligible
function $\nu^{*}(n)$ such that $\textsc{DistUhlmann}_{1-\nu^{*}}$ is hard for
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$. In particular, the value of $\nu$
will depend on the error to which the simulator can prepare the verifier’s
state.

######  Open Problem 10.

Does there exist a negligible function $\mu$ such that every distributional
unitary synthesis problem in $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$ has a
protocol, ($V$, $P^{*}$, $\mathrm{Sim}$), such that $\mathrm{Sim}$ prepares
the verifiers state to within trace distance error $\mu$?

If the above problem was answered in the affirmative, then it would directly
imply that there is a single distributional unitary synthesis problem that is
complete for $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$. Note that the number of
rounds in the algorithm does not matter because the Padding Trick (Section
6.3) can be used to transform a protocol with simulator error $\delta$ to one
with simulator error $\delta/p$ for any polynomial $p$. This question is
tightly related to another broader difference between
$\mathsf{SZK}_{{\mathrm{HV}}}$ and $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$,
which will be discussed in more detail in Section 6.4.

######  Proposition 6.5.

Let $(\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi_{x}})_{x})$ be a distributional
unitary synthesis problem in $\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$. Then
there exists a negligible function $\nu$ such that $(\mathscr{U},\Psi)$
polynomial-time reduces to $\textsc{DistUhlmann}_{1-\nu}$.

###### Proof.

By Definition 4.3, for all polynomials $q$ there exists a negligible function
$\mu$ such that
$(\mathscr{U},\Psi)\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1-\mu,1/2,1/q}$.
Let $V^{*}=(V^{*}_{x})_{x}$ be the honest, $r$-round
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1-\mu,1/2,1/q}$ verifier for
$(\mathscr{U},\Psi)$, and let $(V_{x,i})_{i=1}^{r+1}$ be the unitaries that
this verifier applies throughout the protocol, where $V_{x,i}$ is the unitary
applied in the $i$-th round. $V_{x,i}$ acts on a workspace register
$\mathsf{F_{i-1}}$ and a prover message $\mathsf{Q_{i-1}}$, and outputs a pair
of registers $\mathsf{F_{i}}\mathsf{Q_{i}}$. Additionally, $V_{x,0}$ takes in
a quantum input in register $\mathsf{A}$, and an ancilla register
$\mathsf{R}$. See Figure 2 for an image describing how the verifier and prover
interact.

Let $\mathrm{Sim}$ be the zero-knowledge simulator for $V^{*}$, and let
$\epsilon$ be the negligible function such that $\mathrm{Sim}$, when run on
input $(x,i)$, outputs a state within $\epsilon(|x|)$ of the reduced density
matrix of $V^{*}$ immediately after the $i$-th round of interaction with the
honest prover. Since $\mathrm{Sim}$ is a polynomial time quantum algorithm,
for all $x,i$ there exists a polynomial time unitary circuit
$\mathrm{Sim}_{x,i}$ that implements $\mathrm{Sim}(x,i)$ (i.e. in
$\mathrm{Sim}_{x,i}$, the input $x,i$ is hard-coded). Since the circuit
$\mathrm{Sim}_{x,i}$ implements a unitary while $\mathrm{Sim}(x,i)$ might
perform measurements and trace out registers, we need to assume that
$\mathrm{Sim}_{x,i}$ might require an additional (private) register
$\mathsf{P}$ that is traced out by $\mathrm{Sim}(x,i)$. In this section, we
abuse notation and interchange the unitary implemented by $\mathrm{Sim}_{x,i}$
with the explicit circuit description of $\mathrm{Sim}_{x,i}$ wherever it is
clear from context which one is intended. We emphasize that
$\mathrm{Sim}_{x,i}$ is a fixed quantum circuit that acts only on $\ket{0}$,
and produces a purification of the state that $\mathrm{Sim}$ would produce
when run on input $(x,i)$. Every $\mathrm{Sim}_{x,i}$ acts on registers
$\mathsf{F_{i}Q_{i}PB}$, where $\mathsf{F_{i}}$ and $\mathsf{Q_{i}}$ are the
verifiers registers, $\mathsf{B}$ is the purification register for the initial
input (initially in $\mathsf{AB}$), and $\mathsf{P}$ is a purification
register for the simulator, as explained before. Since $\mathrm{Sim}$ produces
the state _after_ the interaction, we need to define an additional circuit
that prepares the initial state of the system, which we will call
$\mathrm{Sim}_{x,0}$. Since the initial state is in $\mathsf{stateBQP}$, there
is a polynomial-time circuit such that
$(\mathrm{Sim}_{x,0})_{\mathsf{AB}}\otimes\textnormal{id}_{\mathsf{R}}\ket{0}_{\mathsf{ABR}}=\ket{\psi_{x}}\otimes\ket{0}_{\mathsf{R}}$,
which prepares the initial state of the verifier when run on
$\ket{0}_{\mathsf{ABR}}$ (recall that the initial state of the system includes
an ancilla register $\mathsf{R}$ for the verifier). We relabel the registers
$\mathsf{AR}$ to be $\mathsf{F_{0}Q_{0}}$ so that $\mathrm{Sim}_{x,0}$ follows
the pattern of the other $\mathrm{Sim}_{x,i}$. Assume that every
$\mathrm{Sim}_{x,i}$ uses a private register of the same size, and that the
private register has polynomial in $|x|$ many qubits, which we can achieve by
padding every $\mathrm{Sim}_{x,i}$ with extra ancilla qubits.

We now define a quantum query circuit making exactly $r$ calls to a
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ oracle. The classical label for the
$i$-th Uhlmann oracle will be (an explicit classical description of) the
following pair $(A_{i},B_{i})$ of polynomial-time quantum circuits.

$\displaystyle A_{i}$
$\displaystyle=(V_{x,i})_{\mathsf{F_{i-1}Q_{i-1}}}\circ(\mathrm{Sim}_{x,i-1})_{\mathsf{F_{i-1}Q_{i-1}PB}}$
$\displaystyle B_{i}$
$\displaystyle=(\mathrm{Sim}_{x,i})_{\mathsf{F_{i}Q_{i}PB}}$

Both of these are polynomial time quantum circuits. $A_{i}$ is a unitary that,
when applied to
$\ket{0}_{\mathsf{F}_{i-1}\mathsf{Q}_{i-1}\mathsf{P}\mathsf{B}}$, prepares a
purification of the verifier’s state immediately before the $i$-th round of
interaction. $B_{i}$ is a unitary that, when applied to
$\ket{0}_{\mathsf{F_{i}}\mathsf{Q_{i}}\mathsf{P}\mathsf{B}}$, prepares the
verifier’s state after the $i$-th round of interaction with the prover. We
first show that $(A_{i},B_{i})$ are a valid
$\textsc{Uhlmann}_{1-2\epsilon^{2}}$ instance. Let $\Phi_{i}$ be the channel
representing the honest prover in the $i$-th interaction acting on
$\mathsf{Q_{i}}$. Let $\sigma_{x,i}$ be reduced the state of the verifier
registers (and hidden input register $\mathsf{B}$) immediately after the
$i$-th interaction with the honest prover. By the definition of
$\mathrm{Sim}$, we have that

$\displaystyle\mathrm{td}(\mathrm{Tr}_{\mathsf{P}}(\ket{A_{i}}\\!\\!\bra{A_{i}}),V_{x,i}\sigma_{x,i-1}V_{x,i}^{\dagger})$
$\displaystyle\leq\epsilon(|x|)\text{ and }$ (6.2)
$\displaystyle\mathrm{td}(\mathrm{Tr}_{\mathsf{P}}(\ket{B_{i}}\\!\\!\bra{B_{i}}),\sigma_{x,i})$
$\displaystyle\leq\epsilon(|x|).$ (6.3)

We also have that the state of the verifier after the $i$-th round of
interaction can be attained by applying the verifiers unitary $V_{x,i}$ and
the provers channel $\Phi_{i}$ to the state after the $(i-1)$-th round,
formally

$((\Phi_{i})_{\mathsf{Q_{i}}}\otimes\textnormal{id})(V_{x,i}\sigma_{x,i-1}V_{x,i}^{\dagger})=\sigma_{x,i}.$

Fix an $i$, and let $\rho_{A}$ and $\rho_{B}$ be the reduced states of
$\ket{A_{i}}\\!\\!\bra{A_{i}}$ and $\ket{B_{i}}\\!\\!\bra{B_{i}}$ on
$\mathsf{F}_{i}\mathsf{B}$. We have that

$\displaystyle F(\rho_{A},\rho_{B})$ $\displaystyle\geq
F(\left((\Phi_{i})_{\mathsf{Q_{i}}}\otimes
I_{\mathsf{F_{i}}\mathsf{B}}\right)(\mathrm{Tr}_{\mathsf{P}}(\ket{A_{i}}\\!\\!\bra{A_{i}})),\mathrm{Tr}_{\mathsf{P}}(\ket{B_{i}}\\!\\!\bra{B_{i}}))$
$\displaystyle\geq 1-\mathrm{td}(\left((\Phi_{i})_{\mathsf{Q_{i}}}\otimes
I_{\mathsf{F_{i}}\mathsf{B}}\right)(\mathrm{Tr}_{\mathsf{P}}(\ket{A_{i}}\\!\\!\bra{A_{i}})),\mathrm{Tr}_{\mathsf{P}}(\ket{B_{i}}\\!\\!\bra{B_{i}}))^{2}$
$\displaystyle\geq 1-\mathrm{td}(\left((\Phi_{i})_{\mathsf{Q_{i}}}\otimes
I_{\mathsf{F_{i}}\mathsf{B}}\right)(V_{x,i}\sigma_{x,i-1}V_{x,i}^{\dagger}),\mathrm{Tr}_{\mathsf{P}}(\ket{B_{i}}\\!\\!\bra{B_{i}}))^{2}-\epsilon^{2}(|x|)$
$\displaystyle\geq 1-\mathrm{td}(\left((\Phi_{i})_{\mathsf{Q_{i}}}\otimes
I_{\mathsf{F_{i}}\mathsf{B}}\right)(V_{x,i}\sigma_{x,i-1}V_{x,i}^{\dagger}),\sigma_{x,i})^{2}-2\epsilon(|x|)^{2}$
$\displaystyle=1-2\epsilon^{2}(|x|).$

Here the first line holds because the states on the right are extensions of
the states $\rho_{A}$ and $\rho_{B}$. Because $\Phi_{i}$ acts only on
$\mathsf{Q}_{i}$, the reduced state of the left hand state on
$\mathsf{F}_{i}\mathsf{B}$ is the same as $\ket{A_{i}}\\!\\!\bra{A_{i}}$. The
subsequent lines follow because the trace distance obeys the triangle
inequality and contracts under trace preserving channels, using the
inequalities from Equations 6.2 and 6.3. Note that this means the Uhlmann
unitary that acts on $\mathsf{Q_{i}}$ _and_ $\mathsf{P}$, since we only showed
that the reduced states on $\mathsf{F_{i}B}$ have high fidelity with each
other. Now consider the following
$\mathsf{avgUnitaryBQP}^{\textsc{DistUhlmann}_{1-2\epsilon^{2}}}$ query
algorithm protocol for $(\mathscr{U},\Psi)$.

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]

######  Algorithm 1.

$\mathsf{avgUnitaryBQP}^{\textsc{DistUhlmann}_{1-2\epsilon^{2}}}_{3/q(n)}$
query algorithm for $(\mathscr{U},\Psi)$

Input:  Classical string $x$ specifying $U_{x}$ and quantum register
$\mathsf{A}$.

  1. 1.

Initialize $i\leftarrow 1$, register
$\mathsf{R}\leftarrow\ket{0}\\!\\!\bra{0}$ and relabel
$\mathsf{F}_{0}\mathsf{Q}_{0}\leftarrow\mathsf{AR}$. While $i\leq r$:

    1. (a)

Run $V_{x,i}$ on $\mathsf{F}_{i-1}\mathsf{Q}_{i-1}$ to get a state on
$\mathsf{F}_{i}\mathsf{Q}_{i}$, if $V_{x,i}$ rejects, abort and output
$\ket{0}_{\mathsf{A}}$.

    2. (b)

Call $\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ oracle on the instance
corresponding to an explicit circuit representation of $(A_{i},B_{i})$, and
quantum register $\mathsf{Q_{i}P}$.

    3. (c)

$i\leftarrow i+1$.

  2. 2.

Run $V_{x,r+1}$ on $\mathsf{F}_{r}\mathsf{Q}_{r}$ to get a state on
$\mathsf{AR}$.

  3. 3.

Output register $\mathsf{A}$.

$\displaystyle\ket{\psi_{x}}$$\displaystyle V_{x}{}_{,}{}_{1}$$\displaystyle
V_{x}{}_{,}{}_{1}\ \circ\mathrm{Sim}(x,\ 0)\
\ket{0}=\ket{\psi_{x}{}_{,}{}_{1}}$$\displaystyle\mathsf{B}$$\displaystyle
V_{x}{}_{,}{}_{2}$$\displaystyle\ket{\psi_{x},_{2}}=\ \mathrm{Sim}(x,\ 1)\
\ket{0}$$\displaystyle\mathsf{A}$$\displaystyle\mathsf{Q}_{1}$$\displaystyle\mathsf{F}_{1}$$\displaystyle
C_{x}\otimes I\ \ket{\psi_{x}}_{\mathsf{AB}}$$\displaystyle
V_{x}{}_{,}{}_{r+1}$$\displaystyle\mathsf{R}$$\displaystyle\ket{0}$$\displaystyle\Phi_{1}$$\displaystyle\Phi_{r}$
Figure 2: A $\mathsf{avgUnitarySZK}$ protocol with $r$ rounds. The prover
recieves the $\mathsf{A}$ register of $\ket{\psi}_{\mathsf{AB}}$. Every round
of interaction consists of the verifier applying $V_{x,i}$ to
$\mathsf{F}_{i-1}\mathsf{Q}_{i-1}$ to get $\mathsf{F}_{i}\mathsf{Q}_{i}$ and
then exchanging $\mathsf{Q}_{i}$ with the prover. The first and final rounds
are special. In the first round, the verifier takes in $\mathsf{A}$ and a
workspace $\mathsf{R}$, and in the final round the verifier either accepts or
rejects, and outputs a register. $\mathrm{Sim}$ can be used to generate the
state after every interacting with the prover.

In order to show that $(\mathscr{U},\Psi)$ polynomial-time reduces to
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$, we need to show that for all
polynomials $q$, there exists another polynomial $p$ such that all $1/p$-error
average case instantiations of Algorithm 1 with
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ implement $(\mathscr{U},\Phi)$.

######  Claim 6.6.

Fix a polynomial $q$, and let $p(n)=rq(n)$ (where $r$ is the number of rounds
as before). Then all $1/p$-error average case instantiations of Algorithm 1
with $\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ implement $(\mathscr{U},\Phi)$
to average case error $3/q(n)$.

###### Proof.

We first show by induction that for every $i\leq r$, the input to the $i$-th
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ oracle call is at most
$(i-1)\cdot(1/p(n)+\epsilon\sqrt{2})$ in trace distance from the “correct”
distributional state $\ket{A_{i}}\coloneqq A_{i}\ket{0}$ for which the
guarantee of the DistUhlmann holds.

The input to the first call to $\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ is
exactly $\ket{A_{0}}=(V_{x,1})_{\mathsf{A}}\ket{\psi_{x}}_{\mathsf{AB}}$, so
the trace distance error before the $1$-st call is $0$.

Now assume that the claim is true up to the $i$-th call to
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$. Let $\rho_{i}$ be the input to the
$i$-th call to $\textsc{DistUhlmann}_{1-2\epsilon^{2}}$. Let
$\Phi_{(A_{i},B_{i})}$ be the channel that the $i$-th call to the
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ oracle implements, and let $W_{i}$ be
the optimal Uhlmann unitary for instance $(A_{i},B_{i})$. By assumption we
have that

$\displaystyle\mathrm{td}(\Phi_{(A_{i},B_{i})}(\rho_{i}),\ket{B_{i}}\\!\\!\bra{B_{i}})$
$\displaystyle\leq\mathrm{td}(\Phi_{(A_{i},B_{i})}(\rho_{i}),\Phi_{(A_{i},B_{i})}(\ket{A_{i}}\\!\\!\bra{A_{i}})+\mathrm{td}(\Phi_{(A_{i},B_{i})}(\ket{A_{i}}\\!\\!\bra{A_{i}}),\ket{B_{i}}\\!\\!\bra{B_{i}})$
$\displaystyle\leq(i-1)(1/p(n)+\epsilon\sqrt{2})+\mathrm{td}(\Phi_{(A_{i},B_{i})}(A_{i}\ket{0}\\!\\!\bra{0}A_{i}^{\dagger}),B_{i}\ket{0}\\!\\!\bra{0}B_{i}^{\dagger})$
$\displaystyle\leq(i-1)(1/p(n)+\epsilon\sqrt{2})+1/p(n)+\mathrm{td}(W_{i}\ket{A_{i}}\\!\\!\bra{A_{i}}W_{i}^{\dagger},\ket{B_{i}}\\!\\!\bra{B_{i}})$
$\displaystyle\leq i(1/p(n)+\epsilon\sqrt{2})$

Here we first apply the induction hypothesis and the fact that quantum
channels decrease trace distance. Then we use the fact that
$\Phi_{(A_{i},B_{i})}$ is a $1/p(n)$-error average case solver. Finally we use
the fact that $(A_{i},B_{i})$ is a valid
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$ instance, so the states
$W_{i}\ket{A_{i}}$ and $\ket{B_{i}}$ are within $\epsilon\sqrt{2}$ in trace
distance. The state that the query algorithm gives as input to the oracle is

$V_{x,i+1}(\Phi_{(A_{i},B_{i})}(\rho_{i}))\,,$

which is within $i(1/p(n)+\epsilon\sqrt{2})$ trace distance of
$\ket{A_{i+1}}=V_{x,i+1}\ket{B_{i}}$ because unitaries preserve trace
distance. By induction, for all $i$, the input to the $i$-th oracle call in
the protocol is within $(i-1)\cdot(1/p(n)+\epsilon\sqrt{2})$. Following the
same inequalities, the _output_ of the final oracle call satisfies

$\mathrm{td}(\Phi_{(A_{r},B_{r})}(\rho_{r}),\ket{B_{r}}\\!\\!\bra{B_{r}})\leq
r(1/p(n)+\epsilon\sqrt{2})\,.$

Let $\sigma_{x,r}$ be the state of the verifier after the final interaction
with the honest prover. Then by the definition of the simulator, we have that

$\mathrm{td}(\Phi_{(A_{r},B_{r})}(\rho_{r}),\sigma_{x,r})\leq
r/p(n)+(r+1)\epsilon\sqrt{2}.$

By the definition of the honest prover, there exists a negligible function
$\mu$ such that the honest prover is accepted with probability $1-\mu$, and
conditioned on accepting the verifier outputs a state within $1/q(n)$ of
$U_{x}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}U_{x}^{\dagger}$ in trace distance.
Thus we have that

$\mathrm{td}(V_{x,r+1}\sigma_{x,r}V_{x,r+1}^{\dagger},U_{x}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}U_{x}^{\dagger})\leq\mu+1/q.$

Combining everything we have that

$\displaystyle\mathrm{td}(V_{x,r+1}\Phi_{(A_{r},B_{r})}(\rho_{r})V_{x,r+1}^{\dagger},U_{x}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}U_{x}^{\dagger})$
$\displaystyle\qquad\leq\mathrm{td}(V_{x,r+1}\sigma_{x,r}V_{x,r+1}^{\dagger},U_{x}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}U_{x}^{\dagger})+r(1/p(n)+\epsilon\sqrt{2})$
$\displaystyle\qquad\leq 1/q+\mu+r(1/p+\epsilon\sqrt{2})$
$\displaystyle\qquad\leq 2/q+r\epsilon\sqrt{2}+\mu$ $\displaystyle\qquad\leq
3/q.$

Here we use the fact that $p=rq$, and since $\epsilon$ and $\mu$ are
negligible, for sufficiently large $n$, $r\epsilon\sqrt{2}+\mu\leq 1/q$. ∎

Because $(\mathscr{U},\Psi)\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$, there
exists a negligible function $\epsilon$ such that for all polynomials
$q^{\prime}$, there exists a verifier that implements $(\mathscr{U},\Psi)$
with average case error $1/3q^{\prime}$, and a simulator that makes simulation
error $\epsilon$. Thus for all polynomials $q^{\prime}$, there exists a
polynomial time quantum query algorithm, specified by Algorithm 1 when $V$ is
taken to have average case error $1/3q^{\prime}$, and another polynomial
$p=rq^{\prime}$, that achieves average case error $1/q^{\prime}$ when
instantiated with $1/p$-error average case instantiations of
$\textsc{DistUhlmann}_{1-2\epsilon^{2}}$. In other words, $(\mathscr{U},\Psi)$
polynomial-time reduces to $\textsc{DistUhlmann}_{1-2\epsilon^{2}}$. ∎

We summarise the results of Proposition 6.1 and Proposition 6.5 in the
following theorem, which shows that $\textsc{DistUhlmann}_{1-\mathrm{negl}}$
is “almost complete” for $\mathsf{avgUnitarySZK}$ up to the aforementioned
issue that we cannot find a single negligible function $\nu$ such that
$\mathsf{avgUnitarySZK}$ reduces to $\textsc{DistUhlmann}_{1-\nu}$.

######  Theorem 6.7.

For all neglibible functions $\mu$,
$\textsc{DistUhlmann}_{1-\mu}\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$, and
for all distributional unitary synthesis problems $(\mathscr{U},\Psi)$, there
exists a negligible function $\nu$ such that $(\mathscr{U},\Psi)$ reduces to
$\textsc{DistUhlmann}_{1-\nu}$.

####  6.2 Hardness amplification

In this section, we prove a hardness amplification result for the Uhlmann
Transformation Problem, which roughly states that if it is hard to implement
DistUhlmann in polynomial time (i.e.,
$\textsc{DistUhlmann}\notin\mathsf{avgUnitaryBQP}$), then in fact it is hard
to implement DistUhlmann even with large average case error approaching $1$.
This hardness amplification statement has applications to amplifying the
security of quantum commitment schemes as we show in Section 8.

######  Theorem 6.8.

The following two statements are equivalent:

  1. 1.

For all negligible functions $\epsilon(n)$,
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ (resp.
$\mathsf{avgUnitaryBQP/poly}$).

  2. 2.

For all negligible functions $\epsilon(n)$,
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}_{1-\xi}$ (resp.
$\mathsf{avgUnitaryBQP/poly}_{1-\xi}$), where $\xi(n)=n^{-1/16}$.

While Theorem 6.8 will be useful, it is not the strongest possible
amplification statement one would hope to prove: one could hope to show that
instead of just suppressing the error to an inverse exponential, it can
actually be suppressed to an inverse exponential. We call this “strong
amplification” and leave it as an open problem:

######  Open Problem 11.

Can strong amplification be proved? In other words, does solving the Uhlmann
transformation problem with inverse polynomial error imply being able to solve
it with inverse exponential error?

Strong amplification for Uhlmann would also have ramifications for the
question of whether quantum commitments with weak security can be boosted to
commitments with strong security (see 8.9). This would be of independent
interest for quantum cryptography.

We first give an overview of the proof of Theorem 6.8. Recall from Definition
3.10 that $\mathsf{avgUnitaryBQP}_{\delta}$ denotes the class of
distributional unitary synthesis problems that can be implemented with average
case error $\delta$, and that
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ means that for
all inverse polynomials $\delta$,
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}_{\delta}$.

The “only if” direction of the theorem is immediate: by definition, for
$0\leq\delta\leq\delta^{\prime}\leq 1$ we have
$\mathsf{avgUnitaryBQP}_{\delta}\subseteq\mathsf{avgUnitaryBQP}_{\delta^{\prime}}$.

For the “if” direction, the idea is to reduce implementing the Uhlmann
transformation $U_{x}$ corresponding to a valid Uhlmann instance
$x=(1^{n},C,D)$ to the task of implementing the Uhlmann transformation for the
_parallel repetition_ of the instance, which we denote by $x^{\otimes
k}=(1^{nk},C^{\otimes k},D^{\otimes k})$ for some integer $k$. If the circuits
$C,D$ acted on registers $\mathsf{AB}$, then the circuits $C^{\otimes
k},D^{\otimes k}$ act on $k$ copies denoted by
$\mathsf{A}_{1}\mathsf{B}_{1},\ldots,\mathsf{A}_{k},\mathsf{B}_{k}$, and
output the states $\ket{C}^{\otimes k},\ket{D}^{\otimes k}$. What we show is
that being able to implement the repeated Uhlmann transformation with error
very close to $1$ can be turned into a way of implementing the original
Uhlmann transformation $U_{x}$ with very small error. Put another way, if it
was hard to implement the original Uhlmann transformation $U_{x}$ almost
exactly, then it is still hard to implement the repeated Uhlmann
transformation even approximately. We abstract this reduction out in the
following Lemma:

######  Lemma 6.9.

Let $C,D$ be unitary circuits such that the states $\ket{C}\coloneqq
C\ket{0\ldots 0},\ket{D}\coloneqq D\ket{0\ldots 0}$ are bipartite states on
registers $\mathsf{AB}$. Let $k\in\mathbb{N}$ and let $\ket{C}^{\otimes
k},\ket{D}^{\otimes k}$ be states on registers $\mathsf{A}_{[k]}$ and
$\mathsf{B}_{[k]}$ respectively. Suppose there is a quantum circuit $R$ acting
on register $\mathsf{B}_{[k]}$ such that

$\mathrm{F}\Big{(}(\textnormal{id}\otimes R)(\ket{C}\\!\\!\bra{C}^{\otimes
k}),\,\ket{D}\\!\\!\bra{D}^{\otimes k}\Big{)}\geq\nu~{}.$

Then for all $T\in\mathbb{N}$ there exists a quantum circuit $M$ which acts on
register $\mathsf{B}$ such that

$\mathrm{F}\Big{(}(\textnormal{id}\otimes
M)(\ket{C}\\!\\!\bra{C}),\,\ket{D}\\!\\!\bra{D}\Big{)}\geq
1-\Big{(}2(1-\nu)^{T}+\frac{32T}{\sqrt{k}}\Big{)}\,.$

and the size of $M$ is at most $\mathrm{poly}(T,|R|,|C|,|D|)$ where
$|R|,|C|,|D|$ denote the sizes of circuits $R,C,D$. Furthermore, if $R$ is an
instance of a uniformly generated quantum algorithm, so is $M$.

Before proving Lemma 6.9, we first show how it implies Theorem 6.8.

###### Proof of Theorem 6.8.

We present the proof for the uniform class $\mathsf{avgUnitaryBQP}$; the proof
for the non-uniform class $\mathsf{avgUnitaryBQP/poly}$ is entirely analogous.

As mentioned the “only if” direction is trivial, and we focus on the “if”
direction. That is, we assume that
$\textsc{DistUhlmann}_{1-\mu}\in\mathsf{avgUnitaryBQP}_{1-\xi}$ for all
negligible functions $\mu(n)$, where $\xi(n)=n^{-1/16}$, and we aim to show
that $\textsc{DistUhlmann}_{1-\mu}\in\mathsf{avgUnitaryBQP}$ for all
negligible functions $\mu(n)$.

Fix a negligible function $\epsilon(n)$ and a polynomial $q(n)$. Define the
functions

$k(n)\coloneqq(n\,q(n))^{8}\qquad\delta(n)\coloneqq k(n)\epsilon(n)\qquad
T(n)=2q(n)/\xi(nk(n))^{2}~{}.$

Note that $\delta(n)$ is also a negligible function. Therefore by assumption
$\textsc{DistUhlmann}_{1-\delta}\subseteq\textsc{DistUhlmann}_{(1-\epsilon)^{k}}\in\mathsf{avgUnitaryBQP}_{1-\xi}$
there exists a uniform polynomial-time algorithm $R=(R_{x})_{x}$ that
implements $\textsc{DistUhlmann}_{1-\delta}$ with average-case error $1-\xi$.

Fix a $\textsc{Uhlmann}_{1-\epsilon}$ instance $x=(1^{n},C,D)$, and let
$k=k(n),\delta=\delta(n),T=T(n)$. We write $x^{k}$ to denote the parallel
repeated instance $(1^{nk},C^{\otimes k},D^{\otimes k})$. Note $x^{k}$ is a
valid $\textsc{Uhlmann}_{(1-\epsilon)^{k}}$ instance. By the second part of
Proposition 5.8, it holds that

$\mathrm{F}\Big{(}(\textnormal{id}\otimes
R_{x^{k}})(\ket{C}\\!\\!\bra{C}^{\otimes k}),\ket{D}\\!\\!\bra{D}^{\otimes
k}\Big{)}\geq\Big{(}\xi(nk)-5\sqrt{\delta(nk)}\Big{)}^{2}\geq\xi(nk)^{2}-10\sqrt{\delta(nk)}~{}.$
(6.4)

Define $\nu=\xi(nk)^{2}-10\sqrt{\delta(nk)}$. Since $\delta$ is a negligible
function, for sufficiently large $n$ the quantity $\nu$ is lower bounded by
$\xi(nk)^{2}/2$. We now invoke Lemma 6.9: there exists a polynomial-time
quantum algorithm $M=(M_{x})_{x}$ such that for all valid
$\textsc{Uhlmann}_{1-\epsilon}$ instances $x=(1^{n},C,D)$,

$\mathrm{F}\Big{(}(\textnormal{id}\otimes
M_{x})(\ket{C}\\!\\!\bra{C}),\,\ket{D}\\!\\!\bra{D}\Big{)}\geq
1-\Big{(}2(1-\nu(n))^{T(n)}+\frac{32T(n)}{\sqrt{k(n)}}\Big{)}~{}.$

By our choice of $k,\nu,T$, we get

$\displaystyle 2(1-\nu)^{T}+\frac{32T}{\sqrt{k}}$ $\displaystyle\leq
2(1-\xi(nk)^{2}/2)^{2q(n)/\xi(nk)^{2}}+\frac{64q(n)}{n^{4}\,\xi(nk)^{2}\,q(n)^{4}}$
$\displaystyle\leq 2e^{-q(n)}+\frac{64\,(nk)^{1/8}}{n^{4}\,q(n)^{3}}\leq
O\Big{(}\frac{1}{q(n)^{2}}\Big{)}$

where in the second line we used the assumption that
$1/\xi(nk)\leq(nk)^{1/16}$. Thus we have argued that

$\mathrm{F}((\textnormal{id}\otimes
M_{x})\ket{C}\\!\\!\bra{C},\ket{D}\\!\\!\bra{D})\geq 1-O(1/q(n)^{2})\geq
1-\epsilon(n)-O(1/q(n)^{2})~{}.$

Using the first part of Proposition 5.8, we get that the algorithm $M_{x}$
implements $\textsc{DistUhlmann}_{1-\epsilon}$ with average-case error
$O(\sqrt{\epsilon(n)})+O(1/q(n))\leq O(1/q(n))$ for sufficiently large $n$.
Since this is true for all polynomials $q(n)$ and all
$\textsc{Uhlmann}_{1-\epsilon}$ instances $x=(1^{n},C,D)$, this establishes
that $\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$, as desired.
∎

###### Proof of Lemma 6.9.

First, some notation: we write $\mathsf{A}_{-i},\mathsf{B}_{-i}$ to denote
$\mathsf{A}_{[k]}$ without $\mathsf{A}_{i}$ and $\mathsf{B}_{[k]}$ without
$\mathsf{B}_{i}$, respectively.

The circuit $R$ is not necessarily unitary as it may trace out or measure
qubits, so let $\tilde{R}$ denote the unitary extension of $R$, i.e.,
$\tilde{R}$ is the circuit given by $R$ except all the measurements are
performed coherently using ancilla qubits. Note that the size of $\tilde{R}$
is at most polynomial in the size of $R$. The unitary $\tilde{R}$ acts on
registers $\mathsf{B}_{[k]}\mathsf{G}$ where $\mathsf{B}_{[k]}$ is the second
register of the state $\ket{C}^{\otimes k}$ and $\mathsf{G}$ is an ancilla
register.

The algorithm $M$ is presented in Algorithm 2. The algorithm depends on the
parameters $k,T$, and makes calls to the circuits $C,D,R$. Thus the claim
about the circuit size and uniformity of $M$ follow from inspection.

[breakable=true, padding=1em, margin-top=1em, margin-bottom=1em]

######  Algorithm 2.

Algorithm $M$ that maps $\ket{C}$ to $\ket{D}$ with small error, given that
$R$ maps $\ket{C}^{\otimes k}$ to $\ket{D}^{\otimes k}$ with large error.

Input:  Quantum register $\mathsf{B}$.

  1. 1.

Sample $i$ uniformly from $[k]$.

  2. 2.

Initialize registers $\mathsf{A}_{-i}\mathsf{B}_{-i}$ in the state
$\ket{C}^{\otimes k-1}$ and register $\mathsf{G}$ in the all-zero state.

  3. 3.

Relabel the $\mathsf{B}$ register as $\mathsf{B}_{i}$.

  4. 4.

For $t\in[T]$:

    1. (a)

Perform the following measurement, which we will call $P_{-i}$:

      1. i.

Apply $(C^{\otimes k-1})^{\dagger}$ to registers
$\mathsf{A}_{-i}\mathsf{B}_{-i}$.

      2. ii.

Measure whether the $\mathsf{A}_{-i}\mathsf{B}_{-i}$ registers are in the all-
zeroes state.

      3. iii.

Apply $C^{\otimes k-1}$.

    2. (b)

Perform the following measurement, which we will call $Q_{-i}$:

      1. i.

Apply $\tilde{R}$ to registers $\mathsf{B}_{[k]}\mathsf{G}$.

      2. ii.

Apply $(D^{\otimes k-1})^{\dagger}$ to registers
$\mathsf{A}_{-i}\mathsf{B}_{-i}$.

      3. iii.

Measure whether the $\mathsf{A}_{-i}\mathsf{B}_{-i}$ registers are in the all-
zeroes state.

      4. iv.

Apply $D^{\otimes k-1}$.

      5. v.

Apply $\tilde{R}^{\dagger}$ to registers $\mathsf{B}_{[k]}\mathsf{G}$.

    3. (c)

If the $Q_{-i}$ outcome succeeds (i.e., all-zeroes are measured in step
(iii)), then exit loop.

  5. 5.

Apply $\tilde{R}$ to registers $\mathsf{B}_{[k]}\mathsf{G}$, and output
register $\mathsf{B}_{i}$.

Define the projectors

$P\coloneqq\ket{C}\\!\\!\bra{C}^{\otimes
k}_{\mathsf{A}_{[k]}\mathsf{B}_{[k]}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{G}}\qquad\text{and}\qquad
Q\coloneqq\tilde{R}^{\dagger}\left(\ket{D}\\!\\!\bra{D}^{\otimes
k}_{\mathsf{A}_{[k]}\mathsf{B}_{[k]}}\otimes\textnormal{id}_{\mathsf{G}}\right)\tilde{R}~{}.$

The assumption that $R$ maps $\ket{C}^{\otimes k}$ to have fidelity at least
$\nu$ with $\ket{D}^{\otimes k}$ can be rewritten as $\mathrm{Tr}(PQ)\geq\nu$.
For simplicity assume that $\nu=\mathrm{Tr}(PQ)$ exactly. Let

$\ket{v}\coloneqq\ket{C}^{\otimes k}\otimes\ket{0},\qquad\ket{w}\coloneqq
Q\ket{v}/\sqrt{\nu}~{}.$

The two-dimensional subspace spanned by $\ket{v}$ and $\ket{w}$ defines two
additional vectors $\ket{v^{\perp}},\ket{w^{\perp}}$ where

$\displaystyle\ket{v}=\sqrt{\nu}\ket{w}+\sqrt{1-\nu}\ket{w^{\perp}}~{},\qquad\text{}\qquad\ket{v^{\perp}}=\sqrt{1-\nu}\ket{w}-\sqrt{\nu}\ket{w^{\perp}}$
$\displaystyle\ket{w}=\sqrt{\nu}\ket{v}+\sqrt{1-\nu}\ket{v^{\perp}}~{},\qquad\text{}\qquad\ket{w^{\perp}}=\sqrt{1-\nu}\ket{v}-\sqrt{\nu}\ket{v^{\perp}}~{}.$

Furthermore, this two-dimensional subspace is invariant under the action of
$P$, $Q$, as $\ket{v}=P\ket{w}/\sqrt{\nu}$ and $\ket{w}=Q\ket{v}/\sqrt{\nu}$.
We remark that this is a special case of Jordan’s Lemma [Bha13, Chapter VII].

Now for every $i\in[k]$ define the projectors

$P_{-i}=\ket{C}\\!\\!\bra{C}^{\otimes
k-1}\otimes\textnormal{id}_{\mathsf{A}_{i}\mathsf{B}_{i}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{G}}\qquad\text{and}\qquad
Q_{-i}=\tilde{R}^{\dagger}\left(\ket{D}\\!\\!\bra{D}^{\otimes
k-1}\otimes\textnormal{id}_{\mathsf{A}_{i}\mathsf{B}_{i}\mathsf{G}}\right)\tilde{R}~{}.$

Note that $P_{-i},Q_{-i}$ do not act on registers
$\mathsf{A}_{i}\mathsf{B}_{i}$, and that $P_{-i}P=PP_{-i}=P$ and
$Q_{-i}Q=QQ_{-i}=Q$.

We now argue that the operators $P_{-i},Q_{-i}$ are not far from $P,Q$ for a
randomly chosen $i$.

######  Claim 6.10.

For all unit length $\ket{\psi}$,

$\displaystyle\mathop{\mathbb{E}}_{i}\Big{\|}(P-P_{-i})\ket{\psi}\Big{\|}^{2}\leq\frac{1}{k}\qquad\text{and}\qquad\mathop{\mathbb{E}}_{i}\Big{\|}(Q-Q_{-i})\ket{\psi}\Big{\|}^{2}\leq\frac{1}{k}$

where the expectation is over a uniformly random $i\in[k]$.

###### Proof.

Note that $\mathop{\mathbb{E}}_{i}P_{-i}=(1-\frac{1}{k})P$. We now calculate:

$\displaystyle\mathop{\mathbb{E}}_{i}\Big{\|}(P-P_{-i})\ket{\psi}\Big{\|}^{2}$
$\displaystyle=\mathop{\mathbb{E}}_{i}\bra{\psi}(P-P_{-i})(P-P_{-i})\ket{\psi}=\mathop{\mathbb{E}}_{i}\bra{\psi}P_{-i}\ket{\psi}-\bra{\psi}P\ket{\psi}$
$\displaystyle=\bra{\psi}(\mathop{\mathbb{E}}_{i}P_{-i}-P)\ket{\psi}\leq\Big{\|}\mathop{\mathbb{E}}_{i}P_{-i}-P\Big{\|}_{\infty}$
$\displaystyle=\left\lVert\frac{1}{k}P\right\rVert_{\infty}=\frac{1}{k}.$

The proof for $Q$’s proceeds analogously. ∎

######  Claim 6.11.

For all $\ket{\psi}\in\mathrm{span}\\{\ket{v},\ket{w}\\}$, we have

$\mathop{\mathbb{E}}_{i}\max\Big{\\{}\Big{\|}(P-P_{-i})\ket{\psi}\Big{\|}^{2},\Big{\|}(Q-Q_{-i})\ket{\psi}\Big{\|}^{2}\Big{\\}}\leq\frac{4}{k}~{}.$

###### Proof.

Claim 6.10 implies

$\mathop{\mathbb{E}}_{i}\Big{\|}(P-P_{-i})\ket{v}\Big{\|}^{2}\leq\frac{1}{k}\qquad\text{and}\qquad\mathop{\mathbb{E}}_{i}\Big{\|}(P-P_{-i})\ket{v^{\perp}}\Big{\|}^{2}\leq\frac{1}{k}.$

Now a unit vector $\ket{\psi}$ in the span of $\ket{v},\ket{w}$ can be written
as $\ket{\psi}=\alpha\ket{v}+\beta\ket{v^{\perp}}$, so

$\mathop{\mathbb{E}}_{i}\Big{\|}(P-P_{-i})\ket{\psi}\Big{\|}^{2}\leq
2\mathop{\mathbb{E}}_{i}\Big{(}|\alpha|^{2}\Big{\|}(P-P_{-i})\ket{v}\Big{\|}^{2}+|\beta|^{2}\Big{\|}(P-P_{-i})\ket{v^{\perp}}\Big{\|}^{2}\Big{)}\leq\frac{2}{k}$

where we used that $|\alpha|^{2}+|\beta|^{2}=1$. The proof for the $Q$’s is
analogous. ∎

We now analyze the performance of Algorithm 2. Let $V_{i}$ denote the unitary
corresponding to the “for loop” in Algorithm 2, i.e., step 4, conditioned on
sampling $i$ in step 1. The algorithm is described in terms of measurements,
but we can imagine coherently performing the measurements and storing the
outcome in an ancilla qubit. In particular, we describe $V_{i}$ as a sequence
of alternating unitary operations. We introduce the following labels for
registers.

  1. 1.

Let $\mathsf{S}$ denote $\mathsf{A}_{[k]}\mathsf{B}_{[k]}\mathsf{G}$.

  2. 2.

Let $\mathsf{H}_{[T]}$ denote ancilla qubits that store the outcomes of the
$P$ measurements.

  3. 3.

Let $\mathsf{F}$ denote an ancilla qubit that indicates whether a $Q$
measurement succeeded.

The ancilla qubits all start in the zero state. Define the following unitary
transformations:

  1. 1.

For all $j\in[T]$, define

$A_{ij}=\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\otimes\Big{[}P_{-i}\otimes
X_{\mathsf{H}_{j}}+(I-P_{-i})\otimes\textnormal{id}_{\mathsf{H}_{j}}\Big{]}+\ket{1}\\!\\!\bra{1}_{\mathsf{F}}\otimes\textnormal{id}$

In other words, $A_{ij}$ performs the $j$’th $P_{-i}$ measurement: it checks
if the $\mathsf{F}$ qubit is set to $\ket{1}$. If so, it does nothing.
Otherwise, it performs the $P_{-i}$ measurement and flips the qubit in
register $\mathsf{H}_{j}$.

  2. 2.

We define

$B_{i}=\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\otimes(\textnormal{id}-Q_{-i})+\ket{1}\\!\\!\bra{0}_{\mathsf{F}}\otimes
Q_{-i}+\ket{1}\\!\\!\bra{1}_{\mathsf{F}}\otimes\textnormal{id}~{}.$

In other words, $B_{i}$ checks if the $\mathsf{F}$ qubit is set to $\ket{1}$.
If so, it does nothing. Otherwise, it performs the $Q_{-i}$ measurement and if
the $Q_{-i}$ outcome occurs, and flips $\mathsf{F}$ qubit.

Thus the state of the algorithm $V_{i}$ after the $j$’th step is

$\ket{\varphi_{ij}}\coloneqq B_{i}A_{ij}B_{i}A_{i,j-1}\cdots
B_{i}A_{i1}\ket{v}\ket{0\cdots
0}_{\mathsf{S}\mathsf{F}\mathsf{H}_{1}\cdots\mathsf{H}_{T}}~{}.$

Clearly $V_{i}$ is computable by a polynomial-size circuit.

We now consider another algorithm $\hat{V}$ which is the same as $V_{i}$
except instead of performing the $P_{-i},Q_{-i}$ measurements, performs $P,Q$
instead. Define the unitary matrices $\hat{A}_{1},\ldots,\hat{A}_{T}$ and
$\hat{B}$ in the same way except they perform the $P$ and $Q$ measurements
instead of $P_{-i}$ and $Q_{-i}$. Thus the state of the algorithm $\hat{V}$
after the $j$’th step is

$\ket{\hat{\varphi}_{j}}\coloneqq\hat{B}\hat{A}_{j}\hat{B}\hat{A}_{j-1}\cdots\hat{B}\hat{A}_{1}\ket{v}\ket{0\cdots
0}_{\mathsf{S}\mathsf{F}\mathsf{H}_{1}\cdots\mathsf{H}_{T}}~{}.$

Define $\ket{\hat{\varphi}_{0}}\coloneqq\ket{v}\ket{0\cdots 0}$. We will argue
that $\ket{\varphi_{ij}}$ is not far from $\ket{\hat{\varphi}_{j}}$ on average
over a randomly chosen index $i$.

######  Claim 6.12.

For all $j=0,...,T$, the $\mathsf{S}$ register of $\ket{\hat{\varphi}_{j}}$ is
supported on the subspace $\mathrm{span}\\{\ket{v},\ket{w}\\}$.

###### Proof.

We prove this by induction. This holds for $j=0$ because the initial state is
$\ket{v}\ket{0\cdots 0}$. Assume for induction that the statement is true up
to $j-1$. Note that

$\ket{\hat{\varphi}_{j}}=\hat{B}\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}~{}.$

The operator $\hat{A}_{j}$ either performs the $P$ measurement on register
$\mathsf{S}$ or does nothing; the post-measurement states remain inside the
two-dimensional subspace $\mathrm{span}\\{\ket{v},\ket{w}\\}$ because this
subspace is invariant under the action of $P$. Same with the $\hat{B}$
operator, which either performs the $Q$ measurement or does nothing. ∎

######  Claim 6.13.

For all $i\in[k]$ and $j\in[T]$ we have

$\mathop{\mathbb{E}}_{i}\Big{\|}(B_{i}A_{ij}-\hat{B}\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}\leq\frac{8}{\sqrt{k}}~{}.$

###### Proof.

By triangle inequality,

$\displaystyle\Big{\|}(B_{i}A_{ij}-\hat{B}\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}$
$\displaystyle\leq\Big{\|}B_{i}(A_{ij}-\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}+\Big{\|}(B_{i}-\hat{B})\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|}$
$\displaystyle=\Big{\|}(A_{ij}-\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}+\Big{\|}(B_{i}-\hat{B})\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|},$

where in the second line we used that $B_{i}$ is unitary. We analyze each term
separately. By triangle inequality again,

$\displaystyle\Big{\|}(A_{ij}-\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}$
$\displaystyle\leq\Big{\|}\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\otimes(P_{-i}-P)\otimes
X_{\mathsf{H}_{j}}\ket{\hat{\varphi}_{j-1}}\Big{\|}+\Big{\|}\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\otimes(P_{-i}-P)\otimes\textnormal{id}_{\mathsf{H}_{j}}\ket{\hat{\varphi}_{j-1}}\Big{\|}$
$\displaystyle=2\Big{\|}(P_{-i}-P)\ket{\hat{\varphi}_{j-1}}\Big{\|}~{}.$

Similarly we have

$\Big{\|}(B_{i}-\hat{B})\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|}\leq
2\Big{\|}(Q_{-i}-Q)\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|}~{}.$

Averaging over $i\in[k]$ we get

$\displaystyle\mathop{\mathbb{E}}_{i}\Big{\|}(B_{i}A_{ij}-\hat{B}\hat{A_{j}})\ket{\hat{\varphi}_{j-1}}\Big{\|}$
$\displaystyle\leq
2\Big{(}\mathop{\mathbb{E}}_{i}\Big{\|}(P_{-i}-P)\ket{\hat{\varphi}_{j-1}}\Big{\|}+\Big{\|}(Q_{-i}-Q)\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|}\Big{)}$
$\displaystyle\leq
2\Big{(}\sqrt{\mathop{\mathbb{E}}_{i}\Big{\|}(P_{-i}-P)\ket{\hat{\varphi}_{j-1}}\Big{\|}^{2}}+\sqrt{\mathop{\mathbb{E}}_{i}\Big{\|}(Q_{-i}-Q)\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}\Big{\|}^{2}}\Big{)}$
$\displaystyle\leq 4\sqrt{\frac{4}{k}}=\frac{8}{\sqrt{k}}$

where in the second line we used Jensen’s inequality, and in the third line we
used Claim 6.11 with the fact that the $\mathsf{S}$ registers of
$\ket{\hat{\varphi}_{j-1}}$ and $\hat{A}_{j}\ket{\hat{\varphi}_{j-1}}$ are
supported on the subspace $\mathrm{span}\\{\ket{v},\ket{w}\\}$. ∎

Putting everything together, we have by the triangle inequality

$\displaystyle\mathop{\mathbb{E}}_{i}\Big{\|}\ket{\varphi_{iT}}-\ket{\hat{\varphi}_{T}}\Big{\|}$
$\displaystyle\leq\mathop{\mathbb{E}}_{i}\sum_{j=1}^{T}\Big{\|}(B_{i}A_{ij}-\hat{B}\hat{A}_{j})\ket{\hat{\varphi}_{j-1}}\Big{\|}\leq
8T/\sqrt{k}~{}.$ (6.5)

Now we analyze the behavior of the $\hat{V}$ algorithm; by what we just
argued, the behavior of the $V_{i}$ algorithm is similar on average over $i$
(assuming that $T$ is sufficiently smaller than $\sqrt{k}$).

######  Claim 6.14.

$\Big{\|}(\textnormal{id}-Q)\ket{\hat{\varphi}_{T}}\Big{\|}^{2}\leq(1-\nu)^{T}$.

###### Proof.

Since the projector $\textnormal{id}-Q$ does not act on the ancilla
$\mathsf{H}_{[T]}$ registers, the quantity
$\Big{\|}(\textnormal{id}-Q)\ket{\hat{\varphi}_{T}}\Big{\|}^{2}$ is the
probability that running the algorithm $\hat{V}$ with _incoherent_ $P,Q$
measurements never yields a $Q$ outcome at any of the $T$ iterations.

Since the initial state of the algorithm is $\ket{v}\ket{0\ldots 0}$, and the
algorithm simply alternates between performing the $\\{P,\textnormal{id}-P\\}$
and $\\{Q,\textnormal{id}-Q\\}$ projective measurements, no matter what the
measurement outcomes are, the register $\mathsf{S}$ of the post-measurement
state is always either $\ket{v},\ket{w},\ket{v^{\perp}},\ket{w^{\perp}}$. If
register $\mathsf{S}$ is ever in the state $\ket{w}$, then that means the $Q$
outcome must have occurred, and the algorithm stops. Thus the quantity
$\Big{\|}(\textnormal{id}-Q)\ket{\hat{\varphi}_{T}}\Big{\|}^{2}$ is the
probability that the first iteration resulted in register $\mathsf{S}$ being
in the state $\ket{w^{\perp}}$, and for every iteration thereafter started in
$\ket{w^{\perp}}$ and ended in $\ket{w^{\perp}}$.

The probability that the first iteration ends in the state $\ket{w^{\perp}}$
is exactly $1-\nu$. In all the iterations thereafter, conditioned on the
starting state being $\ket{w^{\perp}}$, performing the
$\\{P,\textnormal{id}-P\\}$ measurement followed by the
$\\{Q,\textnormal{id}-Q\\}$ measurement yields the outcome $\ket{w^{\perp}}$
state again with probability $\nu^{2}+(1-\nu)^{2}$. Thus we get

$\Big{\|}(\textnormal{id}-Q)\ket{\hat{\varphi}_{T}}\Big{\|}^{2}=(1-\nu)(\nu^{2}+(1-\nu)^{2})^{T-1}\leq(1-\nu)^{T}$

as desired. ∎

We now bound the performance of $M$. We have that

$\mathrm{F}((\textnormal{id}_{\mathsf{A}}\otimes
M)\ket{C}\\!\\!\bra{C},\ket{D}\\!\\!\bra{D})=\bra{D}(\textnormal{id}_{\mathsf{A}}\otimes
M)(\ket{C}\\!\\!\bra{C})\ket{D}=1-\mathrm{Tr}\Big{(}(\textnormal{id}-\ket{D}\\!\\!\bra{D})(\textnormal{id}_{\mathsf{A}}\otimes
M)(\ket{C}\\!\\!\bra{C})\Big{)}~{}.$

Note that we can write the output of $M$ when given as input register
$\mathsf{B}$ of $\ket{C}$ as

$(\textnormal{id}_{\mathsf{A}}\otimes
M)(\ket{C}\\!\\!\bra{C})=\mathop{\mathbb{E}}_{i}\mathrm{Tr}_{\overline{\mathsf{B}_{i}}}\Big{(}\tilde{R}V_{i}(\ket{C}\\!\\!\bra{C}^{\otimes
k}\otimes\ket{0\ldots 0}\\!\\!\bra{0\ldots
0})V_{i}^{\dagger}\tilde{R}^{\dagger}\Big{)}$

where $\mathrm{Tr}_{\overline{\mathsf{B}_{i}}}(\cdot)$ denotes the partial
trace of all registers except for $\mathsf{B}_{i}$, and $\ket{0\ldots 0}$
denotes the ancilla qubits in registers
$\mathsf{G},\mathsf{F},\mathsf{H}_{[T]}$. Now observe that
$V_{i}\ket{C}^{\otimes k}\ket{0\ldots 0}$ is nothing but $\ket{\varphi_{iT}}$.
Therefore

$\displaystyle\mathrm{Tr}\Big{(}(\textnormal{id}-\ket{D}\\!\\!\bra{D})(\textnormal{id}_{\mathsf{A}}\otimes
M)(\ket{C}\\!\\!\bra{C})\Big{)}$
$\displaystyle=\mathop{\mathbb{E}}_{i}\Big{\|}(\textnormal{id}-\ket{D}\\!\\!\bra{D})_{\mathsf{A}_{i}\mathsf{B}_{i}}\tilde{R}_{x^{k}}\ket{\varphi_{iT}}\Big{\|}^{2}$
$\displaystyle\leq
2\Big{\|}(\textnormal{id}-Q)\ket{\hat{\varphi}_{T}}\Big{\|}^{2}+2\mathop{\mathbb{E}}_{i}\Big{\|}\ket{\varphi_{iT}}-\ket{\hat{\varphi}_{T}}\Big{\|}^{2}$
$\displaystyle\leq
2(1-\nu)^{T}+4\mathop{\mathbb{E}}_{i}\Big{\|}\ket{\varphi_{iT}}-\ket{\hat{\varphi}_{T}}\Big{\|}$
$\displaystyle\leq 2(1-\nu)^{T}+\frac{32T}{\sqrt{k}}~{}.$ (6.6)

In the second line we used the triangle inequality and the fact that

$\Big{\|}(\textnormal{id}-\ket{D}\\!\\!\bra{D})_{\mathsf{A}_{i}\mathsf{B}_{i}}\tilde{R}\ket{\varphi_{iT}}\Big{\|}^{2}=\Big{\|}\tilde{R}^{\dagger}(\textnormal{id}-\ket{D}\\!\\!\bra{D})_{\mathsf{A}_{i}\mathsf{B}_{i}}\tilde{R}\ket{\varphi_{iT}}\Big{\|}^{2}$

because $\tilde{R}$ is unitary, and that
$Q\leq\tilde{R}^{\dagger}\,\ket{D}\\!\\!\bra{D}_{\mathsf{A}_{i}\mathsf{B}_{i}}\,\tilde{R}$
in the positive semidefinite ordering. The third line uses Claim 6.14 and the
fact that $\Big{\|}\ket{\varphi_{iT}}-\ket{\hat{\varphi}_{T}}\Big{\|}^{2}\leq
2\Big{\|}\ket{\varphi_{iT}}-\ket{\hat{\varphi}_{T}}\Big{\|}$. The fourth line
uses Equation 6.5.

This concludes the proof of Lemma 6.9. ∎

####  6.3 The padding trick

We now turn to the complexity of $\textsc{DistUhlmann}_{\kappa}$ when $\kappa$
is bounded away from $0$ and $1$ by some inverse-polynomial quantity. Note
that for all $0\leq\kappa_{1}\leq\kappa_{2}\leq 1$, we have that all valid
instances of $\textsc{Uhlmann}_{\kappa_{2}}$ are valid instances of
$\textsc{Uhlmann}_{\kappa_{1}}$ but not vice versa (a similar statement holds
for SuccinctUhlmann). Thus, implementing general
$\textsc{Uhlmann}_{\kappa_{1}}$ transformations may potentially be more
difficult than implementing $\textsc{Uhlmann}_{\kappa_{2}}$ transformations.
Furthermore, it is no longer apparent that there is a zero-knowledge protocol
for, say, $\textsc{DistUhlmann}_{1/2}$. Thus it is not clear how the
complexities of $\textsc{Uhlmann}_{\kappa_{1}}$ and
$\textsc{Uhlmann}_{\kappa_{2}}$ relate to each other for different
$\kappa_{1},\kappa_{2}$.

We present a simple padding trick which shows that as long as
$\kappa_{1},\kappa_{2}$ are bounded by at least some inverse polynomial from
either $0$ or $1$, the complexities of $\textsc{DistUhlmann}_{\kappa_{1}}$ and
$\textsc{DistUhlmann}_{\kappa_{2}}$ are equivalent under polynomial-time
reductions.

######  Lemma 6.15 (Padding trick).

Let $0\leq\kappa_{1}\leq\kappa_{2}\leq 1$ and let $C,D$ be circuits on $2n$
qubits such that $\mathrm{F}(\rho,\sigma)\geq\kappa_{1}$ where $\rho,\sigma$
are the reduced density matrices of
$\ket{C}=C\ket{0^{2n}},\ket{D}=D\ket{0^{2n}}$, respectively, on the first $n$
qubits. Let $0<\alpha\leq(1-\kappa_{2})/(1-\kappa_{1})$. Define the following
states $\ket{E},\ket{F}$ on $2(n+1)$ qubits where

$\displaystyle\ket{E}$
$\displaystyle=\sqrt{\alpha}\ket{0}\ket{C}\ket{0}+\sqrt{1-\alpha}\ket{1^{2(n+1)}}$
$\displaystyle\ket{F}$
$\displaystyle=\sqrt{\alpha}\ket{0}\ket{D}\ket{0}+\sqrt{1-\alpha}\ket{1^{2(n+1)}}~{}.$

Suppose that the state $\sqrt{\alpha}\ket{0}+\sqrt{1-\alpha}\ket{1}$ can be
prepared using a circuit of size $s$. Then the following hold:

  1. 1.

$\ket{E}$, $\ket{F}$ can be computed by circuits $E,F$ of size $O(|C|+|D|+s)$;

  2. 2.

$\mathrm{F}(\tau,\mu)\geq\kappa_{2}$ where $\tau,\mu$ are the reduced density
matrices of $\ket{E},\ket{F}$ on the first $n+1$ qubits;

  3. 3.

The canonical $(n+1)$-qubit Uhlmann isometry $V$ for $(\ket{E},\ket{F})$ can
be written as

$V=U\otimes\ket{0}\\!\\!\bra{0}+\textnormal{id}\otimes\ket{1}\\!\\!\bra{1}$

where $U$ is the $n$-qubit canonical Uhlmann isometry for $(\ket{C},\ket{D})$.

###### Proof.

We prove the first item. To compute the state $\ket{E}$, consider the circuit
$E$ on $2(n+1)$ qubits that does the following:

  1. 1.

Initialize the first qubit in the state
$\sqrt{\alpha}\ket{0}+\sqrt{1-\alpha}\ket{1}$.

  2. 2.

Apply a CNOT from the first qubit to the last qubit.

  3. 3.

Controlled on the first qubit being $\ket{0}$, run the $n$-qubit circuit $C$
on qubits $2$ through $n+1$.

  4. 4.

Controlled on the first qubit being $\ket{1}$, apply a bitflip operator to
qubits $2$ through $n+1$.

Clearly the size of $E$ is $O(|C|+s)$ where $|C|$ denotes the size of circuit
$C$ where by assumption there is a circuit of size $s$ to initialize the first
qubit. An analogous construction holds for $\ket{F}$.

For the second item, we have

$\displaystyle\tau=\alpha\ket{0}\\!\\!\bra{0}\otimes\rho+(1-\alpha)\ket{1}\\!\\!\bra{1}\otimes\ket{1^{n}}\\!\\!\bra{1^{n}}$
$\displaystyle\mu=\alpha\ket{0}\\!\\!\bra{0}\otimes\sigma+(1-\alpha)\ket{1}\\!\\!\bra{1}\otimes\ket{1^{n}}\\!\\!\bra{1^{n}}~{}.$

The fidelity between $\tau$ and $\mu$ can be bounded as
$\mathrm{F}(\tau,\mu)=\alpha\mathrm{F}(\rho,\sigma)+1-\alpha\geq\alpha\kappa_{1}+1-\alpha\geq\kappa_{2}$.

For the third item, recall that the canonical Uhlmann isometry (where we have
set the cutoff $\eta$ to $0$) for $(\ket{E},\ket{F})$ is defined as

$V=\operatorname{sgn}(\mathrm{Tr}_{\mathsf{A^{\prime}}}(\ket{E}\\!\\!\bra{F}))$

where $\mathsf{A^{\prime}}$ denotes the first $n+1$ qubits of
$\ket{E},\ket{F}$. This is equal to

$\displaystyle\operatorname{sgn}\Big{(}\alpha\mathrm{Tr}_{\mathsf{A}}(\ket{C}\\!\\!\bra{D})\otimes\ket{0}\\!\\!\bra{0}+(1-\alpha)\ket{1^{n}}\\!\\!\bra{1^{n}}\otimes\ket{1}\\!\\!\bra{1}\Big{)}=\operatorname{sgn}(\mathrm{Tr}_{\mathsf{A}}(\ket{C}\\!\\!\bra{D}))\otimes\ket{0}\\!\\!\bra{0}+\ket{1^{n}}\\!\\!\bra{1^{n}}\otimes\ket{1}\\!\\!\bra{1}$

where $\mathsf{A}$ denotes the first $n$ qubits of $\ket{C},\ket{D}$. To
conclude, note that
$\operatorname{sgn}(\mathrm{Tr}_{\mathsf{A}}(\ket{C}\\!\\!\bra{D}))$ is the
canonical Uhlmann isometry for $(\ket{C},\ket{D})$. ∎

######  Lemma 6.16 (Average-case reductions for
$\textsc{DistUhlmann}_{\kappa}$ for different fidelities $\kappa$).

Let $\kappa:\mathbb{N}\to[0,1]$ be such that $1/p(n)\leq\kappa(n)\leq
1-1/p(n)$ for all $n$ for some polynomial $p(n)$. Then
$\textsc{DistUhlmann}_{\kappa}$ polynomial-time reduces to
$\textsc{DistUhlmann}_{1-1/p}$.

###### Proof.

For every valid $\textsc{Uhlmann}_{\kappa}$ instance $x=(1^{n},C,D)$, let
$y=(1^{2(n+1)},E,F)$ denote the valid $\textsc{Uhlmann}_{1-1/p}$ instance
given by the padding trick (Lemma 6.15), where $\alpha(n)=1/p(n)$. The state
$\sqrt{\alpha(n)}\ket{0}+\sqrt{1-\alpha(n)}\ket{1}$ can be prepared with
circuits of size $O(\log n)$ by the Solovay-Kitaev theorem, so by Lemma 6.15
$E$ and $F$ are also polynomial-sized (in $n$) circuits. Furthermore, given
explicit descriptions of $C,D$ one can efficiently compute explicit
descriptions of $E,F$.

To prove the lemma, let $q(n)$ be an arbitrary polynomial. By Definition 3.21
we need to find another polynomial $r(n)$ (which can depend on $q(n)$) and a
polynomial-time quantum query algorithm $A^{*}$ such that any $1/r(n)$-error
average case instantiation (see Definition 3.20) of
$A^{\textsc{DistUhlmann}}_{1-1/p}$ implements $\textsc{DistUhlmann}_{1/p}$
with average-case error $1/q(n)$.

We define $A^{*}=(A^{*}_{x})_{x}$ as follows. The circuit $A^{*}_{x}$ takes as
input an $n$-qubit register $\mathsf{B}$ and initializes a single-qubit
register $\mathsf{F}$ in the state $\ket{0}$. It then applies the
$\textsc{DistUhlmann}_{1-1/p}$ oracle for instance $y$ (whose description can
be efficiently computed from $x$) on registers $\mathsf{F}\mathsf{B}$ and
outputs the result.

To show that this implements $\textsc{DistUhlmann}_{1/p}$, let
$r(n)=p(n)q(n)$, and let $A^{\textsc{DistUhlmann}_{1-1/p}}$ denote a
$1/r(n)$-error average-case instantiation. Concretely, let $V_{y}$ denote the
(exact) Uhlmann partial isometry for instance $y$ and let $H=(H_{y})_{y}$
denote a quantum algorithm that implements $\textsc{DistUhlmann}_{1-1/p}$ with
average-case error $1/r(n)$ and is used to instantiate the
$\textsc{DistUhlmann}_{1-1/p}$-oracle. This means there is a channel
completion $\Phi_{y}$ of $V_{y}$ such that

$\mathrm{td}\Big{(}(\textnormal{id}\otimes
H_{y})(\ket{E}\\!\\!\bra{E}),(\textnormal{id}\otimes\Phi_{y})(\ket{E}\\!\\!\bra{E})\Big{)}\leq\frac{1}{r(|y|)}~{}.$

By the third item of Lemma 6.15, any channel completion $\Phi_{y}$ of $V_{y}$
can be turned into a channel completion of $\Xi_{x}$ of $U_{x}$, the
$\textsc{Uhlmann}_{\kappa}$ transformation corresponding to
$(\ket{C},\ket{D})$. Define
$\Xi_{x}(\rho)\coloneqq\mathrm{Tr}_{\mathsf{G}}(\Phi_{x}(\rho\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{G}}))$
where $\mathsf{G}$ denotes the last qubit. Let $\Pi$ denote the support onto
$U_{x}$. Then
$\Xi_{x}(\Pi\rho\Pi)=\mathrm{Tr}_{\mathsf{G}}(\Phi_{x}(\Pi\rho\Pi\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{G}}))$.
But notice that the state $\Pi\rho\Pi\otimes\ket{0}\\!\\!\bra{0}$ is contained
in the support of $V_{y}$; therefore

$\displaystyle\mathrm{Tr}_{\mathsf{G}}(\Phi_{x}(\Pi\rho\Pi\otimes\ket{0}\\!\\!\bra{0}))=\mathrm{Tr}_{\mathsf{G}}\Big{(}V_{y}(\Pi\rho\Pi\otimes\ket{0}\\!\\!\bra{0})V_{y}^{\dagger}\Big{)}=U_{x}\Pi\rho\Pi
U_{x}^{\dagger}$

where we used the expression for $V_{y}$ given by Lemma 6.15. Thus we can
evaluate the performance of the instantiation
$A^{\textsc{DistUhlmann}_{1-1/p}}$ on the input $\ket{C}$:

$\displaystyle\mathrm{td}\Big{(}(\textnormal{id}\otimes
A^{\textsc{DistUhlmann}_{1-1/p}}_{x})(\ket{C}\\!\\!\bra{C}),\,(\textnormal{id}\otimes\Xi_{x})(\ket{C}\\!\\!\bra{C})\Big{)}$
$\displaystyle=\mathrm{td}\Big{(}(\textnormal{id}\otimes
H_{y})(\ket{0}\\!\\!\bra{0}\otimes\ket{C}\\!\\!\bra{C}\otimes\ket{0}\\!\\!\bra{0}),\,(\textnormal{id}\otimes\Phi_{y})(\ket{0}\\!\\!\bra{0}\otimes\ket{C}\\!\\!\bra{C})\otimes\ket{0}\\!\\!\bra{0}\Big{)}$
$\displaystyle=\frac{1}{\alpha(n)}\mathrm{td}\Big{(}(\textnormal{id}\otimes
H_{y})(P\ket{E}\\!\\!\bra{E}P^{\dagger}),\,(\textnormal{id}\otimes\Phi_{y})(P\ket{E}\\!\\!\bra{E}P^{\dagger})\Big{)}$
$\displaystyle\leq\frac{1}{\alpha(n)}\mathrm{td}\Big{(}(\textnormal{id}\otimes
H_{y})(\ket{E}\\!\\!\bra{E}),\,(\textnormal{id}\otimes\Phi_{y})(\ket{E}\\!\\!\bra{E})\Big{)}$
$\displaystyle\leq\frac{1}{\alpha(n)r(n)}=\frac{1}{q(n)}~{}.$

In the second line, we expanded the definitions of the query circuit $A_{x}$
and the channel completion $\Xi_{x}$. In the third line, we define the
projector $P=\ket{0}\\!\\!\bra{0}$ which acts on the first qubit so that
$\ket{0}\ket{C}\ket{0}=\frac{1}{\sqrt{\alpha(n)}}P\ket{E}$. In the fifth line
we used the guarantees about the algorithm $H_{y}$ and our definitions of
$\alpha(n),r(n)$. ∎

The padding trick allows us to make statements about
$\textsc{Uhlmann}_{\kappa}$ and $\textsc{DistUhlmann}_{\kappa}$ for the case
where $\kappa$ is at least an inverse polynomial. However, it may be that
Uhlmann with negligible $\kappa$ is more powerful than this. We leave this as
an open question.

######  Open Problem 12.

What is the power of $\textsc{Uhlmann}_{\kappa}$ or
$\textsc{DistUhlmann}_{\kappa}$ for negligible $\kappa$?

####  6.4 A polarization lemma for unitary zero knowledge?

Sahai and Vadhan [SV03] introduced the StatisticalDistance problem and showed
that it is complete for SZK. Here, an instance $(1^{n},C_{0},C_{1})$ of
StatisticalDistance consists of a pair of probability distributions (specified
by circuits $C_{0},C_{1}$ which produce samples from them) and the problem is
to decide whether the distributions are _close_ (below the threshold $1/3$) or
_far apart_ (above the threshold $2/3$) in terms of statistical distance. A
key technical ingredient in their proof system is the so-called “polarization
lemma”. This is an efficient transformation that takes as input a pair of
probability distributions (specified by circuits) and produces a new pair of
distributions (in the form of new pair of circuits) with the following two
guarantees:

  * •

if the initial pair of distributions is statistically _close_ (below the
threshold $1/3$), then the new pair of distributions is statistically _much
closer_ (below the threshold $2^{-n}$), whereas

  * •

if the initial pair of distributions is statistically far apart (above the
threshold $2/3$), then new pair is statistically _much further apart_ (above
the threshold $1-2^{-n}$).

This raises the following natural question: is it possible to obtain a
“polarization lemma” in the context of $\mathsf{avgUnitarySZK}$ – the unitary
analogue of (average-case) SZK? Specifically, we ask:

######  Open Problem 13.

Is it possible to prove a “polarization lemma” which transforms an instance of
$\textsc{Uhlmann}_{\kappa}$ for a small $\kappa$, say $\kappa=1/2$, into an
instance of $\textsc{Uhlmann}_{1-\mathrm{negl}(n)}$ for some negligible
function, say $2^{-n}$?

Note that the latter problem is complete for $\mathsf{avgUnitarySZK}$, as we
established in Theorem 6.7. Watrous [Wat06] previously extended the
polarization technique to _density operators_ (specified by quantum circuits
which prepare them), and showed that QuantumStateDistinguishability is
complete for QSZK. This suggests that one could potentially apply a similar
transformation as in [Wat06, Theorem 1] in order to map an
$\textsc{Uhlmann}_{1/2}$ instance $(1^{n},C,D)$ with
$\mathrm{F}(\rho,\sigma)\geq 1/2$ (where $\rho$ and $\sigma$ represent the
mixed states induced by $C,D$) into an $\textsc{Uhlmann}_{1-2^{-n}}$ instance
$(1^{n},\tilde{C},\tilde{D})$ with
$\mathrm{F}(\tilde{\rho},\tilde{\sigma})\geq 1-2^{-n}$. While such a circuit
transformation is indeed possible via auxiliary qubits (which encode random
coins required for polarization), any auxiliary qubits must necessarily be
part of the _purifying register_ on which the Uhlmann unitary is allowed to
act upon. This significantly complicates the matter when quantum input states
are taken into account; for example, it is unclear how to relate instances of
$\textsc{DistUhlmann}_{1/2}$ to valid instances of
$\textsc{DistUhlmann}_{1-2^{-n}}$. We leave the task of finding a polarization
lemma for $\mathsf{avgUnitarySZK}$ – or to find evidence against one – as an
interesting open problem.

###  7 Structural Results about the Succinct Uhlmann Transformation Problem

In this section, we show that the $\textsc{DistSuccinctUhlmann}_{1}$ problem
captures the complexity of both $\mathsf{avgUnitaryPSPACE}$ and
$\mathsf{avgUnitaryQIP}$, which allows us to show that the two unitary
complexity classes are equal. Concretely, we show that
$\textsc{DistSuccinctUhlmann}_{1}$ is a complete problem both for
$\mathsf{avgUnitaryQIP}$ (Section 7.1) and for $\mathsf{avgUnitaryPSPACE}$
(Section 7.2), which implies equality of the classes (Corollary 7.13). We then
show additional structural results about the succinct Uhlmann transformation
problem, namely that SuccinctUhlmann is complete for worst-case
$\mathsf{unitaryPSPACE}$ for a suitable choice of cutoff parameter (Section
7.3), and how DistSuccinctUhlmann relates to classical (worst-case)
$\mathsf{PSPACE}$ (Section 7.4).

####  7.1 Completeness for $\mathsf{avgUnitaryQIP}$

#####  7.1.1 $\textsc{DistSuccinctUhlmann}_{1}\in\mathsf{avgUnitaryQIP}$

We begin with an $\mathsf{avgUnitaryQIP}$ protocol for
$\textsc{DistSuccinctUhlmann}_{1}$, which we will use to show that
$\textsc{DistSuccinctUhlmann}_{1}\in\mathsf{avgUnitaryQIP}$. The protocol
closely mirrors that of 1 (the $\mathsf{avgUnitarySZK}$ protocol for
DistUhlmann), except that the circuits $C$ and $D$ are no longer polynomial
size since now they are specified succinctly. As a result, the polynomial time
verifier can no longer easily get copies of the $\mathsf{statePSPACE}$-state
$\ket{C}$ and can no longer directly implement the unitary $D^{\dagger}$ to
check that the Uhlmann transformation was applied correctly, which were
important steps in 1. For the first problem, we recall that
$\mathsf{statePSPACE}=\mathsf{stateQIP}$ [MY23], so by interacting with the
prover, the verifier generate additional copies of the input state $\ket{C}$
(up to arbitrary inverse polynomial error). To solve the second problem, we
show that the verifier can perform the measurement
$\\{\ket{D}\\!\\!\bra{D},\textnormal{id}-\ket{D}\\!\\!\bra{D}\\}$ on an
arbitrary state with help from the prover. We describe these in more detail
next.

###### Interactive state synthesis.

First we recall the main result of of [RY22], which shows that there is an
efficient interactive protocol to synthesize any state sequence
$(\ket{\psi_{x}})_{x}\in\mathsf{statePSPACE}$. We describe this result at a
high level (for formal details see [RY22]): for every $\mathsf{statePSPACE}$
state sequence $(\ket{\psi_{x}})_{x}$ there exists a polynomial-time quantum
verifier $V=(V_{x})_{x}$ such (a) there exists an honest prover $P^{*}$ that
is accepted by the verifier with probability $1$ (_completeness_), and after
interacting with the honest prover the output register of the verifier is
close to $\ket{\psi_{x}}$ to within $2^{-n}$ in trace distance (_honest
closeness_), and (b) for all provers $P$ that are accepted with probability at
least $\frac{1}{2}$ (_soundness_), the output register of the verifier is
close to $\ket{\psi_{x}}$ within some polynomial $1/p(|x|)$ in trace distance
(_closeness_).

In what follows we will utilize as a subroutine the interactive state
synthesis protocol for the sequence $\Gamma=(\ket{C})_{\hat{C}}$ which is
indexed by all succinct descriptions $\hat{C}$ of a unitary circuit $C$ and
$\ket{C}$ is the corresponding output state of the circuit (given all zeroes).
It is straightforward to see that $\Gamma\in\mathsf{statePSPACE}$, and
therefore there is a $\mathsf{stateQIP}$ protocol to synthesize $\Gamma$.

###### Interactive measurement synthesis.

Next we describe another primitive which is a protocol for _interactive
measurement synthesis_. At a high level, this is a protocol where a verifier
gets a description of a measurement $M$ and an input register $\mathsf{A}$ in
an unknown state $\tau$. The verifier interacts with a prover and at the end
outputs a measurement outcome bit $b$ as well as register $\mathsf{A}$. If the
prover is accepted with sufficiently high probability, then (a) the
measurement outcome bit $b$ is $1$ with probability close to
$\mathrm{Tr}(M\tau)$, and (b) conditioned on acceptance and $b=1$, the output
register $\mathsf{A}$ is close to being in the state $\tau|_{M}$, the post-
measurement state131313Recall the notation used for post-measurement states
defined in Section 2. of $\tau$ conditioned on measuring $M$.

We show there is an efficient interactive measurement synthesis protocol for
the case when the measurement $M$ is a rank-one projector
$\ket{\psi}\\!\\!\bra{\psi}$ for some succinctly described state $\ket{\psi}$.

######  Lemma 7.1 (Approximate measurement protocol).

Let $\Psi=(\ket{\psi_{x}})_{x}$ be a $\mathsf{stateQIP}$ family of states.
Then for all polynomials $p(n)$, there exists a polynomial-time quantum
verifier $V$ that takes as input register $\mathsf{A}$, and outputs an
accept/reject flag, a measurement outcome bit $b$, and a register $\mathsf{A}$
such that the following properties hold:

  1. 1.

(Completeness) There exists an honest prover $P^{*}$ such that for all input
states $\tau_{\mathsf{A}}$

$\Pr[V(\tau_{\mathsf{A}})\mathord{\leftrightarrows}P^{*}\text{ accepts}]=1\,.$

Furthermore, given input state $\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}$ in
register $\mathsf{A}$, the verifier outputs $b=1$ with overwhelming
probability:

$\Pr[V(\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}_{\mathsf{A}})\mathord{\leftrightarrows}P^{*}\text{
outputs $1$}]\geq 1-2^{-|x|}\,.$

  2. 2.

(Soundness) For all input states $\tau_{\mathsf{AR}}$ (where $\mathsf{R}$ is
an arbitrary external register not touched by the verifier or prover) and for
all provers $P$ such that $V(\tau_{\mathsf{AR}})\mathord{\leftrightarrows}P$
accepts with probability at least $1/2$,

$\Big{|}\Pr\left[\text{$V$ outputs $b=1$}\mid\text{$V$
accepts}\right]-\mathrm{Tr}\Big{(}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}_{\mathsf{A}}\,\tau_{\mathsf{A}}\Big{)}\Big{|}\leq\frac{1}{p(|x|)}\,,$

where the events “outputs $b=1$” and “accepts” are with respect to the
interaction $V(\tau_{\mathsf{AR}})\mathord{\leftrightarrows}P$. If
additionally
$\mathrm{Tr}\Big{(}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}_{\mathsf{A}}\,\tau_{\mathsf{A}}\Big{)}\geq\frac{1}{2}$,
then the final state $(\tau_{acc})_{\mathsf{AR}}$ at the end of the protocol
conditioned on acceptance and conditioned on measurement outcome bit $b=1$
satisfies

$\mathrm{td}(\tau_{acc},\tau|_{\psi_{x}\otimes\textnormal{id}})\leq\frac{1}{p(|x|)}\,,$
(7.1)

where $\tau|_{\psi_{x}\otimes\textnormal{id}}$ denotes the post-measurement
state of $\tau_{\mathsf{AR}}$ conditioned on projecting the $\mathsf{A}$
register onto the state $\ket{\psi_{x}}$. Let $1/p(n)$ be the _closeness_ of
the verifier.

In the second part of the soundness condition, we only require that the
verifier’s quantum output is close in trace distance to
$\tau|_{\psi_{x}\otimes\textnormal{id}}$ if the verifier accepts with
probability $\frac{1}{2}$ _and_ the probability of obtaining measurement
outcome $1$ (with the ideal measurement) is at least $1/2$. Intuitively, the
reason for this is that Equation 7.1 makes a statement involving the
conditioned state $\tau|_{\psi_{x}\otimes\textnormal{id}}$, which can become
very sensitive to errors if the measurement probability
$\mathrm{Tr}\Big{(}\ket{\psi_{x}}\\!\\!\bra{\psi_{x}}_{\mathsf{A}}\,\tau_{\mathsf{A}}\Big{)}$
is very small. The $1/2$ threshold can be relaxed to being any inverse
polynomial if the trace distance error is suitably adjusted.

We defer the proof of Lemma 7.1 to Section 7.1.3.

We now use these two primitives (interactive state and measurement synthesis)
to prove the following.

######  Lemma 7.2.

$\textsc{DistSuccinctUhlmann}_{1}\in\mathsf{avgUnitaryQIP}$.

###### Proof.

Fix a polynomial $q(n)$. We present in 2 an $\mathsf{avgUnitaryQIP}$ protocol
for $\textsc{DistSuccinctUhlmann}_{1}$ with completeness $1-2^{-\Omega(n)}$,
soundness $\frac{1}{2}$, and closeness $1/q(n)$. We use as subroutines

  1. 1.

The $\mathsf{stateQIP}$ protocol for synthesizing the state sequence $\Gamma$
(which is all succinctly described states) with completeness $1$, soundness
$1/2$, and closeness $1/32q(n)^{2}$.

  2. 2.

The approximate measurement protocol from Lemma 7.1 for the state sequence
$\Gamma$ with closeness $1/32q(n)^{2}$.

For a circuit $C$ we write $C^{\otimes m}$ to denote $m$ parallel copies of
the circuit which generates the product state $\ket{C}^{\otimes m}$.

[breakable=false, padding=1em, margin-top=1em, margin-bottom=1em]

######  Protocol 2.

$\mathsf{avgUnitaryQIP}_{1-2^{-n+1},\frac{1}{2},\frac{1}{q}}$ verifier for
$\textsc{DistSuccinctUhlmann}_{1}$

Input:  Classical string $x=(1^{n},\hat{C},\hat{D})$ specifying a succinct
description of a pair of circuits $(C,D)$, and quantum register
$\mathsf{B}_{0}$.

  1. 1.

Let $m=16q(n)^{2}$, and perform the $\mathsf{stateQIP}$ protocol to synthesize
$\ket{C}^{\otimes m}$ in registers
$\mathsf{A_{1}}\mathsf{B_{1}}\cdots\mathsf{A_{m}}\mathsf{B_{m}}$. If the
$\mathsf{stateQIP}$ protocol rejects, reject.

  2. 2.

Select a permutation $\pi\in S_{m+1}$ uniformly at random and apply
$\mathcal{P}_{\pi}$ to $\mathsf{B}_{[0:m]}$. Send $\mathsf{B}_{[0:m]}$ to the
prover.

  3. 3.

Verifier receives registers $\mathsf{B}_{[0:m]}$ from the prover. Then

    1. (a)

Apply $\mathcal{P}_{\pi^{-1}}$ to $\mathsf{B}_{[0:m]}$.

    2. (b)

Perform the approximate measurement protocol with measurement
$\ket{D}\\!\\!\bra{D}^{\otimes m}$ on quantum register $\mathsf{AB}_{[m]}$. If
the protocol rejects or outputs $b=0$, reject.

    3. (c)

Accept and output the register $\mathsf{B}_{0}$.

We show that the verifier described in 2 satisfies the required properties of
$\mathsf{avgUnitaryQIP}$ protocols. First, it is clear that the verifier runs
in polynomial time. This uses the fact that the $\mathsf{stateQIP}$ and
approximate measurement verifiers run in polynomial time, and the succinct
descriptions of $\ket{C}^{\otimes m}$ and $\ket{D}^{\otimes m}$ are
polynomial-sized in the lengths of the succinct descriptions $\hat{C}$ and
$\hat{D}$. We prove the completeness and soundness conditions in separate
lemmas:

  1. 1.

There is an honest quantum prover that success with probability at least
$1-2^{-n+1}$ (Lemma 7.3).

  2. 2.

The verifier satisfies the soundness condition of an
$\mathsf{avgUnitaryQIP}_{1-2^{-n+1},1/2,1/q}$ protocol (Lemma 7.4).

Combined, Lemmas 7.3 and 7.4 imply Lemma 7.2. ∎

######  Lemma 7.3 (Completeness).

For all valid $\textsc{SuccinctUhlmann}_{1}$ instances
$x=(1^{n},\hat{C},\hat{D})$, for sufficiently large $n$, there exists an
honest prover for 2 satisfying

$\Pr[V_{x}(\ket{C})\mathord{\leftrightarrows}P]\geq 1-2^{-n+1}\,.$

###### Proof.

We define an honest prover that acts as follows: the honest prover first
implements the honest prover $\mathsf{stateQIP}$ protocol with honest
closeness $2^{-n}$. Then the prover implements the Uhlmann unitary between $C$
and $D$. Finally the prover implements the honest prover for the approximate
measurement protocol. After the first step of the protocol, the verifier holds
a state within trace distance $2^{-n}$ of $\ket{C}^{\otimes m+1}$ on registers
$\mathsf{AB}_{[0:m]}$, and after the second step the optimal Uhlmann unitary
has been performed. Therefore after the second step the verifier holds a state
within trace distance $2^{-n}$ of $\ket{D}^{\otimes m+1}$. By the completeness
property of the approximate measurement protocol, the verifier accepts with
probability $1$, and when run on $\ket{D}^{\otimes m}$, the protocol outputs
the bit $b=1$ with probability at least $1-2^{-n}$. Since the input state is
within $2^{-n}$ of $\ket{D}^{\otimes m}$ in trace distance, the approximate
measurement protocol on the verifier’s real state outputs $1$ with probability
at least $1-2^{-n+1}$. When interacting with this honest prover, this is the
only step where the verifier has a non-zero chance of rejecting, so the
verifier accepts with probability at least $1-2^{-n+1}$. ∎

######  Lemma 7.4 (Soundness).

For all valid $\textsc{SuccinctUhlmann}_{1}$ instances
$x=(1^{n},\hat{C},\hat{D})$, for sufficiently large $n$, for all quantum
provers $P$, there exists a channel completion $\Phi_{x}$ of $U_{x}$ such that

$\text{if }\quad{\rm Pr}\left[V_{x}(\ket{C})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq\frac{1}{2}\qquad\text{then}\qquad\mathrm{td}(\sigma,(\Phi_{x}\otimes\textnormal{id})\ket{C}\\!\\!\bra{C})\leq
1/q(n)~{},$

where $\sigma$ denotes the output of
$V_{x}(\ket{C})\mathord{\leftrightarrows}P$ conditioned on the verifier
$V_{x}$ accepting where $q(n)$ is the polynomial used to define 2.

###### Proof.

By the definition of $\textsc{SuccinctUhlmann}_{1}$, for all channel
completions $\Phi_{x}$ of $U_{x}$ we have that
$(\Phi_{x}\otimes\textnormal{id})(\ket{C}\\!\\!\bra{C})=\ket{D}\\!\\!\bra{D}$,
so it suffices to show that conditioned on accepting, the verifier outputs a
state within $1/q(n)$ of $\ket{D}\\!\\!\bra{D}$ in trace distance. The proof
follows the template set by the proof that
$\textsc{DistUhlmann}_{1-\mathrm{negl}}\in\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$,
with some subtle differences. We first appeal to Lemma 6.3 to claim that if
the verifier could prepare exactly $\ket{C}\\!\\!\bra{C}^{\otimes m}$ in
registers $\mathsf{AB}_{[m]}$ after the $\mathsf{stateQIP}$ protocol,
measuring $\ket{D}\\!\\!\bra{D}$ on $\mathsf{A_{0}B_{0}}$ accepts with high
probability. We then show that the verifier’s true state, with errors coming
from both state preparation and approximate measurement, is close to this
ideal post-measurement state. Finally we apply the Gentle Measurement Lemma.

We begin, as before, by expressing the state of the verifier’s registers. By
the soundness property of $\mathsf{stateQIP}$, if the verifier accepts with
probability at least $1/2$, after step $1$ the verifier has a state in
registers $\mathsf{AB}_{[0:m]}$ that is within $1/32q(n)^{2}$ of
$\ket{C}^{\otimes m}$ in trace distance. Let $\rho_{0}$ be the state of
registers $\mathsf{AB}_{[m]}$ after accepting in step $1$ of the protocol.
After performing the $\mathsf{stateQIP}$ protocol, the verifier applies a
random permutation on $\mathsf{B}_{[0:m]}$; then the prover will perform some
arbitrary action on $\mathsf{B}_{[0:m]}$ represented by a quantum channel
$\Lambda$; and finally the verifier will undo the permutation from the first
step. Treating $\mathsf{A_{0}}$ as a purification of the verifier’s quantum
input, the state of $\mathsf{AB}_{[0:m]}$ is given by

$\rho^{*}\coloneqq\mathbb{E}_{\pi\in
S_{m+1}}\left((\mathcal{P}_{\pi^{-1}})_{\mathsf{B}_{[0:m]}}\circ\Lambda_{\mathsf{B}_{[0:m]}}\circ(\mathcal{P}_{\pi})_{[0:m]}\right)(\ket{C}\\!\\!\bra{C}_{\mathsf{A_{0}B_{0}}}\otimes(\rho_{0})_{\mathsf{AB}_{[m]}})$
(7.2)

Let the state $\sigma^{*}$ be defined as follows

$\sigma^{*}=\mathbb{E}_{\pi\in
S_{m+1}}\left((\mathcal{P}_{\pi^{-1}})_{\mathsf{B}_{[0:m]}}\circ\Lambda_{\mathsf{B}_{[0:m]}}\circ(\mathcal{P}_{\pi})_{\mathsf{B}_{[0:m]}}\right)(\ket{C}\\!\\!\bra{C}^{\otimes
m+1}).$

One can think of $\sigma^{*}$ as the state the verifier hopes to have in their
registers after step $3(a)$. Because trace distance can only decrease when
applying a channel, we have that

$\mathrm{td}(\rho^{*},\sigma^{*})\leq\mathrm{td}((\rho_{0})_{\mathsf{AB}_{[m]}},\ket{C}\\!\\!\bra{C}^{\otimes
m})\leq\frac{1}{32q^{2}}\,,$

where the final inequality comes from the $\mathsf{stateQIP}$ soundness
promise, as explained above. Let $\rho_{acc}$ be the state of the verifier
after step $3(b)$ conditioned on the verifier accepting. In step $3(b)$, the
verifier hopes to measure some ideal measurement and see outcome
$\mathcal{M}$, described below as

$\mathcal{M}=\textnormal{id}_{\mathsf{A}_{0}\mathsf{B}_{0}}\otimes\ket{D}\\!\\!\bra{D}^{\otimes
m}\,.$

Then let $\rho^{*}_{acc}=\rho^{*}|_{\mathcal{M}}$ and
$\sigma^{*}_{acc}=\sigma^{*}|_{\mathcal{M}}$. Our goal is to get a lower bound
for the quantity

$\mathrm{Tr}\left(\ket{D}\\!\\!\bra{D}_{\mathsf{A_{0}B_{0}}}\rho_{acc}\right)\,,$
(7.3)

because applying the Gentle Measurement Lemma will then give us a bound on the
trace distance between $\rho_{acc}$ and
$\ket{D}\\!\\!\bra{D}_{\mathsf{A_{0}B_{0}}}$. Following the calculations in
Lemma 6.3, we have that

$\mathrm{Tr}(\ket{D}\\!\\!\bra{D}_{\mathsf{A_{0}B_{0}}}\sigma^{*}_{acc})\geq
1-\frac{2}{m+1}\,.$

From the approximate measurement soundness (Lemma 7.1), together with the
assumption that the verifier accepts with probability at least $1/2$ (and thus
the outcome bit $b$ of the approximate measurement protocol is $1$ with at
least the same probability), we have that

$\mathrm{td}(\rho_{acc},\rho^{*}_{acc})\leq\frac{1}{32q^{2}}\,.$

We can compute the trace distance between $\rho^{*}_{acc}$ and
$\sigma^{*}_{acc}$ directly as follows:

$\displaystyle 2\mathrm{td}(\sigma^{*}_{acc},\rho^{*}_{acc})$
$\displaystyle=\left\lVert\frac{\mathcal{M}\sigma^{*}\mathcal{M}}{\mathrm{Tr}(\mathcal{M}\sigma^{*})}-\frac{\mathcal{M}\rho^{*}\mathcal{M}}{\mathrm{Tr}(\mathcal{M}\rho^{*})}\right\rVert_{1}$
$\displaystyle\leq\left\lVert\frac{\mathcal{M}\sigma^{*}\mathcal{M}}{\mathrm{Tr}(\mathcal{M}\sigma^{*})}-\frac{\mathcal{M}\sigma^{*}\mathcal{M}}{\mathrm{Tr}(\mathcal{M}\rho^{*})}\right\rVert_{1}+\left\lVert\frac{\mathcal{M}(\sigma^{*}-\rho^{*})\mathcal{M}}{\mathrm{Tr}(\mathcal{M}\rho)}\right\rVert_{1}$
$\displaystyle\leq\left\lVert\mathcal{M}\sigma^{*}\mathcal{M}\right\rVert_{1}\left|\frac{1}{\mathrm{Tr}(\mathcal{M}\sigma^{*})}-\frac{1}{\mathrm{Tr}(\mathcal{M}\rho^{*})}\right|+\frac{\left\lVert\mathcal{M}(\sigma^{*}-\rho^{*})\mathcal{M}\right\rVert_{1}}{\mathrm{Tr}(\mathcal{M}\rho^{*})}$
$\displaystyle\leq\mathrm{Tr}(\mathcal{M}\sigma^{*})\left|\frac{\mathrm{Tr}(\mathcal{M}\rho^{*})-\mathrm{Tr}(\mathcal{M}\sigma^{*})}{\mathrm{Tr}(\mathcal{M}\rho^{*})\mathrm{Tr}(\mathcal{M}\sigma^{*})}\right|+\frac{1}{8q^{2}}$
$\displaystyle\leq\frac{3}{16q^{2}}\,.$

For both terms, we get bounds from the fact that
$\mathrm{td}(\rho^{*},\sigma^{*})\leq 1/32q^{2}$ (and trace distance is
contractive under channels, including measurements) and
$\mathrm{Tr}(\mathcal{M}\rho^{*})\geq 1/2$. For the second term, we multiply
by $2$ because the trace distance is half the $1$-norm. Thus we have that

$\mathrm{td}(\sigma^{*}_{acc},\rho^{*}_{acc})\leq\frac{3}{32q^{2}}\,.$

Applying the triangle inequality we have that

$\mathrm{td}(\rho_{acc},\sigma^{*}_{acc})\leq\frac{1}{8q^{2}}\,.$

From this trace distance bound we can bound Equation 7.3 by

$\mathrm{Tr}\left(\ket{D}\\!\\!\bra{D}_{\mathsf{A_{0}B_{0}}}\rho_{acc}\right)\geq
1-\frac{2}{m+1}-\frac{1}{8q^{2}}\,.$

Applying the gentle measurement lemma (Proposition 2.2), we see that the trace
distance error from the state $\ket{D}\\!\\!\bra{D}$ is at most

$2\sqrt{\frac{2}{m+1}+\frac{1}{8q^{2}}}\leq 2\sqrt{\frac{1}{4q^{2}}}\leq
1/q\,,$

where we use the fact that $m=16q^{2}$, so $2/(m+1)\leq 1/(8q^{2})$. This
completes the proof of Lemma 7.4. ∎

#####  7.1.2 $\textsc{DistSuccinctUhlmann}_{1}$ is
$\mathsf{avgUnitaryQIP}$-hard

Having shown that $\textsc{DistSuccinctUhlmann}_{1}\in\mathsf{avgUnitaryQIP}$,
we now need to show that it is in fact a complete problem, i.e. any unitary
synthesis problem in $\mathsf{avgUnitaryQIP}$ can be reduced to
$\textsc{DistSuccinctUhlmann}_{1}$. This is the statement of Lemma 7.5. Before
giving the full proof of Lemma 7.5, we provide some intuition. We need to show
that any distributional unitary synthesis problem
$(\mathscr{U},\Psi)\in\mathsf{avgUnitaryQIP}$ can be solved by a polynomial-
sized circuit with access to a $\textsc{DistSuccinctUhlmann}_{1}$-oracle.

As a first step, let us consider a $\mathsf{stateQIP}$-protocol (i.e. an
interactive protocol where the verifier receives no input state and is asked
to prepare a certain quantum state from scratch) and implement this in
$\mathsf{stateBQP}^{\textsc{DistSuccinctUhlmann}_{1}}$. For any
$\mathsf{stateQIP}$-protocol, by [MY23, Lemma 7.5] there exist purifications
of the intermediate states of the protocol (on the verifier and message
registers) that are in $\mathsf{statePSPACE}$. Furthermore, from the proof of
[MY23, Lemma 7.5] it is easy to see that the circuits preparing these
purifications have succinct descriptions that are efficiently computable from
the descriptions of the verifier actions. Then, a possible successful prover
strategy in the $\mathsf{stateQIP}$-protocol is simply to implement the
Uhlmann transformation between these purifications; see [MY23, Proof of Thm.
7.1] for a more detailed explanation of this idea. These Uhlmann
transformations can be accomplished by a
$\textsc{DistSuccinctUhlmann}_{1}$-oracle: we can efficiently compute the
succinct descriptions of the circuits between which we need to apply the
Uhlmann transformation and feed these descriptions to the Uhlmann oracle in
order to perform the required transformation, effectively simulating the
prover with the Uhlmann oracle.

Now we consider the more difficult case of an
$\mathsf{avgUnitaryQIP}$-protocol. The key difficulty compared to the
$\mathsf{stateQIP}$-setting is that we are only given one copy of one register
to which we want to apply our desired unitary. However, we can observe that
the above argument for the $\mathsf{stateQIP}$-protocol only relied on being
able to compute the succinct classical descriptions of the circuits preparing
purifications of the intermediate states of the protocol. Once we have these
classical descriptions, we can implement the required Uhlmann transformation
on any given state, i.e. the step of applying the Uhlmann oracle does not
require having access to arbitrarily many copies of the input state.

Therefore, to apply the $\mathsf{avgUnitaryQIP}$-protocol on a given input
register, we proceed in two steps. The first step is purely classical: since
in a distributional unitary synthesis problem
$(\mathscr{U},\Psi)\in\mathsf{avgUnitaryQIP}$ the state family $\Psi$ is in
$\mathsf{stateQIP}$, we can construct a $\mathsf{stateQIP}$-protocol for the
state $U_{x}\ket{\psi_{x}}$ with $U_{x}\in\mathscr{U}$ and
$\ket{\psi_{x}}\in\Psi$.141414Note that of course this is not the same as
solving the average unitary synthesis problem: here, we simply prepare the
desired state from scratch, whereas in the unitary synthesis setting we are
given a single register of an entangled quantum state and have to apply the
desired unitary to that register while keeping the entanglement with the
remaining (inaccessible) register intact. As described above, this
$\mathsf{stateQIP}$-protocol allows us to efficiently (classically) compute
succinct descriptions of the circuits preparing purifications of the
intermediate states of the protocol. In the second (quantum) step, we can now
use these pre-computed succinct classical descriptions to efficiently simulate
the $\mathsf{avgUnitaryQIP}$-protocol with the Uhlmann oracle. For this, when
it is the verifier’s turn, we simply apply the (efficient) verifier actions,
and when it is the prover’s turn we use our pre-computed succinct classical
descriptions and the Uhlmann oracle to apply the prover actions. This way, we
can simulate the actions of the $\mathsf{avgUnitaryQIP}$-protocol given only a
single copy of the input register.

We formalise this idea in the following lemma.

######  Lemma 7.5.

$\mathsf{avgUnitaryQIP}$ polynomial-time reduces to
$\textsc{DistSuccinctUhlmann}_{1}$.

###### Proof.

Let $(\mathscr{U},\Psi)\in\mathsf{avgUnitaryQIP}$. This means that there
exists some polynomial-time quantum verifier $V=(V_{x})$ who receives as input
the $\mathsf{A}$-register of the state $\ket{\psi_{x}}_{\mathsf{AR}}$ and
satisfies the completeness and soundness condition in Definition 4.2.
Throughout the proof, whenever we say “successful prover”, we mean a prover
that is accepted in the protocol with probability at least the soundness
threshold $s(n)=1/2$. Since $\Psi\in\mathsf{stateQIP}$, there exists another
polynomial-time verifier $V^{\prime}=(V^{\prime}_{x})$ for synthesising the
states $\Psi=(\ket{\psi_{x}})$; note that $V^{\prime}$ receives no quantum
input. The can combine these two verifier’s into one verifier
$\tilde{V}=(\tilde{V}_{x})$ who receives no input and first executed the
actions of $V^{\prime}$; at the end of this, $\tilde{V}$ will be in possession
of a state on registers $\mathsf{A}$ and $\mathsf{R}$. $\tilde{V}$ then runs
$V$ with $\mathsf{A}$ as the input register and outputs the resulting state.
If either $V$ or $V^{\prime}$ rejects, so does $\tilde{V}$.

Applying [MY23, Lemma 7.5] to the verifier $\tilde{V}$ shows that the
intermediate states on the message and verifier register in the interaction of
$\tilde{V}$ with any prover with sufficiently high success probability have
purifications in $\mathsf{statePSPACE}$. Furthermore, from the proof of [MY23,
Lemma 7.5] it is easy to see that there are polynomial-time Turing machines
that, given as input a description of the verifier’s actions in the protocol,
output succinct classical descriptions of the quantum polynomial-space
circuits for preparing $\ket{\psi_{n,j}}$ and $\ket{\varphi_{n,j}}$. This
holds because [MY23, Lemma 7.5] only relies on the block-encoding
transformations implemented in [MY23, Theorems 5.5 and 6.1], which have
efficient (and explicit) descriptions.

This means that for each round $i$ of the protocol, there exist polynomial-
space quantum circuits $C_{x}^{i}$ and $D_{x}^{i}$ with efficiently computable
succinct classical descriptions $\hat{C}_{x}^{i}$ and $\hat{D}_{x}^{i}$ such
that $\ket{\alpha^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}=C_{x}^{i}\ket{0\dots 0}$
and $\ket{\beta^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}=D_{x}^{i}\ket{0\dots 0}$
are purifications of the reduced state on the message register
$\mathsf{M^{i}}$ and verifier register $\mathsf{V^{i}}$ of the interactive
protocol right before and after the prover’s action in round $i$. Observe that
because the verifier register in the interactive protocol is not acted upon by
the prover, the reduced states on the verifier register are unchanged, i.e.

$\displaystyle\mbox{\rm
Tr}_{\mathsf{M^{i}P^{i}}}\left(\ket{\alpha^{i}_{x}}\\!\\!\bra{\alpha^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}\right)=\mbox{\rm
Tr}_{\mathsf{M^{i}P^{i}}}\left(\ket{\beta^{i}_{x}}\\!\\!\bra{\beta^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}\right)\,.$

We can therefore interpret the circuit pair $(C_{x}^{i},D_{x}^{i})$ as an
instance of the SuccinctUhlmann problem, with $\mathsf{V^{i}}$ taking the role
of the register that cannot be acted upon by the Uhlmann
unitary.151515Technically we also need to include the space requirement of
$C_{x}^{i}$ and $D_{x}^{i}$, which can be explicitly computed from the proof
of [MY23, Lemma 7.5], as part of the Uhlmann instance, and pad the verifier
register $\mathsf{V^{i}}$ with additional qubits so that $\mathsf{V^{i}}$ and
$\mathsf{M^{i}P^{i}}$ have the same number $n$ of qubits. To help with
readability, we do not do this explicitly in the proof. With access to a
DistSuccinctUhlmann-oracle, we can therefore apply an Uhlmann transformation
mapping $\ket{\alpha^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}=C_{x}^{i}\ket{0\dots
0}$ to $\ket{\beta^{i}_{x}}_{\mathsf{V^{i}M^{i}P^{i}}}=D_{x}^{i}\ket{0\dots
0}$ by acting only on registers $\mathsf{M^{i}P^{i}}$. This means that with
the DistSuccinctUhlmann-oracle, we can efficiently implement the actions of a
successful prover in the interactive protocol.161616Note that of course not
every successful prover has to implement the Uhlmann transformation. The
important point is that we can implement _some_ successful prover in this way,
and the guarantee of the interactive protocol applies to any successful
prover.

We now use this observation to construct a polynomial-size quantum query
circuit that, when instantiated with $\textsc{DistSuccinctUhlmann}_{1}$ and
run on register $\mathsf{A}$ of $\ket{\psi_{x}}$, produces the same output
state as the quantum interactive protocol with verifier $V=(V_{x})$ for this
problem. The query circuit is constructed as follows: the circuit receives as
input register $\mathsf{A}$ of $\ket{\psi_{x}}$. The circuit applies the first
action of the verifier $V$, which we can assume to be unitary by purifying the
actions of $V$ and which can be done in polynomial-time since $V$ is