State complexity and quantum computation

DOI10.1002/ANDP.201400199MaRDI QIDQ3461969zbMATH OpenOpenAlexWikidataFDO

Authors Yu Cai, Huy Nguyen le, Valerio Scarani

Publication date 4 January 2016

Published in Annalen der Physik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04017

zbMATH Keywords

complexityquantum computationtree size

Mathematics Subject Classification ID

Trees (05C05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

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.

Recommendations

• Resources Required for Preparing Graph States
• ALGORITHMIC COMPLEXITY OF QUANTUM STATES
• Cluster-state quantum computation
• MEASUREMENT-BASED QUANTUM COMPUTATION WITH CLUSTER STATES
• Entanglement, flow and classical simulatability in measurement based quantum computation

Cites work

• A simple division-free algorithm for computing determinants
• Classical statistical mechanics approach to multipartite entanglement
• Computational Complexity
• scientific article; zbMATH DE number 5989426 (Why is no real title available?)
• Multipartite entanglement and frustration
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Kolmogorov complexity
• QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
• SECOND QUANTIZED KOLMOGOROV COMPLEXITY
• Statistical mechanics of multipartite entanglement
• The complexity of computing the permanent

Cited in

(8)

• Completing the physical representation of quantum algorithms provides a quantitative explanation of their computational speedup
• Computational Depth Complexity of Measurement-Based Quantum Computation
• Computational Complexity of Projected Entangled Pair States
• Computing complexity measures for quantum states based on exponential families
• The theory of variational hybrid quantum-classical algorithms
• Hay from the haystack: explicit examples of exponential quantum circuit complexity
• Classifying entanglement by algebraic geometry
• Measurement-based quantum computation and undecidable logic

This page was built for publication: State complexity and quantum computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3461969)