Class Description

coUP: Complement of UP

Linked From

QSZK: Quantum Statistical Zero-Knowledge

A quantum analog of SZK (or more precisely HVSZK).

Arthur is a BQP (i.e. quantum) verifier who can exchange quantum messages with Merlin. So Arthur and Merlin's states may become entangled during the course of the protocol.

Arthur's "view" of his interaction with Merlin is taken to be the sequence of mixed states he has, over all steps of the protocol. The zero-knowledge requirement is that each of these states must have trace distance at most (say) 1/10 from a state that Arthur could prepare himself (in BQP), without help from Merlin. Arthur is assumed to be an honest verifier.

Defined in [Wat02], where the following was also shown:

• QSZK is contained in PSPACE.
• QSZK is closed under complement.
• Any protocol can be parallelized to consist of two messages, so that QSZK is in QIP[2].
• One can assume without loss of generality that protocols are public-coin, as for SZK.
• QSZK has a natural complete promise problem, called Quantum State Distinguishability (QSD). We are given quantum circuits Q₀ and Q₁. Let ρ₀ and ρ₁ be the mixed states they produce respectively, when run on the all-0 state (and when non-output qubits are traced out). We are promised that the trace distance between ρ₀ and ρ₁ is either at most α or at least β, where α and β are constants in [0,1] satisfying α < β². The problem is to decide which of these is the case.

Subsequently, [Wat09b] showed that honest-verifier and general-verifier quantum statistical zero-knowledge are equivalent.

There exists an oracle relative to which QSZK does not contain UP ∩ coUP, and a random oracle relative to which QSZK does not contain UP [MW18].

More about...

UP: Unambiguous Polynomial-Time

The class of decision problems solvable by an NP machine such that

1. If the answer is 'yes,' exactly one computation path accepts.
2. If the answer is 'no,' all computation paths reject.

Defined by [Val76].

"Worst-case" one-way functions exist if and only if P does not equal UP ([GS88] and independently [Ko85]). "Worst-case" one-way permutations exist if and only if P does not equal UP ∩ coUP [HT03]. Note that these are weaker than the one-way functions and permutations that are needed for cryptographic applications.

There exists an oracle relative to which P is strictly contained in UP is strictly contained in NP [Rac82]; indeed, these classes are distinct with probability 1 relative to a random oracle [Bei89].

NP is contained in RP^PromiseUP [VV86]. On the other hand, [BBF98] give an oracle relative to which P = UP but still P does not equal NP.

UP is not known or believed to contain complete problems. [Sip82], [HH86] give oracles relative to which UP has no complete problems.

More about...