# Unitary Complexity and the Uhlmann Transformation Problem

John Bostanci  Columbia University  Yuval Efron  Columbia University  Tony
Metger  ETH Zürich
Alexander Poremba  Caltech  Luowen Qian  Boston University  Henry Yuen
Columbia University

###### Abstract

State transformation problems such as compressing quantum information or
breaking quantum commitments are fundamental quantum tasks. However, their
computational difficulty cannot easily be characterized using traditional
complexity theory, which focuses on tasks with classical inputs and outputs.

To study the complexity of such state transformation tasks, we introduce a
framework for _unitary synthesis problems_ , including notions of reductions
and unitary complexity classes. We use this framework to study the complexity
of transforming one entangled state into another via local operations. We
formalize this as the _Uhlmann Transformation Problem_ , an algorithmic
version of Uhlmann’s theorem. Then, we prove structural results relating the
complexity of the Uhlmann Transformation Problem, polynomial space quantum
computation, and zero knowledge protocols.

The Uhlmann Transformation Problem allows us to characterize the complexity of
a variety of tasks in quantum information processing, including decoding noisy
quantum channels, breaking falsifiable quantum cryptographic assumptions,
implementing optimal prover strategies in quantum interactive proofs, and
decoding the Hawking radiation of black holes. Our framework for unitary
complexity thus provides new avenues for studying the computational complexity
of many natural quantum information processing tasks.

###### Contents

  1. 1 Introduction
    1. 1.1 A fully quantum complexity theory
    2. 1.2 Structural results about the Uhlmann Transformation Problem
    3. 1.3 Centrality of the Uhlmann Transformation Problem
    4. 1.4 Summary and future directions
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Partial isometries and channel completions
    3. 2.3 Quantum circuits
    4. 2.4 Quantum state complexity classes
  3. I Unitary Complexity Theory
    1. 3 Unitary Synthesis Problems and Unitary Complexity Classes
      1. 3.1 Unitary synthesis problems
      2. 3.2 Unitary complexity classes
      3. 3.3 Reductions
      4. 3.4 Discussion and open problems
    2. 4 Interactive Proofs for Unitary Synthesis
      1. 4.1 Quantum interactive protocols
      2. 4.2 Interactive proofs for unitary synthesis
      3. 4.3 Zero-knowledge protocols for state and unitary synthesis
  4. II Uhlmann Transformation Problem: Definitions and Structural Results
    1. 5 Definition of the Uhlmann Transformation Problem
      1. 5.1 Uhlmann’s theorem and canonical isometries
      2. 5.2 Worst-case Uhlmann transformation problem
      3. 5.3 Distributional Uhlmann transformation problem
    2. 6 Structural Results about the Uhlmann Transformation Problem
      1. 6.1 Completeness for unitary zero knowledge
      2. 6.2 Hardness amplification
      3. 6.3 The padding trick
      4. 6.4 A polarization lemma for unitary zero knowledge?
    3. 7 Structural Results about the Succinct Uhlmann Transformation Problem
      1. 7.1 Completeness for $\mathsf{avgUnitaryQIP}$
      2. 7.2 Completeness for $\mathsf{avgUnitaryPSPACE}$
      3. 7.3 Completeness for worst-case $\mathsf{unitaryPSPACE}$
      4. 7.4 Relationship between $\mathsf{avgUnitaryPSPACE}$ and $\mathsf{PSPACE}$
  5. III Uhlmann Transformation Problem: Applications
    1. 8 Applications to Quantum Cryptography
      1. 8.1 Quantum commitment schemes
      2. 8.2 One-way state generators
      3. 8.3 Falsifiable quantum cryptographic assumptions
      4. 8.4 Open problems
    2. 9 Applications to Quantum Shannon Theory
      1. 9.1 Decoding channels
      2. 9.2 Compressing quantum information
      3. 9.3 Complexity of classical Shannon tasks?
      4. 9.4 Open problems
    3. 10 Applications to Computational Tasks in High-Energy Physics
      1. 10.1 Black hole radiation decoding
      2. 10.2 Interference detection
      3. 10.3 Open problems

###  1 Introduction

Uhlmann’s theorem [Uhl76] is a fundamental result in quantum information
theory that quantifies how well a bipartite pure state $\ket{C}$ can be mapped
to another bipartite pure state $\ket{D}$ by only acting on a subsystem:
letting $\rho$ and $\sigma$ denote the reduced density matrices on the first
subsystem of $\ket{C}$ and $\ket{D}$, respectively, Uhlmann’s theorem states
that

$\mathrm{F}(\rho,\sigma)=\max_{U}\,|\bra{D}\textnormal{id}\otimes
U\ket{C}|^{2}\,,$ (1.1)

where $\mathrm{F}(\rho,\sigma)$ denotes the fidelity function and the
maximization is over all unitary transformations acting on the second
subsystem. We call a unitary $U$ achieving equality in Equation 1.1 an
_Uhlmann transformation_.111Such Uhlmann transformations are unique only if
$\ket{C},\ket{D}$ have full Schmidt rank.

Transforming entangled states via local operations is a ubiquitous task in
quantum information processing. Some examples include:

Quantum Shannon theory.

Quantum Shannon theory is the study of the fundamental limits of quantum
communication over noisy and noiseless channels. Protocols for a myriad of
tasks such as state redistribution, entanglement distillation, and quantum
communication over a noisy quantum channel all require performing Uhlmann
transformations [HHWY08, ADHW09, BCR11, AJW18].

Quantum cryptography.

While it is known that quantum commitment schemes with information-theoretic
security are impossible [May97, LC98], they are possible under computational
assumptions, and recent oracle separations suggest that their security can be
based on weaker assumptions than what is needed classically (i.e., one-way
functions) [Kre21, AQY22, MY22a, KQST23]. It can be seen from the
impossibility results of Mayers–Lo–Chau [May97, LC98] that the security of a
quantum commitment scheme relies on the hardness of performing certain Uhlmann
transformations.

Quantum gravity.

Attempts to unite quantum mechanics with general relativity have given rise to
apparent paradoxes of whether black holes preserve information or not [Haw76].
Recently, physicists have provided intriguing arguments based on
_computational complexity_ as possible resolutions to these paradoxes [HH13].
These arguments claim that distilling entanglement from the emitted Hawking
radiation of a black hole is computationally infeasible — this can be
equivalently phrased as a statement about the hardness of an Uhlmann
transformation [HH13, Bra23].

Quantum complexity theory.

The $\mathsf{QIP}=\mathsf{PSPACE}$ theorem [JJUW11] gives a characterization
of the power of (single-prover) quantum interactive proofs. Kitaev and Watrous
[KW00] showed that optimal prover strategies in these interactive proofs
involve applying Uhlmann transformations at each round.

These examples motivate investigating a computational task we call the
_Uhlmann Transformation Problem_ (denoted by the shorthand Uhlmann): given the
classical description of quantum circuits $C,D$ acting on $2n$ qubits and an
$n$-qubit quantum system (in some unknown state), apply the Uhlmann
transformation $U$ for the state pair $(\ket{C},\ket{D})$ to the given quantum
system, where $\ket{C}=C\ket{0^{2n}}$ and $\ket{D}=D\ket{0^{2n}}$.

What is the complexity of Uhlmann? What are the implications for the
complexity of the tasks mentioned in the examples above? For instance, many
protocols developed in quantum Shannon theory achieve asymptotically optimal
communication rates, but are not known to be computationally efficient due to
the use of Uhlmann transformations for decoding. Could solving Uhlmann be
_necessary_ for these protocols? What would that mean for quantum cryptography
or quantum gravity? Despite the prevalence of Uhlmann transformations in
quantum information processing, these questions have not been studied
systematically yet.

The goal of this paper is to study these questions formally. Since Uhlmann
transformations are inherently quantum operations and cannot meaningfully be
phrased as decision or function problems, we need to extend the language of
complexity theory to _unitary synthesis problems_ , i.e. computational
problems that involve implementing a unitary operation on a quantum system in
an unknown state. The first main contribution of this paper is to provide a
general formal framework for reasoning about unitary complexity (Part I). This
involves extending many of the traditional notions of complexity theory, such
as reductions, complexity classes, complete problems, etc. to the setting of
unitary synthesis problems. Our second main contribution is to analyze the
complexity of the Uhlmann Transformation Problem within this framework (Part
II). As we will see, this will also naturally lead us to more general
statements about the relationships between unitary complexity classes.
Finally, we show how the Uhlmann transformation problem plays a central role
in connecting the complexity of many natural tasks in quantum information
processing (Part III).

####  1.1 A fully quantum complexity theory

The complexity of Uhlmann transformations deals with the hardness of
implementing a unitary _transformation_ , where the inputs and outputs of the
task are quantum states. Traditional complexity classes deal with tasks with
classical inputs and outputs (e.g., solving a decision problem or computing a
Boolean function). As a consequence, traditional complexity theory cannot
capture the complexity of Uhlmann transformations, or more generally of
implementing unitaries on unknown input states. To study the hardness of
problems with quantum inputs or outputs, we need a new framework.

The idea that the complexity of _inherently quantum_ problems cannot easily be
reduced to the complexity of classical problems has already been explored in
prior works [KA04, Aar16, ACQ22]. Indeed, the oracle separations mentioned
above [Kre21, KQST23] can be rephrased as oracle separations that demonstrate
that the complexity of some quantum cryptographic problems is independent of
the complexity of the decisional complexity classes $\mathsf{NP}$ or
$\mathsf{QMA}$.

Recently, Rosenthal and Yuen initiated the study of complexity classes for
_state synthesis_ and _unitary synthesis_ problems [RY22]. A state synthesis
problem is a sequence $(\rho_{x})_{x\in\\{0,1\\}^{*}}$ of quantum states. A
_state complexity class_ is a collection of state synthesis problems that
captures the computational resources needed to synthesize (i.e., generate) the
states. For example, [RY22] defined the class $\mathsf{statePSPACE}$ as the
set of all state sequences $(\rho_{x})_{x\in\\{0,1\\}^{*}}$ for which there is
a polynomial-space (but possibly exponential-time) quantum algorithm $A$ that,
on input $x$, outputs an approximation to the state $\rho_{x}$.

_Unitary complexity classes_ , which are the focus of this work, describe the
computational resources needed to perform state _transformations_. A unitary
synthesis problem is a sequence of unitary222In our formal definition of
unitary synthesis problems (see Section 3), the $U_{x}$’s are technically
partial isometries, which is a promise version of unitaries, but we gloss over
the distinction for now. operators $(U_{x})_{x\in\\{0,1\\}^{*}}$ and a unitary
complexity class is a collection of unitary synthesis problems. For example
the class $\mathsf{unitaryBQP}$ is the set of all sequences of unitary
operators $(U_{x})_{x\in\\{0,1\\}^{*}}$ where there is a polynomial-time
quantum algorithm $A$ that, given an _instance_ $x\in\\{0,1\\}^{*}$ and a
quantum system $\mathsf{B}$ as input, (approximately) applies $U_{x}$ to
system $\mathsf{B}$. As a simple example, any sequence of unitaries $(U_{x})$
where $x$ is simply (an explicit encoding of) a sequence of quantum gates that
implement the unitary is obviously in $\mathsf{unitaryBQP}$, since given $x$,
the algorithm $A$ can just execute the circuit specified by $x$ in time
polynomial in the length of $x$. On the other hand, $x$ could also specify a
unitary in a sequence in a more implicit way (e.g. by circuits for two quantum
states between which $U_{x}$ is meant to be the Uhlmann transformation), in
which case the sequence $(U_{x})_{x}$ could be harder to implement.

The reason we say that the algorithm $A$ is given a _system_ instead of a
_state_ is to emphasize that the state of the system is not known to the
algorithm ahead of time, and in fact the system may be part of a larger
entangled state. Thus the algorithm has to coherently apply the transformation
$U_{x}$ to the given system, maintaining any entanglement with an external
system. This makes unitary synthesis problems fundamentally different, and in
many cases harder to analyse, than state synthesis problems.

Traditional complexity classes like $\sf P$, $\sf NP$, and $\sf BQP$ have
proven to be powerful ways of organizing and comparing the difficulty of
different decision problems. In a similar way, state and unitary complexity
classes are useful for studying the complexity of quantum states and of
quantum state transformations. We can then ask about the existence of complete
problems, reductions, inclusions, separations, closure properties, and more.
Importantly, state and unitary complexity classes provide a useful language to
formulate questions and conjectures about the computational hardness of
inherently quantum problems. For example, we can ask whether
$\mathsf{unitaryPSPACE}$ is contained in
$\mathsf{unitaryBQP}^{\mathsf{PSPACE}}$ – in other words, can polynomial-
space-computable unitary transformations be also computed by a polynomial-time
quantum computer that is given oracle access to a $\mathsf{PSPACE}$ decision
oracle?333We remark that this question is open — this is related to the
“Unitary Synthesis Problem” raised by Aaronson and Kuperberg [AK07] – whereas
an analogue of this question in traditional complexity theory (e.g. whether
$\mathsf{BQPSPACE}$ is contained in $\mathsf{BQP}^{\mathsf{PSPACE}}$) has a
positive answer [Wat99].

###### Unitary synthesis problems, classes, and reductions.

We begin by giving general definitions for unitary synthesis problems and a
number of useful unitary complexity classes, e.g. $\mathsf{unitaryBQP}$ and
$\mathsf{unitaryPSPACE}$. We then define a notion of _reductions_ between
unitary synthesis problems. Roughly speaking, we say that a unitary synthesis
problem $\mathscr{U}=(U_{x})_{x}$ polynomial-time reduces to
$\mathscr{V}=(V_{x})_{x}$ if an efficient algorithm for implementing
$\mathscr{V}$ implies an efficient algorithm for implementing $\mathscr{U}$.

Next, we define _distributional_ unitary complexity classes that capture the
_average case complexity_ of solving a unitary synthesis problem. Here, the
unitary only needs to be implemented on an input state _randomly chosen_ from
some distribution $\mathcal{D}$ which is known ahead of time. The motivation
behind this notion of average case complexity is that it is equivalent to
implementing the unitary on one half of a larger entangled state $\ket{\psi}$.
This is natural in the context of entanglement transformation problems.

The notion of average case complexity turns out to be central to our paper:
nearly all of our results are about average-case unitary complexity classes
and the average-case complexity of the Uhlmann Transformation Problem. Thus
the unitary complexity classes we mainly deal with will be
$\mathsf{avgUnitaryBQP}$ and $\mathsf{avgUnitaryPSPACE}$, which informally
mean sequences of unitaries that can be implemented by time-efficient and
space-efficient quantum algorithms, respectively, and where the implementation
error is measured with respect to inputs drawn from a fixed distribution over
quantum states. We forgo a formal definition in this introduction and refer to
Section 3 for more details.

###### Interactive proofs for unitary synthesis.

We then explore models of _interactive proofs_ for unitary synthesis problems.
Roughly speaking, in an interactive proof for a unitary synthesis problem
$\mathscr{U}=(U_{x})_{x}$, a polynomial-time verifier receives an instance $x$
and a quantum system $\mathsf{B}$ as input, and interacts with an all-powerful
but untrusted prover to try to apply $U_{x}$ to system $\mathsf{B}$. As usual
in interactive proofs, the main challenge is that the verifier does not trust
the prover, so the protocol has to test whether the prover actually behaves as
intended. We formalize this with the complexity classes $\mathsf{unitaryQIP}$
and $\mathsf{avgUnitaryQIP}$, which capture unitary synthesis problem that can
be verifiably implemented in this interactive model. This generalizes the
interactive state synthesis model studied by [RY22, MY23].444The class
$\mathsf{unitaryQIP}$ was also briefly studied by Rosenthal and Yuen in
[RY22], but the model and class were not formally defined. The primary
difference between the state synthesis and unitary synthesis models is that in
the former, the verifier starts with a fixed input state (say, the all zeroes
state), while in the latter the verifier receives a quantum system
$\mathsf{B}$ in an unknown state that has to be transformed by $U_{x}$. We
refer to Section 4 for more details.

###### Zero-knowledge unitary synthesis.

