{
  "annotation_id": "82fbcebd-e5c9-49c9-9c61-166121c5a507",
  "date_created": "2026-03-02T18:02:37.968000Z",
  "date_modified": "2026-03-02T18:02:37.968000Z",
  "file_hash": "6b7eeb40f4dc69a7dd4ce9752a80ed980133f08de88ea24c34c4e34a021daa2d",
  "private": false,
  "record": {
    "abstract": "We define formally decohered quantum computers (using density matrices), and\npresent a simulation of them by a probabalistic classical Turing Machine. We\nstudy the slowdown of the simulation for two cases: (1) sequential quantum\ncomputers, or quantum Turing machines(QTM), and (2) parallel quantum computers,\nor quantum circuits. This paper shows that the computational power of decohered\nquantum computers depends strongly on the amount of parallelism in the\ncomputation.\n  The expected slowdown of the simulation of a QTM is polynomial in time and\nspace of the quantum computation, for any non zero decoherence rate. This means\nthat a QTM subjected to any amount of noise is worthless. For decohered quantum\ncircuits, the situation is more subtle and depends on the decoherence rate,\neta. We find that our simulation is efficient for circuits with decoherence\nrate higher than some constant, but exponential for general circuits with\ndecoherence rate lower than some other constant. Using computer experiments, we\nshow that the transition from exponential cost to polynomial cost happens in a\nshort range of decoherence rates, and exhibit the phase transitions in various\nquantum circuits.",
    "arxiv_id": "quant-ph/9611029",
    "authors": [
      "Dorit Aharonov",
      "Michael Ben-Or"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Polynomial Simulations of Decohered Quantum Computers",
    "url": "https://arxiv.org/abs/quant-ph/9611029"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "010f6c65-791e-4233-aca1-f1595342ec39",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}