######  Theorem 9.13 (Decoupling Theorem, Theorem 3.8 of [Dup10]).

Let $\rho_{\mathsf{AB}}$ be a density matrix,
$\mathcal{T}:\textnormal{S}(\mathsf{A})\to\textnormal{S}(\mathsf{E})$ be a
completely positive superoperator,
$\omega_{\mathsf{E}\mathsf{A}^{\prime}}=(\mathcal{T}\otimes\textnormal{id}_{\mathsf{A}^{\prime}})(\Phi_{\mathsf{A}\mathsf{A}^{\prime}})$
(where $\Phi$ denotes the maximally entangled state), and $\epsilon\geq 0$.
Then

$\int\,\|(\mathcal{T}\circ
U)(\rho_{\mathsf{AB}})-\omega_{\mathsf{E}}\otimes\rho_{\mathsf{B}}\|_{1}\,\mathrm{d}U\leq
2^{-\frac{1}{2}H^{\epsilon}_{2}(\mathsf{A}^{\prime}|\mathsf{E})_{\omega}-\frac{1}{2}H^{\epsilon}_{2}(\mathsf{A}|\mathsf{B})_{\rho}}+8\epsilon$

where the integral is over the uniform measure on Clifford unitary matrices
acting on $\mathsf{B}$, and $\mathcal{T}\circ U$ denotes the superoperator
where the input state is conjugated by $U$ first, and then $\mathcal{T}$ is
applied.

Define the following channel $\mathcal{T}$ that acts on $\mathsf{A}$: it
measures the first $n-s$ qubits of $\mathsf{A}$ in the standard basis to
obtain a classical outcome $y\in\\{0,1\\}^{n-s}$, traces out $\mathsf{A}$, and
outputs $y$ in register $\mathsf{E}$. We now evaluate the state
$\omega_{\mathsf{E}\mathsf{A}^{\prime}}=(\mathcal{T}\otimes\textnormal{id}_{\mathsf{A}^{\prime}})(\Phi_{\mathsf{A}\mathsf{A}^{\prime}})$.
This can be seen to be

$\omega_{\mathsf{E}\mathsf{A}^{\prime}}=\sum_{y\in\\{0,1\\}^{n-s}}\ket{yy}\\!\\!\bra{yy}_{\mathsf{E}\mathsf{A}_{1}^{\prime}}\otimes
2^{-s}\,\textnormal{id}_{\mathsf{A}_{2}^{\prime}}$

where $\mathsf{A}^{\prime}$ is subdivided into two registers
$\mathsf{A}_{1}^{\prime}\mathsf{A}_{2}^{\prime}$ with
$\mathsf{A}_{1}^{\prime}$ isomorphic to $\mathsf{E}$. The entropy
$H^{\epsilon}_{2}(\mathsf{A}^{\prime}|\mathsf{E})_{\omega}$ can be calculated
as follows:

$H_{2}^{\epsilon}(\mathsf{A}^{\prime}|\mathsf{E})_{\omega}\geq
H_{2}(\mathsf{A}^{\prime}|\mathsf{E})_{\omega}\geq
H_{\min}(\mathsf{A}^{\prime}|\mathsf{E})_{\omega}~{}.$

The first inequality follows from the definition of the smoothed $2$-entropy.
The second inequality follows from Proposition 9.11. Note that
$\omega_{\mathsf{A}^{\prime}\mathsf{E}}$ is a classical state (i.e., it is
diagonal in the standard basis); using the operational definition of the min-
entropy in this case we see that $H_{\min}(\mathsf{A}^{\prime}|\mathsf{E})=s$.

Now we bound the entropy $H^{\epsilon}_{2}(\mathsf{A}|\mathsf{R})_{\rho}$.
Since $\rho_{\mathsf{AR}}$ is pure, Proposition 9.11 gives us

$-H^{\epsilon}_{2}(\mathsf{A}|\mathsf{R})_{\rho}\leq-H^{\epsilon}_{\min}(\mathsf{A}|\mathsf{R})_{\rho}=H^{\epsilon}_{\max}(\mathsf{A})_{\rho}~{}.$

By Theorem 9.13, by averaging there exists a Clifford unitary $U$ such that

$\|(\mathcal{T}\circ
U)(\rho_{\mathsf{AR}})-\omega_{\mathsf{E}}\otimes\rho_{\mathsf{R}}\|_{1}\leq
2^{-\frac{1}{2}(s-H^{\epsilon}_{\max}(\mathsf{A})_{\rho})}+8\epsilon\coloneqq\nu~{}.$

Consider the following two purifications:

  1. 1.

$\ket{\Phi}_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\ket{\rho}_{\mathsf{AR}}$
where $\ket{\Phi}_{\mathsf{E}\mathsf{E}^{\prime}}$ denotes the maximally
entangled state on two isomorphic registers $\mathsf{E},\mathsf{E}^{\prime}$.
This is a purification of the density matrix
$\omega_{\mathsf{E}}\otimes\rho_{\mathsf{R}}$.

  2. 2.

$\ket{\theta}_{\mathsf{E}\mathsf{E}^{\prime}\mathsf{CR}\mathsf{F}}\coloneqq\sum_{y}\ket{y}_{\mathsf{E}}\otimes(\Pi_{y}U\otimes\textnormal{id}_{\mathsf{R}})\ket{\rho}_{\mathsf{AR}}\otimes\ket{0}_{\mathsf{F}}$
where $\Pi_{y}$ is the projection that maps $\mathsf{A}$ into
$\mathsf{E}^{\prime}\mathsf{C}$ with $\mathsf{C}$ being an $s$ qubit register
and $\mathsf{E}^{\prime}$ being $n-s$ qubit register, projecting the first
$n-s$ qubits of $\mathsf{A}$ into the $\ket{y}$ state. The register
$\mathsf{F}$ is isomorphic to $\mathsf{E}$ and is used to ensure that the
dimensions of both purifications are the same. This is a purification of
$(\mathcal{T}\circ U)(\rho_{\mathsf{AR}})$.

By Fuchs-van de Graaf and Uhlmann’s theorem there exist a partial isometry $V$
mapping registers $\mathsf{E}^{\prime}\mathsf{A}$ to
$\mathsf{C}\mathsf{E}^{\prime}\mathsf{F}$ such that

$\mathrm{td}\Big{(}V(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})V^{\dagger}\,,\,\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}}\Big{)}\leq\sqrt{2\nu}~{}.$

Let $\Xi$ be an arbitrary channel completion of $V$. We show that $\Xi$ can be
used in place of $V$ with small error. Let $P$ denote the projection onto the
support of $V$. Then we have

$\displaystyle\Big{|}\mathrm{Tr}(P(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}}))-1\Big{|}\leq\mathrm{td}\Big{(}P(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})P,\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}}\Big{)}\leq\mathrm{td}\Big{(}V(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})V^{\dagger},\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}}\Big{)}\leq\sqrt{2\nu}\,.$

Let $\tau$ denote the post-measurement state of
$\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}}$ after
measuring the projector $P$; by the Gentle Measurement Lemma [Win99] we have
$\mathrm{td}(\tau,\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})\leq
4\nu^{1/4}$. Thus

$\displaystyle\mathrm{td}\Big{(}\Xi(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})\,,\,\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}}\Big{)}$
$\displaystyle\leq\mathrm{td}\Big{(}\Xi(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})\,,\,\Xi(\tau)\Big{)}+\mathrm{td}\Big{(}\Xi(\tau),V\tau
V^{\dagger}\Big{)}$ $\displaystyle\qquad+\mathrm{td}\Big{(}V\tau
V^{\dagger},V(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})V^{\dagger}\Big{)}+\mathrm{td}\Big{(}V(\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}})V^{\dagger}\,,\,\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}}\Big{)}$
$\displaystyle\leq 4\nu^{1/4}+4\nu^{1/4}+\sqrt{2\nu}\leq 10\nu^{1/4}\,,$
(9.11)

where we used that $\Xi(\tau)=V\tau V^{\dagger}$ by definition of channel
completion.

Similarly, let $\Lambda$ be an arbitrary channel completion of the partial
isometry $V^{\dagger}$. A similar argument shows that

$\mathrm{td}\Big{(}\Phi_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\rho_{\mathsf{AR}}\,,\,\Lambda(\theta_{\mathsf{EE}^{\prime}\mathsf{CRF}})\Big{)}\leq
10\nu^{1/4}~{}.$

We now continue with $\Xi$ instead of $V$ and $\Lambda$ instead of
$V^{\dagger}$. Applying the channel that measures the register $\mathsf{E}$ in
the standard basis to both arguments of the left-hand side of Equation 9.11
and using that the trace distance is non-increasing under quantum operations
we have

$\sum_{y}2^{-(n-s)}\mathrm{td}\Big{(}\Xi(\ket{y}\\!\\!\bra{y}_{\mathsf{E}^{\prime}}\otimes\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}})\,,\,2^{n-s}\alpha_{y}\ket{y}\\!\\!\bra{y}_{\mathsf{E}^{\prime}}\otimes\ket{\rho_{U,y}}\\!\\!\bra{\rho_{U,y}}_{\mathsf{CR}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\Big{)}\leq
10\nu^{1/4}~{},$

where $\alpha_{y}\coloneqq\|\Pi_{y}U\ket{\rho}_{\mathsf{AR}}\|^{2}$ and the
pure state $\ket{\rho_{U,y}}_{\mathsf{RC}}$ is defined so that

$\alpha_{y}^{-1/2}\,\Pi_{y}U\ket{\rho}_{\mathsf{AR}}=\ket{y}_{\mathsf{E}^{\prime}}\otimes\ket{\rho_{U,y}}_{\mathsf{CR}}~{}.$

By averaging, there exists a $y^{*}\in\\{0,1\\}^{n-s}$ such that

$\mathrm{td}\Big{(}\Xi(\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}})\,,\,2^{n-s}\alpha_{y^{*}}\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\ket{\rho_{U,y^{*}}}\\!\\!\bra{\rho_{U,y^{*}}}_{\mathsf{CR}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\Big{)}\leq
10\nu^{1/4}\,.$

This also implies that $|2^{n-s}\alpha_{y^{*}}-1|\leq 10\nu^{1/4}$ so thus

$\mathrm{td}\Big{(}\Xi(\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}})\,,\,\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\ket{\rho_{U,y^{*}}}\\!\\!\bra{\rho_{U,y^{*}}}_{\mathsf{CR}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{F}}\Big{)}\leq
10\nu^{1/4}~{}.$ (9.12)

Define the following quantum circuits:

  1. 1.

The circuit $E$ acts on register $\mathsf{A}$ and behaves as follows: it
appends the state $\ket{y^{*}}$ in register $\mathsf{E}^{\prime}$, applies the
channel $\Xi$, and then traces out registers $\mathsf{E}^{\prime}\mathsf{F}$.
In other words, it implements the following channel:

$E(\sigma_{\mathsf{A}})=\mathrm{Tr}_{\mathsf{E}^{\prime}\mathsf{F}}\Big{(}\Xi(\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\sigma_{\mathsf{A}})\Big{)}~{}.$

  2. 2.

