1

Find the complexity of Quantum Approximate Counting (QXC)

by kunal 2026-03-12
Impact 3.0
Solvability 4.0
(1 rating)

Consider the accepting POVM ($\Pi$, $I-\Pi$) of a fixed QMA machine. Let d be the number of eigenstates of $\Pi$ that are at least 2/3. Decide if d is at least some fixed s, or at most s/2.

This is a quantum version of a decision class that “approximately counts” NP witnesses. In that case, it is NP-hard and at most BPP^NP by Stockmeyer.

In the quantum case, it is QMA-hard, and it is known to be in QIP[2] (actually, qq-QAM). But is there a tighter upper bound or lower bound?

What about the complement? Is it in QMA(2)?

Discussion (0)

No comments yet. Start the discussion!

← Back to all problems