The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol. In such an interactive proof(see IP), we have a probabilistic polynomial-time verifier, and a prover who has unbounded computational resources. By exchanging messages with the prover, the verifier must become convinced (with high probability) that the answer is "yes," without learning anything else about the problem (statistically).
What does that mean? For each choice of random coins, the verifier has a "view" of his entire interaction with prover, consisting of his random coins as well as all messages sent back and forth. Then the distribution over views resulting from interaction with the prover has to be statistically close to a distribution that the verifier could generate himself (in polynomial-time), without interacting with anyone. (Here "statistically close" means that, say, the trace distance is at most 1/10.)
The most famous example of such a protocol is for graph nonisomorphism. Given two graphs G and H, the verifier picks at random one of the graphs (each with probability 1/2), permutes its vertices randomly, sends the resulting graph to the prover, and asks, "Which graph did I start with, G or H?" If G and H are non-isomorphic, the prover can always answer correctly (since he can use exponential time), but if they're isomorphic, he can answer correctly with probability at most 1/2. Thus, if the prover always gives the correct answer, then the verifier becomes convinced the graphs are not isomorphic. On the other hand, the verifier already knew which graph (G or H) he started with, so he could simulate his entire view of the interaction himself, without the prover's help.
If that sounds like a complicated definition, well, it is. But it turns out that SZK has extremely nice properties. [Oka96] showed that:
Subsequently, [SV97] showed that SZK has a natural complete promise problem, called Statistical Difference (SD). Given two polynomial-size circuits, C0 and C1, let D0 and D1 be the distributions over their respective outputs when they're given as input a uniformly random n-bit string. We're promised that D0 and D1 have trace distance either at most 1/3 or at least 2/3; the problem is to decide which is the case.
Note: The constants 1/3 and 2/3 can be amplified to 2-poly(n) and 1-2-poly(n) respectively. But it is crucial that (2/3)2 > 1/3.
Another complete promise problem for SZK is Entropy Difference (ED) [GV99]. Here we're promised that either H(D0)>H(D1)+1 or H(D1)>H(D0)+1, where the distributions D0 and D1 are as above, and H denotes Shannon entropy. The problem is to determine which is the case.
If any hard-on-average language is in SZK, then one-way functions exist [Ost91].
See general zero-knowledge (ZK).
Contains PZK and NISZK, and is contained in AM ∩ coAM, as well as CZK and QSZK.
There exists an oracle relative to which SZK is not in BQP [Aar02].
The class of decision problems for which a "yes" answer can be verified by an Arthur-Merlin protocol, as follows.
Arthur, a BPP (i.e. probabilistic polynomial-time) verifier, generates a "challenge" based on the input, and sends it together with his random coins to Merlin. Merlin sends back a response, and then Arthur decides whether to accept. Given an algorithm for Arthur, we require that
Surprisingly, it turns out that such a system is just as powerful as a private-coin one, in which Arthur does not need to send his random coins to Merlin [GS86]. So, Arthur never needs to hide information from Merlin.
Furthermore, define AM[k] similarly to AM, except that Arthur and Merlin have k rounds of interaction. Then for all constant k>2, AM[k] = AM[2] = AM [BM88]. Also, the result of [GS86] can then be stated as follows: IP[k] is contained in AM[k+2] for every k (constant or non-constant).
AM contains graph nonisomorphism.
Contains NP, BPP, and SZK, and is contained in NP/poly.AM is also contained in Π2P and this proof relativizes so the containment holds relative to any oracle.
If AM contains coNP then PH collapses to Σ2P ∩ Π2P [BHZ87].
There exists an oracle relative to which AM is not contained in PP [Ver92].
AM = NP under a strong derandomization assumption: namely that some language in NE ∩ coNE requires nondeterministic circuits of size 2Ω(n) ([MV99], improving [KM99]). (A nondeterministic circuit C has two inputs, x and y, and accepts on x if there exists a y such that C(x,y)=1.)
The class of decision problems solvable in polynomial time by a quantum Turing machine, with at most 1/3 probability of error.
One can equivalently define BQP as the class of decision problems solvable by a uniform family of polynomial-size quantum circuits, with at most 1/3 probability of error [Yao93]. Any universal gate set can be used as a basis; however, a technicality is that the transition amplitudes must be efficiently computable, since otherwise one could use them to encode the solutions to hard problems (see [ADH97]).
BQP is often identified as the class of feasible problems for quantum computers.
Contains the factoring and discrete logarithm problems [Sho97], the hidden Legendre symbol problem [DHI02], the Pell's equation and principal ideal problems [Hal02], and some other problems not thought to be in BPP.
Defined in [BV97], where it is also shown that BQP contains BPP and is contained in P with a #P oracle.
BQPBQP = BQP [BV97].
[ADH97] showed that BQP is contained in PP, and [FR98] showed that BQP is contained in AWPP.
There exist oracles relative to which:
If P=BQP relative to a random oracle then BQP=BPP [FR98].
Same as SZK, except that now the two distributions are merely required to be computationally indistinguishable by any BPP algorithm; they don't have to be statistically close. (The "two distributions" are (1) the distribution over the verifier's view of their interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)
Unlike SZK, it is not known if CZK is closed under complement. CZK is now known to share other properties with SZK: the verifier may as well be honest and may as well show their coins, and CZK is closed under unions [Vad06]. (Previously, these properties were only established in the presence of one-way functions [GMW91].)
Assuming the existence of one-way functions, CZK contains NP [GMW91], and actually equals IP=PSPACE [BGG+90]. However, none of these implications of one-way functions relativize (Impagliazzo, unpublished).
On the other hand, if one-way functions do not exist then CZK = AVBPP [OW93].
The class of decision problems solvable by a BQP machine with oracle access to a dynamical simulator. When given a polynomial-size quantum circuit, the simulator returns a sample from the distribution over "classical histories" induced by the circuit. The simulator can adversarially choose any history distribution that satisfies the axioms of "symmetry" and "locality" -- so that the DQP algorithm has to work for any distribution satisfying these axioms.
See [Aar05] for a full definition.
There it is also shown that SZK is contained in DQP.
Contains BQP, and is contained in EXP [Aar05].
There exists an oracle relative to which DQP does not contain NP [Aar05].
Can be defined as the class of problems polynomial-time Turing reducible to the Graph Isomorphism problem.
Contains GA and is contained in Δ2P.
The Graph Isomorphism problem itself (as opposed to the set of problems Turing reducible to Graph Isomorphism) is contained in NP as well as coAM (and indeed SZK). So in particular, if Graph Isomorphism is NP-complete, then PH collapses.
Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the Wikipedia page. While many of these are GI for a restricted class of graphs, some surprising GI-complete problems are: isomorphism of finite automata, isomorphism of commutative class 3 nilpotent semigroups, isomorphism of algebras over a field whose radical squares to zero and whose radical quotient is abelian [Gri83], and isomorphism of context-free grammars (for all of these and further references see [ZKT85]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [Gro12].
See [KST93] for much more information about GI.
The class of decision problems that have SZK protocols assuming an honest verifier (i.e. one who doesn't try to learn more about the problem by deviating from the protocol).
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.
Defined in [DDP+98].
Contained in SZK.
[GSV99] showed the following:
NIPZK can be defined similarly.
There is an oracle separating NISZK from PP [BCHTV17].
The non-interactive analogue of SZKh.
Defined in [BG03], where the following was also shown:
The quantum lower bound for the set comparison problem in [Aar02] implies an oracle relative to which NISZKh is not in BQP.
This class is a generalization of BQP where one is allowed to perform measuresments without collapsing the wavefunction.[ABFL14]
Unlike, BQP this is likely to be a not physically realizable class.
Contains SZK and thus contains graph isomorphism.
There is an oracle relative to which BQP is not equal to PDQP and an oracle relative to which NP is not contained in PDQP.
PDQP can perform unordered searches faster than BQP.
Compare DQP.
Has the same relation to PZK as SKC does to SZK.
Defined in [GP91].
Same as SZK, but now the two distributions must be identical, not merely statistically close. (The "two distributions" are (1) the distribution over the verifier's view of his interaction with the prover, conditioned on the verifier's random coins, and (2) the distribution over views that the verifier can simulate without the prover's help.)
Contained in SZK and HVPZK.There are oracles separating PZK from SZK, coPZK, NIPZK, and coSBP. [BCHTV17], [DGPV20].
See also: CZK.
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:
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].
A hierarchy of generalizations of SZK, in which Arthur is allowed to gain some information from his interaction with Merlin.
Defined in [GP91].
There are several variants (which we only describe roughly), including:
See also: PKC.
The class of decision problems for which a "yes" answer can be verified by a statistical zero-knowledge proof protocol, and the prover and verifier both have access to a string computed by a trusted probabilistic polynomial-time third party with access to the input.
Defined in [BG03], where it was also shown that SZKh = SZK.
Contains NISZKh.
The class of problems that are polynomial-time Turing reducible to Tensor Isomorphism. Defined in [GQ19]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).
Over any field F, contains GI. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in NP as well as coAM (and indeed SZK; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is NP-complete, then PH collapses.
Many natural problems are TI-complete, such as isomorphism of d-tensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo-)isometry of alternating matrix spaces, isomorphism of matrix p-groups of class 2 and exponent p, and equivalence of cubic forms [GQ19]. This was extended to include p-groups of class c<p and exponent p [GQ21]. Analogous classes were also defined under other group actions such as unitary, orthogonal, and symplectic groups [CGQ+24].
Often used as a shorthand for (computational zero-knowledge) CZK, but may also be used as a general paradigm encomposing various classes ranging from perfect and statistical zero-knowledge (SZK) to computational ones (CZK), and also various forms of non-interactive zero-knowledge proof systems.
Zero-knowledge proofs were introduced in [GMR89], and further studied in [GMW91], which demonstrated the wide applicability of the concept.