Unitary Complexity and the Uhlmann Transformation Problem

We begin by giving general definitions for unitary synthesis problems and a number of useful unitary complexity classes, e.g. $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖡𝖰𝖯}$ and $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$. We then define a notion of reductions between unitary synthesis problems. Roughly speaking, we say that a unitary synthesis problem $𝒰={(U_x)}_x$ polynomial-time reduces to $𝒱={(V_x)}_x$ if an efficient algorithm for implementing $𝒱$ implies an efficient algorithm for implementing $𝒰$.

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 $𝒟$ which is known ahead of time. This is a natural generalisation of traditional average-case complexity statements to the unitary setting. This notion turns out to be particularly natural in the context of entanglement transformation problems because it is closely related to implementing the unitary on part of an entangled state $|\psi ⟩$.

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 $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖡𝖰𝖯}$ and $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$, 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 then explore models of interactive proofs for unitary synthesis problems. Roughly speaking, in an interactive proof for a unitary synthesis problem $𝒰={(U_x)}_x$, a polynomial-time verifier receives an instance $x$ and a quantum system $𝖡$ as input, and interacts with an all-powerful but untrusted prover to try to apply $U_x$ to system $𝖡$. 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 $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}$ and $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}$, which capture unitary synthesis problem that can be verifiably implemented in this interactive model. This generalizes the interactive state synthesis model studied by [49, 40].⁴⁴4The class $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}$ was also briefly discussed informally by Rosenthal and Yuen [49]. 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 $𝖡$ in an unknown state that has to be transformed by $U_x$.

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 [21]. The counterintuitive concept of zero-knowledge proofs has been one of the most consequential discoveries in complexity theory and cryptography.

Motivated by this, we introduce the unitary complexity class $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖲𝖹𝖪}$,⁵⁵5The “$\mathrm{𝖧𝖵}$” modifier signifies that the zero-knowledge property is only required to hold with respect to verifiers that honestly follow the protocol, and the “$𝖲$” in “$\mathrm{𝖲𝖹𝖪}$” signifies that it is statistical zero-knowledge. which is a unitary synthesis analogue of the decision class $\mathrm{𝖧𝖵𝖰𝖲𝖹𝖪}$ in traditional complexity theory [57], which captures the concept of honest-verifier quantum zero-knowledge proofs. Interestingly, for reasons that we explain in more detail in [13], the average-case aspect of $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖲𝖹𝖪}$ 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 [3], 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.

We show that the Uhlmann Transformation Problem (with fidelity parameter $\kappa =1$) characterizes the complexity of the unitary complexity class $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖯𝖹𝖪}$, which is the unitary synthesis version of the decision classes $\mathrm{𝖯𝖹𝖪}$ and $\mathrm{𝖧𝖵𝖰𝖯𝖹𝖪}$ [56]. Here, $\mathrm{𝖯𝖹𝖪}$ stands for “perfect zero knowledge”, and refers to the special case of statistical zero-knowledge where the simulator can perfectly reproduce the view of the verifier.

This is formally stated and proved in [13, Section 6.1]. To show completeness we have to prove two directions. The first direction is to show that every (distributional) unitary synthesis problem in $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖯𝖹𝖪}$ polynomial-time reduces to (the distributional version of) ${\text{Uhlmann}}_1$. This uses a characterization of quantum interactive protocols due to Kitaev and Watrous [33].

The second direction is to show that ${\text{Uhlmann}}_1$ is in $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖯𝖹𝖪}$ 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 $|C⟩=C|0^{2n}⟩$, and the other half is inaccessible. Its goal is to transform, with the help of a prover, the global state $|C⟩$ to $|D⟩$ by only acting on the last $n$ qubits that it received as input. To this end, the verifier generates a “test” copy of $|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 $𝖠$) 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 $|C⟩$ has been transformed to $|D⟩$ by applying the inverse circuit $D^{†}$ to the test copy and checking if all qubits are zero. If so, it accepts and outputs the register $𝖠$, otherwise the verifier rejects.

If the prover is behaving as intended, then both the test copy and the “true” copy of $|C⟩$ are transformed to $|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 $|C⟩⟨C|\otimes \rho$ (where $\rho$ is the reduced density matrix of $|C⟩$), and at the end of the protocol, the verifier’s state is $|D⟩⟨D|\otimes U\rho U^{†}$. Both states can be produced in polynomial time.

One may ask: if the simulator can efficiently compute the state $U\rho U^{†}$ 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^{†}$ is (approximately) the reduced state of $|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.

It is natural to wonder about the complexity of ${\text{Uhlmann}}_{\kappa }$ for fidelity promise . In other words, the reduced density matrices of the two states $|C⟩,|D⟩$ are not exactly equal. A reasonable conjecture is that ${\text{Uhlmann}}_{\kappa }$ (for non-negligible $\kappa$, say), is complete for $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖲𝖹𝖪}$. This would correspond to the famous classical complexity result that the problem of distinguishing between whether two probability distributions (represented via sampling circuits) are close or far in trace distance is a $\mathrm{𝖲𝖹𝖪}$-complete problem [50].

