Source-linked AI summary
Most quantum states are too entangled to be useful as computational resources
D. Gross, S. Flammia, J. Eisert
TL;DR
The paper asks how common universal computational speedups are and what role entanglement plays. It uses geometric entanglement to show that highly entangled states can be useless for MBQC, and that the fraction of universal resources is less than exp(-n^2).
Problem
The paper asks how common universal computational speedups are and what role entanglement plays in enabling them.
Source: p. 1Method
The authors use the geometric measure of entanglement to show that states above a high-entanglement threshold cannot provide universal speedup, and that typical states meet the criterion.
Source: pp. 1–2Results
The fraction of universal resources among n-qubit pure states is less than e^-n^2, and most states also fail CQ-universality even with chosen measurement outcomes.
Source: pp. 2–3Takeaways & Limitations
Universal resource states require entanglement in the right dose, making the role of entanglement in quantum computing more nuanced than simply requiring more.
Source: p. 4
Abstract
from arXiv · showhide
It is often argued that entanglement is at the root of the speedup for quantum compared to classical computation, and that one needs a sufficient amount of entanglement for this speedup to be manifest. In measurement-based quantum computing (MBQC), the need for a highly entangled initial state is particularly obvious. Defying this intuition, we show that quantum states can be too entangled to be useful for the purpose of computation. We prove that this phenomenon occurs for a dramatic majority of all states: the fraction of useful n-qubit pure states is less than exp(-n^2). Computational universality is hence a rare property in quantum states. This work highlights a new aspect of the question concerning the role entanglement plays for quantum computational speed-ups. The statements remain true if one allows for certain forms of post-selection and also cover the notion of CQ-universality. We identify scale-invariant states resulting from a MERA construction as likely candidates for physically relevant states subject to this effect.
APPENDIX – GEOMETRIC MEASURE IN GRAPH STATES
For graph states, geometric entanglement can be bounded using local Pauli measurements and the graph’s adjacency matrix. These graph-based estimates are explicitly calculable, but no family of graph states is known to be too entangled for computation.
APPENDIX – GEOMETRIC MEASURE IN GRAPH STATES
- The geometric measure is invariant under local unitaries, allowing the analysis to relate a state to a locally equivalent state after a measurement.The measurement argument uses eigenvectors of a local Pauli operator at a distinguished site.Source: APPENDIX – GEOMETRIC MEASURE IN GRAPH… · p. 5
- If k local Pauli measurements completely disentangle a graph state, its geometric measure is at most k; a lower bound is the binary logarithm of the rank of an off-diagonal adjacency submatrix.The rank is taken over F2.Source: APPENDIX – GEOMETRIC MEASURE IN GRAPH… · p. 5
- Both graph-based estimates use the graph’s efficient description and can be calculated explicitly, but no family of graph states is known to be too entangled in the paper’s sense.Source: APPENDIX – GEOMETRIC MEASURE IN GRAPH… · p. 5