Difference between revisions of "Complexity Zoo:Q"
m (1 revision: Complexity zoo import.)
Revision as of 03:10, 18 November 2012
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).
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].
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.
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].
QCFL: Quantum 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].
Given a black-box group G and a subgroup H, the problem of testing non-membership in H has polynomial QCMA query complexity [AK06].
QH: Query Hierarchy Over NP
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).
Subsequently [KW00] showed that for all k>3, QIP[k] = QIP = QIP.
QIP = IP = PSPACE [JJUW09]; thus quantum computing adds no power to interactive proofs.
QIP(1) is more commonly known as QMA.
QIP: 2-Message Quantum IP
See QIP for definition.
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).
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.
Approximating the ground state energy of a system composed of a line of quantum particles is QMA-complete [AGK07].
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.)
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.
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.
QMA1: One Sided QMA
Same as QMA except that for a "yes" instance, there exists a state that is accepted with probability 1.
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.
Hence QMAM contains PSPACE.
QMA/qpoly: QMA With Polynomial-Size Quantum Advice
QMIP: Quantum Multi-Prover Interactive Proofs
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!
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.
QMIPne: Quantum Multi-Prover Interactive Proofs With No Prior Entanglement
Same as QMIP, except that now the provers have no prior entanglement.
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.)
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].
QNC1: Quantum NC1
Same as QNC1, but for the exact rather than bounded-error case.
See also [MN02].
QPLIN: Linear Quasipolynomial-Time
Equals DTIME(nO(log n)).
QRG: Quantum Refereed Games
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.
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).
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) 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).
QSZK: Quantum Statistical Zero-Knowledge
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.
- 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.