On quantum interactive proofs with a laconic prover

1 Introduction

• Two-message quantum proofs with a laconic prover merit study because quantum proofs parallelize to three messages, while the two-message setting remains mysterious.The model also connects to succinct non-interactive protocols: moving an instance-independent verifier question to setup leaves only the laconic response online, informing the possibility of succinctness and statistical soundness together.Source: §1 · p. 3

1.1 Main results

• The authors take prover responses to be classical and define QIPℓ-bit(2) for two-message proofs with an ℓ-bit response and inverse-polynomial completeness-soundness gap.Quantum responses can be simulated by classical responses twice as long using teleportation and superdense coding, preserving completeness and soundness.Source: §1.1 · pp. 3–4
• QIPℓ-bit has a complete characterization by MultiQSD for ℓ = O(log n), and QSD is QIPbit-complete, placing these classes just above QSZK.MultiQSD asks for the optimal probability of identifying a uniformly chosen label from an ensemble of quantum states; for ℓ = 1 it recovers QSD.Source: §1.1 · p. 4
• For sufficiently large n, if 0 ≤ b(n) < a(n) ≤ 1 and a(n) − b(n) ≥ 1/O(log n), then QSD[a,b] ∈ QSZK and SD[a,b] ∈ SZK; under analogous c,s bounds, QIPbit[c,s] ⊆ QSZK and IPbit[c,s] ⊆ SZK.Theorem 1.2 is described as the first approach to bypass the oblivious black-box polarization barrier in [HR05, Corollary 2].Source: §1.1 · p. 5
• Answer compression reduces an ℓ-bit QIP response to one bit when c > (1 + 2^(ℓ/2))s/2, yielding another easy regime through QSD.The reduction uses pairwise-independent hashing to encode the ℓ-bit response label as a single bit and bounds its guessability using quantum-side-information extraction.Source: §1.1 · p. 5, §1.2 · p. 7
• Quantum public coins make interaction useless in qc-QAM; in the single-bit case, qc-QAM[1] is in BQP for every inverse-polynomial gap.The underlying quantum algorithm remains efficient whenever ℓ^2/∆^6 = O(log n).Source: §1.1 · p. 6

1.2 Proof techniques: Hardness results and answer compression

• To characterize hardness and compress answers, the authors express verifier acceptance as optimization over the prover’s POVM, then pad subnormalized states into normalized states whose distinguishability reflects acceptance.The ℓ = 1 construction uses binary state discrimination; for larger ℓ, a padding scheme relates the optimal discrimination probability to the verifier’s maximum acceptance probability.Source: §1.2 · p. 6

1.3 Proof techniques: Polarizing the ℓ1-norm distances in the natural regime

• To polarize trace distance in the natural regime, the authors use signed combinations of quantum Jensen–Shannon divergences whose cancellation approximates trace distance with additive error.They encode the approximation as an entropy difference, so the required separation depends on a − b rather than a^2 − b.Source: §1.3 · p. 8
• When a(n)-b(n) ≥ 1/O(log n), the constructed QED instance retains an inverse-polynomial promise gap, placing QSD[a,b] in QSZK.The resulting gap is at least Δ·2^-O(1/Δ), where Δ=a-b; the same polarization also resolves the first open problem posed in.Source: §1.3 · p. 9, §1.5 · p. 11

1.4 Proof techniques: Quantum public coins also make interaction useless

• SteerVal[ℓ,a,b], defined by the steering-game value, is complete for qc-QAM[ℓ,a,b].The game models a prover measuring her halves of shared EPR pairs and sending an ℓ-bit outcome for the verifier’s test.Source: §1.4 · p. 9
• For constant gap and ℓ=O(√log n), qc-QAM is contained in BQP via quantum estimation of the steering-game value.The algorithm estimates that value to constant additive error in time poly(n,ℓ,1/Δ) exp(O(ℓ²/Δ⁶)).Source: §1.4 · pp. 10–11

1.5 Discussion and open problems

• Whether quantum-public-coin proofs with ℓ=O(log n) and inverse-polynomial promise gap are contained in BQP remains open.The result here establishes containment only for ℓ=O(√log n) with constant gap.Source: §1.5 · p. 11
• Whether SD[a,b] is in SZK and QSD[a,b] is in QSZK for inverse-polynomial gaps remains open, and the approach’s normalization factor obstructs resolving it.Within the signed-approximation family, the coefficient norm must be at least 2^Ω(1/ε), making the coefficient bound optimal up to constants in the exponent and requiring new ideas.Source: §1.5 · p. 11

