August 11, 2025

A Collapse-free Quantum Algorithm for a Problem in QSZK

Key Points

The algorithm effectively places the trace distance distinguishability of pure quantum states within the naCQP class.
This result impacts our understanding of the relationship between QSZK and naCQP, revealing potential overlaps.
The approach examines pure quantum states, bringing new insights on statistical zero-knowledge computations.
These findings indicate a potential path toward solving NP-intermediate problems more efficiently in quantum computing.

Abstract

The complexity class of the problems that can be solved by a quantum algorithm in a non-adaptive collapse-free model is called naCQP. This class was introduced in 2016 by Aaronson et al. intended to be a slightly larger class than BQP: larger enough to include important NP-intermediate candidate problems, but likely not to include NP-complete problems. Aaronson et al. (2016) showed that there is an oracle A for which NPA ⊈ naCQPA; and Hepp et al. (2025) showed that relative to an oracle A chosen uniformly at random, (UP ∩ coUP)A ⊈ naCQPA with probability 1, being UP ∩ coUP a subclass of NP. Amongst the NP-intermediate candidate problems in naCQP is the entire class SZK, of the problems that admit a statistical zero-knowledge interactive proof system. The relation between QSZK, which is the class of the problems that admit a quantum zero-knowledge interactive proof system, and naCQP is unknown, with some believing that there is an oracle A for which QSZKA ⊈ naCQPA. A promise problem complete for QSZK is the trace distance distinguishability of mixed quantum states. We show that this problem, when restricted to pure quantum states, is in naCQP.

Bookmark

Cite This Study

Hepp et al. (Thu,) studied this question.

synapsesocial.com/papers/68a35ee30a429f7973327adb https://doi.org/https://doi.org/10.5753/etc.2025.9268

Also Consider

Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context:

Bookmark