Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2306.13073 · Leibniz international proceedings in informatics

Unitary Complexity and the Uhlmann Transformation Problem

John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen

Published Jun 22, 2023• 51 citations
arXivHTMLPDF

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.

DOI
10.3929/ethz-c-000799854

Related papers

Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{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 $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{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 $\mathsf{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 $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

quant-pharXiv:2610.03705•Oct 5, 2026•2 citations

unitaryQIP = unitaryPSPACE

Entong He, Fengning Ou, Mingnan Zhao

Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: $\mathsf{unitaryQIP}$ and $\mathsf{unitaryPSPACE}$ for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ and thereby establish a unitary-complexity analogue of $\mathsf{QIP} = \mathsf{PSPACE}$ (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and $\mathsf{stateQIP}=\mathsf{statePSPACE}$ (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove $\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}$, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that $\mathsf{unitaryPSPACE}$ families can be synthesized in polynomial time with a $\mathsf{PSPACE}$ oracle. We then implement the oracle queries using auxiliary states prepared via the $\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}$ protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for $\mathsf{unitaryPSPACE}$ can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of $\mathsf{EFI}$ pairs.

quant-pharXiv:2611.02819•Nov 3, 2026•0 citations

Quantum State and Unitary Complexity

Gregory Rosenthal

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.

•Nov 1, 2023•0 citations

Interactive Proofs for Synthesizing Quantum States and Unitaries

Gregory Rosenthal, Henry Yuen

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 $\mathsf{PSPACE} \subseteq \mathsf{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.

arXiv:2108.07192•Leibniz international proceedings in informatics•Aug 16, 2021•22 citations

stateQIP = statePSPACE

Tony Metger, Henry Yuen

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 $\subseteq$ stateQIP.Our main result is the reverse inclusion, stateQIP $\subseteq$ 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.

arXiv:2301.07730•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•27 citations

Quantum computational complexity and symmetry

Soorya Rethinasamy, Margarite L. LaBorde, Mark M. Wilde

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.

arXiv:2309.10081•Canadian Journal of Physics•Oct 15, 2024•7 citations
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.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP≠NEXP\mathsf{BPP} \neq \mathsf{NEXP}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\mathsf{unitaryPSPACE}unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP\mathsf{NEXP}NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE would imply breakthrough classical lower bounds such as NC≠NP\mathsf{NC} \neq \mathsf{NP}NC=NP. Along the way, we propose new definitions for the unitary complexity classes unitaryP\mathsf{unitaryP}unitaryP and unitaryPSPACE\mathsf{unitaryPSPACE}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\mathsf{unitaryPSPACE}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\mathsf{unitaryPSPACE}unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: unitaryQIP\mathsf{unitaryQIP}unitaryQIP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality unitaryQIP=unitaryPSPACE\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}unitaryQIP=unitaryPSPACE and thereby establish a unitary-complexity analogue of QIP=PSPACE\mathsf{QIP} = \mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and stateQIP=statePSPACE\mathsf{stateQIP}=\mathsf{statePSPACE}stateQIP=statePSPACE (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove unitaryQIP⊆unitaryPSPACE\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}unitaryQIP⊆unitaryPSPACE, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE families can be synthesized in polynomial time with a PSPACE\mathsf{PSPACE}PSPACE oracle. We then implement the oracle queries using auxiliary states prepared via the statePSPACE⊆stateQIP\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}statePSPACE⊆stateQIP protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of EFI\mathsf{EFI}EFI pairs.
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\mathsf{PSPACE} \subseteq \mathsf{IP}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.
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 ⊆\subseteq⊆ stateQIP.Our main result is the reverse inclusion, stateQIP ⊆\subseteq⊆ 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.
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.