Two Slightly-Entangled NP-Complete Problems
Roman Orus
Quantum Information and Computation, Vol. 5, No. 6 (2005), pp. 449-455 · 2005
We email you when a new notice or a question about this paper appears.
Abstract
We perform a mathematical analysis of the classical computational complexity of two genuine quantum-mechanical problems, which are inspired in the calculation of the expected magnetizations and the entanglement between subsystems for a quantum spin system. These problems, which we respectively call SES and SESSP, are specified in terms of pure slightly-entangled quantum states of n qubits, and rigorous mathematical proofs that they belong to the NP-Complete complexity class are presented. Both SES and SESSP are, therefore, computationally equivalent to the relevant 3-SAT problem, for which an efficient algorithm is yet to be discovered.
Abstract licence: CC0
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.