In the context of interactive protocols, we also introduce a notion of _zero-
knowledge protocols_ for unitary synthesis problems. Roughly speaking, a
protocol is zero-knowledge if the interaction between the verifier and prover
can be efficiently reproduced by an algorithm (called the _simulator_) that
does not interact with the prover at all. This way, the verifier can be
thought of as having learned no additional knowledge from the interaction
aside from the fact that the task was solved. This model gives rise to the
unitary complexity class $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$,555The
“${\mathrm{HV}}$” modifier signifies that the zero-knowledge property is only
required to hold with respect to verifiers that honestly follow the protocol.
which is a unitary synthesis analogue of the decision classes $\mathsf{QSZK}$
and $\mathsf{SZK}$ in traditional complexity theory. Interestingly, for
reasons that we explain in more detail in Section 4.3, the average-case aspect
of $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ appears to be necessary to obtain a
nontrivial definition of zero-knowledge in the unitary synthesis setting.

Just like there is a zoo of traditional complexity classes [Aar23], we expect
that many unitary complexity classes can also be meaningfully defined and
explored. In this paper we focus on the ones that turn out to be tightly
related to the Uhlmann Transformation Problem. We discuss these relationships
next.

######  Remark 1.1.

For simplicity’s sake, in the introduction we present informal statements of
our results that gloss over some technical details that would otherwise
complicate the result statement. For example, we do not distinguish between
unitary synthesis problems and distributional versions of them, nor do we
distinguish between uniform and non-uniform unitary complexity classes. After
each informal result statement we point the reader to where the formal result
is stated and proved.

####  1.2 Structural results about the Uhlmann Transformation Problem

Equipped with the proper language to talk about unitary synthesis problems, we
now turn to the Uhlmann Transformation Problem. We define the unitary
synthesis problem Uhlmann to be the sequence $(U_{x})_{x\in\\{0,1\\}^{*}}$
where we interpret an instance $x$ as an explicit encoding (as a list of
gates) of a pair of quantum circuits $(C,D)$ such that $C$ and $D$, on the
all-zeroes input, output pure bipartite states $\ket{C},\ket{D}$ on the same
number of qubits, and $U_{x}$ is an associated Uhlmann transformation mapping
$\ket{C}$ to $\ket{D}$ by acting on a local system. Usually, we will assume
that $C$ and $D$ output $2n$ qubits (for some $n$ specified as part of $x$)
and the Uhlmann transformation acts on the last $n$ qubits. If $x$ does not
specify such a pair, then an algorithm implementing the unitary synthesis
problem is allowed to behave arbitrarily on such $x$; this is formally
captured by allowing partial isometries as part of unitary synthesis problems
in Definition 3.1.

Furthermore, for a parameter $0\leq\kappa\leq 1$ we define the problem
$\textsc{Uhlmann}_{\kappa}$, which is the same as Uhlmann, except that it is
restricted to instances corresponding to states $\ket{C},\ket{D}$ where the
fidelity between the reduced density matrices $\rho,\sigma$ of
$\ket{C},\ket{D}$ respectively on the first subsystem is at least $\kappa$;
recall by Uhlmann’s theorem that $\kappa$ lower bounds how much overlap
$\ket{C}$ can achieve with $\ket{D}$ by a local transformation. By definition,
$\textsc{Uhlmann}_{\kappa}$ instances are at least as hard as
$\textsc{Uhlmann}_{\kappa^{\prime}}$ instances when
$\kappa\leq\kappa^{\prime}$. The formal definitions of Uhlmann,
$\textsc{Uhlmann}_{\kappa}$, and their distributional versions can be found in
Section 5.

###### Zero-knowledge and the Uhlmann Transformation Problem.

We show that the Uhlmann Transformation Problem (with fidelity parameter
$\kappa=1-\epsilon$ for negligibly small $\epsilon$ as a function of the
length of the string specifying an instance $x$) _exactly characterizes_ the
complexity of the unitary complexity class
$\mathsf{avgUnitarySZK}_{\mathrm{HV}}$, which is the unitary synthesis version
of $\mathsf{QSZK}_{\mathrm{HV}}$ [Wat02].

######  Theorem 1.2 (Informal).

$\textsc{Uhlmann}_{1-\epsilon}$ for negligibly small $\epsilon$ is complete
for $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ under polynomial-time reductions.

This is formally stated and proved in Section 6.1. To show completeness we
have to prove two directions. The first direction is to show that if one can
efficiently solve $\textsc{Uhlmann}_{1-\epsilon}$ in the average case (meaning
that one can approximately map the input state $\ket{C}$ to $\ket{D}$ by
acting locally), then one can efficiently solve any other distributional
unitary synthesis problem in $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$. This uses
a characterization of quantum interactive protocols due to Kitaev and Watrous
[KW00].

The second direction is to show that $\textsc{Uhlmann}_{1-\epsilon}$ is in
$\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ by exhibiting an (honest-verifier)
zero-knowledge protocol to solve the Uhlmann Transformation Problem. Our
protocol is rather simple: in the average case setting, we assume that the
verifier receives the last $n$ qubits of the state $\ket{C}=C\ket{0^{2n}}$,
and the other half is inaccessible. Its goal is to transform, with the help of
a prover, the global state $\ket{C}$ to $\ket{D}$ by only acting on the last
$n$ qubits that it received as input. To this end, the verifier generates a
“test” copy of $\ket{C}$ on its own, which it can do because $C$ is a
polynomial-size circuit. The verifier then sends to the prover two registers
of $n$ qubits; one of them is the first half of the test copy and one of them
(call it $\mathsf{A}$) holds the “true” input state. The two registers are
randomly shuffled. The prover is supposed to apply the Uhlmann transformation
$U$ to both registers and send them back. The verifier checks whether the
“test” copy of $\ket{C}$ has been transformed to $\ket{D}$ by applying the
inverse circuit $D^{\dagger}$ to the test copy and checking if all qubits are
zero. If so, it accepts and outputs the register $\mathsf{A}$, otherwise the
verifier rejects.

If the prover is behaving as intended, then both the test copy and the “true”
copy of $\ket{C}$ are transformed to $\ket{D}$. Furthermore, the prover cannot
tell which of its two registers corresponds to the test copy, and thus if it
wants to pass the verification with high probability, it has to apply the
correct Uhlmann transformation on both registers. This shows that the protocol
satisfies the completeness and soundness properties of an interactive proof.
The zero-knowledge property is also straightforward: if both the verifier and
prover are acting according to the protocol, then before the verifier’s first
message to the prover, the reduced state of the verifier is
$\ket{C}\\!\\!\bra{C}\otimes\rho$ (where $\rho$ is the reduced density matrix
of $\ket{C}$), and at the end of the protocol, the verifier’s state is
$\ket{D}\\!\\!\bra{D}\otimes U\rho U^{\dagger}$. Both states can be produced
in polynomial time.

One may ask: if the simulator can efficiently compute the state $U\rho
U^{\dagger}$ without the help of the prover, does that mean the Uhlmann
transformation $U$ can be implemented in polynomial time? The answer is no,
since the simulator only has to prepare the appropriate reduced state (i.e.
essentially solve a state synthesis task), which is easy since the starting
and ending states of the protocol are efficiently computable; in particular,
$U\rho U^{\dagger}$ is (approximately) the reduced state of $\ket{D}$, which
is easy to prepare. In contrast, the verifier has to implement the Uhlmann
transformation on a _specific_ set of qubits that are entangled with a
_specific_ external register, i.e. it has to perform a state transformation
task that preserves coherence with the purifying register. This again
highlights the distinction between state and unitary synthesis tasks.

###### Hardness amplification for Uhlmann.

We also prove a _hardness amplification_ result for the Uhlmann Transformation
Problem. The unitary complexity classes we define can be parameterized by an
error parameter $\delta$. For example, $\mathsf{unitaryBQP}_{\delta}$ denotes
the set of unitary synthesis problems where the transformation can be
implemented up to error $\delta$ on all input states; when the error parameter
is not specified we assume that the transformation can be implemented with any
error that is an arbitrarily small inverse polynomial. It is clear that if
$\mathscr{U}\in\mathsf{unitaryBQP}_{\delta}$, then
$\mathscr{U}\in\mathsf{unitaryBQP}_{\eta}$ for all $\eta\geq\delta$ (i.e.,
problems cannot get any harder if we are allowed to incur larger error).

Although we do not expect Uhlmann to be solvable in polynomial time, we show
that _if_ Uhlmann transformations can generally be efficiently implemented
with large error (even with error approaching $1$), then they can be
efficiently implemented with arbitrarily small inverse polynomial error.
Written in terms of unitary classes, we have:

######  Theorem 1.3 (Informal).

Let $\epsilon$ be negligibly small. Then
$\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ if and only if
$\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}_{1-\xi}$ where
$\xi(n)=n^{-1/16}$. Here, $n$ refers to the number of qubits of the Uhlmann
instance.

This is formally stated and proved as Theorem 6.8. In other words, being able
to solve Uhlmann (with the guarantee that the fidelity between the reduced
states is negligibly close to $1$) with very large error is no easier (up to
polynomial factors) than solving it with very small error. We prove the more
interesting direction (that
$\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}_{1-\xi}$ implies that
$\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}$) as follows: given an instance
$(\ket{C},\ket{D})$ of Uhlmann for which it is hard to implement the
corresponding Uhlmann transformation $U$ with error $\delta$, we show that it
is hard to to implement the Uhlmann transformation $U^{\otimes k}$ for the
_$k$ -fold repetition_ $(\ket{C}^{\otimes k},\ket{D}^{\otimes k})$ even with
error $1-\frac{1}{\delta k^{2}}$. The proof uses ideas inspired by “quantum
rewinding” techniques from quantum cryptography [Wat06].

A natural question is whether one can prove a _strong_ hardness amplification
result, where one shows that hardness of an Uhlmann transformation $U$ implies
the hardness of implementing the repeated transformation $U^{\otimes k}$ with
error $1-\exp(-\Omega(k))$. Strong hardness amplification results are known in
classical complexity theory and cryptography [Raz98, Hai09, HPWP10]; we
conjecture that an analogous result holds for the Uhlmann Transformation
Problem.

######  Conjecture 1.4.

Let $\epsilon$ be negligibly small. Then
$\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ if and only if
$\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}_{1-\exp(-\Omega(n))}$.

Our hardness amplification result for the Uhlmann Transformation Problem
immediately implies hardness amplification for quantum commitments, which
answers an open question of Yan [Yan22]. We give more details when discussing
the applications to quantum cryptography later in this introduction and in
Section 8.

###### The succinct Uhlmann Transformation Problem.

We also define a _succinct_ version of the Uhlmann Transformation Problem
(denoted by SuccinctUhlmann), where the string $x$ encodes a pair
$(\hat{C},\hat{D})$ of _succinct descriptions_ of quantum circuits $C,D$. By
this we mean that $\hat{C}$ (resp. $\hat{D}$) is a classical circuit that,
given a number $i\in\mathbb{N}$ written in binary, outputs the $i$’th gate in
the quantum circuit $C$ (resp. $D$). Thus the circuits $C$, $D$ in general can
have _exponential_ depth (in the length of the instance string $x$) and
generate states $\ket{C},\ket{D}$ that are unlikely to be synthesizable in
polynomial time. Thus the task of synthesizing the Uhlmann transformation $U$
that maps $\ket{C}$ to a state with maximum overlap with $\ket{D}$,
intuitively, should be much harder than the non-succinct version. We confirm
this intuition with the following result:

######  Theorem 1.5 (Informal).

SuccinctUhlmann is complete for $\mathsf{avgUnitaryPSPACE}$ under polynomial-
time reductions.

This is formally stated and proved as Theorem 7.12. The class
$\mathsf{avgUnitaryPSPACE}$ corresponds to distributional unitary synthesis
problems that can be solved using a polynomial-space (but potentially
exponential-depth) quantum algorithm. The fact that
$\textsc{SuccinctUhlmann}\in\mathsf{avgUnitaryPSPACE}$ was already proved by
Metger and Yuen [MY23], who used this to show that optimal prover strategies
for quantum interactive proofs can be implemented in
$\mathsf{avgUnitaryPSPACE}$.666This was phrased in a different way in their
paper, as $\mathsf{avgUnitaryPSPACE}$ was not yet defined. The fact that
$\mathsf{avgUnitaryPSPACE}$ reduces to SuccinctUhlmann is because solving a
distributional unitary synthesis problem $(U_{x})_{x}$ in
$\mathsf{avgUnitaryPSPACE}$ is equivalent to applying a local unitary that
transforms an entangled state $\ket{\omega_{x}}$ representing the distribution
to $(\textnormal{id}\otimes U_{x})\ket{\omega_{x}}$. This is nothing but an
instance of the SuccinctUhlmann transformation problem. We refer to the proof
of Theorem 7.12 for details.

We show another completeness result for SuccinctUhlmann:

######  Theorem 1.6 (Informal).

SuccinctUhlmann is complete for $\mathsf{avgUnitaryQIP}$ under polynomial-time
reductions.

This is formally stated and proved as Theorem 7.6. Here, the class
$\mathsf{avgUnitaryQIP}$ is like $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$ except
there is no requirement that the protocol between the honest verifier and
prover can be efficiently simulated. The proof of starts similarly to the
proof of the $\mathsf{avgUnitarySZK}_{\mathrm{HV}}$-completeness of Uhlmann,
but requires additional ingredients, such as the state synthesis protocol of
[RY22] and the density matrix exponentiation algorithm of [LMR14]. Putting
together Theorems 1.5 and 1.6 we get the following unitary complexity analogue
of the $\mathsf{QIP}=\mathsf{PSPACE}$ theorem [JJUW11] and the
$\mathsf{stateQIP}=\mathsf{statePSPACE}$ theorem [RY22, MY23]:

######  Corollary 1.7.

$\mathsf{avgUnitaryQIP}=\mathsf{avgUnitaryPSPACE}$.

This partially answers an open question of [RY22, MY23], who asked whether
$\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ (although they did not formalize
this question to the same level as we do here). We resolve this question in
the average case, and leave it as an interesting open question to prove the
same statement for the worst-case complexity classes $\mathsf{unitaryPSPACE}$
and $\mathsf{unitaryQIP}$. The proof of the equivalence of these unitary
complexity classes via the Uhlmann Transformation Problem highlights the
problem’s usefulness and centrality.

We can also relate the traditional decision complexity class $\mathsf{PSPACE}$
to the unitary synthesis problem SuccinctUhlmann with the following theorem.

######  Theorem 1.8.

$\mathsf{PSPACE}\subseteq\mathsf{BQP}^{\textsc{SuccinctUhlmann}}$.

This is formally proved as Theorem 7.15. In other words, all languages in
$\mathsf{PSPACE}$ can be decided by a quantum polynomial time algorithm that
can query an oracle that solves SuccinctUhlmann. Since it is believed that
$\mathsf{PSPACE}\not\subseteq\mathsf{BQP}$, this gives evidence from
“traditional” complexity theory that SuccinctUhlmann is a very difficult
unitary synthesis problem. Our proof of this relies on the random self-
reducibility of $\mathsf{PSPACE}$-complete languages [FF93].

We note that it is an interesting question whether the “converse” direction
holds: can SuccinctUhlmann be synthesized in polynomial time given oracle
access to the decision class $\mathsf{PSPACE}$? We conjecture that the answer
is “no”, and that in general a given unitary complexity class is much harder
than its corresponding decision class.

####  1.3 Centrality of the Uhlmann Transformation Problem

We now relate the Uhlmann Transformation Problem to quantum information
processing tasks in a variety of areas: quantum cryptography, quantum Shannon
theory, and high energy physics. We show that the computational complexity of
a number of these tasks is in fact _equivalent_ to the hardness of Uhlmann.
For some other problems we show that they are efficiently reducible to Uhlmann
or SuccinctUhlmann. Although some of these connections have been already
observed in prior work, we believe that the framework of unitary complexity
theory formalizes and clarifies the relationships between these different
problems.

#####  1.3.1 Quantum cryptography applications