The circuit $D$ takes as input register $\mathsf{C}$ and behaves as follows:
it appends the state $\ket{y^{*}}$ in register $\mathsf{E}^{\prime}$ and
$\ket{0}$ in register $\mathsf{F}$, applies the channel $\Lambda$, and then
traces out register $\mathsf{E}^{\prime}$. In other words, it implements the
following channel:

$D(\tau_{\mathsf{C}})=\mathrm{Tr}_{\mathsf{E}^{\prime}}\Big{(}\Lambda(\ket{y^{*}}\\!\\!\bra{y^{*}}_{\mathsf{E}^{\prime}}\otimes\tau_{\mathsf{C}}\otimes\ket{0}\\!\\!\bra{0}_{\mathsf{F}})\Big{)}~{}.$

Then Equation 9.12 implies that

$\displaystyle\mathrm{td}\Big{(}E(\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}),\,\ket{\rho_{U,y^{*}}}\\!\\!\bra{\rho_{U,y^{*}}}_{\mathsf{CR}}\Big{)}\leq
10\nu^{1/4}$
$\displaystyle\mathrm{td}\Big{(}\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}\,,\,D(\ket{\rho_{U,y^{*}}}\\!\\!\bra{\rho_{U,y^{*}}}_{\mathsf{CR}})\Big{)}\leq
10\nu^{1/4}~{}.$

Put together this means

$\mathrm{td}\Big{(}(D\circ
E)(\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}),\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}\Big{)}\leq
20\nu^{1/4}~{}.$

Although we have defined the circuits $E,D$ in terms of the purification
$\ket{\rho}_{\mathsf{AR}}$, observe that Uhlmann’s theorem implies that the
same circuits works for _all_ purifications of $\rho_{\mathsf{A}}$. Thus,
since the output of channel $E$ is register $\mathsf{C}$ which has size $s$
qubits, this shows that $(E,D)$ compresses $\rho$ to $s$ qubits with error
$20\nu^{1/4}$. By our choice of
$s=H^{\epsilon}_{\max}(\mathsf{B})_{\rho}+8\log\frac{4}{\delta}$ and
$\epsilon=(\delta/40)^{4}$, this error is at most $\delta$. ∎

We note that for tensor product states $\rho^{\otimes k}$, the smoothed max-
entropy converges to the well-known von Neumann entropy:

$\lim_{\epsilon\to
0}\lim_{k\to\infty}\frac{1}{k}H^{\epsilon}_{\max}(\rho^{\otimes
k})=H(\rho)~{}.$

This is an instance of the _quantum asymptotic equipartition property_ , which
roughly states that the min, max, and Rényi entropies approach the von Neumann
entropy in the limit of many copies of a state [TCR09].212121In fact, one can
give stronger quantitative bounds on the convergence to the von Neumann
entropy as a function of the number of copies $k$ and the error $\epsilon$.
Thus Theorem 9.12 applied to tensor product states $\rho^{\otimes k}$ recovers
Schumacher compression [Sch95], using a proof that does not appeal to typical
subspaces and the method of types.

#####  9.2.2 Complexity of near-optimal compression

We now initiate the study of the computational complexity of compressing to
the information-theoretic limit, i.e., to the smoothed max-entropy of a state.
We begin by defining compression as a computational task.

######  Definition 9.14 (Compression as a computational task).

Let $\epsilon,\eta:\mathbb{N}\to[0,1]$ be functions. Let $E=(E_{x})_{x}$ and
$D=(D_{x})_{x}$ be quantum algorithms. We say that $(E,D)$ _compresses to the
$\epsilon$-smoothed max-entropy with error $\eta$_ if for all $x=(1^{n},C)$
where $C$ is a quantum circuit that outputs $n$ qubits, we have that
$(E_{x},D_{x})$ compresses $\rho_{x}\coloneqq C(\ket{0\dots
0}\\!\\!\bra{0\dots 0})$ to at most
$H^{\epsilon(n)}_{\max}(\rho_{x})+O(\log\frac{1}{\epsilon(n)})$ qubits with
error at most $\eta(n)$.

This brings us to the main result of the section, which are upper and lower
bounds on the complexity of the compression task.

######  Theorem 9.15 (Near-optimal compression via Uhlmann transformations).

Let $\epsilon(n)$ be a negligible function. If
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP/poly}$, then for
all polynomials $q(n)$ there exists a pair of non-uniform polynomial-time
algorithms $(E,D)$ that compresses to the $\epsilon$-smoothed max-entropy with
error $\eta(n)=1/q(n)$.

###### Proof.

Let $x=(1^{n},C)$ where $C$ is a quantum circuit that outputs $n$ qubits, and
let $\rho_{x}=C(\ket{0\dots 0}\\!\\!\bra{0\dots 0})$. Let
$\epsilon=\epsilon(n)$. The proof of the upper bound of Theorem 9.12 involves
the following two states:

$\displaystyle\ket{F}\coloneqq\ket{\Phi}_{\mathsf{E}\mathsf{E}^{\prime}}\otimes\ket{\rho}_{\mathsf{AR}}\,,$
$\displaystyle\ket{G}\coloneqq\sum_{y}\ket{y}_{\mathsf{E}}\otimes(\Pi_{y}U\otimes\textnormal{id}_{\mathsf{R}})\ket{\rho}_{\mathsf{AR}}\otimes\ket{0}_{\mathsf{F}}\,.$

(The state $\ket{G}$ was called $\ket{\theta}$ in Theorem 9.12). Here,
$\ket{\Phi}_{\mathsf{E}\mathsf{E}^{\prime}}$ denotes the maximally entangled
state on $\mathsf{E}\mathsf{E}^{\prime}$, $\ket{\rho}_{\mathsf{AR}}$ is the
pure state resulting from evaluating a purification of the circuit $C$ on the
all zeroes input, the projector $\Pi_{y}$ denotes projecting the first $n-s$
qubits of register $\mathsf{A}$ onto $\ket{y}$, and $U$ is a Clifford unitary.
Note that $\ket{F},\ket{G}$ can be prepared by circuits $F,G$ whose sizes are
polynomial in $n$ and in the size of $C$; this uses the fact that Clifford
unitaries can be computed by a circuit of size $O(n^{2})$ [AG04].

The proof of Theorem 9.12 shows that the reduced density matrices of
$\ket{F},\ket{G}$ on registers $\mathsf{EA}$ have fidelity at least
$1-2\nu=1-\epsilon^{2}/16\geq 1-\epsilon$. Thus $(1^{m},F,G)$ is a valid
$\textsc{Uhlmann}_{1-\epsilon}$ instance. Since
$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP/poly}$ by
assumption there exists $\mathrm{poly}(n,|C|)$-size circuit $L$ mapping
registers $\mathsf{E}^{\prime}\mathsf{A}$ to $\mathsf{E}^{\prime}\mathsf{CF}$
and a channel completion $\Xi$ of the canonical Uhlmann transformation $V$
corresponding to $(\ket{F},\ket{G})$ such that

$\mathrm{td}\Big{(}(\textnormal{id}\otimes
L)(\ket{F}\\!\\!\bra{F}),\,\,(\textnormal{id}\otimes\Xi)(\ket{F}\\!\\!\bra{F})\Big{)}\leq\frac{1}{r(n)}$

where $r(n)$ is a polynomial such that $2/r(n)+\epsilon(n)\leq 1/q(n)$, which
is possible because $\epsilon(n)$ is a negligible function. Similarly there
exists a $\mathrm{poly}(n,|C|)$-size circuit $M$ and a channel completion
$\Lambda$ of the Uhlmann transformation $V^{\dagger}$ corresponding to
$(\ket{G},\ket{F})$ such that

$\mathrm{td}\Big{(}(\textnormal{id}\otimes
M)(\ket{G}\\!\\!\bra{G}),\,\,(\textnormal{id}\otimes\Lambda)(\ket{G}\\!\\!\bra{G})\Big{)}\leq\frac{1}{r(n)}~{}.$

The proof of Theorem 9.12 shows shows that there exists a pair of circuits
$(E_{x}^{*},D_{x}^{*})$ that compresses $\rho_{x}$ to
$s=H^{\epsilon}_{\max}(\rho_{x})+O(\log\frac{1}{\epsilon})$ qubits with error
$\epsilon$. Notice that the circuits $E_{x}^{*},D_{x}^{*}$ are
$\mathrm{poly}(n)$-size circuits that make one call to channels $\Xi,\Lambda$,
respectively. Now the idea is to “plug in” the circuits $L,M$ to implement the
call to the channel $\Xi,\Lambda$, respectively. Let $E_{x},D_{x}$ denote the
resulting $\mathrm{poly}(n,|C|)$-sized circuits. Using $L,M$ instead of the
channels $\Xi,\Lambda$ incurs at most $O(1/r(n))$ error, i.e.,
$\mathrm{td}\Big{(}(D_{x}\circ
E_{x})(\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}),(D_{x}^{*}\circ
E_{x}^{*})(\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}})\Big{)}\leq 2/r(n)$.
Therefore

$\displaystyle\mathrm{td}\Big{(}(D_{x}\circ
E_{x})(\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}),\ket{\rho}\\!\\!\bra{\rho}_{\mathsf{AR}}\Big{)}\leq
2/r(n)+\epsilon(n)\leq 1/q(n)\,.$

Letting $E=(E_{x})_{x}$ and $D=(D_{x})_{x}$ we get the desired pair of non-
uniform polynomial-time algorithms that compresses to the $\epsilon$-smoothed
max entropy with inverse polynomial error. ∎

We now turn to proving a hardness result for near-optimal compression; it
cannot be performed in polynomial-time if _stretch pseudorandom state (PRS)
generators_ exist. Pseudorandom state generators are a quantum analogue of
classical pseudorandom generators (PRGs) and in fact can be constructed from
post-quantum pseudorandom generators [JLS18], but there is evidence that the
assumption of PRS is less stringent than the assumption of post-quantum PRGs
[Kre21]. We first recall the definition of a PRS generator:

######  Definition 9.16 (Pseudorandom state generator [JLS18, Definition 3]).

We say that a (uniform) polynomial-time algorithm $G=(G_{\lambda})_{\lambda}$
is a _pseudorandom state (PRS) generator_ if the following holds.

  1. 1.

(_State generation_). For all $\lambda$, on input $k\in\\{0,1\\}^{k}$ the
algorithm $G$ outputs

$G_{\lambda}(k)=\ket{\psi_{k}}\\!\\!\bra{\psi_{k}}$

for some $m(\lambda)$-qubit pure state $\ket{\psi_{k}}$.

  2. 2.

(_Strong pseudorandomness_). For all polynomials $t(\lambda)$ and non-uniform
polynomial-time distinguishers $A=(A_{\lambda})_{\lambda}$ there exists a
negligible function $\epsilon(\lambda)$ such that for all $\lambda$, we have

$\left|\Pr_{k\leftarrow\\{0,1\\}^{\lambda}}\left[A_{\lambda}^{O_{\psi_{k}}}(G_{\lambda}(k)^{\otimes
t(\lambda)})=1\right]-\Pr_{\ket{\vartheta}\leftarrow\mathrm{Haar}_{m(\lambda)}}\left[A_{\lambda}^{O_{\vartheta}}(\ket{\vartheta}\\!\\!\bra{\vartheta}^{\otimes
t(\lambda)})=1\right]\right|\leq\epsilon(\lambda),$

