A Collapse-free Quantum Algorithm for a Problem in QSZK - Hepp, Henrique; Silva, Murilo V. G. da; Zatesko, Leandro M. (Anais do Encontro de Teoria da Computação (ETC); 2025: Anais do X Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2025.9268, 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 NP A ⊈ naCQP A ; and Hepp et al. (2025) showed that relative to an oracle A chosen uniformly at random, (UP ∩ coUP) A ⊈ naCQP A 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 QSZK A ⊈ naCQP A . 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.