We begin by exploring connections between the Uhlmann Transformation Problem
and several concepts in quantum cryptography.

###### Quantum commitments.

A bit commitment scheme is a fundamental cryptographic primitive that allows
two parties (called a _sender_ and _receiver_) to engage in a two-phase
communication protocol with the following properties: in the first phase (the
“commit phase”), the sender sends a commitment (i.e. some string) to a bit $b$
to the receiver; the _hiding_ property of a bit commitment scheme ensures that
the receiver cannot decide the value of $b$ from this commitment string alone.
In the second phase (the “reveal phase”), the sender sends another string to
the receiver that allows the receiver to compute the value of $b$; the
_binding_ property of commitments ensures that the sender can only reveal the
correct value of $b$, i.e. if the sender sent a reveal string that was meant
to convince the receiver it had committed to a different value of $b$, the
receiver would detect this.

Commitment schemes — even quantum ones — require computational assumptions
[May97, LC98]; at least one of the hiding or binding properties must rely on
computational assumptions. In classical cryptography, commitment schemes can
be constructed from one-way functions [Nao03], but recent works suggest the
possibility of basing quantum commitment schemes on weaker, inherently quantum
assumptions such as the existence of pseudorandom states [Kre21, AQY22, MY22a,
KQST23] or EFI pairs [BCQ23].

In an in-depth study of the properties of quantum commitment schemes, Yan
[Yan22] suggested connecting the hardness of Uhlmann transformations to the
existence of quantum commitments. We formalize this connection within the
unitary complexity framework and show the following:

######  Theorem 1.9 (Informal).

If $\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$ for all negligible
$\epsilon$, then quantum commitments do not exist. On the other hand, if
$\textsc{Uhlmann}_{1-\epsilon}\not\in\mathsf{avgUnitaryBQP}$ for some
negligible $\epsilon$, and furthermore hard instances of
$\textsc{Uhlmann}_{1-\epsilon}$ can be uniformly and efficiently generated,
then quantum commitments with strong statistical hiding and weak computational
binding exist.

Here, _strong statistical hiding_ means that no adversary (even a
computationally unbounded one) can distinguish commitments to $b=0$ from
commitments to $b=1$ with more than negligible advantage, and _weak
computational binding_ means that no computationally bounded adversary can
swap the committed bit with fidelity greater than $1-1/p(\lambda)$ for some
polynomial $p(\lambda)$ in the security parameter. This theorem is formally
stated and proved as Theorem 8.10.

We also show that the proof of hardness amplification for the Uhlmann
Transformation Problem (Theorem 1.3) can be used to amplify the security of
the binding property of quantum commitments: roughly speaking, if there is a
commitment scheme where it is hard for a malicious sender to transform the
$0$-commitment to have fidelity more than $1-1/p(\lambda)$ with the
$1$-commitment for some polynomial $p(\lambda)$, then there exists another
commitment scheme where it is hard for an adversary to transform the
$0$-commitment to have more than $\frac{1}{q(\lambda)}$ overlap with the
$1$-commitment for all polynomials $q(\lambda)$. This answers an open question
of Yan [Yan22], who asked whether hardness amplification for commitments is
possible.

######  Theorem 1.10 (Informal).

Quantum commitments with strong statistical hiding and weak computational
binding exist if and only if quantum commitments with strong statistical
hiding and $1/q(\lambda)$-computational binding exist for all $q(\lambda)$.

This theorem is formally stated and proved as Theorem 8.8. Furthermore, since
we can generically perform _flavor switching_ of quantum commitments (i.e.
swap which security property holds statistically and which computationally)
[HMY23, GJMZ23, Yan22], both Theorems 1.9 and 1.10 can be extended to quantum
commitments with computational hiding and statistical binding.

Assuming 1.4 about strong amplification for the Uhlmann Transformation
Problem, we also obtain a stronger statement, which is that if
$\textsc{Uhlmann}_{1-\epsilon}\not\in\mathsf{avgUnitaryBQP}$ for some
negligibly small $\epsilon$ and hard instances can be uniformly and
efficiently generated, then quantum commitments with strong hiding and strong
binding properties exist (whereas Theorem 1.9 only guarantees commitments with
weak binding). These strong commitments are in turn equivalent to a number of
quantum cryptographic primitives, such as EFI pairs [BCQ23], oblivious
transfer [BCQ23], (secretly-verifiable and statistically-invertible) one-way
state generators [MY22], and secure quantum multi-party quantum computation
scheme for any classical functionality [BCQ23, AQY22].

###### Breaking one-way state generators.

We consider the cryptographic notion of _one-way state generators_ introduced
by Morimae and Yamakawa [MY22a], which can be seen as a quantum analogue of
one-way function: it efficiently maps a classical key $k$ to a quantum state
$\ket{\phi_{k}}$, but is hard to invert. We show the following relation
between a natural class of one-way state generators and Uhlmann (see Theorem
8.17 for the formal statement):

######  Theorem 1.11 (Informal).

A real-valued, clean-output one-way state generator is either information-
theoretically secure, or the task of cloning its output can be efficiently
reduced to $\textsc{Uhlmann}_{\kappa}$ for $\kappa=1/\mathrm{poly}(n)$.

Here, _real-valued_ means that the output state of the one-way state generator
is represented as a real vector. The _clean-output_ property means that the
one-way state generator, on input key $k$, only outputs $\ket{\phi_{k}}$ and
no other residual state depending on $k$. We argue in Section 8.2 that most
existing constructions of OWSGs are real-valued and clean-output.

Note that this theorem uses a regime where $\kappa\ll 1$. This marks our first
application of $\textsc{Uhlmann}_{\kappa}$ for small $\kappa$; most of the
applications in this paper are connected to $\textsc{Uhlmann}_{1-\epsilon}$
for a negligible function $\epsilon(n)$. The class $\textsc{Uhlmann}_{\kappa}$
for small $\kappa$ is at least as hard as $\textsc{Uhlmann}_{1-\epsilon}$, and
_a priori_ it could be harder.

###### Breaking falsifiable quantum cryptographic assumptions.

Finally, we consider the general notion of a _falsifiable quantum
cryptographic assumption_ , which can be seen as a quantum analogue of the
notion of a falsifiable assumption considered by Naor [Nao03] as well as
Gentry and Wichs [GW11]. Our notion of a falsifiable quantum cryptographic
assumption captures most cryptographic assumptions in both classical and
quantum cryptography. The definition resembles a regular $\mathsf{QIP}$
protocol, albeit in a cryptographic setting by means of a security experiment
between an adversary and a challenger. Our main result of this section is the
following statement, which provides a generic upper bound on the complexity of
breaking falsifiable quantum cryptographic assumptions:

######  Theorem 1.12 (Informal).

A quantum cryptographic assumption is either information-theoretically secure,
or the task of breaking security reduces to SuccinctUhlmann.

This theorem is formally stated and proved as Theorem 8.20. It shows that any
reasonable definition of security in quantum cryptography (which can be
phrased in terms of an interactive _security game_ between an adversary and a
challenger) either amounts to _information-theoretic_ security (and thus
requires no computational assumptions) or (by Theorem 1.5) can be broken in
$\mathsf{avgUnitaryPSPACE}$.

#####  1.3.2 Quantum Shannon theory applications

Quantum Shannon theory studies the achievability and limits of quantum
communication tasks. It has become a mature subject with many foundational
results that characterize the optimal ways to compress quantum information,
transmit quantum information over noisy channels, and transform entangled
states in a distributed fashion with limited communication. For comprehensive
references on quantum Shannon theory we refer the reader to [Wil13, KW20,
Ren22].

We study the computational complexity of some fundamental tasks in quantum
Shannon theory, namely noisy channel decoding and compression of quantum
states.

###### Decodable channel problem.

Consider a quantum channel $\mathcal{N}$ that maps a register $\mathsf{A}$ to
a register $\mathsf{B}$. Suppose that the channel $\mathcal{N}$ is _decodable_
, meaning that it is possible to information-theoretically (approximately)
recover the information sent through the channel; i.e., there exists a
decoding channel $\mathcal{D}$ mapping register $\mathsf{B}$ back to register
$\mathsf{A}$ such that
$\mathcal{D}_{\mathsf{B}\to\mathsf{A}^{\prime}}\Big{(}\mathcal{N}_{\mathsf{A}\to\mathsf{B}}(\Phi_{\mathsf{AR}})\Big{)}\approx\Phi_{\mathsf{A}^{\prime}\mathsf{R}}$,
where $\ket{\Phi}_{\mathsf{AR}}$ is the maximally entangled state. Note that
the register $\mathsf{R}$ is not touched.

Important examples of decodable channels come from coding schemes for noisy
quantum channels: suppose $\mathcal{K}$ is a noisy quantum channel that has
capacity $C$ (meaning it is possible to (asymptotically) transmit $C$ qubits
through $\mathcal{K}$). Let $\mathcal{E}$ denote a channel that takes $C$
qubits and maps it to an input to $\mathcal{K}$. For example, we can think of
$\mathcal{E}$ as an encoder for a quantum error-correcting code. If
$\mathcal{E}$ is a good encoding map, the composite channel
$\mathcal{N}:\rho\mapsto\mathcal{K}(\mathcal{E}(\rho))$ is decodable.

We define the _Decodable Channel Problem_ : given as input a circuit
description of a channel $\mathcal{N}$ that maps register $\mathsf{A}$ to
register $\mathsf{B}$ and furthermore is promised to be decodable, and given
the register $\mathsf{B}$ of the state
$(\mathcal{N}\otimes\textnormal{id})(\Phi_{\mathsf{AR}})$, decode and output a
register $\mathsf{A}^{\prime}\equiv A$ such that the final joint state of
$\mathsf{A}^{\prime}\mathsf{R}$ is close to $\ket{\Phi}$. Although it is
information-theoretically possible to decode the output of $\mathcal{N}$, it
may be computationally intractable to do so. The following theorem shows that
the Decodable Channel Problem is equivalent to the Uhlmann Transformation
Problem in terms of computational hardness.

######  Theorem 1.13 (Informal).

The Decodable Channel Problem can be solved in polynomial-time if and only if
$\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}$.

This theorem is formally stated and proved as Theorem 9.6; since we do not
expect that $\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}$, this suggests that
the Decodable Channel Problem is hard to solve in general. The main idea
behind the upper bound (Decodable Channel Problem is easy if Uhlmann is easy)
is that a channel $\mathcal{N}$ is decodable if and only if the output of the
_complementary channel_ 777The output of the complementary channel can be
thought of as the qubits that a purification (formally, a Stinepring dilation)
of the channel $\mathcal{N}$ discards to the environment. $\mathcal{N}^{c}$,
when given register $\mathsf{A}$ of the maximally entangled state
$\ket{\Phi}_{\mathsf{AR}}$, is approximately unentangled with register
$\mathsf{R}$. Thus by Uhlmann’s theorem there exists an Uhlmann transformation
acting on the output of the channel $\mathcal{N}$ that recovers the maximally
entangled state. If $\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}$, then this
transformation can be performed efficiently.

The proof of the lower bound (Decodable Channel Problem is hard if Uhlmann is
hard) draws inspiration from quantum commitments. As discussed earlier, the
hardness of Uhlmann essentially implies the existence of strong statistical
hiding and weak computational binding quantum commitments. From this, we can
construct a hard instance of the Decodable Channel Problem: consider a channel
$\mathcal{N}$ that takes as input a single bit $\ket{b}$, and then outputs the
commitment register of the commitment to bit $b$ (and discards the reveal
register). The ability to decode this “commitment channel” implies the ability
to break the hiding property of the underlying commitment scheme, and
therefore decoding must be computationally hard.

###### Compression of quantum information.

Another fundamental task in information theory – both classical and quantum –
is compression of data. Shannon’s source coding theorem shows that the Shannon
entropy of a random variable $X$ characterizes the rate at which many
independent copies of $X$ can be compressed [Sha48]. Similarly, Schumacher
proved that the von Neumann entropy of a density matrix $\rho$ characterizes
the rate at which many independent copies of $\rho$ can be (coherently)
compressed [Sch95].

We consider the _one-shot_ version of the information compression task, where
one is given just one copy of a density matrix $\rho$ (rather than many
copies) and the goal is to compress it to as few qubits as possible while
being able to recover the original state within some error. In the one-shot
setting the von Neumann entropy no longer characterizes the optimal
compression of $\rho$; instead this is given by a one-shot entropic quantity
known as the _smoothed max-entropy_ [Tom13]. What is the computational effort
required to perform near-optimal one-shot compression of quantum states? Our
next result gives upper and lower bounds for the computational complexity of
this task.

######  Theorem 1.14 (Informal).

Quantum states can be optimally compressed to their smoothed max entropy in
polynomial-time if $\textsc{Uhlmann}_{1-\epsilon}\in\mathsf{avgUnitaryBQP}$
for some negligible $\epsilon$. Furthermore, if stretch pseudorandom state
generators exist, then optimal compression of quantum states cannot be done in
polynomial time.

This theorem is formally stated and proved as Theorems 9.15 and 9.17. The
upper bound (i.e., compression is easy if Uhlmann is easy) is proved using a
powerful technique in quantum information theory known as _decoupling_
[Dup10]. The hardness result for compression is proved using a variant of
_pseudorandom states_ , a cryptographic primitive that is a quantum analogue
of pseudorandom generators [JLS18].

#####  1.3.3 Theoretical physics applications

In recent years, quantum information has provided a new lens on long-standing
questions in theoretical physics. Perhaps the most important question in this
area is whether quantum mechanics and general relativity can be reconciled.
Attempts to find a unified theory have led to apparent paradoxes, particularly
in the context of finding a consistent quantum mechanical description of black
holes [Pre92, AMPS13]. Recently, computational complexity has emerged as a way
to explore – and possibly resolve – these paradoxes [HH13, BRS+16, Sus16,
BFV19, YE23]. We consider applications of the Uhlmann Transformation Problem
to two computational tasks arising from this research.

###### Black hole radiation decoding.

First, we consider the so-called Harlow-Hayden _black hole radiation decoding
task_ [HH13], which is defined as follows. We are given as input a circuit
description of a tripartite state $\ket{\psi}_{\mathsf{BHR}}$ that represents
the global pure state of a single qubit (register $\mathsf{B}$), the interior
of a black hole (register $\mathsf{H}$), and the Hawking radiation that has
been emitted by the black hole (register $\mathsf{R}$). Moreover, we are
promised that it is possible to _decode_ from the emitted radiation
$\mathsf{R}$ a single qubit $\mathsf{A}$ that forms a maximally entangled
state $\ket{\mathrm{EPR}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11})$ with register
$\mathsf{B}$. The task is to perform this decoding when given register
$\mathsf{R}$ of a system in the state $\ket{\psi}$.

This task is motivated by a thought experiment proposed by Almheiri, Marolf,
Polchinski, and Sully [AMPS13], where Alice drops half of an EPR pair into a
black hole and waits for it to be radiated back out. If she can perform the
radiation decoding task, then Alice could jump into the black hole with the
recovered EPR pair and find the original qubit that was dumped in. However
that should _also_ be maximally entangled with the EPR pair, violating the
monogamy of entanglement principle. Harlow and Hayden [HH13] proposed a way to
sidestep the paradox by arguing that the decoding task is computationally
intractable assuming that $\mathsf{SZK}\not\subseteq\mathsf{BQP}$.

While the hardness of the black hole radiation decoding task can be based on
plausible hardness assumptions in traditional complexity theory, precisely
characterizing the task’s complexity appears to require the notions of a fully
quantum complexity theory. Brakerski recently showed that this task is
equivalent to breaking the security of a quantum cryptographic primitive known
as EFI pairs [Bra23]. We reformulate this equivalence in our unitary
complexity framework:

######  Theorem 1.15 (Informal).

Black-hole radiation decoding can be solved in polynomial-time if and only if
$\textsc{Uhlmann}\in\mathsf{avgUnitaryBQP}$.

This theorem is formally stated and proved as Theorem 10.3. We prove this by
showing that the black hole radiation decoding task is equivalent to the
Decodable Channel Problem, which, as we explained above, is equivalent to the
Uhlmann Transformation Problem.

