The same as BQP, except that the quantum algorithm must return the correct answer with probability 1, and run in polynomial time with probability 1. Unlike bounded-error quantum computing, there is no theory of universal QTMs for exact quantum computing models. In the original definition in [BV97], each language in EQP is computed by a single QTM, equivalently to a uniform family of quantum circuits with a finite gate set K whose amplitudes can be computed in polynomial time. See EQPK. However, some results require an infinite gate set. The official definition here is that the gate set should be finite.
Without loss of generality, the amplitudes in the gate set K are algebraic numbers [ADH97].
There is an oracle that separates EQP from NP [BV97], indeed from Δ2P [GP01]. There is also an oracle relative to which EQP is not in ModpP where p is prime [GV02]. On the other hand, EQP is in LWPP [FR98].
P||NP[2k] is contained in EQP||NP[k], where "||NP[k]" denotes k nonadaptive oracle queries to NP (queries that cannot depend on the results of previous queries) [BD99].
See also ZBQP.
Same as EQP, but with f(n)-time (for some constructible function f) rather than polynomial-time machines.
Defined in [BV97].
The class of decision problems solvable by an NP machine such that
Significantly, the number of candidate witnesses is restricted to be a power of 2. (This is implicit if they are binary strings.)
Contained in RP, EP, and ModkP for every odd k. Contained in EQP by the Deutsch-Jozsa algorithm.
Defined in [BB92], where it was called C==P[half] (C==P being an alternative name for WPP, that apparently didn't catch on or stick). The name used here is from [BS00]. There it was shown that HalfP is contained in every similar class in which 1/2 is replaced by some other dyadic fraction.
For any k>1: The class of decision problems solvable by an NP machine such that the number of accepting paths is divisible by k, if and only if the answer is "no."
Mod2P is more commonly known as ⊕P "parity-P."
For every k, ModkP contains graph isomorphism [AK02].
[Her90] and [BG92] showed that ModkP is the set of unions of languages in ModpP for each prime p that divides k. In particular, if p is prime, then ModpP = Modp^mP for all positive integers m. A further fact is that ModpP is closed under union, intersection, and complement, and low for itself, for p prime.
On the other hand, if k is not a prime power, then there exists an oracle relative to which ModkP is not closed under intersection or complement [BBR94].
For prime p, there exists an oracle relative to which ModpP does not contain EQP [GV02].
An unfortunate name collision. The class of problems nondeterministically recognized by Kondacs-Watrous Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and are measured after each step to check for acceptance or rejection. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>A. Kondacs; J. Watrous. On the power of quantum finite state automata. https://ieeexplore.ieee.org/document/646094</ref>, where they show that it contains all regular languages. In <ref>Abuzer Yakaryılmaz and A.C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081v2</ref> it was shown that this inclusion was strict. Also showed that NQL = S≠
Contrast with QRL, which is a different model of quantum finite automaton, in which measurement only occurs at the end.
Unrelated to the other NQL above.
The class of decision problems solvable by a QTM in polynomial time such that a particular '|Accept>' state has nonzero amplitude at the end of the computation, if and only if the answer is 'yes.' Since it has an exact amplitude condition, NQP has the same technical caveats as EQP. Or it would, except that it turns out to equal coC=P [FGH+98].
Defined in [ADH97].
Contrast with QMA.
The class of problems nondeterministically recognized by Moore-Crutchfield Quantum Finite Automata. These are automata that undergo a unitary transformation for each symbol consumed, and at the end are observed to be in an accepting state or not. The "nondeterminism" refers to the fact that the automaton will accept with positive probability if in the language, or with exactly zero probability otherwise.
Has the same caveats as NQP and EQP because of the exact acceptance probabilities.
Initially studied in <ref>Cristopher Moore and James P. Crutchfield. Quantum automata and quantum grammars.Theoretical ComputerScience, 237(1-2):275–306, 2000.</ref>, although they described QRL as probabilities over words, rather a language in the strict sense. Several important properties established by <ref>Alberto Bertoni and Marco Carpentieri. Analogies and differences between quantum and stochastic automata.Theoretical Computer Science, 262(1-2):69–81, 2001</ref>, where it was shown that QRL has no finite-size languages, but also contains several non-regular languages.
Also called NMCL, in <ref>Abuzer Yakaryilmaz, A. C. Cem Say. Languages recognized by nondeterministic quantum finite automata. https://arxiv.org/abs/0902.2081</ref>, in order to disambiguate from NQL.
Contrast with NQL, which is an analogous class for a different model of quantum finite automaton: there the automaton is measured after each step for acceptance or rejection.
The class of problems in NP whose witnesses are in FBQP. For example, the set of square-free numbers is in coRBQP using only the fact that factoring is in FBQP. (Even without a proof that the factors are prime, the factorization proves that there is a square divisor.)
Contains RP and ZBQP, and is contained in BQP and RQP. Defined here to clarify EQP; see also ZBQP.
The class of questions that can be answered by a QTM that accepts with probability 0 when the true answer is no, and accepts with probability at least 1/2 when the true answer is yes. Since one of the probabilities has to vanish, RQP has the same technical caveats as EQP.
Contains ZQP and RBQP, and is contained in BQP.
Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.
For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).
Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.
Contains ZPP and is contained in RBQP and ZQP. Also, ZBQPZBQP = ZBQP. Defined here to clarify EQP and ZQP.
The class of questions that can be answered by a QTM that answers yes, no, or "maybe". If the correct answer is yes, then P[no] = 0, and vice-versa; and the probability of maybe is at most 1/2. Since some of the probabilities have to vanish, ZQP has the same technical caveats as EQP.
Defined independently in [BW03] and in [Nis02].
Contains EQP and ZBQP and is contained in BQP. Equals RQP ∩ coRQP. There is an oracle such that ZQPZQP is larger than ZQP [BW03]; c.f. with ZBQP.