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 - Σ₁ - Σ₂ - Σ₃ - Σ₄ intersect Tensor₄ - Tensor₁ - Tensor₂ - Tensor₃ - 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 Σ₂.
• MOTree strictly contains Tensor₂.

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

Σ₁: 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 Σ₂ and Tensor₂.

Σ₂: 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₁) states.
Strictly contains Σ₁ and Tensor₁, and is strictly contained in Σ₃ and Tensor₃.

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

Σ₄intersect Tensor₄: Intersection of Fourth Levels of TSH
Does not equal Tensor₃ [Aar03b].

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

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

• Tensor₂ is strictly contained in Tensor₃, Σ₃, and MOTree.
• Tensor₂ is not contained in Vidal.

Tensor₃: Third Tensor Class in TSH
The class of Pure quantum state families that can be written as a tensor product of Σ₂ states.
Strictly contains Σ₂ and Tensor₂, and is strictly contained in Σ₄ intersect Tensor₄ [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 w₁,...,w_k are the children of v, then S(w₁),...,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₁, Tensor₂, Tensor₃, ... (corresponding to trees whose root vertex is Tensor), and Σ₁, Σ₂, Σ₃, ... (corresponding to trees whose root vertex is +). (We have Tensor₀ = Σ₀ = 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 Σ₂.
• Vidal does not contain Tensor₂. top