###### Interference detection.

Finally, we consider the complexity of detecting interference between
orthogonal states. Here, we revisit recent work by Aaronson, Atia, and
Susskind [AAS20], who proved the following (sometimes called the _swapping-
distinguishing equivalence_): for two orthogonal states $\ket{\psi}$ and
$\ket{\varphi}$, if one can distinguish $(\ket{\psi}+\ket{\varphi})/\sqrt{2}$
from $(\ket{\psi}-\ket{\varphi})/\sqrt{2}$, then one can also _swap_ between
$\ket{\psi}$ and $\ket{\varphi}$, and vice versa. One of the motivations for
considering this problem comes from the field of quantum gravity, where it is
related to the task of physically detecting interference between
superpositions of spacetime geometries in the AdS/CFT correspondence [AAS20].
The equivalence between swapping and distinguishing has also recently been
used for flavor conversion of quantum bit commitment schemes, as well as to
construct public-key encryption from cryptographic non-abelian group actions
[HMY23]. We give the following upper bound on the complexity of
InterferenceDetection between orthogonal $\mathsf{statePSPACE}$ states
(formally defined in Definition 10.6):

######  Theorem 1.16 (Informal).

InterferenceDetection between orthogonal $\mathsf{statePSPACE}$ states
polynomial-time reduces to SuccinctUhlmann.

This theorem is formally stated and proved as Theorem 10.8. The proof of the
theorem uses a simple circuit transformation which allows one to perform a
_controlled_ Uhlmann unitary with a single call to a SuccinctUhlmann oracle—a
trick that may be of independent interest.

####  1.4 Summary and future directions

Computational tasks with quantum inputs and/or outputs are ubiquitous
throughout quantum computing and quantum information theory. The traditional
framework of complexity theory, which is focused on computational tasks with
classical inputs and outputs, cannot naturally capture the complexity of these
“fully quantum” tasks.

In this paper we introduce a framework to reason about the computational
complexity of unitary synthesis problems. We then use this framework to study
Uhlmann’s theorem through an algorithmic lens, i.e. to study the complexity of
Uhlmann transformations. We prove that variants of the Uhlmann Transformation
Problem are complete for some unitary complexity classes, and then explore
relationships between the Uhlmann Transformation Problem and a myriad of
computational tasks in quantum cryptography, quantum Shannon theory, and high
energy physics.

The study of the complexity of state transformation tasks is a very new field
and we hope that our formal framework of unitary complexity theory and our
findings about the Uhlmann Transformation Problem lay the foundations for a
rich theory of the complexity of “fully quantum” problems. A lot of questions
in this direction are completely unexplored. Throughout this paper, we have
included many concrete open problems, which we hope will spark future research
in this new direction in complexity theory. Additionally, our work suggests
some high-level, open-ended future directions to explore:

###### Populating the zoo.

An important source of the richness of computational complexity theory is the
variety of computational problems that are studied. For example, the class
$\mathsf{NP}$ is so interesting because it contains many complete problems
that are naturally studied across the sciences [Pap97], and the theory of
$\mathsf{NP}$-completeness gives a unified way to relate them to each other.

Similarly, a fully quantum complexity theory should have its own zoo of
problems drawn from a diverse range of areas. We have already shown that core
computational problems in quantum cryptography, quantum Shannon theory, and
high energy physics can be related to each other through the language of
unitary complexity theory. What are other natural problems in, say, quantum
error-correction, quantum metrology, quantum chemistry, or condensed matter
physics, and what can we say about their computational complexity?

###### The crypto angle.

Complexity and cryptography are intimately intertwined. Operational tasks in
cryptography have motivated models and concepts that have proved indispensible
in complexity theory (such as pseudorandomness and zero-knowledge proofs), and
conversely complexity theory has provided a rigorous theoretical foundation to
study cryptographic hardness assumptions.

We believe that there can be a similarly symbiotic relationship between
quantum cryptography and a fully quantum complexity theory. Recent quantum
cryptographic primitives (such as quantum pseudorandom states [JLS18] and one-
way state generators [MY22a]) and new protocols (such as quantum copy-
protection [Aar09, CMP20] and certified deletion [BI20]) are unique to the
quantum setting, and the relationships between them are barely understood. For
example, an outstanding question is whether there is a meaningful _minimal
hardness assumption_ in quantum cryptography, just like one-way functions are
in classical cryptography.

Can a fully quantum complexity theory help answer this question about minimal
quantum cryptographic assumptions, or at least provide some guidance? For
example, there are many beautiful connections between one-way functions,
average-case complexity, and Kolomogorov complexity [IL89, Imp95, LP20]. Do
analogous results hold in the fully quantum setting?

###### The learning theory angle.

Quantum learning theory has also seen rapid development, particularly on the
topic of quantum state learning [Aar07, HKP20, BO21, AA23]. Learning quantum
states or quantum processes can most naturally be formulated as tasks with
quantum inputs. Traditionally these tasks have been studied in the
information-theoretic setting, where sample complexity is usually the main
measure of interest. However we can also study the computational difficulty of
learning quantum objects. What does a complexity theory of quantum learning
look like?

###### Traditional versus fully quantum complexity theory.

While traditional complexity theory appears to have difficulty reasoning about
fully quantum tasks, can we obtain _formal_ evidence that the two theories
are, in a sense, independent of each other? For example, can we show that
$\mathsf{P}=\mathsf{PSPACE}$ does not imply
$\mathsf{unitaryBQP}=\mathsf{unitaryPSPACE}$? One would likely have to show
this in a _relativized_ setting, i.e., exhibit an oracle $O$ relative to which
$\mathsf{P}^{O}=\mathsf{PSPACE}^{O}$ but
$\mathsf{unitaryBQP}^{O}\neq\mathsf{unitaryPSPACE}^{O}$. Such a result would
give compelling evidence that the reasons for the hardness of unitary
transformations are intrinsically different than the reasons for the hardness
of a Boolean function. There are a few works that have made some initial steps
towards this direction [Kre21, INN+22, KQST23]. More generally, what are other
ways of separating traditional from fully quantum complexity theory?

#### Guide for readers

Although the paper is rather long, the material is organized in a way that
supports random-access reading – depending on your interests, it is not
necessary to read Section $X$ before reading Section $X+1$. All sections
depend on the basic definitions of unitary complexity theory (Section 3) and
the basic definitions of the Uhlmann Transformation Problem (Section 5). From
then on, it’s choose-your-own-adventure. If you are interested in:

  * •

Structural results about the complexity of Uhlmann. Read Sections 4, 6 and 7.

  * •

Quantum cryptography. Read Section 8. It may be helpful to review the
definitions of quantum interactive protocols (Section 4) and the hardness
amplification result (Section 6.2).

  * •

Quantum Shannon theory. Read Section 9. It may be helpful to read the section
on quantum commitments (Section 8.1).

  * •

Quantum gravity. Read Section 10. It may be helpful to read the section on the
Decodable Channel Problem (Section 9.1).

#### Acknowledgments

We thank Anurag Anshu, Lijie Chen, Andrea Coladangelo, Sam Gunn, Yunchao Liu,
Joe Renes, and Renato Renner for helpful discussions. We thank Fred Dupuis for
his help with understanding the decoupling results in his thesis. JB and HY
are supported by AFOSR award FA9550-21-1-0040, NSF CAREER award CCF-2144219,
and the Sloan Foundation. TM acknowledges support from SNSF Project Grant No.
200021_188541 and AFOSR-Grant No. FA9550-19-1-0202. AP is partially supported
by AFOSR YIP (award number FA9550-16-1-0495), the Institute for Quantum
Information and Matter (an NSF Physics Frontiers Center; NSF Grant
PHY-1733907) and by a grant from the Simons Foundation (828076, TV). LQ is
supported by DARPA under Agreement No. HR00112020023. We thank the Simons
Institute for the Theory of Computing, where some of this work was conducted.

###  2 Preliminaries

####  2.1 Notation

For a bit string $x\in\\{0,1\\}^{*}$, we denote by $|x|$ its length (not its
Hamming weight). When $x$ describes an instance of a computational problem, we
will often use $n=|x|$ to denote its size.

A function $\delta:\mathbb{N}\to[0,1]$ is an _inverse polynomial_ if
$\delta(n)\leq 1/p(n)$ for all sufficiently large $n$. A function
$\epsilon:\mathbb{N}\to[0,1]$ is _negligible_ if for every polynomial $p(n)$,
for all sufficiently large $n$ we have $\epsilon(n)\leq 1/p(n)$.

A _register_ $\mathsf{R}$ is a named finite-dimensional complex Hilbert space.
If $\mathsf{A},\mathsf{B},\mathsf{C}$ are registers, for example, then the
concatenation $\mathsf{A}\mathsf{B}\mathsf{C}$ denotes the tensor product of
the associated Hilbert spaces. We abbreviate the tensor product state
$\ket{0}^{\otimes n}$ as $\ket{0^{n}}$. For a linear transformation $L$ and
register $\mathsf{R}$, we write $L_{\mathsf{R}}$ to indicate that $L$ acts on
$\mathsf{R}$, and similarly we write $\rho_{\mathsf{R}}$ to indicate that a
state $\rho$ is in the register $\mathsf{R}$. We write $\mathrm{Tr}(\cdot)$ to
denote trace, and $\mathrm{Tr}_{\mathsf{R}}(\cdot)$ to denote the partial
trace over a register $\mathsf{R}$.

We denote the set of linear transformations on $\mathsf{R}$ by
$\mathrm{L}(\mathsf{R})$, and linear transformations from $\mathsf{R}$ to
another register $\mathsf{S}$ by $\mathrm{L}(\mathsf{R},\mathsf{S})$. We
denote the set of positive semidefinite operators on a register $\mathsf{R}$
by $\operatorname{Pos}(\mathsf{R})$. The set of density matrices on
$\mathsf{R}$ is denotes $\textnormal{S}(\mathsf{R})$. For a pure state
$\ket{\varphi}$, we write $\varphi$ to denote the density matrix
$\ket{\varphi}\\!\\!\bra{\varphi}$. We denote the identity transformation by
id. For an operator $X\in\mathrm{L}(R)$, we define $\|X\|_{\infty}$ to be its
operator norm, and $\|X\|_{1}=\mathrm{Tr}(|X|)$ to denote its trace norm,
where $|X|=\sqrt{X^{\dagger}X}$. We write
$\mathrm{td}(\rho,\sigma)=\frac{1}{2}\|\rho-\sigma\|_{1}$ to denote the trace
distance between two density matrices $\rho,\sigma$, and
$\mathrm{F}(\rho,\sigma)=\|\sqrt{\rho}\sqrt{\sigma}\|_{1}^{2}$ for the
fidelity between $\rho,\sigma$.888We note that in the literature there are two
versions of fidelity that are commonly used; here we use the _squared_ version
of it. Throughout the paper we frequently invoke the following relationship
between fidelity and trace distance:

######  Proposition 2.1 (Fuchs-van de Graaf inequalities).

For all density matrices $\rho,\sigma$ acting on the same space, we have that

$1-\sqrt{\mathrm{F}(\rho,\sigma)}\leq\mathrm{td}(\rho,\sigma)\leq\sqrt{1-\mathrm{F}(\rho,\sigma)}\,.$

A _quantum channel_ from register $\mathsf{A}$ to $\mathsf{B}$ is a completely
positive trace-preserving (CPTP) map from $\mathrm{L}(\mathsf{A})$ to
$\mathrm{L}(\mathsf{B})$. For simplicity, we often write
$\mathcal{N}:\mathsf{A}\to\mathsf{B}$ instead of
$\mathcal{N}:\mathrm{L}(\mathsf{A})\to\mathrm{L}(\mathsf{B})$ when it is clear
that $\mathcal{N}$ is a channel. We denote the set of quantum channels as
$\textnormal{CPTP}(\mathsf{A},\mathsf{B})$. We also call a channel a
_superoperator_. For a channel $\Phi$, we write
$\operatorname{\textnormal{supp}}(\Phi)$ to denote the number of qubits it
takes as input. We call a channel unitary (isometric) if it conjugates its
input state with a unitary (isometry). The diamond norm of a channel
$\Phi\in\textnormal{CPTP}(\mathsf{A},\mathsf{B})$ is defined as
$\|\Phi\|_{\diamond}=\max_{\rho}\|(\Phi\otimes\textnormal{id}_{\mathsf{C}})(\rho)\|_{1}$
where the maximization is over all density matrices
$\rho\in\textnormal{S}(\mathsf{A}\otimes\mathsf{C})$ where $\mathsf{C}$ is an
arbitrary register.

Another important type of quantum operation that can be performed on a quantum
state is a measurement. In general a quantum measurement is described by a
finite set of positive semidefinite matrices $\mathcal{M}=\\{M_{i}\\}_{i}$
satisfying $\sum_{i}M_{i}=\textnormal{id}$. Performing a measurement on a
state $\rho$ results in an _output_ $i$, where each $i$ occurs with
probability $\mathrm{Tr}[M_{i}\rho]$, and conditioned on the outcome being
$i$, the resulting state is

$\rho|_{M_{i}}=\frac{\sqrt{M_{i}}\rho\sqrt{M_{i}}}{\mathrm{Tr}(M_{i}\rho)}\,.$
(2.1)

The gentle measurement lemma is an important property about quantum
measurements that connects the trace distance between a state and its post-
measurement state to the probability that the measurement accepts.

######  Proposition 2.2 (Gentle Measurement lemma).

Let $\rho$ be a density matrix and $\Lambda$ be a positive semidefinite
hermitian matrix. If $\mathrm{Tr}[\Lambda\rho]\geq 1-\epsilon$, then
$\mathrm{F}(\rho,\rho|_{\Lambda})\geq 1-\epsilon$ and
$\left\lVert\rho-\rho|_{\Lambda}\right\rVert_{1}\leq 2\sqrt{\epsilon}$.

A proof of this can be found in, e.g., [Wil13, Lemma 9.4.1].

####  2.2 Partial isometries and channel completions

Usually, operations on a quantum state can be described by a unitary matrix,
an isometry (if new qubits are introduced), or more generally a quantum
channel (if one allows incoherent operations such as measuring or discarding
qubits). However, we will find it useful to consider operations whose action
is only defined on a certain subspace; outside of this “allowed subspace” of
input states, we do not want to make a statement about how the operation
changes a quantum state. Such operations can be described by partial
isometries.

######  Definition 2.3 (Partial isometry).

A linear map $U\in\mathrm{L}(\mathsf{A},\mathsf{B})$ is called a partial
isometry if there exists a projector $\Pi\in\mathrm{L}(A)$ and an isometry
$\tilde{U}\in\mathrm{L}(A,B)$ such that $U=\tilde{U}\Pi$. We call the image of
the projector $\Pi$ the _support_ of the partial isometry $U$.

Of course in practice we cannot implement a partial isometry because it is not
a trace-preserving operation: states in the orthogonal complement of the
support are mapped to the 0-vector. We therefore define a _channel completion_
of a partial isometry as any quantum channel that behaves like the partial
isometry on its support, and can behave arbitrarily on the orthogonal
complement of the support.

######  Definition 2.4 (Channel completion).

Let $U\in\mathrm{L}(\mathsf{A},\mathsf{B})$ be a partial isometry. A channel
completion of $U$ is a quantum channel
$\Phi\in\textnormal{CPTP}(\mathsf{A},\mathsf{B})$ such that for any input
state $\rho\in\textnormal{S}(\mathsf{A})$,

$\displaystyle\Phi(\Pi\rho\Pi)=U\Pi\rho\Pi U^{\dagger}\,,$

where $\Pi\in\mathrm{L}(\mathsf{A})$ is the projector onto the support of $U$.
If $\Phi$ is a unitary or isometric channel, we also call this a unitary or
isometric completion of the partial isometry.

####  2.3 Quantum circuits

