A Collapse-free Quantum Algorithm for a Problem in QSZK

Henrique Hepp; Murilo V. G. da Silva; Leandro M. Zatesko

doi:10.5753/etc.2025.9268

Henrique Hepp UFPR
Murilo V. G. da Silva UFPR
Leandro M. Zatesko UTFPR

DOI: https://doi.org/10.5753/etc.2025.9268

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 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.

References

Aaronson, S. (2018). PDQP/qpoly = ALL. URL: [link].

Aaronson, S., Bouland, A., Fitzsimons, J., and Lee, M. (2016). The space “just above” BQP. In Proc. 2016 ACM Conference on Innovations in Theor. Comp. Sci., pages 271–280.

Arora, S. and Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.

Bennett, C. H., Bernstein, E., Brassard, G., and Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523.

Hepp, H., Silva, M. V. G., and Zatesko, L. M. (2025). Oracle separations for non-adaptive collapse-free quantum computing. Theor. Comput. Sci., 1030:115078.

Kitaev, A. Y. (1995). Quantum measurements and the abelian stabilizer problem. arXiv preprint quant-ph/9511026.

Nielsen, M. A. and Chuang, I. L. (2010). Quantum Computation and Quantum Information. Cambridge University Press, 1st edition.

Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proc. 35th annual symposium on foundations of computer science, pages 124–134.

Watrous, J. (2002). Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd Annual IEEE Symposium on Foundations of Comp. Sci., pages 459–468.

Watrous, J. (2018). The Theory of Quantum Information. Cambridge University Press, 1st edition.