Entanglement of -LME states and the SAT problem
arXiv:1405.7429 · doi:10.1103/PhysRevA.90.042308
Abstract
In this paper we investigate the entanglement properties of the class of -locally maximally entanglable (-LME) states, which are also known as the "real equally weighted states" or the "hypergraph states". The -LME states comprise well-studied classes of quantum states (e.g. graph states) and exhibit a large degree of symmetry. Motivated by the structure of LME states, we show that the capacity to (efficiently) determine if a -LME state is entangled would imply an efficient solution to the boolean satisfiability (SAT) problem. More concretely, we show that this particular problem of entanglement detection, phrased as a decision problem, is -complete. The restricted setting we consider yields a technically uninvolved proof, and illustrates that entanglement detection, even when quantum states under consideration are highly restricted, still remains difficult.
References in corpus (11)
- Quantum entanglement
- Entanglement detection
- Measurement-based quantum computation with cluster states
- Quantum State Discrimination
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Quantum Hypergraph States
- Multipartite entanglement in quantum algorithms
- Multipartite Entanglement and Global Information
- Encoding Hypergraphs into Quantum States
- Purification to Locally Maximally Entangleable States
- Quantum entanglement in n-qubit real equally weighted states