where $O_{\psi}\coloneqq\textnormal{id}-2\ket{\psi}\\!\\!\bra{\psi}$ is the
reflection oracle for $\ket{\psi}$.

We say that $G$ is a _stretch_ PRS generator if $m(\lambda)>\lambda$.

Here we use the strong pseudorandomness guarantee, which is known to be
equivalent to the weaker (standard) pseudorandomness guarantee where the
adversary does not get access to the reflection oracle [JLS18, Theorem 4]. We
also note that PRS generators do not necessarily provide any _stretch_ ; there
are nontrivial PRS generators where the output length $m(\lambda)$ can be
smaller than the key length $\lambda$. Furthermore, unlike classical PRGs, it
is not known whether PRS can be generically stretched (or shrunk); see [AQY22]
for a longer discussion of this.

We now state our hardness result.

######  Theorem 9.17 (Hardness of near-optimal compression).

Let $\epsilon(n)$ be a function. Let $m(\lambda)$ be a function satisfying

$m(\lambda)>\lambda+O\Big{(}\log\frac{1}{\epsilon(m(\lambda))}\Big{)}+2$

for all sufficiently large $\lambda$. If stretch pseudorandom state generators
that output $m(\lambda)$ qubits exist, then there is no non-uniform
polynomial-time algorithm $(E,D)$ that compresses to the $\epsilon$-smoothed
max-entropy with error $\frac{1}{2}$.

###### Proof.

Let $G$ be a PRS generator that outputs $m(\lambda)$-qubit states for
$m(\lambda)$ satisfying the conditions stated in Theorem 9.17, and fix a
sufficiently large $\lambda\in\mathbb{N}$ for which the condition is
satisfied. Define the pure state $\ket{\varphi_{\lambda}}$ that represents
running a unitary purification of the generator $G$ coherently with the keys
$k$ in superposition:

$\ket{\varphi_{\lambda}}_{\mathsf{KQA}}\coloneqq
2^{-\lambda/2}\sum_{k\in\\{0,1\\}^{\lambda}}\ket{k}_{\mathsf{K}}\otimes\ket{\tau_{\lambda}}_{\mathsf{Q}}\otimes\ket{\psi_{k}}_{\mathsf{A}}$

where $\ket{\psi_{k}}$ denotes the pseudorandom state output by $G$ on key
$k$, and $\ket{\tau_{k}}$ denotes the state of the ancilla qubits of $G$. Let
$\mathsf{R}\coloneqq\mathsf{KQ}$. The reduced density matrix of
$\ket{\varphi_{\lambda}}$ on register $\mathsf{A}$ is the following mixed
state:

$\rho_{\lambda}\coloneqq
2^{-\lambda}\sum_{k\in\\{0,1\\}^{\lambda}}\ket{\psi_{k}}\\!\\!\bra{\psi_{k}}~{}.$

By the second item of Proposition 9.11 we have
$H^{\epsilon}_{\max}(\rho_{\lambda})\leq\lambda$.

Assume for contradiction that there exists a polynomial-time pair of quantum
algorithms $(E,D)$ that compresses to the $\epsilon$-smoothed max-entropy with
error $\frac{1}{2}$. Let $x=(1^{n},C)$ where $C$ outputs the state
$\rho_{\lambda}$ by first synthesizing the state $\ket{\varphi_{\lambda}}$ and
then tracing out register $\mathsf{R}$. Clearly $C$ is a
$\mathrm{poly}(\lambda)$-sized circuit. Therefore $(E_{x},D_{x})$ runs in
$\mathrm{poly}(\lambda)$ time and compresses $\rho_{\lambda}$ to
$r_{\lambda}\coloneqq
H^{\epsilon}_{\max}(\rho_{\lambda})+O\Big{(}\log\frac{1}{\epsilon(m(\lambda))}\Big{)}\leq\lambda+O\Big{(}\log\frac{1}{\epsilon(m(\lambda))}\Big{)}$
qubits. By assumption we have

$\mathrm{td}\Big{(}(D_{x}\circ
E_{x})(\ket{\varphi_{\lambda}}\\!\\!\bra{\varphi_{\lambda}}),\,\ket{\varphi_{\lambda}}\\!\\!\bra{\varphi_{\lambda}}\Big{)}\leq\frac{1}{2}~{}.$

By measuring register $\mathsf{K}$ and tracing out register $\mathsf{Q}$ on
both arguments (which does not increase the trace distance), we have that

$\mathop{\mathbb{E}}_{k}\mathrm{td}\Big{(}(D_{x}\circ
E_{x})(\ket{\psi_{k}}\\!\\!\bra{\psi_{k}})\,,\,\ket{\psi_{k}}\\!\\!\bra{\psi_{k}}\Big{)}\leq\frac{1}{2}~{}.$
(9.13)

Now consider the following distinguisher $A=(A_{\lambda})_{\lambda}$: it gets
as input $\ket{\theta}$ where $\ket{\theta}$ is either $\ket{\psi_{k}}$ for a
randomly sampled $k$ or $\ket{\vartheta}$ sampled from the Haar measure; it
also gets access to a (controlled) reflection oracle
$O_{\theta}=\textnormal{id}-2\ket{\theta}\\!\\!\bra{\theta}$. It then

  1. 1.

applies the channel $D_{x}\circ E_{x}$ to input $\ket{\theta}$;

  2. 2.

measures
$\\{\ket{\theta}\\!\\!\bra{\theta},\textnormal{id}-\ket{\theta}\\!\\!\bra{\theta}\\}$
using the reflection oracle, and accept if measurement accepts.

From Equation 9.13 we have that, since the measurement step with respect to
$O_{\psi_{k}}$ accepts on $\ket{\psi_{k}}$ with probability $1$, then
$A_{\lambda}$ with oracle access to $O_{\psi_{k}}$ accepts $\ket{\psi_{k}}$
with probability at least $1-\eta$ over the choice of key $k$ and the
randomness of $A_{\lambda}$.

Now consider what happens when we run $A_{\lambda}$ with $\ket{\vartheta}$ as
input where $\ket{\vartheta}$ is sampled from the Haar measure, as well as
with the reflection oracle $O_{\vartheta}$. Since $A$ runs in
$\mathrm{poly}(\lambda)$ time, by the pseudorandomness property of $G$ the
probability that $A_{\lambda}$ accepts $\ket{\vartheta}$ is at least
$\frac{1}{2}-\mathrm{negl}(\lambda)$.

On the other hand we show that since a Haar-random state cannot be compressed,
$A_{\lambda}$ cannot accept with high probability. Let $R\coloneqq
2^{r_{\lambda}}$ denote the dimensionality of the output of $E_{\lambda}$, and
let $M=2^{m(\lambda)}$ denote the dimensionality of register $\mathsf{A}$. For
brevity we abbreviate $E_{x},D_{x}$ as $E,D$ respectively. The success
probability of $A_{\lambda}$ given a Haar-random state $\ket{\vartheta}$ and
the reflection oracle $O_{\vartheta}$ can be calculated as follows. First,
observe that

$\int_{\vartheta}\mathrm{Tr}\Big{(}(D\circ
E)(\ket{\vartheta}\\!\\!\bra{\vartheta})\,\ket{\vartheta}\\!\\!\bra{\vartheta}\Big{)}\,\mathrm{d}\vartheta=\int_{\vartheta}\mathrm{Tr}\Big{(}E(\ket{\vartheta}\\!\\!\bra{\vartheta})\,D^{*}(\ket{\vartheta}\\!\\!\bra{\vartheta})\Big{)}\,\mathrm{d}\vartheta$

where $D^{*}$ denotes the _adjoint channel_ corresponding to $D$; it is the
unique superoperator mapping register $\mathsf{A}^{\prime}$ to $\mathsf{B}$
satisfying $\mathrm{Tr}(XD(Y))=\mathrm{Tr}(D^{*}(X)Y)$ for all operators
$X,Y$. Viewing $E\otimes D^{*}$ as a superoperator mapping registers
$\mathsf{A}_{1}\mathsf{A}_{2}$ to $\mathsf{B}_{1}\mathsf{B}_{2}$ and letting
$S_{\mathsf{B}_{1}\mathsf{B}_{2}}$ denote the swap operator on registers
$\mathsf{B}_{1}\mathsf{B}_{2}$ the above is equal to

$\mathrm{Tr}\Big{(}S_{\mathsf{B}_{1}\mathsf{B}_{2}}(E\otimes
D^{*})(\int_{\vartheta}\ket{\vartheta}\\!\\!\bra{\vartheta}^{\otimes
2}\mathrm{d}\vartheta)\Big{)}~{}.$

Now, it is well-known [Har13] that the integral over two copies of an
$m(\lambda)$-qubit Haar-random state is proportional to the projector
$\frac{1}{2}(\textnormal{id}+S)$ onto the _symmetric subspace_ of
$(\mathbb{C}^{M})^{\otimes 2}$. The dimension of the projector is $M(M+1)/2$.
Thus the above is equal to

$\displaystyle\frac{1}{M(M+1)}\mathrm{Tr}\Big{(}S_{\mathsf{B}_{1}\mathsf{B}_{2}}\,(E\otimes
D^{*})(\textnormal{id}_{\mathsf{A}_{1}\mathsf{A}_{2}}+S_{\mathsf{A}_{1}\mathsf{A}_{2}})\Big{)}$
$\displaystyle\qquad\leq\frac{1}{M(M+1)}\mathrm{Tr}\Big{(}(E\otimes
D^{*})(\textnormal{id}_{\mathsf{A}_{1}\mathsf{A}_{2}}+S_{\mathsf{A}_{1}\mathsf{A}_{2}})\Big{)}$
$\displaystyle\qquad=\frac{1}{M(M+1)}\Big{[}\mathrm{Tr}\Big{(}(E\otimes
D^{*})(\textnormal{id}_{\mathsf{A}_{1}\mathsf{A}_{2}})\Big{)}+\mathrm{Tr}\Big{(}(E\otimes
D^{*})(S_{\mathsf{A}_{1}\mathsf{A}_{2}})\Big{)}\Big{]}$
$\displaystyle\qquad=\frac{1}{M(M+1)}\Big{[}\mathrm{Tr}\Big{(}\textnormal{id}_{\mathsf{A}_{1}}\otimes
D^{*}(\textnormal{id}_{\mathsf{A}_{2}})\Big{)}+\mathrm{Tr}\Big{(}(\textnormal{id}_{\mathsf{A}_{1}}\otimes
D^{*})(S_{\mathsf{A}_{1}\mathsf{A}_{2}})\Big{)}\Big{]}$
$\displaystyle\qquad=\frac{1}{M(M+1)}\Big{[}\mathrm{Tr}\Big{(}\textnormal{id}_{\mathsf{A}_{1}}\Big{)}\,\mathrm{Tr}\Big{(}D^{*}(\textnormal{id}_{\mathsf{A}_{2}})\Big{)}+\mathrm{Tr}\Big{(}D^{*}(\textnormal{id}_{\mathsf{A}_{2}})\Big{)}\Big{]}$
$\displaystyle\qquad=\frac{1}{M(M+1)}\Big{[}RM+R\Big{]}$
$\displaystyle\qquad=R/M=2^{-(m(\lambda)-\lambda-O(\log
1/\epsilon))}\leq\frac{1}{4}~{}.$

