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 - QAC⁰ - QAC⁰[m] - QACC⁰ - QAC_f⁰ - QAM - QCFL - QCMA - QCPH - QEPH - QH - QIP - QIP[2] - QL - QMA - QMA-plus - QMA(2) - QMA₁ - QMA_log - QMAM - QMA/qpoly - QMIP - QMIP_le - QMIP_ne - QNC - QNC⁰ - QNC⁰/qpoly - QNC⁰/🐱 - QNC_f⁰ - QNC¹ - 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.

---

QAC⁰: Quantum AC⁰

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 QAC_f⁰, but it is not known if it contains AC⁰. Notice that the latter containment is not obvious, since the set of gates in QAC⁰ do not allow to implement fanout in any way we may take for granted.

---

QAC⁰[m]: Quantum AC⁰[m]

Same as QAC⁰, 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].

---

QACC⁰: Quantum ACC⁰

Same as QAC⁰[m], except that Mod-m gates are allowed for any m.

Defined in [Moo99].

[GHP00] showed that QACC⁰ equals QAC⁰[p] for any prime p.

---

QAC_f⁰: QAC⁰ With Fanout

Same as QAC⁰, 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 QAC_f⁰ = QAC⁰[2] = QACC⁰.

---

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.

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.

---

QH: Query Hierarchy Over NP

QH_k is defined to be P^NP[k]; that is, P with k queries to an NP oracle (where k is a constant). Then QH is the union of QH_k 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

1. If the answer is "yes," then the prover can behave in such a way that the verifier accepts with probability at least 2/3.
2. 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 interactive proofs.

QIP(1) is more commonly known as QMA.

See also: QIP[2], QSZK.

---

QIP[2]: 2-Message Quantum IP

See QIP for definition.

Contains QSZK [Wat02].

---

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].

See also: Q, NQL.

---

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

1. If the answer is "yes," then there exists a state such that verifier accepts with probability at least 2/3.
2. 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 A₀PP.

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]. It is unknown whether QMA(k) = QMA(2) for all k>2, and also whether QMA(2) = QMA. Another open problem is to provide an upper bound for QMA(2) better than NEXP.

It was shown in [ABD+08] that the Additivity Conjecture implies that QMA(k) may be amplified to exponentially small error, and that this amplification in turn implies that QMA(k) = QMA(2) for all k > 2. Moreover, the authors show that a stronger conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE. Finally, the authors 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.

---

QMA₁: 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 QMA₁-complete for any $k\geq 4$. It was also shown there that Quantum 2-SAT is in P, and the status of Quantum 3-SAT still remains unknown.

---

QMA_log: QMA With Logarithmic-Size Proofs

Same as QMA except that the quantum proof has O(log n) qubits instead of a polynomial number.

Equals BQP [MW05].

---

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 contains 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].

Fascinatingly, no relationship between QMIP and NEXP is known. We don't know whether allowing the provers unlimited prior entanglement makes the class more powerful, less powerful, or both!

---

QMIP_le: 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 QMIP_le is contained in NEXP = QMIP_ne.

---

QMIP_ne: 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 QMIP_ne = NEXP. Thus, QMIP_ne contains QMIP_le.

---

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.

---

QNC⁰: Quantum NC⁰

Constant-depth quantum circuits without fanout gates.

Defined in [Spa02].

Contained in QNC_f⁰.

---

QNC_f⁰: Quantum NC⁰ With Unbounded Fanout

Constant-depth quantum circuits with unbounded-fanout gates.

Defined in [Spa02].

Contains QNC⁰, and is contained in QACC⁰.

---

QNC¹: Quantum NC¹

Same as QNC¹, but for the exact rather than bounded-error case.

In contrast to NC¹, it is not clear how to simulate QNC¹ 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(2^polylog(n)).

---

QPLIN: Linear Quasipolynomial-Time

Equals DTIME(n^{O(log n)}).

Has the same relationship to QP that E does to EXP.

---

QPSPACE: Quasipolynomial-Space

Equals DSPACE(2^polylog(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 $k\geq 2$). 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 $k=1$, 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 P^QMA).

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 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.