# Complexity Zoo Exhibit

(Redirected from Zoo Exhibit)

This page is an exhibit of the Complexity Zoo which was originally created at http://www.complexityzoo.com/ by Scott Aaronson.

Special Complexity Zoo Exhibit: Classes of Quantum States and Probability Distributions

24 classes and counting!

A whole new phylum of the Complexity kingdom has recently been identified. This phylum consists of classes, not of problems or languages, but of quantum states and probability distributions. Well, actually, infinite families of states and distributions, one for each number of bits n. Admittedly, computer scientists have been talking about the complexity of sampling from probability distributions for years, but they haven't tended to organize those distributions into classes designated by inscrutable sequences of capital letters. This needs to change. The present Zookeeper has started the analogous project for quantum states; indeed, he puts the classes below in a special exhibit to avoid the appearance of favoritism toward his own classes in the main Zoo.

AmpP: States with Polytime-Computable Amplitudes
The class of Pure quantum state families |ψn> = Σxαx|x> such that for all n,b, there exists a classical circuit of size p(n+b) that outputs αx to b bits of precision given x as input, for some polynomial p.
Defined in [Aar03b], where the following was also shown:

AmpP contains Circuit and Tree, and is contained in Pure.

Basis: Computational Basis States
The class of quantum state families of the form |x> where x is an n-bit string.
The zeroth level of TSH.
Equals Pure intersect Dist.

Circuit: Circuit States
A generalization of Tree, where we allow amplitudes to be computed by polynomial-size multilinear circuits rather than just multilinear formulas.
Defined in [Aar03b], where it was also observed that Circuit contains Vidal (indeed, strictly contains it).
Contained in AmpP.

Dist: Classical Probability Distributions
The class of classical probability distribution families over n-bit strings.
Contains Basis, and is contained in Mixed.

FPAUS: Fully-Polynomial Almost-Uniform Samplable
The class of probability distribution families Dn over n-bit strings such that (1) Dn is the uniform distribution over some subset, and (2) there exists a uniform probabilistic algorithm, running in time polynomial in n and log(1/δ), that outputs a sample from a distribution at most δ from Dn in variation distance.

Mixed: Mixed Quantum States
The class of mixed quantum state families of n qubits.
Contains Pure and Dist.

MOTree: Manifestly Orthogonal Tree States
The class of quantum state families in Tree representable by polynomial-size trees in which all additions are of states that are mutually manifestly orthogonal. Two states of n qubits, Σxαx|x> and Σxβx|x>, are manifestly orthogonal if αxβx=0 for all x.
Defined in [Aar03b], where the following was also shown:

• MOTree is strictly contained in Tree. Indeed, MOTree does not contain Σ2.
• MOTree strictly contains Tensor2.

OTree: Orthogonal Tree States
The class of quantum state families in Tree representable by polynomial-size trees in which all additions are of mutually orthogonal states.
Contains MOTree.
Defined in [Aar03b], where it was also shown that OTree is contained in ΨP.
Showing a separation between Tree and OTree remains an excellent open problem.

ProbP: Distributions With Polytime-Computable Probabilities

ΨP: Pure States Preparable by Polynomial-Size Circuits
The class of Pure quantum state families |ψn> such that for all n and ε>0, there exists a quantum circuit of size p(n+log(1/ε)) that maps the all-0 state to a state some subsystem of which has trace distance at most 1-ε from |ψn>, for some polynomial p. Because of the Solovay-Kitaev Theorem (see [NC00]), the definition of ΨP is invariant under the choice of universal gate set.
The following was shown in [Aar03b]:

• ΨP is not contained in Tree.
• OTree is contained (indeed strictly contained) in ΨP.
• If BQP = P#P then AmpP is contained in ΨP.
• If AmpP is contained in hΨP then NP is contained in BQP/poly.
• If P = P#P then ΨP = AmpP.
• If ΨP is contained in AmpP then BQP is contained in P/poly.

Whether Tree is contained in ΨP remains an intriguing open problem.

Pure: Pure Quantum States
The class of quantum state families of n qubits that have the form Σxαx|x>; that is, that cannot be written as a nontrivial probability distribution over two other quantum states.
Contains Basis, and is contained in Mixed.

Samplable: Polytime-Samplable Distributions

Separable: Separable Mixed States
The class of Mixed quantum state families of n qubits that can be written as a probability distribution over Tensor1 states.
A well-known open problem asks whether a quantum computer that is in a separable state at every time step can be simulated in BPP, or alternatively, whether such a computer can simulate BQP.

