A Collapse-free Quantum Algorithm for a Problem in QSZK
Henrique Hepp, Murilo V. G. da Silva, Leandro M. Zatesko · 2025
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.