Tree-size complexity of multiqubit states

Abstract

Complexity is often invoked alongside size and mass as a characteristic of macroscopic quantum objects. In 2004, Aaronson introduced the \textit{tree size} (TS) as a computable measure of complexity and studied its basic properties. In this paper, we improve and expand on those initial results. In particular, we give explicit characterizations of a family of states with superpolynomial complexity $n^{\Omega (\log n)}=\mathrm{TS}=O(\sqrt{n}!)$ in the number of qubits $n$; and we show that any matrix-product state whose tensors are of dimension $D\times D$ has polynomial complexity $\mathrm{TS}=O(n^{{\log }_{2}2D})$.

7 pages, 2 figures

References in corpus (10)

• Multi-party entanglement in graph states
• Observation of strong coupling between a micromechanical resonator and an optical cavity field
• Photonic Boson Sampling in a Tunable Circuit
• Aspects of generic entanglement
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Macroscopicity of Mechanical Quantum Superposition States
• Real-time single-molecule imaging of quantum interference
• Inductive Entanglement Classification of Four Qubits under SLOCC
• Measures of macroscopicity for quantum spin systems
• A measurement-based measure of the size of macroscopic quantum superpositions

Cited by in corpus (1)

• Maximal tree size of few-qubit states