2 Preliminaries

• Quantum register notation includes positive semidefinite operators, density operators, maximally entangled states, and an all-zero state whose length is context-dependent.The maximally entangled state is defined for two m-qubit registers, and the all-zero register length is polynomially bounded in the relevant input length.Source: §2 · p. 11

2.1 Complexity classes

• QIP[2,c,s] restricts prover responses to either ℓ-qubit states or ℓ-bit computational-basis states, while qc-QAM uses EPR-pair questions and bit responses.The related qq-QAM and qc-QAM classes are equivalent when the bit response length is twice the qubit response length.Source: §2.1 · pp. 12–13

2.2 Quantum state distinguishability and mixed-state preparation

• QSD distinguishes circuit-generated output states whose trace distance is at least a(n) from those whose distance is at most b(n).A dyadic convex combination of J states can be prepared by circuits that query each state-preparation circuit once, using O(J(L + r + log J)) additional gates.Source: §2.2 · p. 13

2.3 Information-theoretic measures for distributions and states

• The information-theoretic toolkit defines total variation and trace distances, Shannon and quantum entropies, quantum Jensen–Shannon divergence, and hockey-stick divergence.For smoothed states, quantum Jensen–Shannon divergence also has an integral representation using a symmetrized hockey-stick divergence.Source: §2.3 · pp. 14–16

2.4 Quantum algorithmic toolkit

• Block-encoding and QSVT provide polynomial transformations of Hermitian operators, with degree-d circuits using O(d) block-encoding applications and O((a + 1)d) additional gates.The toolkit also gives an efficiently computable even polynomial approximation to absolute value with degree at most ⌈β/η⌉ and error at most η.Source: §2.4 · pp. 16–17
• An efficiently computable polynomial approximates e^(κ(x−1)) within η on [−1,1] while remaining bounded by 1 there.The exponential approximation is provided for κ ≥ 0 and η ∈ (0, 1/2).Source: §2.4 · p. 17
• An efficiently computable odd polynomial approximates sgn(x) within η outside (−δ, δ) on [−2,2], with degree O(ln(1/η)/δ) and magnitude at most 1.This guarantee holds for δ > 0 and η ∈ (0, 1/2).Source: §2.4 · p. 17
• The LCU method combines block-encodings of operators, with polynomial gate cost when the number of terms and each implementation's gate cost are polynomial.The construction uses no additional ancillary qubits for implementing the combination unitary.Source: §2.4 · pp. 17–18
• Normalized trace estimation achieves additive error ε+δ with success probability at least 8/π^2, using O(α/ε) queries and O(α(m+a)/ε) additional gates.For Hermitian A, the estimate is of Tr(A)/2^m.Source: §2.4 · p. 18

3.2 A complete problem for QIPℓ-bit via distinguishing multiple states

• MultiQSD on 2^ℓ states is QIPℓ-bit-complete for efficiently computable ℓ=O(log n).The verifier samples a label s, sends its state ρs, and accepts the prover's ℓ-bit answer exactly when it matches s; completeness and soundness follow from the ensemble's optimal discrimination probability.Source: §3 · p. 19, §3.2 · pp. 22–23

3 QIP(2) with a laconic prover: the landscape “just above” QSZK

• Distinguishing low from high conditional min-entropy gives another QIPℓ-bit-complete problem for ℓ=O(log n).For the associated classical-quantum state, 2^-H∞(J|M) equals the optimal probability of guessing the label [KRS09, Theorem 1], which is the ensemble's MultiQSD success probability.Source: §3 · p. 19

3.1 Warm-up: QSD is QIPbit-complete

• QSD is QIPbit-complete: two circuit-prepared states have trace distance that captures the maximum acceptance probability of a cheating prover.The completeness and hardness directions establish the characterization; QSD (and thus QSZK) is also in QIPbit [BSW11, Section 5].Source: §3 · p. 19, §3.1 · pp. 20–22

3.2 A complete problem for QIPℓ-bit via distinguishing multiple states

