State complexity and quantum computation
arXiv:1503.04017 · doi:10.1002/andp.201400199
Abstract
The complexity of a quantum state may be closely related to the usefulness of the state for quantum computation. We discuss this link using the tree size of a multiqubit state, a complexity measure that has two noticeable (and, so far, unique) features: it is in principle computable, and non-trivial lower bounds can be obtained, hence identifying truly complex states. In this paper, we first review the definition of tree size, together with known results on the most complex three and four qubits states. Moving to the multiqubit case, we revisit a mathematical theorem for proving a lower bound on tree size that scales superpolynomially in the number of qubits. Next, states with superpolynomial tree size, the Immanant states, the Deutsch-Jozsa states, the Shor's states and the subgroup states, are described. We show that the universal resource state for measurement based quantum computation, the 2D-cluster state, has superpolynomial tree size. Moreover, we show how the complexity of subgroup states and the 2D cluster state can be verified efficiently. The question of how tree size is related to the speed up achieved in quantum computation is also addressed. We show that superpolynomial tree size of the resource state is essential for measurement based quantum computation. The necessary role of large tree size in the circuit model of quantum computation is still a conjecture; and we prove a weaker version of the conjecture.
arXiv comment15 pages, 9 figures. Annalen der Physik, Topical issue on Complex Quantum Systems, 2015
References in corpus (34)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Three qubits can be entangled in two inequivalent ways
- Efficient classical simulation of slightly entangled quantum computations
- Persistent entanglement in arrays of interacting particles
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Matrix product states represent ground states faithfully
- Classification of mixed three-qubit states
- Generalized Schmidt decomposition and classification of three-quantum-bit states
- Witnessing multipartite entanglement
- Testing the limits of quantum mechanical superpositions
- A Schmidt number for density matrices
- Detecting Genuine Multipartite Entanglement with Two Local Measurements
- Valence Bond Solids for Quantum Computation
- Most quantum states are too entangled to be useful as computational resources
- Detection of entanglement with few local measurements
- The wave nature of biomolecules and fluorofullerenes
- Experimental observation of four-photon entanglement from down-conversion
- Fast simulation of stabilizer circuits using a graph state representation
- Inductive Entanglement Classification of Four Qubits under SLOCC
- Measures of macroscopicity for quantum spin systems
- Universal quantum computation with little entanglement
- Entanglement of three-qubit Greenberger-Horne-Zeilinger-symmetric states
- Quantum Kolmogorov Complexity
- Classical simulation versus universality in measurement based quantum computation
- Multipartite entanglement in quantum algorithms
- Algorithmic complexity and entanglement of quantum states
- Probability density function characterization of multipartite entanglement
- Multipartite Entanglement and Frustration
- A Quantitative Measure of Interference
- Classical Statistical Mechanics Approach to Multipartite Entanglement
- Statistical mechanics of multipartite entanglement
- Interference versus success probability in quantum algorithms with imperfections
- Maximal tree size of few-qubit states
Cited by in corpus (7)
- The theory of variational hybrid quantum-classical algorithms
- Tripartite entanglement: Foundations and applications
- Fine-Structure Classification of Multiqubit Entanglement by Algebraic Geometry
- Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
- Classifying Entanglement by Algebraic Geometry
- Oracle problems as communication tasks and optimization of quantum algorithms
- Topologically driven no-superposing theorem with a tight error bound