The second line follows from the fact that
$|\mathrm{Tr}(A^{\dagger}B)|\leq\|A\|_{\infty}\|B\|_{1}$ for all operators
$A,B$ and $\left\lVert S\right\rVert_{\infty}\leq 1$. The fourth line follows
from the fact that $E$ is a trace-preserving superoperator. The sixth line
follows from the fact that since $D$ is a channel that takes as input
$\mathsf{B}$,
$\mathrm{Tr}(D^{*}(\textnormal{id}_{\mathsf{A}_{2}}))=\mathrm{Tr}(\textnormal{id}_{\mathsf{B}})=R$.
The last line follows because our assumption about the stretch of the PRS.
This shows that the acceptance probability of $A_{\lambda}$ given a Haar
random state and access to its reflection oracle is at most $\frac{1}{4}$,
which is less than $\frac{1}{2}-\mathrm{negl}(\lambda)$ for sufficiently large
$\lambda$.

Thus we have arrived at a contradiction. There is no polynomial-time pair of
algorithms that compresses to the $\epsilon$-smoothed max entropy. ∎

We compare our hardness result with the upper bound proved in Theorem 9.15. As
an example, let $\epsilon(n)=2^{-\log^{2}(n)}$, which is a negligible
function. Then roughly, if $\textsc{DistUhlmann}_{1-\epsilon}$ is easy, then
compressing to $H^{\epsilon}_{\max}(\rho)+O(\log
1/\epsilon)=H^{\epsilon}_{\max}(\rho)+O(\log^{2}(n))$ is easy. On the other
hand, the lower bound shows that if PRS generators with output length
$m(\lambda)\geq\lambda+\Omega(\log^{2}(\lambda))$ exist, then compressing to
$H^{\epsilon}_{\max}(\rho)+O(\log^{2}(n))$ is not easy.

We remark that it should be possible to base the lower bound on seemingly
weaker assumptions, such as one-way state generators [MY22a]. However, ideally
we would be able to base the hardness on an assumption such as the existence
of quantum commitments or the hardness of the Uhlmann transformation problem,
which would give a true converse to the upper bound of Theorem 9.15. However
the main issue is _verifiability_ : with pseudorandom states or one-way state
generators (with pure-state outputs), one can check whether the state has been
compressed and decompressed; it is not clear whether this is possible with
quantum commitments. We leave it as an open problem to prove matching upper
and lower complexity bounds on compression.

######  Open Problem 22.

Is the complexity of optimal compression equivalent to the complexity of the
Uhlmann Transformation Problem?

####  9.3 Complexity of classical Shannon tasks?

Given the results in this section, the reader may naturally wonder about the
complexity of _classical_ Shannon tasks. For example, one can consider the
problems of decoding noisy classical channels and optimally compressing
classical information. The complexity of both these tasks appears to be
essentially _equivalent_ to the existence of one-way functions, which provides
some evidence that the hardness of the Uhlmann Transformation Problem could be
regarded as the natural quantum analogue of the existence of one-way
functions.

We sketch this equivalence for these two Shannon theory problems. The
classical analogue of the Decodable Channel Problem is as follows. A decodable
classical channel $N$ is a classical circuit that takes as input two strings
$(x,r)$ where both $x$ and $r$ are sampled from the uniform distribution, and
outputs a string $y$ such that with high probability over $(x,r)$, the
original message $x$ is information-theoretically recoverable. The task is to
recover the original message $x$ given the output $y$ of the channel.

Impagliazzo and Levin [IL89] showed that if all one-way functions can be
inverted in polynomial time with high probability, then there exists a
_distributional inverter_ that, given an output $y$ of the channel $N$, finds
a uniformly random preimage $(x,r)$. The decodability of $N$ ensures that the
computed $x$ is the original message with high probability. Conversely, if
one-way functions exist then pseudorandom generators exist [HILL99]. The
channel $N$ that takes the input $x$ and computes a pseudorandom generator on
it is not efficiently decodable in polynomial time.

We now turn to compression. Interestingly, the complexity of compression – and
other Shannon theory tasks – was already discussed in Yao’s seminal 1982 paper
introducing the theory of pseudorandomness [Yao82]. In modern day terms, Yao
argued that the existence of pseudorandom generators (which follows from the
existence of one-way functions [HILL99]) gives rise to efficiently sampleable
distributions $X$ that cannot be efficiently compressed to their Shannon
entropy $H(X)$. Conversely, a recent work of [HMS23] shows that if one-way
functions do not exist, every efficiently sampleable distribution $X$ can be
compressed to a prefix-free encoding of at most $H(X)+2$ bits.

These two examples motivate asking the broader question: what is the
complexity of other fundamental classical Shannon theory tasks, such as
obtaining capacity-achieving encoders and decoders for a given classical
channel (which is provided in the form of a randomized circuit), or performing
distributed source coding? Is the complexity of these tasks all equivalent to
the hardness of one-way functions? To our knowledge there has not been a
systematic study of the complexity of classical Shannon theory tasks, aside
from a few isolated discussions [Yao82, Lip94].

######  Open Problem 23.

Can the complexity of _classical_ Shannon theory tasks be characterized?

####  9.4 Open problems

We end this section with some additional open questions. First, the complexity
result about compression is stated in terms of the non-uniform complexity
class $\mathsf{avgUnitaryBQP/poly}$. The main reason for this is that the
upper bound (i.e., if DistUhlmann is easy, then compression is also easy)
involves hardcoding some information that depends on the instance of the
problem.

######  Open Problem 24.

Can the assumptions in the upper bound result for compression (Theorem 9.15)
be improved to be about uniform unitary complexity classes (namely,
$\mathsf{avgUnitaryBQP}$)?

This may require finding a new proof approach for the upper bound.

In this section we considered two basic quantum Shannon theory tasks. There
are many more that have been studied information-theoretically (including a
whole family tree of them [ADHW09]), and one can ask about the complexity of
each of these tasks.

######  Open Problem 25.

What is the complexity of other quantum Shannon theory tasks, such as
achieving capacity over a noisy channel, entanglement distillation, or quantum
state redistribution?

We remark that the problem of proving complexity lower bounds on entanglement
distillation appears to be conceptually challenging as it requires reasoning
about LOCC protocols.

###  10 Applications to Computational Tasks in High-Energy Physics

In this section, we discuss connections between the Uhlmann Transformation
Problem and computational tasks motivated by questions in high-energy physics.
We first discuss the _black hole radiation decoding task_ , which was
introduced by Harlow and Hayden [HH13]. We argue that the complexity of this
task is characterized by the complexity of the distributional Uhlmann
Transformation Problem. Then, we discuss the _interference detection task_ as
formalized by Aaronson, Atia, and Susskind [AAS20]: this is the problem of
detecting the interference between two orthogonal states $\ket{\psi}$ and
$\ket{\varphi}$, i.e. whether the states are in an equal plus or minus
superposition. One of the motivations for considering this problem is the task
of physically distinguishing between superpositions of spacetime geometries in
the AdS/CFT correspondence [AAS20]. We show that solving the interference
detection problem between two orthogonal $\mathsf{statePSPACE}$ states reduces
to $\textsc{SuccinctUhlmann}_{1}$ in polynomial time.

####  10.1 Black hole radiation decoding

