⚛️ quantum physics

Unitary complexity in polynomial space

This paper introduces robust definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$ and proves that the existence of quantum commitments implies either the hardness of the unitary synthesis problem or the separation $\mathsf{BPP} \neq \mathsf{NEXP}$ , thereby linking quantum cryptographic assumptions to major open questions in classical complexity theory.

Original authors: William Kretschmer, Ewin Tang

Published 2026-10-05

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: William Kretschmer, Ewin Tang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, there is a fundamental divide between what a machine can do quickly and what it can do if given a vast amount of memory. For decades, computer scientists have mapped out these territories, creating categories for problems that are easy to solve, problems that are hard to solve, and problems that seem impossible to solve within any reasonable timeframe. A central question in this field is whether the ability to use more memory allows a computer to solve problems that are strictly out of reach for a computer with limited time. While we have strong suspicions about the answers, many of these questions remain unproven.

Parallel to this classical world is the realm of quantum computing, where machines use the strange properties of subatomic particles to process information. Here, the rules are different. A quantum computer does not just flip bits on or off; it manipulates complex waves of probability. This allows it to perform certain tasks that would take a classical computer an eternity. However, a deep mystery has persisted: does the power of quantum computing rely on a completely new kind of hardness, or is it secretly just a very efficient version of classical computing in disguise? Specifically, researchers have wondered if every possible operation a quantum computer can perform can be broken down into a sequence of steps that a classical computer could eventually figure out, given the right hints. If the answer is yes, then the unique power of quantum cryptography might be an illusion. If the answer is no, then quantum computers possess a fundamental strength that classical machines can never replicate.

Two researchers, William Kretschmer and Ewin Tang, have recently taken a significant step toward resolving this uncertainty. They did not solve the mystery entirely, but they constructed a powerful logical bridge connecting the existence of secure quantum cryptography to some of the oldest, most stubborn unsolved problems in classical computer science. Their work suggests that if secure quantum cryptography exists in the real world, then one of two things must be true: either there is a fundamental limit to how well we can translate quantum operations into classical instructions, or a specific, decades-old question about the power of classical computers must have a surprising answer.

To understand their achievement, one must first grasp the nature of the task they are analyzing. Imagine a quantum computer as a device that can rotate a complex, multi-dimensional object in a way that is perfectly reversible. The "unitary synthesis problem" asks whether, for any such rotation, we can find a set of classical instructions that a standard computer could follow to recreate that rotation. If we could always do this, it would mean that the quantum world is, in a sense, just a very complicated version of the classical world. The researchers focused on a specific class of these rotations: those that a quantum computer can perform using a reasonable amount of memory. They asked whether these specific rotations could always be synthesized by a classical computer with the help of an oracle, which is essentially a magical black box that can instantly answer specific questions.

The authors began by addressing a practical hurdle: how to define these quantum tasks precisely. Previous attempts to categorize them had led to confusing results, partly because they allowed for "garbage" to be left behind during the calculation. In quantum computing, when a machine performs a calculation, it often leaves behind extra data that is no longer needed but cannot be simply deleted without disturbing the result. Some definitions allowed this messy leftover data, while others demanded a perfectly clean process. Kretschmer and Tang showed that for tasks involving large amounts of memory, this distinction does not matter. They proved that any messy, garbage-filled quantum process can be converted into a clean, garbage-free one without changing the fundamental difficulty of the task. This was a crucial step, as it allowed them to treat these complex quantum operations with a level of mathematical clarity that had been missing.

With these definitions in place, they tackled the core question. They demonstrated that for any quantum operation that can be performed with polynomial space (a manageable amount of memory), there are only two possibilities. Either the operation is so complex that no classical computer, no matter how clever or how much help it gets from an oracle, can ever synthesize it efficiently. Or, the operation is not that hard at all; it can be synthesized efficiently if the classical computer is allowed to ask questions about a specific type of difficult problem known as an NEXP search problem. This second category is a very high bar in classical complexity theory, representing problems that are exponentially harder than the hardest problems we currently know how to solve.