• For uniform verifiers, the reduction maps yes and no instances to corresponding MultiQSD instances of size |x|+c, with ℓ derivable from the verifier description and |x|.The yes-instance mapping and size bound are stated for uniform verifiers; the no-instance mapping has the same size.Source: §3.2 · p. 25

4 Easy regimes for QIPℓ-bit(2) that collapse to QSZK

• If 2c > (1 + 2^(ℓ/2))s, the prover’s ℓ-bit response can be compressed to one bit, yielding an easy regime for QIPℓ-bit.The result applies for positive integer-valued ℓ = O(log n) and is an answer-compression theorem for QIPℓ-bit.Source: §4 · pp. 25–26
• When a(n) − b(n) ≥ 1/O(log n), QSD[a,b] and the corresponding one-bit QIP class lie in QSZK, and QIP_bit = co-QIP_bit.The complement equality follows from QSD’s QSZK-hardness, its inclusion in QIP_bit, and QSZK closure under complement [Wat02] [Wat09].Source: §4 · p. 25, §4.1 · p. 26, §4.1.2 · p. 31

4.1.1 Approximating the trace distance

• A signed linear combination of quantum Jensen–Shannon divergences approximates trace distance, enabling the reduction from QSD to Quantum Entropy Difference.The approximation uses coefficients from an efficiently computable uniform polynomial approximation of the absolute-value function.Source: §4.1 · p. 26

4.1 Polarizing the trace distance in the natural regime

• The proof strategy underlying Theorem 4.4 also applies to polarizing total variation distance, thereby resolving the first open problem posed in [SV03, Section 6].Source: §4.1 · p. 26

4.1.2 Implementing the QED instance

• Reducing QSD[a,b] to QED[g] with inverse-polynomial g puts the natural-gap QSD problem in QSZK, since QED[g] lies in QSZK.The QED containment holds for every efficiently computable g(n) ≥ 1/poly(n).Source: §4.1.2 · pp. 30–31
• The QED-instance construction achieves an entropy gap g(n) ≥ n−O(1), sufficient to apply Lemma 4.9.The circuit descriptions and circuit sizes are computable in poly(n,1/∆) time and size.Source: §4.1.2 · p. 33

4.2 Answer compression from QIPlog -bit(2) to QIPbit via QSD

• Theorem 4.10 gives answer compression for QIPℓ-bit via QSD when ℓ(n) is efficiently computable, positive, and O(log n), with efficiently computable a and b satisfying 0 ≤ b(n) < a(n) ≤ 1.For n ≥ c, the shifted parameters are a′(n)=a(n−c), b′(n)=b(n−c), and ℓ′(n)=ℓ(n−c).Source: §4.2 · p. 33
• The compression hashes the prover’s ℓ-bit answer with an affine inner-product pairwise-independent family, making the hashed index nearly uniform in the soundness analysis.The proof compares states containing a uniformly random bit and the hashed result, using the hashed-state lemma to establish soundness.Source: §4.2 · p. 35

5.1 A complete problem for qc-QAM[ℓ] via 2ℓ-ary steering-game values

• The 2^ℓ-ary steering-game value problem is complete for qc-QAM[ℓ], providing a complete characterization of these two-message quantum public-coin proof systems.The steering game naturally aligns with an ℓ-bit prover response.Source: §5 · p. 36, §5.1 · p. 37
• For inverse-polynomial gap, qc-QAM[1] equals BQP; the proof estimates the closed-form binary steering-game value and compares it with the midpoint threshold.The estimate has additive error 3∆/16 with probability at least 3/4, using O(1/∆^2) queries to the verifier circuits.Source: §5.1 · pp. 38, 39, 41

with constant gap is in BQP

• qc-QAM[O(sqrt(log n))] with constant gap is in BQP, using matrix multiplicative weights and QSVT to estimate updates without materializing exponentially large matrices.Theorem 5.6 applies when the prover sends O(sqrt(log n)) bits and the promise gap is Θ(1).Source:
  with constant gap is in BQP · p. 41

5.3.1 Approximating the 2^ℓ-ary steering-game value

• Replacing the SDP constraint with a trace-norm penalty yields an approximation whose maximum lies between MSV(ℓ; Q) and MSV(ℓ; Q) + ε.This provides a matrix-multiplicative-weights-friendly approximation of the steering-game value.Source: §5.3.1 · p. 42

5.3.1 Approximating the 2ℓ-ary steering-game value