The black hole radiation decoding task is motivated by the following thought
experiment of Almheiri, Marolf, Polchinski, Sully [AMPS13]: imagine that Alice
creates a maximally entangled pair of qubits
$\ket{\mathrm{EPR}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ and throws one half
into a newly-formed black hole. After a long time, Alice could potentially
decode the Hawking radiation of the black hole and recover the qubit she threw
in. However, Alice could then jump into the black hole and find another qubit
that is supposed to be maximally entangled with the qubit that was not thrown
in – witnessing a violation of the monogamy of entanglement. These conclusions
were derived assuming supposedly uncontroversial principles of quantum field
theory and general relativity.

Harlow and Hayden proposed a resolution to this paradox via a computational
complexity argument [HH13]: it may not be _feasible_ for Alice to decode the
black hole’s Hawking radiation in any reasonable amount of time — by the time
she decodes the qubit that she threw in, the black hole may have evaporated
anyways! They argued that, assuming $\mathsf{SZK}\not\subseteq\mathsf{BQP}$ –
note that these are classes of _decision_ problems — a formulation of the
black hole radiation decoding task cannot be done in polynomial time.

What about the converse? That is, does a traditional complexity class
statement such as $\mathsf{SZK}\subseteq\mathsf{BQP}$ imply that the black
hole radiation decoding task is solvable in polynomial time? As pointed out by
Aaronson [Aar16], it is not even clear that the black hole radiation decoding
task is easy even if we assume $\mathsf{P}=\mathsf{PSPACE}$. As with all the
other “fully quantum” tasks considered in this paper, it appears difficult to
characterize the complexity of the black hole decoding problem in terms of
traditional notions from complexity theory.

Brakerski recently gave a characterization of the hardness of the black hole
radiation task in terms of the existence of a cryptographic primitive known as
_quantum EFI pairs_ [Bra23], which are in turn equivalent to quantum
commitments (as well as many other quantum cryptographic primitives, see
[BCQ23] for an in-depth discussion). Given the discussion in Section 8 that
connects quantum commitments with the Uhlmann Transformation Problem, one
would then expect an equivalence between black hole radiation decoding and the
Uhlmann Transformation Problem.

We spell out this equivalence by showing that complexity of the black hole
radiation decoding task is the same as the complexity of the Decodable Channel
Problem, which we showed to be equivalent to the (distributional) Uhlmann
Transformation Problem in Section 9.1. We believe that the direct reduction to
and from the Decodable Channel Problem is natural, and may be useful to those
who are more comfortable with quantum Shannon theory.

We first describe a formulation of the black hole radiation decoding task,
which is an adaptation of the formulations of [HH13, Bra23].

$H_{\mathrm{early}}$$R_{\mathrm{early}}$$B$$A$$H_{\mathrm{old}}$$R_{\mathrm{old}}$$B$$H_{\mathrm{old}}$$R^{\prime}_{\mathrm{old}}$$B$$A$(a)(b)(c)
Figure 4: Decoding black hole radiation. (a) Qubit $A$, maximally entangled
with qubit $B$, falls into an early black hole $H_{\mathrm{early}}$, which is
entangled with some early Hawking radiation $R_{\mathrm{early}}$. (b) After
evaporating much of its mass, the old black hole $H_{\mathrm{old}}$ is
entangled with the radiation $R_{\mathrm{old}}$ which is entangled with the
qubit $B$. (c) By performing a computation on the radiation only, the partner
qubit $A$ can be decoded.

######  Definition 10.1 (Decodable black hole states).

Let $P$ denote a unitary quantum circuit mapping registers
$\mathsf{A}\mathsf{G}$ to $\mathsf{H}\mathsf{R}$ where $\mathsf{A}$ is a
single qubit register. Consider the state

$\ket{\psi}_{\mathsf{BHR}}\coloneqq(\textnormal{id}_{\mathsf{B}}\otimes
P_{\mathsf{AG}\to\mathsf{HR}})\ket{\mathrm{EPR}}_{\mathsf{BA}}\otimes\ket{0}_{\mathsf{G}}~{}.$

We say that _$\ket{\psi}$ is an $\epsilon$-decodable black hole state_ if
there exists a quantum circuit $D$ that takes as input register $\mathsf{R}$
and outputs a qubit labelled $\mathsf{A}$, such that letting
$\rho_{\mathsf{HBA}}$ denote the state $(\textnormal{id}\otimes
D)(\ket{\psi}\\!\\!\bra{\psi})$, we have

$\mathrm{F}\Big{(}\ket{\mathrm{EPR}}\\!\\!\bra{\mathrm{EPR}}_{\mathsf{AB}}\,,\,\rho_{\mathsf{AB}}\Big{)}\geq
1-\epsilon$

i.e., measuring the registers $\mathsf{BA}$ in the Bell basis yields the state
$\ket{\mathrm{EPR}}\coloneqq\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ with
probability at least $1-\epsilon$. We say that the circuit $D$ is a
_$\epsilon$ -decoder_ for the state $\ket{\psi}$.

The circuit $P$ generating the decodable black hole state can be thought of as
a unitary that encodes the laws of black hole evolution: given a qubit in
register $\mathsf{A}$ and a fixed number of ancilla qubits, it forms a black
hole in register $\mathsf{H}$ as well as the outgoing Hawking radiation in
register $\mathsf{R}$. The decodability condition implies that, by acting on
the radiation only, it is information-theoretically possible to decode the
original qubit that was input. See Figure 4 for an illustration of black hole
radiation decoding. We formalize black hole radiation decoding as a
computational task.

######  Definition 10.2 (Black hole radiation decoding task).

Let $\epsilon(n),\delta(n)$ be functions. We say that a quantum algorithm
$D=(D_{x})_{x}$ solves the _$\epsilon$ -black hole radiation decoding task
with error $\delta$_ if for all $x=(1^{n},P)$ where $P$ is a unitary quantum
circuit acting on $n$ qubits and gives rise to an $\epsilon(n)$-decodable
black hole state $\ket{\psi}$, the circuit $D_{x}$ is a $\delta(n)$-decoder
for $\ket{\psi}$.

We now prove that the task of black hole radiation decoding in Definition 10.2
is equivalent to the Decodable Channel Problem in Definition 9.5, which
results in the following theorem.

######  Theorem 10.3.

$\textsc{DistUhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ for all
negligible functions $\epsilon(n)$ if and only if the $\epsilon(n)$-black hole
radiation decoding task is solvable in polynomial-time for all inverse
polynomials $\delta(n)$.

###### Proof.

We prove this via reduction to the Decodable Channel Problem described in
Section 9.1. First, observe (from the proof) that the statement in Theorem 9.6
still holds when considering instances of the $\epsilon$-Decodable Channel
Problem of the form $y=(1^{1},1^{r},C)$, i.e., where we restrict $C$ to single
qubit inputs only. Define the following bijection $\varphi$: for every
$x=(1^{n},P)$, where $P:\mathsf{AG}\rightarrow\mathsf{HR}$ is a unitary
quantum circuit acting on $n$ qubits and where $r$ is the size of the register
$\mathsf{R}$, define $\varphi(x)=(1^{1},1^{r},\tilde{P})$, where $\tilde{P}$
is the quantum circuit first appends $n-1$ qubits initialized to $\ket{0}$ to
its input and then runs $P$.

It is clear that $x$ corresponds to an $\epsilon$-decodable black hole state
if and only if $\varphi(x)$ corresponds to an $\epsilon$-decodable channel:
the channel can be viewed as taking the input qubit, dumping it in the black
hole, and the outputting the radiation emitted by the black hole. Decoding the
EPR pair from the channel associated with $\tilde{P}$ exactly corresponds to
decoding the EPR pair from the black hole associated with $P$. Therefore, the
claim follows from Theorem 9.6, which shows that the complexity of the
Decodable Channel Problem is equivalent to the complexity of DistUhlmann. ∎

######  Remark 10.4.

We remark that Brakerski proved a stronger theorem by relating the black hole
radiation task to EFI [BCQ23]. For simplicity, we focus on the task of
decoding the EPR pair with fidelity $1-\epsilon$, for a small $\epsilon$,
whereas Brakerski [Bra23] used amplification to boost weak decoders that
succeed with fidelity much smaller than $1$.

####  10.2 Interference detection

In this section, we consider the computational task of _interference
detection_ between orthogonal $\mathsf{PSPACE}$ states. Aaronson, Atia, and
Susskind [AAS20] recently proved the following folklore observation, sometimes
called the _swapping-distinguishing equivalence_ : if one can detect the
interference between two orthogonal states $\ket{\psi}$ and $\ket{\varphi}$,
i.e. whether the states are in an equal superposition

$\frac{\ket{\psi}+\ket{\varphi}}{\sqrt{2}}\quad\quad\text{ and
}\quad\quad\frac{\ket{\psi}-\ket{\varphi}}{\sqrt{2}},$

then one can also _swap_ between $\ket{\psi}$ and $\ket{\varphi}$, and vice
versa. We first review the swapping-distinguishing equivalence shown by
Aaronson, Atia, and Susskind [AAS20].

######  Theorem 10.5 ([AAS20], Theorem 1).

Suppose that $\ket{\psi}$ and $\ket{\varphi}$ are $n$-qubit orthogonal states.
Then, the following two statements are equivalent:

  * •

There exists a “swapping” unitary $U$ such that

$U\ket{\psi}=\ket{\varphi}\quad\quad\text{ and }\quad\quad
U\ket{\varphi}=\ket{\psi}\,.$

  * •

There exists an “interference detector” unitary $V$ that perfectly
distinguishes between

$\frac{\ket{\psi}+\ket{\varphi}}{\sqrt{2}}\quad\quad\text{ and
}\quad\quad\frac{\ket{\psi}-\ket{\varphi}}{\sqrt{2}}\,.$

Specifically, by “distinguish” we mean that $V$ takes one of the two states as
input and stores its guess for which state it received as the first qubit of
its output.

Moreover, constructing $V$ from $U$ (and vice versa) only incurs a constant
multiplicative factor in terms of circuit complexity. The conversion uses the
following circuits:

$\Qcircuit<EMAIL_ADDRESS>\lstick{\frac{\ket{\psi}\pm\ket{\varphi}}{\sqrt{2}}}\qw\gate{U}\qw\qw}$

Circuit for interference detection unitary $V$ using a controlled-swap
(controlled-$U$) operation.

$\Qcircuit<EMAIL_ADDRESS>\lstick{}\qw\ghost{V}\qw\qw\qw\ghost{V^{\dagger}}\qw\\\ {\begin{split}&\\\
&~{}\\\
&~{}\end{split}}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}^{\vdots}~{}~{}~{}\ghost{A}\qw^{\vdots}\ghost{A^{\dagger}}\qw\\\
\lstick{}\qw\ghost{A}\qw\qw\qw\ghost{A^{\dagger}}\qw\\\ }$

Circuit for swapping unitary $U$ using the interference detection unitary $V$
and its inverse.

We now formalize the task of detecting interference between orthogonal states
as the following problem, where the input consists of two orthogonal
$\mathsf{statePSPACE}$ states.

######  Definition 10.6 (Interference detection between orthogonal
$\mathsf{statePSPACE}$ states).

We say that a quantum algorithm $A=(A_{x})_{x}$ _solves the
InterferenceDetection task_ if for all $x=(1^{n},\hat{C},\hat{D})$ where
$\hat{C}$ and $\hat{D}$ are succinct descriptions of unitary quantum circuits
$C$ and $D$ acting on $n$ qubits such that the states $\ket{C}\coloneqq
C\ket{0^{n}}$ and $\ket{D}\coloneqq D\ket{0^{n}}$ are orthogonal, the circuit
$A_{x}$ perfectly distinguishes between the superpositions

$\frac{\ket{C}+\ket{D}}{\sqrt{2}}\quad\quad\text{ and
}\quad\quad\frac{\ket{C}-\ket{D}}{\sqrt{2}}\,.$

######  Remark 10.7.

One can also relax Definition 10.6 to allow the algorithm $A$ to distinguish
between the two superpositions imperfectly, but for simplicity we focus on the
perfect case. We also note that $A$ is solving a “quantum-input decision
problem” in the sense that we only care about a single bit of its output, but,
in contrast to traditional decision problems, its input is one of two quantum
states.

The motivation behind this definition of InterferenceDetection is the
following. It is an interesting task only if the two states $\ket{C},\ket{D}$
for which we are trying to swap or determine the phase are in some sense
highly complex. For example if $\ket{C},\ket{D}$ were computable by polynomial
sized circuits then one could efficiently swap or detect the phase by applying
$C^{\dagger}$ and then checking whether the result is all zeroes. On the other
hand, suppose that $\ket{C},\ket{D}$ were the results of some very long
computations. An example that motivated Aaronson, Atia, and Susskind is if
$\ket{C},\ket{D}$ represent distinct spacetime geometries that were produced
by a complex physical process (such as black hole formation) after a long
amount of time. What is the complexity of detecting whether one is a
_superposition_ of the two spacetime geometries? Theorem 10.5 shows that this
is the same complexity as mapping from one spacetime to another.

Thus in our definition we incorporate the high complexity of the states
$\ket{C},\ket{D}$ by allowing them to be generated by a polynomial space
computation. One could also consider the interference detection problem for
other classes of states; we leave this for future work.

We now upper bound the complexity of solving InterferenceDetection (for
$\mathsf{statePSPACE}$ states). We show that InterferenceDetection polynomial-
time reduces to $\textsc{DistSuccinctUhlmann}_{1}$, in a sense made precise in
the following theorem.

######  Theorem 10.8.

There exists a polynomial-time query algorithm $A$ with access to a
$\textsc{DistSuccinctUhlmann}_{1}$ oracle that solves InterferenceDetection.

###### Proof.

Consider an instance $x=(1^{n},\hat{C},\hat{D})$, where $C,D$ are succinct
descriptions of unitary quantum circuits $C,D$ such that $\ket{C},\ket{D}$ are
orthogonal $n$ qubit states. First, we show how to construct circuits
$C^{\prime},D^{\prime}$ to obtain a swapping unitary with

$U\ket{C}=\ket{D}\quad\quad\text{ and }\quad\quad U\ket{D}=\ket{C}$

with a single call to the oracle for $\textsc{DistSuccinctUhlmann}_{1}$. Next,
we show how to modify $C^{\prime}$ and $D^{\prime}$ in order to obtain a
controlled-$U$ unitary instead which suffices for interference detection
according to the swapping and distinguishing equivalence from Theorem 10.5.

Let $\mathsf{A}$ be a single-qubit register initialized to $\ket{0}$, and let
$\mathsf{B}$ be an $n$-qubit register initialized to $\ket{0^{n}}$. We first
construct circuits $\bar{C},\bar{D}$ acting on $n+1$ qubits as follows:

