Complexity Zoo:Q
Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References
Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z
Lists of related classes: Communication Complexity - Hierarchies - Nonuniform
Q - QAC0 - QAC0[m] - QACC0 - QACf0 - QAM - QCFL - QCMA - QCPH - QEPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA(2) - QMA1 - QMAlog - QMAM - QMA/qpoly - QMIP - QMIPle - QMIPne - QNC - QNC0 - QNC0/qpoly - QNC0/🐱 - QNCf0 - QNC1 - QP - QPH - QPLIN - QPSPACE - QRG - QRG(k) - QRG(2) - QRG(1) - QRL - QSZK
Q: Quasi-Realtime Languages
The class of problems solvable by a nondeterministic multitape Turing machine in linear time. Defined in [BG69], where it was shown that Q equals the class of problems solvable by a nondeterministic multitape Turing machine in exactly n steps (as opposed to O(n) steps).
Contains GCSL.
QAC0: Quantum AC0
The class of decision problems solvable by a family of constant-depth, polynomial-size quantum circuits. Here each layer of the circuit is a tensor product of one-qubit gates and Toffoli gates, or is a tensor product of controlled-NOT gates.
A uniformity condition may also be imposed.
Defined in [Moo99].
It is contained in QACf0, but it is not known if it contains AC0. Notice that the latter containment is not obvious, since the set of gates in QAC0 do not allow to implement fanout in any way we may take for granted.
QAC0[m]: Quantum AC0[m]
Same as QAC0, except that now Mod-m gates are also allowed. A Mod-m gate computes whether the sum of a given set of bits is congruent to 0 modulo m, and exclusive-OR's the answer into another bit.
Defined in [Moo99].
QACC0: Quantum ACC0
Same as QAC0[m], except that Mod-m gates are allowed for any m.
Defined in [Moo99].
[GHP00] showed that QACC0 equals QAC0[p] for any prime p.
QACf0: QAC0 With Fanout
Same as QAC0, except that an additional "quantum fanout" gate is available, which CNOT's a qubit into arbitrarily many target qubits in a single step.
Defined in [Moo99], where it was also shown that QACf0 = QAC0[2] = QACC0.
QAM: Quantum AM
The class of decision problems for which a "yes" answer can be verified by a public-coin quantum AM protocol, as follows. Arthur generates a uniformly random (classical) string and sends it to Merlin. Merlin responds with a polynomial-size quantum certificate, on which Arthur can perform any BQP operation. The completeness and soundness requirements are the same as for AM.
Defined by Marriott and Watrous [MW05].
Contains QMA and is contained in QIP[2] and BP•PP (and therefore PSPACE).
QCFL: Quantum CFL
The class of decision problems recognized by quantum context-free languages, which are defined in [MC00]. The authors also showed that QCFL does not equal CFL.
QCMA: Quantum Classical MA
The class of decision problems for which a "yes" answer can be verified by a quantum computer with access to a classical proof. Also known as the subclass of of QMA with classical witnesses. Defined in [AN02].
Called MQA by Watrous [Wat09].
Contains MA, and is contained in QMA.
Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].
See [AK06] for a "quantum oracle separation" between QCMA and QMA. No classical oracle separation between QCMA and QMA is currently known.
The problem GROUND STATE CONNECTIVITY, which intuitively asks whether a local Hamiltonian's ground space has an "energy barrier", is QCMA-complete [GS15]. Roughly: Given a local Hamiltonian H and ground states v and w, is there a polynomial-length sequence of local unitary operations mapping v to w, such that each intermediate state encountered remains in the ground space of H?
QCPH: Quantum Classical PH
A bounded-error quantum generalization of PH in which all proofs are classical, and the verifier is a quantum circuit.
Defined in [GSSSY18].
Contained in PPPPP [GSSSY18].
QH: Query Hierarchy Over NP
QHk is defined to be PNP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QHk over all nonnegative k.
QH = BH [Wag88]; thus, either both hierarchies are infinite or both collapse to some finite level.
QIP: Quantum IP
The class of decision problems such that a "yes" answer can be verified by a quantum interactive proof. Here the verifier is a BQP (i.e. quantum polynomial-time) algorithm, while the prover has unbounded computational resources (though cannot violate the linearity of quantum mechanics). The prover and verifier exchange a polynomial number of messages, which can be quantum states. Thus, the verifier's and prover's states may become entangled during the course of the protocol. Given the verifier's algorithm, we require that
- If the answer is "yes," then the prover can behave in such a way that the verifier accepts with probability at least 2/3.
- If the answer is "no," then however the prover behaves, the verifier rejects with probability at least 2/3.
Let QIP[k] be QIP where the prover and verifier are restricted to exchanging k messages (with the prover going last).
Defined in [Wat99], where it was also shown that PSPACE is in QIP[3].
Subsequently [KW00] showed that for all k>3, QIP[k] = QIP[3] = QIP.
QIP is contained in EXP [KW00].
QIP = IP = PSPACE [JJUW09]; thus quantum computing adds no power to single-prover interactive proofs.
QIP(1) is more commonly known as QMA.
QIP[2]: 2-Message Quantum IP
See QIP for definition.
QL: Quasi-Linear
The class of problems that can be decided in quasi-linear time by a multitape deterministic Turing machine. Quasi-linear time here means n(log n)k + k, for some k.
Defined in [Sch78].
QMA: Quantum MA
The class of decision problems such that a "yes" answer can be verified by a 1-message quantum interactive proof. That is, a BQP (i.e. quantum polynomial-time) verifier is given a quantum state (the "proof"). We require that
- If the answer is "yes," then there exists a state such that verifier accepts with probability at least 2/3.
- If the answer is "no," then for all states the verifier rejects with probability at least 2/3.
QMA = QIP(1).
Defined in [Wat00], where it is also shown that group non-membership is in QMA.
Based on this, [Wat00] gives an oracle relative to which MA is strictly contained in QMA.
Kitaev and Watrous (unpublished) showed QMA is contained in PP (see [MW05] for a proof). Combining that result with [Ver92], one can obtain an oracle relative to which AM is not in QMA.
Kitaev ([KSV02], see also [AN02]) showed that the 5-Local Hamiltonians Problem is QMA-complete. Subsequently, Kempe and Regev [KR03] showed that even 3-Local Hamiltonians is QMA-complete. A subsequent paper by Kempe, Kitaev, and Regev [KKR04], has hit rock bottom (assuming P does not equal QMA), by showing 2-local Hamiltonians QMA-complete.
Compare to NQP.
If QMA = PP then PP contains PH [Vya03]. This result uses the fact that QMA is contained in A0PP.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
See also: QCMA, QMA/qpoly, QSZK, QMA(2), QMA-plus.
QMA-plus: QMA With Super-Verifier
Same as QMA, except now the verifier can directly obtain the probability that a given observable of the certificate state, if measured, would equal 1. (In the usual model, by contrast, one can only sample an observable.)
Defined in [AR03], where it was also shown that QMA-plus = QMA.
QMA(2): Quantum MA With Multiple Certificates
Same as QMA, except that now the verifier is given two polynomial-size quantum certificates, which are guaranteed to be unentangled.
Defined in [KMY01].
In [BT09], the authored presented a QMAlog(2) (that is, the length of the certificates is logarithmic in the size of the problem -- see, e.g., QMAlog) protocol for 3-Coloring, with perfect completeness and 1-1/poly(n) soundness. Note that a similar construction for QMA is highly unlikely, since it would imply NP is contained in QMAlog=BQP. An analogous result, with constant soundness but with quadratic proof length was shown in [ABD+08]. It was shown shown there that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE. The authors also show that there exists no perfectly disentangler that can be used to simulate QMA(2) in QMA, though other approaches to showing QMA = QMA(2) may still exist.
It was shown in [HM13] that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. It was shown in [BCY11] that QMA(2) = QMA if the verifier is restricted to one-way LOCC protocols.
The best known unconditional upper bound is NEXP. If QMA(2)=NEXP, then QΣ2=QΠ2 (see QPH) (alternating quantifiers provide no additional power in the quantum setting) [GSSSY18]. If QCPH=QPH (quantum proofs provide no additional power in the presence of alternating quantifiers), then QMA(2) is in PPPPP [GSSSY18].
Approximating the minimal energy of a sparse Hamiltonian with respect to a separable state (which is known as the Separable Sparse Hamiltonian problem) is QMA(2)-complete [CS12]. This is in contrast to the Separable Local Hamiltonian problem which is in QMA [CS12].
QMA1: One Sided QMA
Same as QMA except that for a "yes" instance, there exists a state that is accepted with probability 1.
Defined in [Bra06]. It was shown there that Quantum k-SAT is QMA1-complete for any . It was also shown there that Quantum 2-SAT is in P.
This result was later improved in [GN13] where it was shown that Quantum 3-SAT is QMA1-complete.
QMAlog: QMA With Logarithmic-Size Proofs
Same as QMA except that the quantum proof has O(log n) qubits instead of a polynomial number.
QMAM: Quantum Merlin-Arthur-Merlin Public-Coin Interactive Proofs
The class of decision problems for which a "yes" answer can be verified by a public-coin quantum MAM protocol, as follows. Merlin sends a polynomial-size quantum state to Arthur. Arthur then flips some classical coins (in fact, he only has to flip one without loss of generality) and sends the outcome to Merlin. At this stage Arthur is not yet allowed to perform any quantum operations. Merlin then sends Arthur another quantum state. Finally, Arthur performs a BQP operation on both of the states simultaneously, and either accepts or rejects. The completeness and soundness requirements are the same as for AM. Also, Merlin's messages might be entangled.
Defined by Marriott and Watrous [MW05], who also showed that QMAM = QIP(3) = QIP.
Hence QMAM equals PSPACE.
QMA/qpoly: QMA With Polynomial-Size Quantum Advice
Is contained in PSPACE/poly [Aar06b].
QMIP: Quantum Multi-Prover Interactive Proofs
The quantum generalization of MIP, and the multi-prover generalization of QIP.
A quantum multi-prover interactive proof system is the same as a classical one, except that all messages and verifier computations are quantum. As in MIP, there is no communication among the provers; however, the provers share unlimited prior entanglement. The number of provers and number of rounds can both be polynomial in n.
Defined in [KM02].
Shown to be equal to MIP* in [RUV12], and thus RE [JNVWY20].
QMIP contains NEXP simply because MIP* contains NEXP [IV12]. Since we know that NEXP = QMIPne, this tells us that giving the provers unlimited prior entanglement does not make the class less powerful.
QMIPle: Quantum Multi-Prover Interactive Proofs With Limited Prior Entanglement
Same as QMIP, except that now the provers share only a polynomial number of EPR pairs, instead of an unlimited number.
Defined in [KM02], where it was also shown that QMIPle is contained in NEXP = QMIPne.
QMIPne: Quantum Multi-Prover Interactive Proofs With No Prior Entanglement
Same as QMIP, except that now the provers have no prior entanglement.
Defined in [KM02], where it was also shown that QMIPne = NEXP. Thus, QMIPne contains QMIPle.
QNC: Quantum NC
The class of decision problems solvable by polylogarithmic-depth quantum circuits with bounded probability of error. (A uniformity condition may also be imposed.)
Has the same relation to NC as BQP does to P.
[CW00] showed that factoring is in ZPP with a QNC oracle.
Is incomparable with BPP as far as anyone knows.
See also: RNC.
QNC0: Quantum NC0
Constant-depth quantum circuits without fanout gates.
Defined in [Spa02].
Contained in QNCf0.
QNCf0: Quantum NC0 With Unbounded Fanout
Constant-depth quantum circuits with unbounded-fanout gates.
Defined in [Spa02].
Contains QNC0, and is contained in QACC0.
QNC1: Quantum NC1
Same as QNC1, but for the exact rather than bounded-error case.
In contrast to NC1, it is not clear how to simulate QNC1 on a quantum computer in which one qubit is initialized to a pure state, and the remaining qubits are in the maximally mixed state [ASV00].
See also [MN02].
QP: Quasipolynomial-Time
Equals DTIME(2polylog(n)).
QPH: Quantum PH
A bounded-error quantum generalization of PH in which all proofs are mixed quantum states, and the verifier is a quantum circuit. Note the utilization of mixed states is non-trivial, due to the presence of alternating quantifiers.
Defined in [GSSSY18].
Contains QMA(2).
Its second and third levels, QΣ2 and QΣ3, are contained in EXP and NEXP, respectively [GSSSY18].
In contrast to PH, it is open whether QΣ2=QΠ2 collapses QPH to its second level.
QPLIN: Linear Quasipolynomial-Time
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.
QPSPACE: Quasipolynomial-Space
Equals DSPACE(2polylog(n)).
According to [BG94], Beigel and Feigenbaum and (independently) Krawczyk showed that QPSPACE is not contained in Check.
QRG: Quantum Refereed Games
Same as RG, except that now the verifier is a BQP machine, and can exchange polynomially many quantum messages with the competing provers.
The two provers are computationally unbounded, but must obey the laws of quantum mechanics. Also, we can assume without loss of generality that the provers share no entanglement, because adversaries gain no advantage by sharing information.
Defined in [Gut05], where it was also shown that QRG is contained in NEXP ∩ coNEXP.
QRG trivially contains RG (and hence EXP), as well as SQG.
QRG is contained in EXP [GW07]. Hence QRG = RG = EXP and finding optimal strategies for zero-sum quantum games is no harder than finding optimal strategies for zero-sum classical games.
QRG(k): k-turn Quantum Refereed Games
Same as QRG, except that now the verifier exchanges exactly k messages with each prover where k is a polynomial-bounded function of the input length. Messages are exchanged in parallel. QRG(k) is the quantum version of RG(k). By definition, QRG(poly) = QRG. See also QRG(1) and QRG(2).
QRG(k) trivially contains RG(k) for each k (and hence PSPACE when ). QRG(4) trivially contains SQG.
QRG(k) is trivially contained in QRG for each k (and hence EXP).
Other than these trivial bounds, very little is known of QRG(k) for intermediate values of k. For example, does QRG(k) = RG(k) for each k?
QRG(2): Two-turn (one-round) Quantum Refereed Games
Same as QRG, except that now the verifier can exchange only two messages with each prover. Messages are exchanged in parallel, so the verifier cannot process the answer from one prover before preparing the question for the other. QRG(2) is the quantum version of RG(2). See also QRG(k).
QRG(2) trivially contains RG(2) (and hence PSPACE).
QRG(2) is trivially contained in SQG (and hence PSPACE). Hence QRG(2) = RG(2) = PSPACE and finding optimal strategies for two-turn zero-sum quantum games is no harder than finding optimal strategies for two-turn zero-sum classical games.
QRG(1): One-turn Quantum Refereed Games
The class of problems for which there exists a BQP machine M such that:
- If the answer is "yes," then there exists a quantum state ρ such that for all quantum states σ, M(ρ,σ) accepts with probability at least 2/3.
- If the answer is "no," then there exists a σ such that for all ρ, M(ρ,σ) rejects with probability at least 2/3.
In other words, it's the same as QRG(k) for , the class of problems that admit quantum interactive proofs with competing provers in which there's no communication from the verifier back to the provers. QRG(1) is the quantum version of RG(1).
Defined in [JW09], where it was shown that QRG(1) is contained in PSPACE .
QRG(1) trivially contains QMA (and indeed PQRG(1)).
QRG(1) is trivially contained in QRG(2) (and hence PSPACE).
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 Q0 and Q1. Let ρ0 and ρ1 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 ρ0 and ρ1 is either at most α or at least β, where α and β are constants in [0,1] satisfying α < β2. 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].