For convenience we assume that all quantum circuits use gates from the
universal gate set $\\{H,\mathit{CNOT},T\\}$ [NC10, Chapter 4] (although our
results hold for any universal gate set consisting of gates with algebraic
entries). A _unitary quantum circuit_ is one that consists only of gates from
this gate set. A _general quantum circuit_ is a quantum circuit that can
additionally have non-unitary gates that (a) introduce new qubits initialized
in the zero state, (b) trace them out, or (c) measure them in the standard
basis. We say that a general quantum circuit uses space $s$ if the total
number of qubits involved at any time step of the computation is at most $s$.
The description of a general quantum circuit is a sequence of gates (unitary
or non-unitary) along with a specification of which qubits they act on. A
general quantum circuit $C$ implements a quantum channel; we will abuse
notation slightly and also use $C$ to denote the channel. For a unitary
quantum circuit $C$ we will write $\ket{C}$ to denote the state $C\ket{0\dots
0}$.

######  Definition 2.5 (Polynomial size and space circuit families).

We say that $(C_{x})_{x\in\\{0,1\\}^{*}}$ is a family of _polynomial-size
general quantum circuits_ if there exists a polynomial $p$ such that $C_{x}$
has size (i.e. number of gates) at most $p(|x|)$. We say that
$(C_{x})_{x\in\\{0,1\\}^{*}}$ is a family of _polynomial-space general quantum
circuits_ if there exists a polynomial $p$ such that $C_{x}$ uses at most
$p(|x|)$ space.

######  Definition 2.6 (Uniform circuit families).

A family of general quantum circuits $(C_{x})_{x\in\\{0,1\\}^{*}}$ is called
_time-uniform_ (or simply _uniform_) if $(C_{x})_{x\in\\{0,1\\}^{*}}$ is
polynomial-size and there exists a classical polynomial-time Turing machine
that on input $x$ outputs the description of $C_{x}$. Similarly, a family of
general quantum circuits $(C_{x})_{x\in\\{0,1\\}^{*}}$ is called _space-
uniform_ if $(C_{x})_{x\in\\{0,1\\}^{*}}$ is polynomial-space and there exists
a classical polynomial-space Turing machine that on input $(x,i)$ outputs the
$i$’th gate of $C_{x}$. For brevity, we also call a time-uniform (resp. space-
uniform) family of quantum circuits a _polynomial time (resp. polynomial
space) quantum algorithm_.

######  Definition 2.7 (Unitary purification of a general quantum circuit).

A _unitary purification_ (or _dilation_) of a general quantum circuit $C$ is a
unitary circuit $\tilde{C}$ formed by performing all measurements in $C$
coherently (with the help of additional ancillas) and not tracing out any
qubits.

The following proposition relates a general quantum circuit to its unitary
purification; it follows directly from the definition of the unitary
purification. This proposition also demonstrates that the unitary purification
$\tilde{C}$ of a general quantum circuit $C$ is a specific _Stinespring
dilation_ of the quantum channel corresponding to $C$.

######  Proposition 2.8.

Let $C$ be a size-$m$ general quantum circuit acting on $n$ qubits, and let
$\tilde{C}$ be its unitary purification where register $\mathsf{R}$ denote all
the qubits that are traced out in the original circuit $C$ as well as the
ancilla qubits introduced for the purification. Then for all states $\rho$,

$C(\rho)=\mathrm{Tr}_{\mathsf{R}}(\tilde{C}\,\rho\tilde{C}^{\dagger})\,.$

Furthermore, $\tilde{C}$ acts on at most $n+m$ qubits and has size at most
$m$.

####  2.4 Quantum state complexity classes

Here we present the definitions of some state complexity classes that were
introduced in [RY22]. Intuitively, they are classes of sequences of quantum
states that require certain resources to be synthesized (e.g., polynomial time
or space).

######  Definition 2.9 ($\mathsf{stateBQP}$, $\mathsf{statePSPACE}$).

Let $\delta:\mathbb{N}\to[0,1]$ be a function. Then
$\mathsf{stateBQP}_{\delta}$ (resp. $\mathsf{statePSPACE}_{\delta}$) is the
class of all sequences of density matrices $(\rho_{x})_{x\in\\{0,1\\}^{*}}$
such that each $\rho_{x}$ is a state on $\mathrm{poly}(|x|)$ qubits, and there
exists a time-uniform (resp. space-uniform) family of general quantum circuits
$(C_{x})_{x\in\\{0,1\\}^{*}}$ such that for all $x\in\\{0,1\\}^{*}$ with
sufficiently large length $|x|$, the circuit $C_{x}$ takes no inputs and
$C_{x}$ outputs a density matrix $\sigma_{x}$ such that

$\mathrm{td}(\sigma_{x},\rho_{x})\leq\delta(|x|)\,.$

We define

$\mathsf{stateBQP}=\bigcap_{q}\mathsf{stateBQP}_{1/q(n)}\quad\;\textnormal{~{}and~{}}\;\quad\mathsf{statePSPACE}=\bigcap_{q}\mathsf{statePSPACE}_{1/q(n)}$

where the intersection is over all polynomials $q:\mathbb{N}\to\mathbb{R}$.

##  Part I Unitary Complexity Theory

###  3 Unitary Synthesis Problems and Unitary Complexity Classes

To be able to make formal statements about the complexity of quantum tasks, we
present a framework for unitary complexity theory: we define unitary synthesis
problems, algorithms for implementing them, unitary complexity classes, and
reductions between unitary synthesis problems.

####  3.1 Unitary synthesis problems

In traditional complexity theory, decision problems are formalized as
_languages_ , which are sets of binary strings. The analogue in our framework
is the following formalization of unitary synthesis problems.

######  Definition 3.1 (Unitary synthesis problem).

A _unitary synthesis problem_ is a sequence
$\mathscr{U}=(U_{x})_{x\in\\{0,1\\}^{*}}$ of partial isometries.999We note
that while unitary synthesis problems are not necessarily sequences of
unitaries, we believe that it is a better name than “partial isometry
synthesis problem”.

One should think of $x\in\\{0,1\\}^{*}$ as an encoding of the particular
partial isometry in the sequence $\mathscr{U}$. The precise form of this
encoding can differ between unitary synthesis problems. Some examples of
encodings include: $x$ describes a polynomial-length sequence of quantum
gates; or $x$ describes a classical circuit that, on input $i$, outputs the
$i$-th gate of a (potentially exponentially long) quantum circuit implementing
a unitary. We call the latter a _succinct description_ of the unitary.

We note that Definition 3.1 considers partial isometries, not only unitaries
(which are of course the special case of partial isometries for which the
projector in Definition 2.3 is $\Pi_{x}=\textnormal{id}$). A partial isometry
is only required to be unitary on some subspace, and does not specify any
action on the orthogonal complement of the subspace. This is analogous to the
idea of a “promise” on the inputs in standard complexity theory: the unitary
synthesis problem includes a “promised subspace” on which all input states to
that unitary are supposed to lie; if an input state has support on the
orthogonal complement to this subspace, the behaviour is not specified by the
unitary synthesis problem.

###### Examples.

We present some examples of unitary synthesis problems.

  1. 1.

(_Hamiltonian time evolution_) Consider some natural string encoding of pairs
$(H,t)$ where $H$ is a local Hamiltonian and $t$ is a real number: the
encoding will specify the number of qubits that $H$ acts on as well as each
local term of $H$. If $x$ is a valid encoding of such a pair $(H,t)$, then
define $U_{x}=e^{-iHt}$. Otherwise, define $U_{x}=0$. Then we define
$\textsc{TimeEvolution}=(U_{x})_{x\in\\{0,1\\}^{*}}$.

  2. 2.

(_Decision languages_) Let $L\subseteq\\{0,1\\}^{*}$ be a decision language.
Define $\textsc{UnitaryDecider}_{L}=(U_{x})_{x\in\\{0,1\\}^{*}}$ as follows:
interpreting $x$ as the binary representation of an integer $n\in\mathbb{N}$,
the unitary $U_{n}$ acts on $n+1$ qubits and for all
$y\in\\{0,1\\}^{n},b\in\\{0,1\\}$, we define
$U_{n}\ket{y}\ket{b}=\ket{y}\ket{b\oplus L(y)}$ where $L(y)=1$ iff $y\in L$.
In other words, the unitary $U_{n}$ coherently decides whether $y\in L$ or
not.

  3. 3.

(_State preparation_) Let $(\ket{\psi_{x}})_{x\in\\{0,1\\}^{*}}$ be a family
of states where $\ket{\psi_{x}}$ is on $n_{x}$ qubits. Then the partial
isometries $U_{x}=\ket{\psi_{x}}\\!\\!\bra{0^{n_{x}}}$ form a unitary
synthesis problem. In other words, these partial isometries map the zero state
to $\ket{\psi_{x}}$.

We now define what it means to _implement_ a unitary synthesis problem.
Intuitively, an implementation of a unitary synthesis problem is just a
sequence of (not necessarily unitary) quantum circuits that implement the
corresponding partial isometries. The only subtlety is that a quantum circuit
is trace-preserving on all inputs, so it cannot map states in the orthogonal
complement of the support of the partial isometry to 0. Therefore, we require
that the quantum circuit implements any channel completion of the partial
isometry (Definition 2.4). This is analogous to classical promise problems,
where a Turing machine deciding the promise problem is allowed to behave
arbitrarily on inputs violating the promise, instead of being e.g. required to
abort.

######  Definition 3.2 (Worst-case implementation of unitary synthesis
problems).

Let $\mathscr{U}=(U_{x})_{x\in\\{0,1\\}^{*}}$ denote a unitary synthesis
problem and $\delta:\mathbb{N}\to\mathbb{R}$ a function. Let
$C=(C_{x})_{x\in\\{0,1\\}^{*}}$ denote a (not necessarily uniform) family of
quantum circuits, where $C_{x}$ implements a channel whose input and output
registers are the same as those of $U_{x}$. We say that _$C$ implements
$\mathscr{U}$ with worst-case error $\delta$_ if for all $x\in\\{0,1\\}^{*}$,
there exists a channel completion $\Phi_{x}$ of $U_{x}$ such that

$\Big{\|}C_{x}-\Phi_{x}\Big{\|}_{\diamond}\leq\delta(|x|)\,,$

where $\|\cdot\|_{\diamond}$ denotes the diamond norm.

Recall that a small diamond distance between two channels means that the
channels are difficult to distinguish even if the channels are applied to an
entangled state.

######  Remark 3.3.

For a unitary synthesis problem $\mathscr{U}=(U_{x})_{x\in\\{0,1\\}^{*}}$ we
call $x$ an _instance_ , and $U_{x}$ the transformation of $\mathscr{U}$
corresponding to instance $x$. We call the register that $U_{x}$ or its
implementation $C_{x}$ acts on the _quantum input_ to the unitary synthesis
problem.

We also define a notion of _distributional (or average-case) unitary synthesis
problems_. Here, in addition to a partial isometry, we also specify a state
and a register of this state on which the partial isometry is going to act;
note, however, that this is very different from a state synthesis problem, as
we discuss in Remark 3.12. We first give the formal definition and then
explain why this is a reasonable notion of a distributional unitary synthesis
problem.

######  Definition 3.4 (Distributional unitary synthesis problem).

We say that a pair $(\mathscr{U},\Psi)$ is a _distributional unitary synthesis
problem_ if $\mathscr{U}=(U_{x})_{x}$ is a unitary synthesis problem with
$U_{x}\in\mathrm{L}(\mathsf{A}_{x},\mathsf{B}_{x})$ for some registers
$\mathsf{A}_{x},\mathsf{B}_{x}$, and $\Psi=(\ket{\psi_{x}})_{x}$ is a family
of bipartite pure states on registers $\mathsf{A}_{x}\mathsf{R}_{x}$. We call
$\ket{\psi_{x}}$ the _distribution state_ with _target register_
$\mathsf{A}_{x}$ and _ancilla register_ $\mathsf{R}_{x}$.

######  Definition 3.5 (Average-case implementation of distributional unitary
synthesis problems).

Let $(\mathscr{U},\Psi)$ denote a distributional unitary synthesis problem,
where $\mathscr{U}=(U_{x})_{x}$ and $\Psi=(\ket{\psi_{x}})_{x}$, and let
$\delta:\mathbb{N}\to\mathbb{R}$ be a function. Let $C=(C_{x})_{x}$ denote a
family of quantum circuits, where $C_{x}$ implements a channel whose input and
output registers are the same as those of $U_{x}$. We say that _$C$ implements
$(\mathscr{U},\Psi)$ with average-case error $\delta$_ if for all
$x\in\\{0,1\\}^{*}$, there exists a channel completion $\Phi_{x}$ of $U_{x}$
such that

$\mathrm{td}\Big{(}(C_{x}\otimes\textnormal{id})(\psi_{x}),\,(\Phi_{x}\otimes\textnormal{id})(\psi_{x})\Big{)}\leq\delta(|x|)\,,$

where the identity channel acts on the ancilla register of $\ket{\psi_{x}}$.

The term “distributional” may seem a bit odd at first; for example, where is
the distribution in Definition 3.4? In classical average-case complexity
theory, a distributional problem is one where the inputs are sampled from some
probability distribution $\mathcal{D}$. The state family
$\Psi=(\ket{\psi_{x}})_{x}$ in a distributional unitary synthesis problem
$(\mathscr{U},\Psi)$ can be viewed as a _purification_ of a distribution over
pure states: by the Schmidt decomposition, we can always write

$\displaystyle\ket{\psi_{x}}=\sum_{j}\sqrt{p_{x,j}}\ket{\phi_{x,j}}\otimes\ket{j}$
(3.1)

for orthonormal states $\\{\ket{\phi_{x,j}}\\}_{j}$ on $\mathsf{A}_{x}$ and
$\\{\ket{j}\\}_{j}$ on $\mathsf{R}_{x}$. The Schmidt coefficients
$\\{p_{x,j}\\}_{j}$ form a probability distribution $\mathcal{D}_{x}$, so
$\ket{\psi_{x}}$ can be viewed as the purification of the distribution
$\mathcal{D}_{x}$ over pure states $\\{\ket{\phi_{x,j}}\\}_{j}$. The condition
of $C$ implementing $(\mathscr{U},\Psi)$ with average-case error $\delta$ is
equivalent to the following: for all $x\in\\{0,1\\}^{*}$ there exists a
channel completion $\Phi_{x}$ of $U_{x}$ such that

$\displaystyle\mathop{\mathbb{E}}_{j\sim\mathcal{D}_{x}}\mathrm{td}(C_{x}(\phi_{x,j}),\,\Phi_{x}(\phi_{x,j}))\leq\delta(|x|)\,.$
(3.2)

Conversely, any distribution over pure states can be purified into a state of
the form Equation 3.1, so the condition in Equation 3.2 is equivalent to
Definition 3.5. We will find it more convenient to simply specify (for each
$x$) one pure state $\ket{\psi_{x}}_{\mathsf{A}_{x}\mathsf{R}_{x}}$ instead of
a set of pure states on $\mathsf{A}_{x}$ and a distribution over them.

One might also wonder about specifying a distribution over the strings $x$
that label the partial isometries $U_{x}$. However this can be “folded” into
the state distribution by consider a larger unitary $U_{n}$ that takes as
input $\ket{x}\otimes\ket{\psi}$.

######  Remark 3.6.

Comparing Definition 3.2 and Definition 3.5, we see that we can also define
the worst-case error in terms of the average-case error: a circuit family
$C=(C_{x})_{x\in\\{0,1\\}^{*}}$ implements a unitary synthesis problem
$\mathscr{U}=(U_{x})_{x\in\\{0,1\\}^{*}}$ with worst case error $\delta$ if
and only if it implements the distributional unitary synthesis problem
$(\mathscr{U},\Psi)$ with average-case error $\delta$ for all state sequences
$\Psi=(\ket{\psi_{x}})_{x}$.

####  3.2 Unitary complexity classes

A _unitary complexity class_ is a collection of unitary synthesis problems. We
introduce some natural unitary complexity classes. First we define the unitary
synthesis analogues of $\mathsf{BQP}$ and $\mathsf{PSPACE}$, respectively.

######  Definition 3.7 ($\mathsf{unitaryBQP}$, $\mathsf{unitaryPSPACE}$).

