A Meta-Complexity Characterization of Minimal Quantum Cryptography

Bruno Pasqualotto Cavalar, Boyang Chen, Andrea Coladangelo, Matthew Gray, Zihan Hu, Zhengfeng Ji, Xingjian LiECCC 2025

TL;DR

This paper establishes a fundamental link between quantum cryptography and "meta-complexity"—the study of how hard it is to determine the complexity of an object. The authors prove that the most basic building block of quantum cryptography (EFI pairs) exists if and only if it is computationally hard to estimate the "quantum Kolmogorov complexity" of a quantum state given just a single copy.

What Problem Does This Paper Address?

In classical cryptography, the "holy grail" is finding the minimum complexity assumption required for secure communication. We know that One-Way Functions (OWFs) are the "minimal" primitive for most classical tasks. Recently, researchers found a "meta-complexity" characterization for OWFs: they exist if and only if problems like the Minimum Circuit Size Problem (MCSP) are hard.

Quantum cryptography is a different beast. Primitives like EFI pairs (pairs of quantum states that are Efficiently samplable, statistically Far apart, but computationally Indistinguishable) can exist even in worlds where classical OWFs do not. These EFI pairs are considered the "minimal" primitive for quantum cryptography, as they are equivalent to quantum bit commitments and multiparty computation.

Until now, we lacked a meta-complexity characterization for this quantum "minimal" world (often called NanoCrypt). This paper fills that gap by asking: Is the existence of quantum cryptography equivalent to the hardness of calculating the complexity of quantum states?

Methods

The authors use several sophisticated theoretical tools to bridge the gap between state complexity and cryptographic security:

  1. Quantum Kolmogorov Complexity: They focus on Gács’ "quantum algorithmic entropy" ($H$-complexity) and a related measure they call $U$-complexity (based on relative min-entropy). These measures essentially ask: "What is the shortest classical program that can produce this quantum state?"
  2. The 1-PRS Bridge: A major technical contribution is proving that EFI pairs are equivalent to non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). These are generators that produce states looking like Haar-random states to any efficient observer who only sees one copy.
  3. Quantum Randomness Extractors: To move from complexity to indistinguishability, the authors use quantum extractors (specifically based on Clifford 2-designs). This allows them to "extract" the high entropy inherent in high-complexity states to create states that are statistically close to the maximally mixed state.
  4. Non-uniformity: The proofs require a small amount of "advice" ($O(\log \lambda)$ bits), leading to a non-uniform characterization. This advice typically represents an estimate of the von Neumann entropy of the states involved.

Datasets

As a theoretical paper in computational complexity, no empirical datasets were used. The "data" consists of mathematical constructions of quantum state families, specifically:

  • Haar-random states (the gold standard for quantum randomness).
  • Keyed state families (where a classical key determines the quantum state).
  • Unkeyed state families (more general families where the state might not be reproducible even with the key).

Key Insights and Ideas

  • Complexity $\iff$ Entropy: The "aha moment" is the tight relationship between a state's Kolmogorov complexity and its von Neumann entropy. If a state has low complexity, it must have low entropy (it's "simple"). If it's hard to tell if a state is simple or complex, you can use that hardness to build a cryptographic primitive.
  • The Power of a Single Copy: Unlike previous work that required many copies of a state (which can be broken by "shadow tomography"), this paper focuses on the single-copy regime. This is what makes the characterization truly "minimal" and places it in the NanoCrypt category.
  • Universal EFI: By showing the equivalence to 1-PRS, the authors provide a new, simpler way to build a "Universal EFI pair"—a single construction that is guaranteed to be secure if any EFI pair exists.
  • The "Span of Easy States": They show that EFI existence is equivalent to the hardness of deciding whether a state lies in the linear span of all "easy" (low-complexity) states.

Key Results

  • Theorem 1.1: EFI pairs exist if and only if non-uniform 1-PRS generators exist with $O(\log \lambda)$ advice.
  • Theorem 1.2: EFI pairs exist if and only if the GapH problem (estimating quantum Kolmogorov complexity) is hard on average for a non-uniform family of states.
  • Theorem 10.1: The characterization holds even for unkeyed state families, which are relevant for advanced quantum primitives like quantum money and quantum lightning.
  • Simplification: The work provides a more direct path to universal quantum primitives than previous "combiner" methods.

Limitations and Future Work

  • The Non-Uniformity Gap: The current characterization is non-uniform (it requires a tiny bit of classical advice). A major open question is whether EFI pairs are equivalent to uniform 1-PRS or if a uniform meta-complexity characterization exists.
  • One-Way State Generators (OWSGs): While EFI pairs are characterized here, other primitives like OWSGs (which are thought to be strictly stronger) still lack a meta-complexity characterization.
  • Quantum Learning: In the classical world, the non-existence of OWFs implies that many things are easy to learn. The authors suggest exploring whether the non-existence of EFI pairs would similarly make quantum circuit learning or state synthesis easy.

Summary updated

BibTeX
@article{cavalar2025meta,
  author = {Bruno Pasqualotto Cavalar and Boyang Chen and Andrea Coladangelo and Matthew Gray and Zihan Hu and Zhengfeng Ji and Xingjian Li},
  title = {{A Meta-Complexity Characterization of Minimal Quantum Cryptography}},
  journal = {Electron. Colloquium Comput. Complex.},
  year = {2025},
}

Loading related content...

Figure