Tree-size complexity of multiqubit states
arXiv:1303.4843 · doi:10.1103/PhysRevA.88.012321
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 in the number of qubits ; and we show that any matrix-product state whose tensors are of dimension has polynomial complexity .
arXiv comment7 pages, 2 figures
References in corpus (22)
- Three qubits can be entangled in two inequivalent ways
- Efficient classical simulation of slightly entangled quantum computations
- Persistent entanglement in arrays of interacting particles
- Efficient simulation of one-dimensional quantum many-body systems
- An Area Law for One Dimensional Quantum Systems
- 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
- Generalized Schmidt decomposition and classification of three-quantum-bit states
- Aspects of generic entanglement
- Most quantum states are too entangled to be useful as computational resources
- The wave nature of biomolecules and fluorofullerenes
- Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
- The Schmidt Measure as a Tool for Quantifying Multi-Particle Entanglement
- 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
- Stability of quantum states of finite macroscopic systems against classical noises, perturbations from environments, and local measurements
- A size criterion for macroscopic superposition states
- Algorithmic complexity and entanglement of quantum states