# Complexity 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 -
Basis -
Circuit -
Dist -
FPAUS -
Mixed -
MOTree -
OTree -
ProbP -
ΨP -
Pure -
Samplable -
Separable -
Σ_{1} -
Σ_{2} -
Σ_{3} -
Σ_{4} intersect Tensor_{4} -
Tensor_{1} -
Tensor_{2} -
Tensor_{3} -
Tree -
TreeSize(f(n)) -
TSH -
Vidal

**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:

- If BQP = P
^{#P}then AmpP is contained in ΨP. - If AmpP is contained in Ψ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.

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 D_{n} over n-bit strings such that (1) D_{n} 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 D_{n} in variation distance.

See [JW04] for more information.

**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 Tensor
_{2}.

**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 Tensor_{1} 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 Tensor

_{2}.

**Σ _{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 Tensor

_{1}) states.

Strictly contains Σ

_{1}and Tensor

_{1}, and is strictly contained in Σ

_{3}and Tensor

_{3}.

**Σ _{3}: Third Sum Class in TSH**

The class of Pure quantum state families that can be written as superpositions over a polynomial number of Tensor

_{2}states.

Strictly contains Σ

_{2}and Tensor

_{2}, and is contained in Σ

_{4}intersect Tensor

_{4}(strict containment is not yet known for this and higher levels of TSH).

**Σ _{4}intersect Tensor_{4}: Intersection of Fourth Levels of TSH**

Does not equal Tensor

_{3}[Aar03b].

**Tensor _{1}: First Tensor Class in TSH**

Equals Separable intersect Pure.

Strictly contains Basis, and is strictly contained in Σ

_{2}and Tensor

_{2}.

**Tensor _{2}: 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:

- Tensor
_{2}is strictly contained in Tensor_{3}, Σ_{3}, and MOTree. - Tensor
_{2}is not contained in Vidal.

**Tensor _{3}: 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 Tensor

_{2}, and is strictly contained in Σ

_{4}intersect Tensor

_{4}[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

- If v is a leaf then |S(v)|=1.
- If v is the root then S(v)={1,...,n}.
- If v is a + gate and w is a child of v, then S(w)=S(v).
- If v is a Tensor gate and w
_{1},...,w_{k}are the children of v, then S(w_{1}),...,S(w_{k}) 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(n^{k}).

TreeSize(n^{O(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 Tensor_{1}, Tensor_{2}, Tensor_{3}, ... (corresponding to trees whose root vertex is Tensor), and Σ_{1}, Σ_{2}, Σ_{3}, ... (corresponding to trees whose root vertex is +). (We have Tensor_{0} = Σ_{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}α_{i}|φ_{i}^{A}>Tensor|φ_{i}^{B}>, where |φ_{i}^{A}> and |φ_{i}^{B}> are states of qubits in A and B respectively. (χ_{A}(|ψ_{n}> is known as the *Schmidt rank*.) Let χ(|ψ_{n}>) = max_{A}χ_{A}(ψ_{n}>). 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:

- Vidal is strictly contained in Circuit and in TreeSize(n
^{O(log n)}). - Vidal strictly contains Σ
_{2}. - Vidal does not contain Tensor
_{2}. top