dorsal/arxiv
View SchemaClassical deterministic complexity of Edmonds' problem and Quantum Entanglement
| Authors | Leonid Gurvits |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0303055 |
| URL | https://arxiv.org/abs/quant-ph/0303055 |
Abstract
This paper continues research initiated in quant-ph/0201022 . The main subject here is the so-called Edmonds' problem of deciding if a given linear subspace of square matrices contains a nonsingular matrix . We present a deterministic polynomial time algorithm to solve this problem for linear subspaces satisfying a special matroids motivated property, called in the paper the Edmonds-Rado property . This property is shown to be very closely related to the separability of bipartite mixed states . One of the main tools used in the paper is the Quantum Permanent introduced in quant-ph/0201022 .
{
"annotation_id": "0efd2596-4f3c-4582-b067-c25056530e4b",
"date_created": "2026-03-02T18:01:56.463000Z",
"date_modified": "2026-03-02T18:01:56.463000Z",
"file_hash": "79856ea22a7e4842a077dc9805894fa7fec0f555870b8aa2e9fcc545678758b0",
"private": false,
"record": {
"abstract": "This paper continues research initiated in quant-ph/0201022 . The main\nsubject here is the so-called Edmonds\u0027 problem of deciding if a given linear\nsubspace of square matrices contains a nonsingular matrix . We present a\ndeterministic polynomial time algorithm to solve this problem for linear\nsubspaces satisfying a special matroids motivated property, called in the paper\nthe Edmonds-Rado property . This property is shown to be very closely related\nto the separability of bipartite mixed states . One of the main tools used in\nthe paper is the Quantum Permanent introduced in quant-ph/0201022 .",
"arxiv_id": "quant-ph/0303055",
"authors": [
"Leonid Gurvits"
],
"categories": [
"quant-ph"
],
"title": "Classical deterministic complexity of Edmonds\u0027 problem and Quantum Entanglement",
"url": "https://arxiv.org/abs/quant-ph/0303055"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "135e3bdc-ff52-47d1-a012-08a5fed4896e",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}