$\Qcircuit<EMAIL_ADDRESS>\lstick{\mathsf{B}}\gate{C}\gate{C^{\dagger}}\gate{D}\qw}$

Circuit $\bar{C}$

$\Qcircuit<EMAIL_ADDRESS>\lstick{\mathsf{B}}\gate{D}\gate{D^{\dagger}}\gate{C}\qw}$

Circuit $\bar{D}$

In other words, the circuits $\bar{C},\bar{D}$ produce the following states

$\displaystyle\bar{C}\ket{0}_{\mathsf{A}}\otimes\ket{0^{n}}_{\mathsf{B}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0}_{\mathsf{A}}\otimes\ket{C}_{\mathsf{B}}+\ket{1}_{\mathsf{A}}\otimes\ket{D}_{\mathsf{B}})\,,$
$\displaystyle\bar{D}\ket{0}_{\mathsf{A}}\otimes\ket{0^{n}}_{\mathsf{B}}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0}_{\mathsf{A}}\otimes\ket{D}_{\mathsf{B}}+\ket{1}_{\mathsf{A}}\otimes\ket{C}_{\mathsf{B}})\,.$

Since $\ket{C}$ and $\ket{D}$ are orthogonal, the reduced states in system
$\mathsf{A}$ are equal to $\frac{\textnormal{id}}{2}$ in both cases.
Therefore, with a single call to the oracle for
$\textsc{DistSuccinctUhlmann}_{1}$ with respect to the circuits $C^{\prime}$
and $D^{\prime}$, we obtain swapping unitary $U\in\mathrm{L}(\mathsf{B})$ such
that

$U\ket{C}=\ket{D}\quad\quad\text{ and }\quad\quad U\ket{D}=\ket{C}\,.$

We now construct circuits $\tilde{C}$ and $\tilde{D}$ which allow us to obtain
a controlled-$U$ operation with a single call to
$\textsc{DistSuccinctUhlmann}_{1}$. The circuits are defined as follows:

$\Qcircuit@C=2em@R=1.2em{\lstick{\mathsf{A}\,\,}&\multigate{1}{\bar{C}}\qw\qw\\\
\lstick{\mathsf{B}\,\,}\ghost{\bar{C}}\qw\qw\\\
\lstick{\mathsf{A}^{\prime}}\qw\targ\qw\\\
\lstick{\mathsf{B}^{\prime}}\gate{H}\ctrl{-1}\qw}$

Circuit $\tilde{C}$

$\Qcircuit@C=2em@R=1.2em{\lstick{\mathsf{A}\,\,}&\multigate{1}{\bar{C}}\qw\multigate{1}{\bar{C}^{\dagger}}\multigate{1}{\bar{D}}\qw\\\
\lstick{\mathsf{B}\,\,}\ghost{\bar{C}}\qw\ghost{\bar{C}^{\dagger}}\ghost{\bar{D}}\qw\\\
\lstick{\mathsf{A}^{\prime}}\qw\targ\qw\qw\qw\\\
\lstick{\mathsf{B}^{\prime}}\gate{H}\ctrl{-1}\ctrl{-2}\ctrl{-2}\qw}$

Circuit $\tilde{D}$

We now consider the pure states generated by $\tilde{C}$ and $\tilde{D}$ when
applied to $n+2$ qubits inititialized to $\ket{0}$. Let $\mathsf{A}^{\prime}$
and $\mathsf{B}^{\prime}$ be single qubit registers initialized to $\ket{0}$.
First, by applying $\tilde{C}$ to $\ket{0^{n+2}}$, we obtain the following
state

$\ket{\tilde{C}}_{\mathsf{A}\mathsf{A}^{\prime}\mathsf{B}\mathsf{B}^{\prime}}=\frac{1}{\sqrt{2}}(\ket{0}_{\mathsf{A}}\otimes\ket{\rm
EPR}_{\mathsf{A}^{\prime}\mathsf{B}^{\prime}}\otimes\ket{C}_{\mathsf{B}}+\ket{1}_{\mathsf{A}}\otimes\ket{\rm
EPR}_{\mathsf{A}^{\prime}\mathsf{B}^{\prime}}\otimes\ket{D}_{\mathsf{B}}).$

Moreover, by applying $\tilde{D}$ to $\ket{0^{n+2}}$, we obtain the state

$\ket{\tilde{D}}_{\mathsf{A}\mathsf{A}^{\prime}\mathsf{B}\mathsf{B}^{\prime}}=\left(\sum_{c\in\\{0,1\\}}\ket{c}\\!\\!\bra{c}_{\mathsf{B}^{\prime}}\otimes\bar{D}_{\mathsf{A}\mathsf{B}}^{c}\right)\,\left(\sum_{b\in\\{0,1\\}}\ket{b}\\!\\!\bra{b}_{\mathsf{B}^{\prime}}\otimes(\bar{C}^{\dagger})^{b}_{\mathsf{A}\mathsf{B}}\right)\ket{\tilde{C}}_{\mathsf{A}\mathsf{A}^{\prime}\mathsf{B}\mathsf{B}^{\prime}}\,.$

Let us now define density operators

$\rho_{\mathsf{AA}^{\prime}\mathsf{BB}^{\prime}}=\ket{\tilde{C}}\\!\\!\bra{\tilde{C}}_{\mathsf{AA}^{\prime}\mathsf{BB}^{\prime}}\quad\quad\text{
and
}\quad\quad\sigma_{\mathsf{ABB}^{\prime}}=\ket{\tilde{D}}\\!\\!\bra{\tilde{D}}_{\mathsf{AA}^{\prime}\mathsf{BB}^{\prime}}\,.$

Because $\ket{C}$ and $\ket{D}$ are orthogonal, the reduced states
$\rho_{\mathsf{A}\mathsf{A}^{\prime}}$ and
$\sigma_{\mathsf{A}\mathsf{A}^{\prime}}$ satisfy

$\rho_{\mathsf{A}\mathsf{A}^{\prime}}=\sigma_{\mathsf{A}\mathsf{A}^{\prime}}=\frac{\textnormal{id}_{\mathsf{A}\mathsf{A}^{\prime}}}{4}\,.$

By Uhlmann’s theorem there exists a unitary $\tilde{U}$ acting on registers
$\mathsf{B}^{\prime}\mathsf{B}$ such that
$\ket{\tilde{D}}=(\textnormal{id}_{\mathsf{A}\mathsf{A}^{\prime}}\otimes\tilde{U}_{\mathsf{B}^{\prime}\mathsf{B}})\ket{\tilde{C}}$.
In particular, the unitary $\tilde{U}$ satisfies

$\displaystyle\tilde{U}\ket{0}_{\mathsf{B}^{\prime}}\ket{C}_{\mathsf{B}}$
$\displaystyle=\ket{0}_{\mathsf{B}^{\prime}}\ket{C}_{\mathsf{B}}$
$\displaystyle\tilde{U}\ket{0}_{\mathsf{B}^{\prime}}\ket{D}_{\mathsf{B}}$
$\displaystyle=\ket{0}_{\mathsf{B}^{\prime}}\ket{D}_{\mathsf{B}}$
$\displaystyle\tilde{U}\ket{1}_{\mathsf{B}^{\prime}}\ket{C}_{\mathsf{B}}$
$\displaystyle=\ket{1}_{\mathsf{B}^{\prime}}\ket{D}_{\mathsf{B}}$
$\displaystyle\tilde{U}\ket{1}_{\mathsf{B}^{\prime}}\ket{D}_{\mathsf{B}}$
$\displaystyle=\ket{1}_{\mathsf{B}^{\prime}}\ket{C}_{\mathsf{B}}\,.$

Hence, $\tilde{U}$ acts as the controlled-$U$ operator of the form

$\tilde{U}=\sum_{c\in\\{0,1\\}}\ket{c}\\!\\!\bra{c}_{\mathsf{B}^{\prime}}\otimes
U_{\mathsf{B}}^{c}\,,$

where $U$ is the swapping unitary from before. Therefore, we can use the
following circuit to perfectly distinguish between
$\frac{\ket{C}+\ket{D}}{\sqrt{2}}$ and $\frac{\ket{C}-\ket{D}}{\sqrt{2}}$ with
a single call to the oracle for $\textsc{DistSuccinctUhlmann}_{1}$ with
respect to the circuits $\tilde{C}$ and $\tilde{D}$ and the state
$\ket{+}\otimes\frac{\ket{C}\pm\ket{D}}{\sqrt{2}}$.

$\Qcircuit<EMAIL_ADDRESS>\lstick{\frac{\ket{C}\pm\ket{D}}{\sqrt{2}}}\qw\gate{U}\qw\qw}$

∎

####  10.3 Open problems

We conclude with some open problems related to the physics-inspired
applications considered in this section.

######  Open Problem 26.

Does the complexity of any of the information processing tasks discussed in
this paper (e.g., compression or state merging) have any ramifications for
holography or models of quantum gravity? May [May19] has recently suggested
that information tasks performable in the bulk are also performable on the
boundary of the AdS/CFT correspondence. Does this correspondence also preserve
the complexity of the task?

######  Open Problem 27.

What is the complexity of InterferenceDetection? Can we argue that it is hard
for some unitary complexity class? For example, can we use the equivalence in
Theorem 10.5 to argue that $\textsc{DistSuccinctUhlmann}_{1}$ reduces to
InterferenceDetection, thereby rendering the two tasks equivalent?

######  Open Problem 28.

What is the complexity of InterferenceDetection with states drawn from some
other state complexity class (e.g., a state complexity analogue of
$\mathsf{QMA}$ or $\mathsf{SZK}$)?