• The multiplicative-weights bound replaces the dimension term ln(2^ℓd_R) with ℓln 2, removing dependence on d_R.A block-diagonal optimal state satisfies ρ ⪯ I_I ⊗ I_R/d_R, giving relative entropy D(ρ∥ρ_1) ≤ ℓln 2.Source: §5.3.1 · p. 43

5.3.2 Proof of Theorem 5.6

• The proof solves the complete SteerVal problem by estimating the steering-game value and comparing it with the completeness–soundness threshold.The estimate is within additive error ∆/8 with probability at least 9/10.Source: §5.3.2 · pp. 43, 47
• The constructed block-encodings have gate complexity bounded by poly(n, ℓ, 1/∆) exp(O(ℓ²/∆⁶)).This bound applies to each E_t for t ∈ [T].Source: §5.3.2 · p. 48
• Classical computations, including generating circuit descriptions, take poly(n, ℓ, 1/∆) exp(O(ℓ²/∆⁶)) time, establishing Algorithm 5.3’s efficiency.Source: §5.3.2 · p. 48

• Large language model tools were used at every stage of manuscript preparation, from exploratory research through final exposition and writing.Source: AI use disclosure · p. 49
• The authors substantially revised the final manuscript.Source: AI use disclosure · p. 49
• The authors remain solely responsible for the manuscript’s mathematical claims, proofs, references, and conclusions.Source: AI use disclosure · p. 49

A Polarizing the total variation distance in the natural regime

• If a(n) − b(n) ≥ 1/O(log n), then SD[a, b] ∈ SZK for all sufficiently large n.The proof reduces SD to an entropy-difference problem with an inverse-polynomial promise gap.Source: A Polarizing the total variation… · pp. 55–56
• The classical proof approximates total variation distance and encodes the approximation as an Entropy Difference Problem instance.ED[g] is in SZK when g(n) ≥ 1/poly(n).Source: A Polarizing the total variation… · pp. 55–56
• If a(n)^2 − b(n) ≥ 1/poly(n), then QSD[a, b] ∈ QSZK for all sufficiently large n.The proof reduces QSD to QJSP without the earlier parameter loss.Source: A Polarizing the total variation… · p. 59
• For the quantum reduction, the proof bounds quantum Jensen–Shannon divergence along an interpolation between the input states and integrates the change.It uses a Fréchet derivative and matrix inequalities to avoid the obstacle to a direct quantum analogue of the classical analysis.Source: A Polarizing the total variation… · pp. 60–61

C Classical messages suffice for a laconic prover

• QIPℓ-qubit[2, c, s] = QIP2ℓ-bit[2, c, s] for efficiently computable ℓ, c, and s in the stated ranges.The theorem applies when 1 ≤ ℓ(n) ≤ poly(n) and 0 ≤ s(n) < c(n) ≤ 1.Source: C Classical messages suffice for a… · p. 62
• The construction preserves the public-coin property, yielding a quantitative version of qq-QAM = qc-QAM.The corollary states the equality for efficiently computable parameters in the given ranges.Source: C Classical messages suffice for a… · p. 62
• Teleportation converts an ℓ-qubit prover response into 2ℓ classical bits, preserving the verifier’s completeness and soundness.The verifier prepares EPR pairs, receives the classical measurement outcomes, and applies the corresponding Pauli correction.Source: C Classical messages suffice for a… · pp. 62–63
• Superdense coding converts a 2ℓ-bit response into ℓ qubits, allowing the verifier to recover the original classical message and preserve completeness.The construction uses ℓ EPR pairs and a Bell-basis measurement.Source: C Classical messages suffice for a… · pp. 63–64

D.1 Proof of Lemma 4.11

• The compared states encode either the index s or its hash hu,v(s), alongside the corresponding subnormalized state Xx,s.The proof writes these state constructions explicitly before bounding their distance.Source: §D.1 · p. 64
• When the summed traces of the subnormalized states Xx,s are at most b, the proof bounds the trace distance between ς and ς′.Lemma 4.11 identifies this as the almost-uniformity guarantee for the hashed state index.Source: §D.1 · pp. 64, 66
• Negative powers of Xx in the bound are interpreted as powers of its Moore–Penrose inverse on supp(Xx).The proof uses that the support of Xx contains the support of Au.Source: §D.1 · p. 65