In [13, Section 6.3] we argue that this conjecture is true assuming that a unitary version of the polarization lemma holds, which was instrumental for the $\mathrm{𝖲𝖹𝖪}$-completeness result of Sahai and Vadhan [50]. The unitary polarization lemma, if true, would state that ${\text{Uhlmann}}_{\kappa }$ polynomial-time reduces to ${\text{Uhlmann}}_{1-2^{-\mathrm{poly}(n)}}$ for all inverse polynomial $\kappa$.

We also define a succinct version of the Uhlmann Transformation Problem (denoted by SuccinctUhlmann), where the string $x$ encodes a pair $(\widehat{C},\widehat{D})$ of succinct descriptions of quantum circuits $C,D$. By this we mean that $\widehat{C}$ (resp. $\widehat{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 $|C⟩,|D⟩$ that are unlikely to be synthesizable in polynomial time. Thus the task of synthesizing the Uhlmann transformation $U$ that maps $|C⟩$ to a state with maximum overlap with $|D⟩$, intuitively, should be much harder than the non-succinct version. We confirm this intuition with the following result:

The class $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ corresponds to distributional unitary synthesis problems that can be solved using a polynomial-space (but potentially exponential-depth) quantum algorithm. The fact that $\text{SuccinctUhlmann}\in \mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ was already proved by Metger and Yuen [40], who used this to show that optimal prover strategies for quantum interactive proofs can be implemented in $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$.⁶⁶6This was phrased in a different way in their paper, as $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ was not yet defined. The fact that $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ reduces to SuccinctUhlmann is because solving a distributional unitary synthesis problem ${(U_x)}_x$ in $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ is equivalent to applying a local unitary that transforms an entangled state $|{\psi }_x⟩$ representing the distribution to $(\mathrm{𝟙}\otimes U_x)|{\psi }_x⟩$. This is nothing but an instance of the SuccinctUhlmann transformation problem. We refer to the proof of [13, Lemma 7.5] for details.

We show another completeness result for SuccinctUhlmann:

Here, the class $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}$ is like $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖯𝖹𝖪}$ except there is no requirement that the protocol between the honest verifier and prover can be efficiently simulated. The proof of Theorem 4 starts similarly to the proof of the $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖧𝖵𝖯𝖹𝖪}$-completeness of Uhlmann, but requires additional ingredients, such as the state synthesis protocol of [49, 48] and the ability to simulate reflections about a state, given copies of the state [29]. We prove this by showing that SuccinctUhlmann is contained in $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}$, $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}\subseteq \mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$, and then argue that $\mathrm{𝖺𝗏𝗀𝖴𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ is polynomial-time reducible to SuccinctUhlmann (see [13] for details).

Theorems 3 and 4 imply the following unitary complexity analogue of the $\mathrm{𝖰𝖨𝖯}=\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ theorem [28] and the $\mathrm{𝗌𝗍𝖺𝗍𝖾𝖰𝖨𝖯}=\mathrm{𝗌𝗍𝖺𝗍𝖾𝖯𝖲𝖯𝖠𝖢𝖤}$ theorem [49, 40]:

This partially answers an open question of [49, 40], who asked whether $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖰𝖨𝖯}=\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$ (although they did not formalize this question to the same level as we do here).

An important source of the richness of computational complexity theory is the variety of computational problems that are studied. For example, the class $\mathrm{𝖭𝖯}$ is so interesting because it contains many complete problems that are naturally studied across the sciences [45], and the theory of $\mathrm{𝖭𝖯}$-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 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 e.g. quantum error-correction, quantum metrology, quantum chemistry, or condensed matter physics, and what can we say about their computational complexity?

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 [29] or one-way state generators [41] 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 [27, 26, 36]. Do analogous results hold in the fully quantum setting?

Quantum learning theory has also seen rapid development, particularly on the topic of quantum state learning [1, 25, 18, 9]. 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?

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 $𝖯=\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}$ does not imply $\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖡𝖰𝖯}=\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}$? One would likely have to show this in a relativized setting, i.e., exhibit an oracle $O$ relative to which ${𝖯}^O={\mathrm{𝖯𝖲𝖯𝖠𝖢𝖤}}^O$ but ${\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖡𝖰𝖯}}^O\ne {\mathrm{𝗎𝗇𝗂𝗍𝖺𝗋𝗒𝖯𝖲𝖯𝖠𝖢𝖤}}^O$. Another way would be to settle Aaronson and Kuperberg’s “Unitary Synthesis Problem” [4] in the negative; see [38] for progress on this. Such results 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. More generally, what are other ways of separating traditional from fully quantum complexity theory?