### References

  * [AA17] Yosi Atia and Dorit Aharonov  “Fast-forwarding of Hamiltonians and exponentially precise measurements”  In _Nature Communications_ 8.1, 2017, pp. 1572  DOI: 10.1038/s41467-017-01637-7
  * [AA23] Anurag Anshu and Srinivasan Arunachalam  “A survey on the complexity of learning quantum states”, 2023  arXiv:2305.20069
  * [Aar07] Scott Aaronson  “The learnability of quantum states”  In _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ 463.2088 The Royal Society London, 2007, pp. 3089–3114  DOI: 10.1098/rspa.2007.0113
  * [Aar09] Scott Aaronson  “Quantum Copy-Protection and Quantum Money”  In _2009 24th Annual IEEE Conference on Computational Complexity_ IEEE, 2009  DOI: 10.1109/ccc.2009.42
  * [Aar14] Scott Aaronson  “The Equivalence of Sampling and Searching”  In _Theory of Computing Systems_ 55.2, 2014, pp. 281–298  DOI: 10.1007/s00224-013-9527-3
  * [Aar16] Scott Aaronson  “The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes”, 2016  arXiv:1607.05256
  * [Aar23] Scott Aaronson  “The Complexity Zoo” Accessed: 2023-04-01, https://complexityzoo.net/Complexity_Zoo, 2023
  * [AAS20] Scott Aaronson, Yosi Atia and Leonard Susskind  “On the Hardness of Detecting Macroscopic Superpositions”, 2020  arXiv:2009.07450
  * [AC12] Scott Aaronson and Paul Christiano  “Quantum Money from Hidden Subspaces”  In _Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing_ , STOC ’12  New York, New York, USA: Association for Computing Machinery, 2012, pp. 41–60  DOI: 10.1145/2213977.2213983
  * [ACQ22] Dorit Aharonov, Jordan Cotler and Xiao-Liang Qi  “Quantum algorithmic measurement”  In _Nature Communications_ 13.1, 2022, pp. 887  DOI: 10.1038/s41467-021-27922-0
  * [ADHW09] Anura Abeyesinghe, Igor Devetak, Patrick Hayden and Andreas Winter  “The Mother of All Protocols: Restructuring Quantum Information’s Family Tree”  In _Proceedings: Mathematical, Physical and Engineering Sciences_ 465.2108 Royal Society, 2009, pp. 2537–2563  DOI: 10.1098/rspa.2009.0202
  * [AE07] Andris Ambainis and Joseph Emerson  “Quantum $t$-designs: $t$-wise independence in the quantum world”  In _Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07)_ , 2007, pp. 129–140  DOI: 10.1109/CCC.2007.26
  * [AG04] Scott Aaronson and Daniel Gottesman  “Improved simulation of stabilizer circuits”  In _Physical Review A_ 70 American Physical Society, 2004, pp. 052328  DOI: 10.1103/PhysRevA.70.052328
  * [Aha03] Dorit Aharonov  “A Simple Proof that Toffoli and Hadamard are Quantum Universal”, 2003  arXiv:quant-ph/0301040
  * [AJW18] Anurag Anshu, Rahul Jain and Naqueeb Ahmad Warsi  “A One-Shot Achievability Result for Quantum State Redistribution”  In _IEEE Transactions on Information Theory_ 64.3, 2018, pp. 1425–1435  DOI: 10.1109/TIT.2017.2776112
  * [AK07] Scott Aaronson and Greg Kuperberg  “Quantum Versus Classical Proofs and Advice”  In _Theory of Computing_ 3.7 Theory of Computing, 2007, pp. 129–157  DOI: 10.4086/toc.2007.v003a007
  * [AKL+22] Prabhanjan Ananth et al.  “On the Feasibility of Unclonable Encryption, and More”  In _Advances in Cryptology – CRYPTO 2022_ Cham: Springer Nature Switzerland, 2022, pp. 212–241  DOI: 10.1007/978-3-031-15979-4_8
  * [AMPS13] Ahmed Almheiri, Donald Marolf, Joseph Polchinski and James Sully  “Black holes: complementarity or firewalls?”  In _Journal of High Energy Physics_ 2013.2, 2013, pp. 62  DOI: 10.1007/JHEP02(2013)062
  * [AQY22] Prabhanjan Ananth, Luowen Qian and Henry Yuen  “Cryptography from Pseudorandom Quantum States”  In _Advances in Cryptology – CRYPTO 2022_ Cham: Springer Nature Switzerland, 2022, pp. 208–236  DOI: 10.1007/978-3-031-15802-5_8
  * [BCQ23] Zvika Brakerski, Ran Canetti and Luowen Qian  “On the Computational Hardness Needed for Quantum Cryptography”  In _14th Innovations in Theoretical Computer Science Conference (ITCS 2023)_ 251, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, pp. 24:1–24:21  DOI: 10.4230/LIPIcs.ITCS.2023.24
  * [BCR11] Mario Berta, Matthias Christandl and Renato Renner  “The Quantum Reverse Shannon Theorem Based on One-Shot Information Theory”  In _Communications in Mathematical Physics_ 306.3, 2011, pp. 579–615  DOI: 10.1007/s00220-011-1309-7
  * [BCT16] Mario Berta, Matthias Christandl and Dave Touchette  “Smooth Entropy Bounds on One-Shot Quantum State Redistribution”  In _IEEE Transactions on Information Theory_ 62.3, 2016, pp. 1425–1439  DOI: 10.1109/TIT.2016.2516006
  * [BFL91] László Babai, Lance Fortnow and Carsten Lund  “Non-deterministic exponential time has two-prover interactive protocols”  In _computational complexity_ 1.1, 1991, pp. 3–40  DOI: 10.1007/BF01200056
  * [BFV19] Adam Bouland, Bill Fefferman and Umesh Vazirani  “Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality”  In _arXiv preprint arXiv:1910.14646_ , 2019
  * [Bha13] Rajendra Bhatia  “Matrix Analysis”  Springer New York, 2013  DOI: 10.1007/978-1-4612-0653-8
  * [BI20] Anne Broadbent and Rabib Islam  “Quantum Encryption with Certified Deletion”  In _Theory of Cryptography_ Cham: Springer International Publishing, 2020, pp. 92–122  DOI: 10.1007/978-3-030-64381-2_4
  * [BL20] Anne Broadbent and Sébastien Lord  “Uncloneable Quantum Encryption via Oracles”  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020  DOI: 10.4230/LIPICS.TQC.2020.4
  * [BO21] Costin Bădescu and Ryan O’Donnell  “Improved quantum data analysis”  In _Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing_ , 2021, pp. 1398–1411
  * [Bra23] Zvika Brakerski  “Black-Hole Radiation Decoding is Quantum Cryptography”, 2023  arXiv:2211.05491
  * [BRS+16] Adam R Brown et al.  “Complexity, action, and black holes”  In _Physical Review D_ 93 American Physical Society, 2016, pp. 086006  DOI: 10.1103/PhysRevD.93.086006
  * [BS19] Zvika Brakerski and Omri Shmueli  “(Pseudo) Random Quantum States with Binary Phase”, 2019  arXiv:1906.10611
  * [CLLZ21] Andrea Coladangelo, Jiahui Liu, Qipeng Liu and Mark Zhandry  “Hidden Cosets and Applications to Unclonable Cryptography”  In _Advances in Cryptology – CRYPTO 2021_ Cham: Springer International Publishing, 2021, pp. 556–584  DOI: 10.1007/978-3-030-84242-0_20
  * [CLS01] Claude Crépeau, Frédéric Légaré and Louis Salvail  “How to Convert the Flavor of a Quantum Bit Commitment”  In _Advances in Cryptology - EUROCRYPT 2001_ 2045, Lecture Notes in Computer Science  Springer, 2001, pp. 60–77  DOI: 10.1007/3-540-44987-6_5
  * [CMP20] Andrea Coladangelo, Christian Majenz and Alexander Poremba  “Quantum copy-protection of compute-and-compare programs in the quantum random oracle model”, 2020  arXiv:2009.13865
  * [DBWR14] Frédéric Dupuis, Mario Berta, Jürg Wullschleger and Renato Renner  “One-Shot Decoupling”  In _Communications in Mathematical Physics_ 328.1, 2014, pp. 251–284  DOI: 10.1007/s00220-014-1990-4
  * [Dup10] Frédéric Dupuis  “The decoupling approach to quantum information theory”, 2010  arXiv:1004.1641
  * [FF93] Joan Feigenbaum and Lance Fortnow  “Random-Self-Reducibility of Complete Sets”  In _SIAM Journal on Computing_ 22.5, 1993, pp. 994–1005  DOI: 10.1137/0222061
  * [GJMZ23] Sam Gunn, Nathan Ju, Fermi Ma and Mark Zhandry  “Commitments to Quantum States”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , STOC 2023  Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1579–1588  DOI: 10.1145/3564246.3585198
  * [GMN22] François Le Gall, Masayuki Miyamoto and Harumichi Nishimura  “Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications”, 2022  arXiv:2210.01389
  * [GSV98] Oded Goldreich, Amit Sahai and Salil Vadhan  “Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge”  In _Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing_ , STOC ’98  Dallas, Texas, USA: Association for Computing Machinery, 1998, pp. 399–408  DOI: 10.1145/276698.276852
  * [GW11] Craig Gentry and Daniel Wichs  “Separating Succinct Non-Interactive Arguments from All Falsifiable Assumptions”  In _Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing_ , STOC ’11  San Jose, California, USA: Association for Computing Machinery, 2011, pp. 99–108  DOI: 10.1145/1993636.1993651
  * [Hai09] Iftach Haitner  “A Parallel Repetition Theorem for Any Interactive Argument”  In _2009 50th Annual IEEE Symposium on Foundations of Computer Science_ , 2009, pp. 241–250  DOI: 10.1109/FOCS.2009.50
  * [Har13] Aram W. Harrow  “The Church of the Symmetric Subspace”, 2013  arXiv:1308.6595
  * [Haw76] Stephen W Hawking  “Breakdown of predictability in gravitational collapse”  In _Physical Review D_ 14 American Physical Society, 1976, pp. 2460–2473  DOI: 10.1103/PhysRevD.14.2460
  * [HH13] Daniel Harlow and Patrick Hayden  “Quantum computation vs. firewalls”  In _Journal of High Energy Physics_ 2013.6, 2013, pp. 85  DOI: 10.1007/JHEP06(2013)085
  * [HHWY08] Patrick Hayden, Michał Horodecki, Andreas Winter and Jon Yard  “A Decoupling Approach to the Quantum Capacity”  In _Open Systems & Information Dynamics_ 15.01, 2008, pp. 7–19  DOI: 10.1142/S1230161208000043
  * [HILL99] Johan Håstad, Russell Impagliazzo, Leonid A. Levin and Michael Luby  “A Pseudorandom Generator from any One-way Function”  In _SIAM J. Comput._ 28.4, 1999, pp. 1364–1396  DOI: 10.1137/S0097539793244708
  * [HKP20] Hsin-Yuan Huang, Richard Kueng and John Preskill  “Predicting many properties of a quantum system from very few measurements”  In _Nature Physics_ 16.10, 2020, pp. 1050–1057  DOI: 10.1038/s41567-020-0932-7
  * [HMS23] Iftach Haitner, Noam Mazor and Jad Silbak  “Incompressiblity and Next-Block Pseudoentropy”  In _14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA_ 251, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 66:1–66:18  DOI: 10.4230/LIPIcs.ITCS.2023.66
  * [HMY23] Minki Hhan, Tomoyuki Morimae and Takashi Yamakawa  “From the Hardness of Detecting Superpositions to Cryptography: Quantum Public Key Encryption and Commitments”  In _Advances in Cryptology – EUROCRYPT 2023_ Cham: Springer Nature Switzerland, 2023, pp. 639–667  DOI: 10.1007/978-3-031-30545-0_22
  * [HPWP10] Johan Håstad, Rafael Pass, Douglas Wikström and Krzysztof Pietrzak  “An Efficient Parallel Repetition Theorem”  In _Theory of Cryptography_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 1–18  DOI: 10.1007/978-3-642-11799-2_1
  * [IL89] Russell Impagliazzo and Michael Luby  “One-way functions are essential for complexity based cryptography”  In _30th Annual Symposium on Foundations of Computer Science_ , 1989, pp. 230–235  DOI: 10.1109/SFCS.1989.63483
  * [Imp95] Russell Impagliazzo  “A personal view of average-case complexity”  In _Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference_ , 1995, pp. 134–147  DOI: 10.1109/SCT.1995.514853
  * [INN+22] Sandy Irani et al.  “Quantum Search-To-Decision Reductions and the State Synthesis Problem”  In _37th Computational Complexity Conference (CCC 2022)_ 234, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 5:1–5:19  DOI: 10.4230/LIPIcs.CCC.2022.5
  * [JJUW11] Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous  “$\mathsf{QIP}=\mathsf{PSPACE}$”  In _Journal of the ACM_ 58.6 New York, NY, USA: Association for Computing Machinery, 2011  DOI: 10.1145/2049697.2049704
  * [JLS18] Zhengfeng Ji, Yi-Kai Liu and Fang Song  “Pseudorandom Quantum States”  In _Advances in Cryptology – CRYPTO 2018_ Cham: Springer International Publishing, 2018, pp. 126–152  DOI: 10.1007/978-3-319-96878-0_5
  * [JNV+21] Zhengfeng Ji et al.  “$\mathsf{MIP}^{*}=\mathsf{RE}$”  In _Communications of the ACM_ 64.11 New York, NY, USA: Association for Computing Machinery, 2021, pp. 131–138  DOI: 10.1145/3485628
  * [KA04] Elham Kashefi and Carolina Moura Alves  “On the Complexity of Quantum Languages”, 2004  arXiv:quant-ph/0404062
  * [KLL+17] Shelby Kimmel et al.  “Hamiltonian simulation with optimal sample complexity”  In _npj Quantum Information_ 3.1 Springer ScienceBusiness Media LLC, 2017  DOI: 10.1038/s41534-017-0013-7
  * [KQST23] William Kretschmer, Luowen Qian, Makrand Sinha and Avishay Tal  “Quantum Cryptography in Algorithmica”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , STOC 2023  Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 1589–1602  DOI: 10.1145/3564246.3585225
  * [Kre21] William Kretschmer  “Quantum Pseudorandomness and Classical Complexity”  In _16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)_ 197, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, pp. 2:1–2:20  DOI: 10.4230/LIPIcs.TQC.2021.2
  * [KRS09] Robert Konig, Renato Renner and Christian Schaffner  “The Operational Meaning of Min- and Max-Entropy”  In _IEEE Transactions on Information Theory_ 55.9, 2009, pp. 4337–4347  DOI: 10.1109/TIT.2009.2025545
  * [KW00] Alexei Kitaev and John Watrous  “Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems”  In _Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing_ , STOC ’00  Portland, Oregon, USA: Association for Computing Machinery, 2000, pp. 608–617  DOI: 10.1145/335305.335387
  * [KW20] Sumeet Khatri and Mark M. Wilde  “Principles of Quantum Communication Theory: A Modern Approach”, 2020  arXiv:2011.04672
  * [LC98] Hoi-Kwong Lo and H.F. Chau  “Why quantum bit commitment and ideal quantum coin tossing are impossible” Proceedings of the Fourth Workshop on Physics and Consumption  In _Physica D: Nonlinear Phenomena_ 120.1, 1998, pp. 177–187  DOI: 10.1016/S0167-2789(98)00053-0
  * [Lip94] Richard J. Lipton  “A new approach to information theory”  In _STACS 94_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1994, pp. 699–708  DOI: 10.1007/3-540-57785-8_183
  * [LMR14] Seth Lloyd, Masoud Mohseni and Patrick Rebentrost  “Quantum principal component analysis”  In _Nature Physics_ 10.9 Springer ScienceBusiness Media LLC, 2014, pp. 631–633  DOI: 10.1038/nphys3029
  * [LP20] Yanyi Liu and Rafael Pass  “On One-way Functions and Kolmogorov Complexity”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 1243–1254  DOI: 10.1109/FOCS46700.2020.00118
  * [May19] Alex May  “Quantum tasks in holography”  In _Journal of High Energy Physics_ 2019.10, 2019, pp. 233  DOI: 10.1007/JHEP10(2019)233
  * [May97] Dominic Mayers  “Unconditionally Secure Quantum Bit Commitment is Impossible”  In _Physical Review Letters_ 78 American Physical Society, 1997, pp. 3414–3417  DOI: 10.1103/PhysRevLett.78.3414
  * [MY22] Tomoyuki Morimae and Takashi Yamakawa  “One-Wayness in Quantum Cryptography”, 2022  arXiv:2210.03394
  * [MY22a] Tomoyuki Morimae and Takashi Yamakawa  “Quantum Commitments and Signatures Without One-Way Functions”  In _Advances in Cryptology – CRYPTO 2022_ Cham: Springer Nature Switzerland, 2022, pp. 269–295  DOI: 10.1007/978-3-031-15802-5_10
  * [MY23] Tony Metger and Henry Yuen  “$\sf stateQIP=\sf statePSPACE$”, 2023  arXiv:2301.07730
  * [Nao03] Moni Naor  “On Cryptographic Assumptions and Challenges”  In _Advances in Cryptology – CRYPTO 2003_ Berlin, Heidelberg: Springer Berlin Heidelberg, 2003, pp. 96–109  DOI: 10.1007/978-3-540-45146-4_6
  * [NC10] Michael A. Nielsen and Isaac L. Chuang  “Quantum Computation and Quantum Information: 10th Anniversary Edition”  Cambridge University Press, 2010  DOI: 10.1017/CBO9780511976667
  * [Oka96] Tatsuaki Okamoto  “On Relationships between Statistical Zero-Knowledge Proofs”  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96  Philadelphia, Pennsylvania, USA: Association for Computing Machinery, 1996, pp. 649–658  DOI: 10.1145/237814.238016
  * [Pap97] Christos H. Papadimitriou  “$\mathsf{NP}$-completeness: A retrospective”  In _Automata, Languages and Programming_ Berlin, Heidelberg: Springer Berlin Heidelberg, 1997, pp. 2–6  DOI: 10.1007/3-540-63165-8_160
  * [Pre92] John Preskill  “Do Black Holes Destroy Information?”  In _Proceedings of the International Symposium on Black Holes, Membranes, Wormholes and Superstrings_ , 1992, pp. 22–39  World Scientific  DOI: 10.1142/9789814536752
  * [Raz98] Ran Raz  “A Parallel Repetition Theorem”  In _SIAM Journal on Computing_ 27.3, 1998, pp. 763–803  DOI: 10.1137/S0097539795280895
  * [Ren22] Joseph M. Renes  “Quantum Information Theory”  Berlin, Boston: De Gruyter Oldenbourg, 2022  DOI: 10.1515/9783110570250
  * [RY22] Gregory Rosenthal and Henry Yuen  “Interactive Proofs for Synthesizing Quantum States and Unitaries”  In _13th Innovations in Theoretical Computer Science Conference (ITCS 2022)_ 215, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 112:1–112:4  DOI: 10.4230/LIPIcs.ITCS.2022.112
  * [Sch95] Benjamin Schumacher  “Quantum coding”  In _Physical Review A_ 51 American Physical Society, 1995, pp. 2738–2747  DOI: 10.1103/PhysRevA.51.2738
  * [Sha48] Claude E. Shannon  “A mathematical theory of communication”  In _The Bell System Technical Journal_ 27.3, 1948, pp. 379–423  DOI: 10.1002/j.1538-7305.1948.tb01338.x
  * [Shi03] Yaoyun Shi  “Both Toffoli and Controlled-NOT Need Little Help to Do Universal Quantum Computing”  In _Quantum Information & Computation_ 3.1 Paramus, NJ: Rinton Press, Incorporated, 2003, pp. 84–92  URL: https://dl.acm.org/doi/10.5555/2011508.2011515
  * [Sus16] Leonard Susskind  “Computational complexity and black hole horizons”  In _Fortschritte der Physik_ 64.1 Wiley Online Library, 2016, pp. 24–43  DOI: 10.1002/prop.201500092
  * [SV03] Amit Sahai and Salil Vadhan  “A Complete Problem for Statistical Zero Knowledge”  In _Journal of the ACM_ 50.2 New York, NY, USA: Association for Computing Machinery, 2003, pp. 196–249  DOI: 10.1145/636865.636868
  * [TCR09] Marco Tomamichel, Roger Colbeck and Renato Renner  “A Fully Quantum Asymptotic Equipartition Property”  In _IEEE Transactions on Information Theory_ 55.12, 2009, pp. 5840–5847  DOI: 10.1109/TIT.2009.2032797
  * [Tom13] Marco Tomamichel  “A Framework for Non-Asymptotic Quantum Information Theory”, 2013  arXiv:1203.2142
  * [Uhl76] Armin Uhlmann  “The “transition probability” in the state space of a $*$-algebra”  In _Reports on Mathematical Physics_ 9.2, 1976, pp. 273–279  DOI: 10.1016/0034-4877(76)90060-4
  * [VW16] Thomas Vidick and John Watrous  “Quantum Proofs”  In _Foundations and Trends® in Theoretical Computer Science_ 11.1-2, 2016, pp. 1–215  DOI: 10.1561/0400000068
  * [Wat02] John Watrous  “Limits on the power of quantum statistical zero-knowledge”  In _The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings._ , 2002, pp. 459–468  DOI: 10.1109/SFCS.2002.1181970
  * [Wat06] John Watrous  “Zero-Knowledge against Quantum Attacks”  In _Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’06  Seattle, WA, USA: Association for Computing Machinery, 2006, pp. 296–305  DOI: 10.1145/1132516.1132560
  * [Wat99] John Watrous  “Space-Bounded Quantum Complexity”  In _Journal of Computer and System Sciences_ 59.2, 1999, pp. 281–326  DOI: 10.1006/jcss.1999.1655
  * [Wie83] Stephen Wiesner  “Conjugate Coding”  In _SIGACT News_ 15.1 New York, NY, USA: Association for Computing Machinery, 1983, pp. 78–88  DOI: 10.1145/1008908.1008920
  * [Wil13] Mark M. Wilde  “Quantum Information Theory”  Cambridge University Press, 2013  DOI: 10.1017/CBO9781139525343
  * [Win99] Andreas Winter  “Coding theorem and strong converse for quantum channels”  In _IEEE Transactions on Information Theory_ 45.7, 1999, pp. 2481–2485  DOI: 10.1109/18.796385
  * [Yan22] Jun Yan  “General Properties of Quantum Bit Commitments (Extended Abstract)”  In _Advances in Cryptology – ASIACRYPT 2022_ Cham: Springer Nature Switzerland, 2022, pp. 628–657  DOI: 10.1007/978-3-031-22972-5_22
  * [Yao82] Andrew Chi-Chih Yao  “Theory and application of trapdoor functions”  In _23rd Annual Symposium on Foundations of Computer Science_ , 1982, pp. 80–91  DOI: 10.1109/SFCS.1982.45
  * [YE23] Lisa Yang and Netta Engelhardt  “The Complexity of Learning (Pseudo)random Dynamics of Black Holes and Other Chaotic Systems”, 2023  arXiv:2302.11013
  * [Zha21] Mark Zhandry  “Quantum Lightning Never Strikes the Same State Twice. Or: Quantum Money from Cryptographic Assumptions”  In _Journal of Cryptology_ 34.1, 2021, pp. 6  DOI: 10.1007/s00145-020-09372-x