The implications of this finding are profound, particularly for the future of cryptography. Quantum cryptography relies on the idea that certain tasks, like creating a secure commitment scheme (a way to lock a secret in a digital box so it cannot be changed or peeked at), are impossible for an adversary to break. If secure quantum commitments exist, then the researchers' logic dictates that we are in a very specific situation. Either the unitary synthesis problem has a negative answer, meaning there are quantum operations that are fundamentally beyond the reach of classical synthesis, or a major classical complexity question must be resolved. Specifically, it would imply that a class of problems called BPP (problems solvable quickly with random chance) is not equal to NEXP (problems solvable with exponential time and non-determinism). This is a question that has remained open for over forty years.

In simpler terms, the paper argues that proving the existence of secure quantum cryptography is not just a matter of building better quantum devices. It is inextricably linked to the deepest theoretical limits of classical computing. If we could unconditionally prove that quantum commitments are secure, we would simultaneously be forced to answer one of two massive, decades-old riddles in computer science. We would either have to accept that quantum operations can be fundamentally harder to simulate than we thought, or we would have to prove that a specific, incredibly powerful type of classical computation is strictly more capable than a standard randomized one.

The work also sheds light on the relationship between quantum and classical power in a more general sense. The authors showed that if we assume the unitary synthesis problem has a positive answer (that everything can be synthesized), then the power of quantum computers with large memory is tightly constrained by the power of classical computers solving NEXP search problems. This suggests that the "magic" of quantum computing, if it exists, is not a free-floating phenomenon but is deeply rooted in the structure of classical complexity. If quantum computers can do something truly new, it is because they are accessing a layer of difficulty that classical computers cannot reach, even with the best possible shortcuts.

Ultimately, this research does not tell us whether quantum cryptography is secure or whether the unitary synthesis problem is solvable. Instead, it maps the terrain between these two possibilities. It reveals that the path to proving the security of quantum systems is blocked by the same walls that have kept classical complexity theorists from solving their hardest problems for half a century. The paper suggests that we cannot simply build our way to a proof; we must first understand the fundamental limits of computation itself. By clarifying the definitions and establishing these rigorous connections, Kretschmer and Tang have provided a clearer view of the landscape, showing that the fate of quantum cryptography and the destiny of classical complexity theory are bound together in a way that was not previously understood.

Technical Summary: Unitary Complexity in Polynomial Space

Problem Statement
The paper addresses the foundational complexity of quantum cryptographic primitives, specifically quantum commitment schemes, and their relationship to classical complexity theory. While classical cryptography relies on the hardness assumption $P \neq NP$ , recent oracle separations suggest quantum cryptography might exist even if $P = NP$ . This has led to the "Microcrypt" paradigm, where quantum commitments are viewed as the minimal primitive for quantum cryptography. However, the complexity-theoretic hardness underlying these commitments remains unclear.

A central unresolved issue is the unitary synthesis problem (posed by Aharonov and Knill, 2007): Does there exist a polynomial-time quantum algorithm that can implement any $n$ -qubit unitary transformation $U$ given access to a classical oracle? A positive resolution would imply that superpolynomial lower bounds for unitary implementation yield superpolynomial hardness for classical functions. Conversely, a negative resolution might not directly inform the hardness of specific cryptographic schemes.

The authors aim to probe the computational hardness of unitaryPSPACE (unitaries implementable in polynomial space) using classical complexity techniques, specifically investigating the relationship between unitary complexity classes, the unitary synthesis problem, and classical lower bounds.

Methodology and Definitions
The paper first identifies significant conceptual flaws in existing definitions of unitary complexity classes (specifically those by Bostanci et al. [BEMPQY26] and Zhandry [Zha25]). The primary issues involve:

Error Scaling: Prior definitions often scale time/space with $1/\epsilon$ (inverse polynomial in error), which leads to pathological behavior under composition (e.g., failing self-lowness) and allows "smuggling" hard problems into low-complexity classes via phase encoding.
Garbage Handling: Definitions vary on whether implementations must return ancilla qubits to the zero state (garbage-free) or allow arbitrary garbage states.