Let $\delta:\mathbb{N}\to\mathbb{R}$ be a function. Define the unitary
complexity class $\mathsf{unitaryBQP}_{\delta}$ (resp.
$\mathsf{unitaryPSPACE}_{\delta}$) to be the set of unitary synthesis problems
$\mathscr{U}=(U_{x})_{x}$ for which there exists a _uniform_ polynomial-time
(resp. polynomial-space) quantum algorithm $C$ that implements $\mathscr{U}$
with worst-case error $\delta$. We define $\mathsf{unitaryBQP}$ (resp.
$\mathsf{unitaryPSPACE}$) to be the intersection of
$\mathsf{unitaryBQP}_{1/q(n)}$ (resp. $\mathsf{unitaryPSPACE}_{1/q(n)}$) over
all polynomials $q(n)$.

A natural question about unitary complexity classes such
$\mathsf{unitaryBQP}_{\delta}$ and $\mathsf{unitaryPSPACE}_{\delta}$ is
whether the error $\delta$ can be generically reduced, in analogy to how the
completeness/soundness errors can be generically reduced in randomized
complexity classes like $\mathsf{BPP}$ or $\mathsf{BQP}$. In particular, is it
true that $\mathsf{unitaryBQP}_{1/3}$ is the same as
$\mathsf{unitaryBQP}_{n^{-1}}$ or even $\mathsf{unitaryBQP}_{\exp(-n)}$? We
first present a simple argument for why error reduction for unitary synthesis
classes is not possible in general.

######  Proposition 3.8 (Impossibility of error reduction for unitary
synthesis problems).

Let $\alpha,\beta$ be such that $0<\alpha<\beta<1$ and
$\beta>2\sqrt{3\alpha}$. Then
$\mathsf{unitaryBQP}_{\alpha}\neq\mathsf{unitaryBQP}_{\beta}$.

###### Proof.

Define $\mathscr{U}=(U_{x})_{x\in\\{0,1\\}^{*}}$ as follows. If $x$ is the
description of a Turing machine that halts on the empty input, then $U_{x}$ is
the single-qubit unitary $\begin{pmatrix}\sqrt{1-3\alpha}&-\sqrt{3\alpha}\\\
\sqrt{3\alpha}&\sqrt{1-3\alpha}\end{pmatrix}$. Otherwise, $U_{x}$ is the
identity matrix on a single qubit. It is clear that
$\mathscr{U}\in\mathsf{unitaryBQP}_{\beta}$: this is because in the case that
$x$ represents a halting Turing machine, the identity matrix approximates
$U_{x}$ in diamond norm with error $2\sqrt{3\alpha}<\beta$.

On the other hand, $\mathscr{U}\notin\mathsf{unitaryBQP}_{\alpha}$. Suppose
for contradiction there was a uniform quantum algorithm $C=(C_{x})_{x}$ that
implements $\mathscr{U}$ with worst-case error $\alpha$. Then we can use $C$
to decide the Halting Problem as follows. Given an input $x$, repeatedly run
the circuit $C_{x}$ on $\ket{0}$, and then measure in the standard basis.
Since $C_{x}$ implements $U_{x}$ with worst-case error $\alpha$, this means
that if $x$ represents a halting Turing machine, then each trial results in
$\ket{1}$ with probability at least $3\alpha-\alpha\geq 2\alpha$, and if $x$
represents a non-halting Turing machine, then each trial results in $\ket{1}$
with probability at most $\alpha$. Since $\alpha$ is constant, after a
constant number of trials one can distinguish with high confidence whether $x$
represents a halting Turing machine or not. Thus this implies the Halting
problem can be decided by a quantum algorithm in polynomial time, which is a
contradiction. ∎

######  Remark 3.9.

It is interesting that a simple argument can prove separations between unitary
complexity classes, whereas in contrast it is much harder to prove analogous
separations between traditional complexity classes. For example, it remains
unknown whether $\mathsf{BPP}\neq\mathsf{BQP}$. However we also point out that
this has nothing to do with the fact that we’re dealing with quantum
complexity classes; one could also prove similar separations between
_classical sampling complexity classes_ (see, e.g., [Aar14]).

Next we define classes of distributional unitary synthesis problems, the
unitary complexity analogues of classical average case complexity classes.

######  Definition 3.10 ($\mathsf{avgUnitaryBQP}$,
$\mathsf{avgUnitaryPSPACE}$).

Let $\delta:\mathbb{N}\to\mathbb{R}$ be a function. Define the unitary
complexity class $\mathsf{avgUnitaryBQP}_{\delta}$ (resp.
$\mathsf{avgUnitaryPSPACE}_{\delta}$) to be the set of distributional unitary
synthesis problems
$\Big{(}\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi}_{x})_{x}\Big{)}$ where
$\Psi\in\mathsf{stateBQP}$ (resp. $\Psi\in\mathsf{statePSPACE}$) and there
exists a uniform polynomial-time (resp. polynomial-space) quantum algorithm
$C$ that implements $(\mathscr{U},\Psi)$ with average-case error $\delta$. We
define $\mathsf{avgUnitaryBQP}$ (resp. $\mathsf{avgUnitaryPSPACE}$) to be the
intersection of $\mathsf{avgUnitaryBQP}_{1/q(n)}$ (resp.
$\mathsf{avgUnitaryPSPACE}_{1/q(n)}$) over all polynomials $q(n)$.

######  Remark 3.11.

In our definition of $\mathsf{avgUnitaryBQP}$ and $\mathsf{avgUnitaryPSPACE}$,
we require that the state sequence with respect to which the average case
unitary synthesis problem is defined be in the corresponding state complexity
class (i.e. $\mathsf{stateBQP}$ and $\mathsf{statePSPACE}$, respectively). We
will follow this general pattern throughout the paper: whenever we define an
average case unitary complexity class, we will require that the state sequence
is in the corresponding state class (see e.g. Definition 4.2). This is in
analogy to classical average case complexity classes, where it is common to
require that the distribution over which the problem is defined can be sampled
from with reasonable complexity. As we will see e.g. in Theorem 7.12, this
assumption will be necessary to prove several natural results about average
unitary complexity.

######  Remark 3.12.

Since an average-case unitary synthesis problem specifies both an input state
$\ket{\psi_{x}}$ and a unitary $U_{x}$ to be applied on that state, it may
seem like this is just a complicated way of stating the state synthesis
problem for the state $U_{x}\ket{\psi_{x}}$. This, however, is not the case:
the state $\ket{\psi_{x}}$ is defined on register
$\mathsf{A}_{x}\mathsf{R}_{x}$, but the unitary $U_{x}$ is only allowed to act
on $\mathsf{A}_{x}$. Therefore, if we imagine that we hand a unitary synthesis
problem to some black box to implement, we should imagine that we provide as
input the string $x$ as well as register $\mathsf{A}_{x}$ of $\ket{\psi_{x}}$.
With sufficient computational resources, the black box can of course
synthesise many more copies of $\ket{\psi_{x}}$ because the state is in the
corresponding state complexity class. However, to solve the unitary synthesis
problem, it has to apply the unitary on register $\mathsf{A}_{x}$ of the state
that we provided as input, not any other copy of $\ket{\psi_{x}}$ it created
itself. This is because otherwise the output state would not be entangled with
our register $\mathsf{R}_{x}$ (which the black box does not have access to) in
the correct way. This has the important consequence that in contrast to state
synthesis problems, in average unitary synthesis problems the black box cannot
re-run the synthesis algorithm many times and post-select on success, as it is
only provided with a single copy of a register of the input state
$\ket{\psi_{x}}$. We therefore see that solving an average-case unitary
synthesis problem $(\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi_{x}})_{x})$ is
potentially much harder than the state synthesis problem for the sequence
$\Psi^{\prime}\coloneqq(U_{x}\ket{\psi_{x}})_{x}$. Conversely, if we can show
that $(\mathscr{U},\Psi)$ is in some average unitary complexity class, it
immediately follows that the state synthesis problem $\Psi^{\prime}$ is in the
corresponding state complexity class.

###### Non-uniform unitary synthesis classes.

The classes $\mathsf{unitaryBQP}$ and $\mathsf{unitaryPSPACE}$ are _uniform_
complexity classes in the sense that a unitary synthesis problem
$\mathscr{U}=(U_{x})_{x}$ in either class must be implemented by a _uniform_
quantum algorithm, i.e. a collection of circuits $C=(C_{x})_{x}$ that are
uniformly generated by a single (classical) Turing machine.

However one can also consider _nonuniform_ variants of these classes, where
the circuits $C_{x}$ are not required to be uniformly generated by a Turing
machine. These are analogous to nonuniform complexity classes like
$\sf{P/poly}$ in classical complexity theory, but there is one key difference:
the implementation algorithm can have a different circuit for each instance
$x$, whereas the definition of $\sf{P/poly}$ only allows the circuit to depend
on the _input length_. If the circuits in the definition of $\mathsf{P/poly}$
could depend on the instance, then all languages would trivially be in
$\mathsf{P/poly}$: the circuit could just output $1$ or $0$ depending on
whether the instance were in the language.

As we will see in Section 8, this notion of nonuniformity allows us to
establish a tight connection between the (non-uniform) complexity of unitary
synthesis problems and the hardness of breaking various quantum cryptographic
primitives.

######  Definition 3.13 ($\mathsf{unitaryBQP/poly}$).

Let $\delta:\mathbb{N}\to\mathbb{R}$ be a function. Define the unitary
complexity class $\mathsf{unitaryBQP/poly}_{\delta}$ to be the set of unitary
synthesis problems $\mathscr{U}=(U_{x})_{x}$ for which there exists a _non-
uniform_ polynomial-size family of quantum algorithms $C_{x}$ that implements
$\mathscr{U}$ with worst-case error $\delta$. We define
$\mathsf{unitaryBQP/poly}$ to be the intersection of
$\mathsf{unitaryBQP/poly}_{1/q(n)}$ for all polynomials $q(n)$.

We also define an nonuniform variant of $\mathsf{avgUnitaryBQP}$.

######  Definition 3.14 ($\mathsf{avgUnitaryBQP/poly}$).

Let $\delta:\mathbb{N}\to\mathbb{R}$ be a function. Define the unitary
complexity class $\mathsf{avgUnitaryBQP/poly}_{\delta}$ to be the set of
distributional unitary synthesis problems
$\Big{(}\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi}_{x})_{x}\Big{)}$ where
$\Psi\in\mathsf{stateBQP}$ and there exists a _non-uniform_ polynomial-size
family of quantum circuits $(C_{x})_{x}$ that implements $(\mathscr{U},\Psi)$
with average-case error $\delta$. We define $\mathsf{avgUnitaryBQP/poly}$ to
be the intersection of $\mathsf{avgUnitaryBQP/poly}_{1/q(n)}$ for all
polynomials $q(n)$.

One can also define non-uniform versions of these classes with _quantum_
advice, e.g., $\mathsf{unitaryBQP/qpoly}$, but we leave that for future work.

####  3.3 Reductions

Notions of reductions are crucial in complexity theory and theoretical
computer science. We introduce a basic notion of reduction that allows one to
relate one unitary synthesis problem to another. First, we to formalize the
notion of circuits that can make queries to a unitary synthesis oracle.
Intuitively, a quantum circuit with access to a unitary synthesis oracle is
just like a normal quantum circuit, except that it can apply some set of
partial isometries (or more precisely arbitrary channel completions of partial
isometries) in a single computational step by using the unitary synthesis
oracle.

######  Definition 3.15 (Quantum query circuits).

A _quantum query circuit_ $C^{*}$ specifies a sequence of gates like those in
a general quantum circuit (defined in Section 2.3), except it may also include
special “oracle gates”. An oracle gate is specified by a label
$y\in\\{0,1\\}^{*}$; its action on its input qubits will be specified
separately, i.e. a quantum query circuit is not actually a quantum circuit,
but rather a _template_ for a quantum circuit.

Figure 1 depicts an example of a quantum query circuit.

$\Qcircuit<EMAIL_ADDRESS>\ket{0}\qw\gate{\phantom{H}}\ghost{H}\ghost{U_{x_{1}}}\gate{\phantom{H}}\qw\multigate{2}{U_{x_{2}}}\qw\\\
\ket{0}\qw\gate{\phantom{H}}\qw\ghost{U_{x_{1}}}\gate{\phantom{H}}\qw\ghost{U_{x_{2}}}\qw\\\
\ket{0}\qw\gate{\phantom{H}}\qw\qw\gate{\phantom{H}}\qw\ghost{U_{x_{2}}}\qw}$
Figure 1: An example of a quantum query circuit that calls members of a
unitary synthesis problem $\mathscr{U}$; the subscripts $x_{1},x_{2}$ denote
instances that are hardcoded in the query circuit.

######  Definition 3.16 (Instantiations of quantum query circuits).

An _instantiation_ of a quantum query circuit $C^{*}$ with a unitary synthesis
problem $\mathscr{U}=(U_{x})$, denoted $C^{\mathscr{U}}$, is a quantum channel
obtained from $C^{*}$ by replacing all the oracle gates with label $y$ by some
channel completion of $U_{y}$ (which can be different each time $U_{y}$ is
called). Whenever we write $C^{\mathscr{U}}$, we implicitly require that
$\mathscr{U}$ is such that the input and output registers of $U_{y}$ match the
input and output registers of any oracle gate with label $y$ in $C^{*}$.

######  Definition 3.17 (Uniformity of quantum query circuits).

We say that a family $(C^{*}_{x})_{x}$ of quantum query circuits is _time-
uniform_ (resp.  _space-uniform_) if there exists a classical polynomial time
(resp. polynomial space) Turing machine that on input $x$ outputs a
description of $C_{x}$ and furthermore all labels $y$ in an oracle gate in
$C^{*}_{x}$ satisfy $|y|=\mathrm{poly}(|x|)$. For brevity, we also call a
time-uniform (resp. space-uniform) family of quantum query circuits a
_polynomial time (resp. polynomial space) quantum query algorithm_. If
$C^{*}=(C^{*}_{x})_{x}$ is a quantum query algorithm, then we write
$C^{\mathscr{V}}$ to denote a family of instantiations
$(C_{x}^{\mathscr{V}})_{x}$. Just like for individual query circuits, for
families of query circuits we call $C^{\mathscr{V}}$ an instantiation of
$C^{*}$.

We note that our definition of quantum query circuit has the classical
instances $y$ “hardcoded” into the description of the circuit. In particular,
the query circuit cannot choose which oracles it queries depending on its
quantum input.101010Of course, for a family of query circuits $(C^{*}_{x})$,
the labels $y$ used by $C_{x}^{*}$ can depend on the index $x$; the point here
is that a given $C_{x}^{*}$ cannot compute the labels $y$ as a function of the
quantum input it is given. To accommodate situations when the oracle circuit
may want to query different oracles $\mathscr{U}=(U_{x})_{x}$ (perhaps even in
superposition), one can define a “controlled oracle”
$\tilde{U}_{n}=\sum_{x:|x|=n}\ket{x}\\!\\!\bra{x}\otimes U_{x}$. In other
words, $\tilde{U}_{n}$ applies the oracle $U_{x}$ conditioned on some
$n$-qubit register being in the state $\ket{x}$. A quantum query circuit with
access to this controlled oracle can then apply different $U_{x}$ coherently
depending on its quantum input, i.e. the controlled oracle gives a query
circuit more power than the uncontrolled one.

We also note that the instantiation $C^{\mathscr{V}}$ is not unique because
the oracle gates can implement any channel completion of the partial
isometries $V_{x}\in\mathscr{V}$. Whenever we say that a statement holds for
$C^{\mathscr{V}}$, we mean that it holds for all possible instantiations, i.e.
for all possible choices of channel completions.

Using quantum query circuits, we can define reductions between unitary
synthesis problems.

######  Definition 3.18 (Reductions between unitary synthesis problems).

