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.
Foundational results in theoretical computer science have established that everything provable, is provable in zero knowledge. However, this assertion fundamentally assumes a classical interpretation of computation and many interesting physical statements that one can hope to prove are not characterized. In this work, we consider decision problems, where the problem instance itself is specified by a (pure) quantum state. We discuss several motivating examples for this notion and, as our main technical result, we show that every quantum problem that is provable with an interactive protocol, is also provable in zero-knowledge. Our protocol achieves unconditional soundness and computational zero-knowledge, under standard assumptions in cryptography. In addition, we show how our techniques yield a protocol for the Uhlmann transformation problem that achieves a meaningful notion of zero-knowledge, also in the presence of a malicious verifier.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or
BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in
unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for
NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving
unitaryPSPACE would imply breakthrough classical lower bounds such as
NC=NP.
Along the way, we propose new definitions for the unitary complexity classes
unitaryP and
unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that
unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that
unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
Many natural problems in quantum computing involve constructing a quantum state or implementing a unitary transformation. However, relatively little is known about the computational complexity of these problems compared to that of computing boolean functions. In this thesis we do the following:• We prove upper bounds on the complexity of constructing arbitrary states and implementing arbitrary unitaries with the help of a classical oracle. • We prove bounds on the complexity of computing parity in QAC0, a quantum analogue of AC0, by way of a reduction to the task of constructing a certain type of state. • We prove upper bounds on the circuit size and depth required to construct arbitrary states and implement arbitrary unitaries, in various quantum circuit models. Many of these bounds are tight. • We define models of interactive proofs for constructing states and implementing unitaries with the help of an untrusted prover. We prove a quantum state analogue of the inclusion PSPACE ⊆ QIP, and obtain somewhat analogous results for unitaries and with multiple entangled provers. • We present barriers to improving several of the above results.
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion
PSPACE⊆IP: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.
Testing the symmetries of quantum states and channels provides a way to assess their usefulness for different physical, computational, and communication tasks. Here, we establish several complexity-theoretic results that classify the difficulty of symmetry-testing problems involving a unitary representation of a group and a state or a channel that is being tested. In particular, we prove that various such symmetry-testing problems are complete for bounded-error quantum polynomial time, quantum Merlin–Arthur (QMA), quantum statistical zero-knowledge, two-message quantum interactive proofs (QIPs), two-message QIPs restricted to entanglement-breaking provers, and QIPs, thus spanning the prominent classes of the QIP hierarchy and forging a nontrivial connection between symmetry and quantum computational complexity. Finally, we prove the inclusion of two Hamiltonian symmetry-testing problems in QMA and quantum Arthur–Merlin, while leaving it as an intriguing open question to determine whether these problems are complete for these classes.
Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE
⊆ stateQIP.Our main result is the reverse inclusion, stateQIP
⊆ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.