To resolve these, the authors propose new, rigorous definitions for unitaryP and unitaryPSPACE based on first principles:

Error Scaling: Complexity must scale polynomially with $\log(1/\epsilon)$ , not $1/\epsilon$ . This ensures robustness under composition and alignment with the Solovay-Kitaev theorem.
Garbage-Free vs. Projective: The authors define two classes:
- unitaryP/unitaryPSPACE: Implementations must be "clean" (ancilla reset to $|0\rangle$ ), preserving global phase.
- projUnitaryP/projUnitaryPSPACE: Implementations may produce garbage (ancilla in state $|g\rangle$ ), effectively ignoring global phase (projective unitary group).
Oracle Access: Oracles provide access to a unitary $U$ and its homomorphisms ( $U^\dagger, U^*, U^T$ , and controlled versions), ensuring composability.

Key Contributions and Results

Equivalence of Definitions (Time and Space):
- The authors prove that the "clean" and "garbage" definitions are deeply related. Specifically, $U \in \text{projUnitaryP}$ if and only if $U \otimes U^\dagger \in \text{unitaryP}$ .
- Crucially, for polynomial space, they prove a stronger result: UnitaryPSPACE can generically erase garbage. They show that for every $U \in \text{projUnitaryPSPACE}$ , there exists a $V \in \text{unitaryPSPACE}$ such that $U = \phi V$ (where $\phi$ is a global phase). This is achieved by characterizing unitaryPSPACE via the computability of matrix entries: a unitary is in unitaryPSPACE if and only if its entries can be approximated to arbitrary precision in polynomial space.
- Contrast: This garbage-erasure property fails relative to unitary oracles, where topological obstructions prevent the continuous assignment of global phases.
The Main Dichotomy (Lemma 1.2 / Lemma 7.4):
The paper establishes a fundamental dichotomy for any unitary $U \in \text{unitaryPSPACE}$ :
- Either $U$ is unitary synthesis-hard (i.e., $U \notin \text{unitaryP}^{\text{ALL}}$ , meaning it cannot be synthesized efficiently relative to any classical oracle),
- Or $U$ reduces efficiently to NEXP search problems (i.e., $U \in \text{unitaryP}^{\text{FNEXP}}$ , where FNEXP denotes access to witnesses for NEXP problems).
Implications for Cryptography and Complexity:
- Theorem 1.1: If quantum commitments (equivalent to EFI pairs) exist, then either the unitary synthesis problem has no polynomial-time solution, or $\text{BPP} \neq \text{NEXP}$ .
- This implies that an unconditional proof of the existence of quantum commitments would require resolving at least one of two longstanding open problems in complexity theory: the unitary synthesis problem (open for 20+ years) or the separation of BPP and NEXP (open for 40+ years).
- Corollary 7.10: If there exists a classical oracle $L$ relative to which $\text{unitaryP}^L_{\text{PSPACE}} \neq \text{unitaryPSPACE}^L$ , then either the unitary synthesis problem is false ( $\text{unitaryP}^{\text{ALL}} \neq \text{unitaryALL}$ ) or $\text{NC} \neq \text{NP}$ . This explains why constructing such an oracle has remained elusive.

Significance
The paper claims that its definitions provide a "robust" and "elegant" foundation for unitary complexity theory, resolving previous inconsistencies regarding error scaling and garbage. By establishing the entrywise characterization of unitaryPSPACE, the authors demonstrate that space-bounded unitary computation is tightly linked to classical complexity classes.

The primary significance lies in bridging quantum cryptography, unitary synthesis, and classical lower bounds. The authors argue that the existence of quantum commitments is not isolated from classical complexity; rather, proving their existence unconditionally would necessitate breakthroughs in classical complexity theory (specifically separating BPP from NEXP or resolving unitary synthesis). The work suggests that "Microcrypt" cannot be fully understood without addressing these deep complexity-theoretic questions.

The paper concludes by noting that while garbage erasure is possible in polynomial space, the question of whether it is possible in polynomial time (i.e., is $\text{unitaryP} = \text{projUnitaryP}$ ?) remains open, though they provide a negative answer relative to unitary oracles.

More like this