Let $\mathscr{U}=(U_{x})_{x}$ and $\mathscr{V}=(V_{x})_{x}$ denote unitary
synthesis problems. Then $\mathscr{U}$ _(polynomial-time) reduces_ to
$\mathscr{V}$ if for all polynomials $q(n)$ there exists a polynomial-time
quantum query algorithm $C^{*}$ such all instantiations $C^{\mathscr{V}}$ of
$C^{*}$ implement $\mathscr{U}$ with worst-case error $1/q(|x|)$.

Just like one can define oracle complexity classes like
$\mathsf{P}^{\textsc{3SAT}}$ (i.e., polynomial-time computation with oracle
access to a 3SAT oracle), we can now also define oracle complexity classes for
unitary synthesis problems:

######  Definition 3.19 (Oracle unitary complexity classes).

We define the oracle class $\mathsf{unitaryBQP}^{\mathscr{V}}$ to be the set
of all unitary synthesis problems that are polynomial-time reducible to a
unitary synthesis problem $\mathscr{V}$.

We can also define reductions between distributional unitary synthesis
problems, analogously to how reductions between distributional problems are
defined in classical average case complexity.

First, we need to define what it means for a query circuit to be instantiated
with an average-case implementation of an oracle.

######  Definition 3.20 (Average-case instantiation of a query circuit).

Let $(\mathscr{V}=(U_{x})_{x},\Psi=(\ket{\psi_{x}})_{x})$ denote a
distributional unitary synthesis problem. Let $\epsilon(n)$ be a function and
let $C^{*}$ denote a quantum query circuit that queries
$U_{x_{1}},U_{x_{2}},\ldots,U_{x_{m}}$. An _$\epsilon$ -error average-case
instantiation_ of $C^{*}$ with $(\mathscr{U},\Psi)$, denoted by
$C^{(\mathscr{U},\Psi)}$, is a quantum channel obtained from $C^{*}$ by
replacing all the oracle gates with label $x$ by some quantum algorithm (which
can be different each time $U_{x}$ is called) that implements $U_{x}$ on the
distribution $\psi_{x}$ with average-case error $\epsilon(|x|)$.

Furthermore, whenever we write $C^{(\mathscr{U},\Psi)}$, we implicitly require
that $\mathscr{U}$ is such that the input and output registers of $U_{x}$
match the input and output registers of any oracle gate with label $x$ in
$C^{*}$.

We note that the error $\epsilon$ in an “$\epsilon$-error average-case
instantiation” only refers to the error with which the oracle gates are
implemented, not the error of the output of the overall quantum query circuit.
The latter will of course depend on $\epsilon$, but also on other factors,
e.g. how many oracle queries are made and how sensitive the overall output is
to errors in the oracle implementation.

We now define reductions between distributional problems.

######  Definition 3.21 (Reductions between distributional problems).

Let $\Big{(}\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi_{x}})_{x}\Big{)}$ and
$\Big{(}\mathscr{V}=(V_{x})_{x},\Omega=(\ket{\omega_{x}})_{x}\Big{)}$ denote
distributional unitary synthesis problems. Then $(\mathscr{U},\Psi)$
_(polynomial-time) reduces_ to $(\mathscr{V},\Omega)$ if for all polynomials
$q(n)$ there exists a polynomial-time quantum query algorithm $C^{*}$ and a
polynomial $r(n)$ such that all $1/r(n)$-error average-case instantiations
$C^{(\mathscr{V},\Omega)}$ implement $(\mathscr{U},\Psi)$ with average-case
error $1/q(n)$.

Next we aim to define the oracle class
$\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}$. For this, we will have to
specify a state complexity class which the distributional states are required
to be from. For $\mathsf{avgUnitaryBQP}$, we required that the distributional
states be from $\mathsf{stateBQP}$. However, if we give the
$\mathsf{avgUnitaryBQP}$ oracle access to $(\mathscr{V},\Omega)$, it is
natural to allow the same oracle access for the preparation of the
distributional states, too. Therefore, we have to specify a notion “oracle
state complexity class”, which we will naturally denote by
$\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$. Similar definitions can be made
for other state classes in addition to $\mathsf{stateBQP}$.

######  Definition 3.22 (Oracle state complexity classes).

Let $\Big{(}\mathscr{V}=(V_{x})_{x},\Omega=(\ket{\omega_{x}})_{x}\Big{)}$ be a
distributional unitary synthesis problem. We define the oracle state
complexity class $\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$ to be the set of
state families $\Psi=(\ket{\psi_{x}})_{x}$ where for all polynomials $q(n)$
there exists a polynomial-time quantum query algorithm $C^{*}=(C_{x}^{*})_{x}$
and a polynomial $r(n)$ such that for all $x$, all $1/r(n)$-error average-case
instantiations $C^{(\mathscr{V},\Psi)}_{x}$ on the all zeroes input outputs a
state that is $1/q(n)$-close to $\ket{\psi_{x}}$.

In other words, a state family $\Psi=(\ket{\psi_{x}})_{x}$ is in
$\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$ if it can be synthesized by
polynomial-sized circuits that also have the ability to query algorithms that
solve $\mathscr{V}$ in the average case. We now define the oracle class
$\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}$:

######  Definition 3.23 (Average-case oracle unitary complexity classes).

We define the oracle class $\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}$ to
be the set of all distributional problems $(\mathscr{U},\Psi)$ that are
polynomial-time reducible to the distributional unitary synthesis problem
$(\mathscr{V},\Omega)$ and for which
$\Psi\in\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$.

Just like for classical complexity classes, we can use this notion of
reduction to define hard and complete problems for (average-case) unitary
complexity classes.

######  Definition 3.24 (Hard and complete problems).

We call a unitary synthesis problem $\mathscr{U}$ _hard_ (under polynomial-
time reductions) for a unitary complexity class $\mathsf{unitaryC}$ if
$\mathsf{unitaryC}\subseteq\mathsf{unitaryBQP}^{\mathscr{U}}$. If additionally
$\mathscr{U}\in\mathsf{unitaryC}$, we call $\mathscr{U}$ _complete_ for the
class $\mathsf{unitaryC}$.

Analogously, we call a distributional unitary synthesis problem
$(\mathscr{U},\Psi)$ _hard_ (under polynomial-time reductions) for an average-
case unitary complexity class $\mathsf{avgUnitaryC}$ if
$\mathsf{avgUnitaryC}\subseteq\mathsf{avgUnitaryBQP}^{(\mathscr{U},\Psi)}$. If
additionally $(\mathscr{U},\Psi)\in\mathsf{avgUnitaryC}$, we call
$(\mathscr{U},\Psi)$ _complete_ for the class $\mathsf{avgUnitaryC}$.

As would be expected, $\mathsf{unitaryBQP}$ and $\mathsf{avgUnitaryBQP}$ are
closed under polynomial-time reductions.

######  Lemma 3.25.

$\mathsf{unitaryBQP}$ is closed under polynomial-time reductions, i.e. for all
$\mathscr{V}\in\mathsf{unitaryBQP}$, we have that
$\mathsf{unitaryBQP}^{\mathscr{V}}\subseteq\mathsf{unitaryBQP}$.

Likewise, $\mathsf{avgUnitaryBQP}$ is closed under polynomial-time reductions,
i.e. for all $(\mathscr{V},\Omega)\in\mathsf{avgUnitaryBQP}$, we have that
$\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}\subseteq\mathsf{avgUnitaryBQP}$.

###### Proof.

Consider a unitary synthesis problem
$\mathscr{U}=(U_{x})_{x}\in\mathsf{unitaryBQP}^{\mathscr{V}}$. By definition,
for all polynomials $q$ there exists a polynomial-time quantum query algorithm
$C^{*}=(C^{*}_{x})_{x}$ such that all instantiations $C^{\mathscr{V}}_{x}$
implement $U_{x}$ with worst-case error $1/q(|x|)$. Since
$\mathscr{V}\in\mathsf{unitaryBQP}$, for all polynomials $p$ there exists a
polynomial-size circuit family $\tilde{C}_{y}$ such that $\tilde{C}_{y}$ is
$1/p(|y|)$-close to a channel completion of $V_{y}$. Since $C^{*}_{x}$ can
include $r(|x|)=\mathrm{poly}(|x|)$ many oracle gates with labels $y$ such
that $|y|=\mathrm{poly}(|x|)$, we can simply replace each oracle gate by the
polynomial-time circuit $\tilde{C}_{y}$; this will yield another polynomial-
size circuit, and this circuit will be
$(r(|x|)/p(\mathrm{poly}(|x|))+1/q(|x|))$-close to a channel completion of
$U_{x}$ by the triangle inequality and monotonicity property of the diamond
norm. Since $p,q$ can be chosen arbitrarily large, we get that
$\mathscr{U}\in\mathsf{unitaryBQP}$. The statement for
$\mathsf{avgUnitaryBQP}$ follows analogously after noting that for
$(\mathscr{V},\Omega)\in\mathsf{avgUnitaryBQP}$,
$\mathsf{stateBQP}^{(\mathscr{V},\Omega)}\subseteq\mathsf{stateBQP}$. ∎

The same statement holds for $\mathsf{unitaryPSPACE}$ and
$\mathsf{avgUnitaryPSPACE}$, too.

######  Lemma 3.26.

$\mathsf{unitaryPSPACE}$ is closed under polynomial-time reductions, i.e. for
all $\mathscr{V}\in\mathsf{unitaryPSPACE}$, we have that
$\mathsf{unitaryBQP}^{\mathscr{V}}\subseteq\mathsf{unitaryPSPACE}$.

Similarly, $\mathsf{avgUnitaryPSPACE}$ is closed under polynomial-time
reductions, i.e. for all $(\mathscr{V},\Omega)\in\mathsf{avgUnitaryPSPACE}$,
we have that
$\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}\subseteq\mathsf{avgUnitaryPSPACE}$.

###### Proof.

The proof for the worst-case class $\mathsf{unitaryPSPACE}$ is identical to
that of Lemma 3.25. The proof for the average-case setting is analogous, too,
except that we now need to ensure that the distributional states
$\Psi\in\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$ allowed by the oracle class
$\mathsf{avgUnitaryBQP}^{(\mathscr{V},\Omega)}$ are also valid input states
for a problem in $\mathsf{avgUnitaryPSPACE}$; that is we need to show that
$\mathsf{stateBQP}^{(\mathscr{V},\Omega)}\subseteq\mathsf{statePSPACE}$ for a
distributional problem $(\mathscr{V},\Omega)\in\mathsf{avgUnitaryPSPACE}$.
This is easily seen to hold by the same argument we used for Lemma 3.25: we
can simply replace all oracle calls in the state preparation procedure for
$\Psi\in\mathsf{stateBQP}^{(\mathscr{V},\Omega)}$ by the corresponding space-
uniform circuit that implements $(\mathscr{V},\Omega)$; since there are at
most polynomially oracle calls, the result is a space-uniform circuit, so
$\Psi\in\mathsf{statePSPACE}$. ∎

####  3.4 Discussion and open problems

In this section, we have introduced a formal framework for studying the
complexity of unitary synthesis problems. We have already seen the unitary
complexity classes $\mathsf{unitaryBQP}$ and $\mathsf{unitaryPSPACE}$, as well
as their average-case versions. In the next section, we will consider
interactive proofs for unitary synthesis problems, which will naturally lead
us to define the classes $\mathsf{unitaryQIP}$ and $\mathsf{unitarySZK}$.
This, however, is by no means a full list of all unitary complexity classes
that might be of interest — our aim here is to introduce the classes relevant
to the Uhlmann transformation problem, not to provide a complete account. As
such, it is natural to consider the following question.

######  Open Problem 1.

What are other unitary complexity classes that naturally relate to physically
interesting problems? For example, is there a useful notion of
$\mathsf{unitaryQMA}$?

Later in this paper, we will prove some results relating unitary complexity
classes to one another. However, one would naturally conjecture that certain
unitary complexity classes are in fact different, e.g. one would expect
$\mathsf{unitaryBQP}\neq\mathsf{unitaryPSPACE}$. For decision languages,
proving such separations unconditionally is significantly out of reach of
current techniques. However, it is not clear whether this necessarily
constitutes a barrier for proving similar results in the unitary setting, as
it might for example be possible that
$\mathsf{unitaryBQP}\neq\mathsf{unitaryPSPACE}$, but
$\mathsf{BQP}=\mathsf{PSPACE}$. Therefore, another interesting question is the
following:

######  Open Problem 2.

Are there barriers from traditional complexity theory to proving unitary
complexity class separations?

Another important direction is to find complete problems for unitary
complexity classes. We make progress on this by showing that (certain variants
of) of the Uhlmann transformation problem are complete for certain unitary
classes, but there might be other interesting complete problems for other
unitary classes. One natural option is the following:

######  Open Problem 3.

Is Hamiltonian Fast-Forwarding [AA17] complete for $\mathsf{unitaryPSPACE}$?

One can also consider variations of the model for unitary synthesis. In this
paper, we always assume that the unitary needs to be applied on a single copy
of an unknown state. However, it might also make sense to consider a model
where an implementation of a unitary is allowed to “consume” multiple copies
of an input state, but only has to produce a single output state.

######  Open Problem 4.

How can a multi-input version of unitary synthesis problems be formalised,
including cases where the unitary is supposed to act on a part of a larger
pure state? Are there meaningful notions of reductions and complexity classes
of unitary synthesis problems in this multi-input model?

###  4 Interactive Proofs for Unitary Synthesis

In this section we introduce the model of interactive proofs for unitary
synthesis problems, as well as the corresponding unitary complexity classes.
In particular we introduce the unitary synthesis classes $\mathsf{unitaryQIP}$
and $\mathsf{avgUnitarySZK}$, which are analogues of $\mathsf{QIP}$ and
(average-case) $\mathsf{SZK}$, respectively. As we will see in Sections 6 and
7, the complexity of such interactive proof classes is captured by the Uhlmann
Transformation Problem.

####  4.1 Quantum interactive protocols

First we formally describe the model of quantum interactive protocols. (For a
more in-depth account we refer the reader to the survey of Vidick and Watrous
[VW16].) Since in quantum computing the standard model of computation is the
quantum circuit model (rather than quantum Turing machines), we model the
verifier in a quantum interactive protocol as a sequence of _verifier
circuits_ , one for each input length. A verifier circuit is itself a tuple of
quantum circuits that correspond to the operations performed by the verifier
in each round of the protocol.

More formally, a _$k$ -round quantum verifier circuit_ $C=(C_{j})_{j\in[k]}$
is a tuple of general quantum circuits that each act on a pair of registers
$(\mathsf{V},\mathsf{M})$. The register $\mathsf{V}$ is further divided into
disjoint sub-registers
$(\mathsf{V}_{\mathsf{work}},\mathsf{V}_{\mathsf{flag}},\mathsf{V}_{\mathsf{out}})$.
The register $\mathsf{V}_{\mathsf{work}}$ is the verifier circuit’s
“workspace", the register $\mathsf{V}_{\mathsf{flag}}$ is a single qubit
indicating whether the verifier accepts or rejects, and the register
$\mathsf{V}_{\mathsf{out}}$ holds the verifier’s output (if applicable). The
register $\mathsf{M}$ is the message register. The size of a verifier circuit
$C$ is the sum of the circuit sizes of the $C_{j}$’s.

A _quantum prover_ $P$ for a verifier circuit $C$ is a unitary that acts on
$\mathsf{M}$ as well as a disjoint register $\mathsf{P}$. Note that we could
also define the prover to be a collection of unitaries, one for each round, in
analogy to the verifier; the two definitions are equivalent since we can
always combine the single-round unitaries into a larger unitary that keeps
track of which round is being executed and applies the corresponding single-
round unitary. Since we will rarely deal with prover unitaries for individual
rounds, we will find it more convenient to just treat the prover as one large
unitary. Furthermore, since the prover register is of unbounded size, we can
assume without loss of generality that the prover applies a unitary (rather
than a quantum channel).