Σ1: First Sum Class in TSH
The class of Pure quantum state families that can be written as superpositions over a polynomial number of computational basis states.
Strictly contains Basis, and is strictly contained in Σ2 and Tensor2.

Σ2: Second Sum Class in TSH
The class of Pure quantum state families that can be written as superpositions over a polynomial number of Separable (or equivalently Tensor1) states.
Strictly contains Σ1 and Tensor1, and is strictly contained in Σ3 and Tensor3.

Σ3: Third Sum Class in TSH
The class of Pure quantum state families that can be written as superpositions over a polynomial number of Tensor2 states.
Strictly contains Σ2 and Tensor2, and is contained in Σ4intersect Tensor4 (strict containment is not yet known for this and higher levels of TSH).

Σ4intersect Tensor4: Intersection of Fourth Levels of TSH
Does not equal Tensor3 [Aar03b].

Tensor1: First Tensor Class in TSH
Equals Separable intersect Pure.
Strictly contains Basis, and is strictly contained in Σ2 and Tensor2.

Tensor2: Second Tensor Class in TSH
The class of Pure quantum state families that can be written as a tensor product of Σ1 states.
Defined in [Aar03b], where the following was also shown:

Tensor3: Third Tensor Class in TSH
The class of Pure quantum state families that can be written as a tensor product of Σ2 states.
Strictly contains Σ2 and Tensor2, and is strictly contained in Σ4 intersect Tensor4 [Aar03b].

Tree: Tree States
The class of Pure quantum state families {|ψn>} such that TS(|ψn>)=O(p(n)) for some polynomial p, where TS, or tree size, is defined as follows.
A quantum state tree is a rooted tre where each leaf vertex is labeled with either |0> or |1>, and each non-leaf vertex is labeled with either + or Tensor. Each vertex v is also labeled with a subset S(v) of {1,...,n} such that

1. If v is a leaf then |S(v)|=1.
2. If v is the root then S(v)={1,...,n}.
3. If v is a + gate and w is a child of v, then S(w)=S(v).
4. If v is a Tensor gate and w1,...,wk are the children of v, then S(w1),...,S(wk) are pairwise disjoint and form a partition of S(v).

Finally, if v is a + gate, then the outgoing edges of v are labeled with complex numbers. For each v, the subtree rooted at v represents a quantum state in the obvious way (we require this state to be normalized for each v).
The tree size TS(|ψ>) is then the minimum size of a tree representing |ψ>, where size means number of vertices.
Defined in [Aar03b], where the following was also shown:

• ΨP is not contained in Tree.
• Tree strictly contains MOTree.
• Any state family in Tree can be represented by trees of polynomial size and logarithmic depth.
• Most quantum states cannot even be well-approximated by states of subexponential tree size.

Contains OTree and TSH, and is contained in Circuit.

TreeSize(f(n)): Pure Quantum States of Tree Size O(f(n))
The class of Pure quantum state families that have O(f(n)) tree size in the sense of [Aar03b]. So for example, Tree equals the union over all k of TreeSize(nk).
TreeSize(nO(log n)) contains Vidal [Aar03b].

TSH: Tensor-Sum Hierarchy
The class of quantum state families in Tree represented by trees of polynomial size and constant depth, where the depth is just the maximum length of a path from the root to a leaf.
The levels of TSH are Tensor1, Tensor2, Tensor3, ... (corresponding to trees whose root vertex is Tensor), and Σ1, Σ2, Σ3, ... (corresponding to trees whose root vertex is +). (We have Tensor0 = Σ0 = Basis.)
Whether TSH = Tree and whether TSH is contained in ΨP remain intriguing open problems.

Vidal: States of Polynomially-Bounded Schmidt Rank
The class of Pure quantum state families that are polynomially entangled in the sense of Vidal [Vid03]. More precisely, given a partition of {1,...,n} into A and B, let χA(|ψn>) be the minimum k for which |ψn> can be written as Σi=1 to kαiiA>Tensor|φiB>, where |φiA> and |φiB> are states of qubits in A and B respectively. (χA(|ψn> is known as the Schmidt rank.) Let χ(|ψn>) = maxAχAn>). Then |ψn> is contained in Vidal if and only if χ(|ψn> is at most p(n) for some polynomial p.
[Vid03] shows that, if a quantum computer is in Vidal at every time step, then it can be simulated classically with only polynomial slowdown.
[Aar03b] observes the following: