Class Description

NIQSZK: Non-Interactive QSZK

Has the same relation to QSZK as NISZK does to SZK.

Defined in [Kob02], where it was also shown that the following promise problem is complete for NIQSZK. Given a quantum circuit, we are promised that the state it prepares (when run on the all-0 state, and tracing out non-output qubits) has trace distance either at most 1/3 or at least 2/3 from the maximally mixed state. The problem is to output "no" in the former case and "yes" in the latter.

NIQPZK can be defined similarly.

Linked From

No class.