Let $\ket{\psi}$ denote a quantum state whose size is at most the number of
qubits in $\mathsf{V}_{\mathsf{work}}$. We write
$C(\ket{\psi})\mathord{\leftrightarrows}P$ to denote the interaction between
the verifier circuit $C$ and the prover $P$ on input $\rho$, which is defined
according to the following process. The initial state of the system is
$\ket{\phi_{0}}=\ket{\psi,0\cdots 0}_{\mathsf{V}_{\mathsf{work}}}\ket{0\cdots
0}_{\mathsf{V}_{\mathsf{flag}}\mathsf{V}_{\mathsf{out}}\mathsf{M}\mathsf{P}}$.
Inductively define $\ket{\phi_{i}}=P\ket{\phi_{i-1}}$ for odd $i\leq 2k$, and
$\ket{\phi_{i}}=C_{i/2}\ket{\phi_{i-1}}$ for even $i\leq 2k$. We say that
$C(\ket{\psi})\mathord{\leftrightarrows}P$ accepts (resp. rejects) if
measuring the register $\mathsf{V}_{\mathsf{flag}}$ in the standard basis
yields the outcome $1$ (resp. $0$). We say that the _output of
$C(\ket{\psi})\mathord{\leftrightarrows}P$ conditioned on accepting_ is the
density matrix

$\frac{\mathrm{Tr}_{\mathsf{V}\mathsf{M}\mathsf{P}\setminus\mathsf{V}_{\mathsf{out}}}\left(\ket{1}\\!\\!\bra{1}_{\mathsf{V}_{\mathsf{flag}}}\cdot\phi_{2k}\right)}{\mathrm{Tr}\left(\ket{1}\\!\\!\bra{1}_{\mathsf{V}_{\mathsf{flag}}}\cdot\phi_{2k}\right)}\,;$

in other words, it is the reduced density matrix of $\ket{\phi_{2k}}$ on
register $\mathsf{V}_{\mathsf{out}}$, conditioned on
$C(\ket{\psi})\mathord{\leftrightarrows}P$ accepting. (If the probability of
accepting is $0$, then we leave the output undefined.)

A _quantum verifier_ $V=(V_{x})_{x\in\\{0,1\\}^{*}}$ is a uniform sequence of
polynomial-size and polynomial-round quantum verifier circuits.

####  4.2 Interactive proofs for unitary synthesis

We now present our notion of interactive protocols for unitary synthesis.

######  Definition 4.1 ($\mathsf{unitaryQIP}$).

Let $c,s,\delta:\mathbb{N}\to[0,1]$ be functions. The class
$\mathsf{unitaryQIP}_{c,s,\delta}$ is the set of unitary synthesis problems
$\mathscr{U}=(U_{x})_{x}$ where there exists a polynomial-time quantum
verifier $V=(V_{x})_{x\in\\{0,1\\}^{*}}$ satisfying, for all
$x\in\\{0,1\\}^{*}$ of sufficiently large length,

  * •

_Completeness:_ There exists a quantum prover $P$ (called an _honest prover_)
such that for all input states $\ket{\psi}$ in the support of $U_{x}$,

${\rm Pr}\left[V_{x}(\ket{\psi})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq c(|x|)$

  * •

_Soundness:_ For all input states $\ket{\psi}$ and for all quantum provers
$P$, there exists a channel completion of $\Phi_{x}$ of $U_{x}$ such that

$\text{if }\quad{\rm
Pr}\left[V_{x}(\ket{\psi})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq
s(|x|)\qquad\text{then}\qquad\mathrm{td}(\sigma,\Phi_{x}(\psi))\leq\delta(|x|)\,,$

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

Here the probabilities are over the randomness of the interaction.

Finally, define

$\mathsf{unitaryQIP}_{\delta}=\bigcup_{\epsilon(n)\
\mathrm{negl}}\mathsf{unitaryQIP}_{1-\epsilon,\frac{1}{2},\delta}$

where the union is over all negligible functions $\epsilon(n)$, and define

$\mathsf{unitaryQIP}=\bigcap_{q(n)\
\mathrm{poly}}\mathsf{unitaryQIP}_{1/q(n)}$

where the intersection ranges over all polynomials $q(n)$.

Intuitively, a unitary synthesis problem $\mathscr{U}=(U_{x})_{x}$ has an
interactive proof if a polynomial-time verifier who receives a pair
$(x,\ket{\psi})$ can interact with an all-powerful prover, and conditioned on
accepting, output a state close to $U_{x}\ket{\psi}$.

The class $\mathsf{unitaryQIP}$ is analogous to the state synthesis class
$\mathsf{stateQIP}$ introduced by [RY22]; the only difference is that a
$\mathsf{stateQIP}$ verifier for the state family $\Psi=(\ket{\psi_{x}})_{x}$
has its input registers fixed to the all zeroes state, and in the soundness
condition, if a prover makes $V_{x}$ accept with probability at least $s(n)$,
then its output conditioned on accepting is close to the target state
$\ket{\psi_{x}}$.

We make a few remarks regarding the definition. First, one may notice a
peculiar asymmetry between the definitions of the classes
$\mathsf{unitaryQIP}_{\delta}$ and $\mathsf{unitaryQIP}$. The class
$\mathsf{unitaryQIP}_{\delta}$ is defined as a _union_ over completeness
parameters $c(n)=1-\epsilon(n)$ for some negligible function $\epsilon(n)$.
This is because we want to consider unitary synthesis protocols as long as
there is an honest prover that can be accepted with probability
$1-\epsilon(n)$ for _some_ negligible function $\epsilon(n)$; we do not want
to fix a particular negligible function. On the other hand, the class
$\mathsf{unitaryQIP}$ is defined as the _intersection_ of
$\mathsf{unitaryQIP}_{1/q(n)}$ over all choices of polynomials $q(n)$. Here
the quantity $1/q(n)$ denotes how well the output state (conditioned on the
verifier accepting) approximates the target state, and we want to consider
state sequences where for all polynomials $q(n)$ there is a protocol that can
synthesize the state with error smaller than $1/q(n)$ (for sufficiently large
$n$).

A second remark concerns the default choice of soundness $s(n)=\frac{1}{2}$
for the definition of $\mathsf{unitaryQIP}_{\delta}$ and
$\mathsf{unitaryQIP}$. In the state synthesis setting, the soundness parameter
can be generically amplified via sequential repetition (see [RY22] for a
proof). Thus the class $\mathsf{stateQIP}$ is the same for any soundness,
completeness parameters that are separated by at least an inverse polynomial.
It is not clear whether soundness amplification is possible in the unitary
synthesis setting, however. This is because the verifier only gets one copy of
the input state, and if a verifier does not accept the interaction it is
unclear how to recover the input state for another repetition of the protocol.
This motivates the following open question.

######  Open Problem 5.

Can completeness/soundness amplification be performed for
$\mathsf{unitaryQIP}$, or is there evidence that it’s not possible?

In analogy to Definition 4.1, we also define an average-case complexity
version of $\mathsf{unitaryQIP}$, where the verifier only has to synthesize
the desired unitary well on a given distribution state.

######  Definition 4.2 ($\mathsf{avgUnitaryQIP}$).

Let $c,s,\delta:\mathbb{N}\to[0,1]$ be functions. The class
$\mathsf{avgUnitaryQIP}_{c,s,\delta}$ is the set of distributional unitary
synthesis problems $(\mathscr{U}=(U_{x})_{x},\Psi=(\ket{\psi_{x}})_{x})$ such
that $\Psi\in\mathsf{stateQIP}$ and there exists a polynomial-time quantum
verifier $V=(V_{x})_{x\in\\{0,1\\}^{*}}$ satisfying, for all
$x\in\\{0,1\\}^{*}$ of sufficiently large length,

  * •

_Completeness:_ There exists a quantum prover $P$ (called an _honest prover_)
such that

${\rm Pr}\left[V_{x}(\ket{\psi_{x}})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq c(|x|)$

  * •

_Soundness:_ 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{\psi_{x}})\mathord{\leftrightarrows}P\text{
accepts}\right]\geq
s(|x|)\qquad\text{then}\qquad\mathrm{td}(\sigma,(\Phi_{x}\otimes\textnormal{id})(\psi_{x}))\leq\delta(|x|)\,.$

where $\sigma$ denotes the output of
$V_{x}(\ket{\psi_{x}})\mathord{\leftrightarrows}P$ conditioned on accepting
and $V_{x}$ acts the identity on the ancilla register of $\ket{\psi_{x}}$.

Here the probabilities are over the randomness of the interaction. Finally,
define

$\mathsf{avgUnitaryQIP}_{\delta}=\bigcup_{\epsilon(n)\
\mathrm{negl}}\mathsf{avgUnitaryQIP}_{1-\epsilon,\frac{1}{2},\delta}$

where the union is over all negligible functions $\epsilon(n)$, and define

$\mathsf{avgUnitaryQIP}=\bigcap_{q(n)\
\mathrm{poly}}\mathsf{avgUnitaryQIP}_{1/q(n)}$

where the intersection ranges over all polynomials $q(n)$.

For this section, we only consider single-prover interactive protocols.
However, in traditional (classical and quantum) complexity theory, multi-
prover protocols have been shown to be surprisingly powerful [BFL91, JNV+21].
It is natural to ask whether multi-prover models might also provide additional
power (and insights) in the unitary synthesis setting:

######  Open Problem 6.

Is there a meaningful notion of multi-prover unitary synthesis protocols, and
what is their power?

A related question concerns distributed protocols for unitary synthesis, where
multiple provers have to apply a unitary collectively under certain resource
constraints. Such a scenario was recently studied for state synthesis problems
[GMN22], and it is natural to ask what can be said in the unitary synthesis
setting.

######  Open Problem 7.

How are unitary synthesis problems related to distributed quantum computation?

####  4.3 Zero-knowledge protocols for state and unitary synthesis

In this section we present a notion of _zero knowledge_ for unitary synthesis
problems. _A priori_ , it is unclear how to reasonably define zero knowledge
in the unitary synthesis setting. First, defining zero-knowledge quantum
protocols for decision languages is already challenging, as the notion of
“view” in the quantum setting is less straightforward than with classical
protocols [Wat02, Wat06]. Second, in the unitary synthesis setting the
verifier additionally gets one copy of an unknown state $\ket{\psi}$ for the
quantum part of its input; this poses an additional conceptual difficulty in
trying to come up with a reasonable notion of zero knowledge simulation.

We first explore several attempts to define zero knowledge for unitary
synthesis, and highlight their shortcomings. A first attempt is to require
that the view of the verifier, when given instance $x$ and a quantum input
$\ket{\psi}$ and interacts with the honest prover, can be efficiently output
by the simulator $\mathrm{Sim}$ that only receives instance $x$ and state
$\ket{\psi}$ as input and does not interact with the prover. However, since
the verifier supposed to end up with $U_{x}\ket{\psi}$ at the end of the
protocol, this means that the simulator can output $U_{x}\ket{\psi}$ from $x$
and $\ket{\psi}$ in polynomial time, meaning that
$\mathscr{U}\in\mathsf{unitaryBQP}$. This would lead to an uninteresting
definition of zero knowledge.

A second attempt to define zero knowledge is inspired by simulation-based
security, where we allow the simulator to query the ideal Uhlmann
transformation $U_{x}$ once. In particular, the simulator gets as input the
honest verifier’s input $\ket{\psi}$, and gets a single query to $U_{x}$,
before being asked to output the verifier’s view. This still seems problematic
in the honest verifier setting, since the simulator might decide to query
$U_{x}$ on a state other than $\ket{\psi}$. If it does that, it seems tricky
to argue that the verifier does not learn anything from the interaction since
it could potentially learn the target unitary transformation applied to a
state that is completely unrelated to the input.

These difficulties point to the core issue with devising a notion of zero
knowledge in the unitary synthesis setting. With the standard definition of
zero knowledge for decision problems, the input and outputs of the verifier
are fully specified for the simulator: in particular, the simulator only has
to reproduce the interaction in the accepting case. In the unitary synthesis
setting, the verifier does not have a full classical description of what state
it is supposed to output: the classical string $x$ provides the simulator with
a complete classical description of the partial isometry $U_{x}$, but it only
gets the input state $\ket{\psi}$ in quantum form.

This motivates us to define a notion of _honest-verifier, average-case_ zero
knowledge for unitary synthesis, where we consider verifiers that get a
classical input $x$ and an input state that comes from half of a distribution
state $\ket{\psi_{x}}$. We assume the distribution state $\ket{\psi_{x}}$ has
an efficient classical description (i.e. it comes from a $\mathsf{stateBQP}$
state family). Thus, the input/output behavior of the unitary synthesis
protocol when both the verifier and prover are honest is completely specified,
which then allows for the possibility of a simulator. Although this is
seemingly a weak notion of zero knowledge, as we will see in Section 6 it
captures the complexity of the Uhlmann Transformation Problem.

######  Definition 4.3 ($\mathsf{avgUnitarySZK}_{{\mathrm{HV}}}$).

Let $c,s,\delta:\mathbb{N}\to[0,1]$ be functions. The class
$\mathsf{avgUnitarySZK}_{{\mathrm{HV}},c,s,\delta}$ is the set of
distributional unitary synthesis problems $(\mathscr{U},\Psi)$ with
$\mathscr{U}=(U_{x})_{x}$ and $\Psi=(\ket{\psi_{x}})_{x}\in\mathsf{stateBQP}$
for which there exists a polynomial-time quantum verifier
$V^{*}=(V_{x}^{*})_{x\in\\{0,1\\}^{*}}$ (called the _honest verifier_), an
unbounded prover $P^{*}$ (called the _honest prover_), and a polynomial-time
quantum algorithm $\mathrm{Sim}$ (called the _simulator_) such that for
sufficiently long $x\in\\{0,1\\}^{*}$,

  1. 1.

The prover $P^{*}$ on input $x$ is accepted with probability at least
$c(|x|)$.

  2. 2.

The verifier $V^{*}$ satisfies the soundness condition (in Definition 4.2) of
an $\mathsf{avgUnitaryQIP}_{c,s,\delta}$ verifier for $(\mathscr{U},\Psi)$.

  3. 3.

There exists a negligible function $\epsilon:\mathbb{N}\to\mathbb{R}$ such
that the simulator $\mathrm{Sim}$, on input $(x,r)$ (for $r\in\mathbb{N}$),
outputs a state $\rho$ satisfying

$\mathrm{td}(\rho,\sigma_{x,r})\leq\epsilon(|x|)$

where $\sigma_{x,r}$ is the reduced density matrix of the verifier $V^{*}_{x}$
(which was given the target register of the distribution state
$\ket{\psi_{x}}$) immediately after the $r$’th round of interaction with the
honest prover $P^{*}$.

Finally, define

$\mathsf{avgUnitarySZK}_{{\mathrm{HV}},\delta}=\bigcup_{\epsilon(n)\
\mathrm{negl}}\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1-\epsilon,\frac{1}{2},\delta}\,,$

where the union ranges over all negligible functions $\epsilon(n)$, and

$\mathsf{avgUnitarySZK}_{\mathrm{HV}}=\bigcap_{q(n)\
\mathrm{poly}}\mathsf{avgUnitarySZK}_{{\mathrm{HV}},1/q(n)}$

where the intersection ranges over all polynomials $q(n)$.

Note that the definition of $\mathsf{avgUnitaryQIP}$ (Definition 4.2 already
includes a completeness condition. However, we need to list the completeness
condition for $\mathsf{avgUnitarySZK}$ explicitly because we need to ensure
that the prover $P^{*}$ for whom the completeness condition holds is the same
as the prover $P^{*}$ in the zero-knowledge condition.

We now make several additional remarks regarding the zero knowledge
definition.

###### Simulation of the average case.

If we think of running a unitary synthesis protocol on the distribution state
$\ket{\psi_{x}}$, then from the point of view of the verifier, it is given a
pure state input $\ket{\phi}$ sampled from a distribution corresponding to the
reduced density matrix of $\ket{\psi_{x}}$. Let $\mathcal{D}_{x}$ denote this
distribution of pure states. (This distribution may not be unique because the
spectral decomposition is not unique, but the end result is the same.) Then in
this definition the simulator’s job is to produce the view of the verifier
_averaged over inputs sampled from $\mathcal{D}_{x}$._ In other words, the
simulator does not have to reproduce the view of the verifier on any specific
input state $\ket{\phi}$, just on average.

###### Complexity of the distribution state.