dorsal/arxiv
View SchemaQuantum Matching Theory (with new complexity theoretic, combinatorial and topological insights on the nature of the Quantum Entanglement)
| Authors | Leonid Gurvits |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0201022 |
| URL | https://arxiv.org/abs/quant-ph/0201022 |
Abstract
Classical matching theory can be defined in terms of matrices with nonnegative entries. The notion of Positive operator, central in Quantum Theory, is a natural generalization of matrices with nonnegative entries. Based on this point of view, we introduce a definition of perfect Quantum (operator) matching . We show that the new notion inherits many "classical" properties, but not all of them . This new notion goes somewhere beyound matroids . For separable bipartite quantum states this new notion coinsides with the full rank property of the intersection of two corresponding geometric matroids . In the classical situation, permanents are naturally associated with perfects matchings. We introduce an analog of permanents for positive operators, called Quantum Permanent and show how this generalization of the permanent is related to the Quantum Entanglement. Besides many other things, Quantum Permanents provide new rational inequalities necessary for the separability of bipartite quantum states . Using Quantum Permanents, we give deterministic poly-time algorithm to solve Hidden Matroids Intersection Problem and indicate some "classical" complexity difficulties associated with the Quantum Entanglement. Finally, we prove that the weak membership problem for the convex set of separable bipartite density matrices is NP-HARD.
{
"annotation_id": "60947696-c917-4419-821d-c30d9fdb3bbe",
"date_created": "2026-03-02T18:01:48.823000Z",
"date_modified": "2026-03-02T18:01:48.823000Z",
"file_hash": "65fff06214683bb8762b118189f121d3cdb24c8a6195d683a816b2671a51953c",
"private": false,
"record": {
"abstract": "Classical matching theory can be defined in terms of matrices with\nnonnegative entries. The notion of Positive operator, central in Quantum\nTheory, is a natural generalization of matrices with nonnegative entries. Based\non this point of view, we introduce a definition of perfect Quantum (operator)\nmatching . We show that the new notion inherits many \"classical\" properties,\nbut not all of them . This new notion goes somewhere beyound matroids . For\nseparable bipartite quantum states this new notion coinsides with the full rank\nproperty of the intersection of two corresponding geometric matroids . In the\nclassical situation, permanents are naturally associated with perfects\nmatchings. We introduce an analog of permanents for positive operators, called\nQuantum Permanent and show how this generalization of the permanent is related\nto the Quantum Entanglement. Besides many other things, Quantum Permanents\nprovide new rational inequalities necessary for the separability of bipartite\nquantum states . Using Quantum Permanents, we give deterministic poly-time\nalgorithm to solve Hidden Matroids Intersection Problem and indicate some\n\"classical\" complexity difficulties associated with the Quantum Entanglement.\nFinally, we prove that the weak membership problem for the convex set of\nseparable bipartite density matrices is NP-HARD.",
"arxiv_id": "quant-ph/0201022",
"authors": [
"Leonid Gurvits"
],
"categories": [
"quant-ph"
],
"title": "Quantum Matching Theory (with new complexity theoretic, combinatorial and topological insights on the nature of the Quantum Entanglement)",
"url": "https://arxiv.org/abs/quant-ph/0201022"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "1ff27592-2db6-421a-8432-883a0ca7361f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}