On quantum interactive proofs with a laconic prover

Interactive proof systems with a laconic prover, studied by Goldreich, Vadhan, and Wigderson (CC, 2002), capture problems verifiable with logarithmic prover communication in the classical setting. For two-message quantum analogs, even a single-bit prover response contains quantum statistical zero-knowledge (QSZK), introduced by Watrous (FOCS 2002). However, restricting the verifier's question to classical public coins collapses the corresponding class to BQP, as shown by Beigi, Shor, and Watrous (ToC, 2011). We further study two-message quantum interactive proof systems with a laconic prover. To this end, we introduce the class QIP- bit(2), where is the length of the prover's response, and establish: 1. A natural complete characterization of QIP- bit(2) by Multi-State Distinguishability. In particular, Quantum State Distinguishability (QSD) is QIP bit-complete. Since QSD is QSZK-hard, our result places QIP- bit(2), for at least 2, in a landscape "just above" QSZK. 2. Easy regimes for QIP- bit(2) collapsing to QSZK. We prove that QSD [a,b] (and thus QIP bit[a,b]) is in QSZK when a(n)-b(n) at least 1/O(n), and combine this with an answer compression from QIP- bit[2,c,s] to QIP bit to obtain another easy regime when 2c>(1+2/2)s. Remarkably, our improved polarization applies to SD and SZK, resolving an open problem in Sahai and Vadhan (JACM, 2003). 3. Quantum public coins also make the interaction useless: qc- QAM [O(sqrt)] with constant gap is in BQP, where qc- QAM [] is a subclass of QIP- bit(2) in which the verifier's question is exactly halves of EPR pairs.