dorsal/arxiv
View SchemaQuantum Computing and Dynamical Quantum Models
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0205059 |
| URL | https://arxiv.org/abs/quant-ph/0205059 |
Abstract
A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^{1/3} steps (though not fewer).
{
"annotation_id": "f6ff340b-de95-4137-8f7a-f07e0607aef9",
"date_created": "2026-03-02T18:01:51.776000Z",
"date_modified": "2026-03-02T18:01:51.776000Z",
"file_hash": "2be8fb14b79d503c8aed0b112992266d73c1b59b946274361f0cad836a4ee163",
"private": false,
"record": {
"abstract": "A dynamical quantum model assigns an eigenstate to a specified observable\neven when no measurement is made, and gives a stochastic evolution rule for\nthat eigenstate. Such a model yields a distribution over classical histories of\na quantum state. We study what can be computed by sampling from that\ndistribution, i.e., by examining an observer\u0027s entire history. We show that,\nrelative to an oracle, one can solve problems in polynomial time that are\nintractable even for quantum computers; and can search an N-element list in\norder N^{1/3} steps (though not fewer).",
"arxiv_id": "quant-ph/0205059",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph"
],
"title": "Quantum Computing and Dynamical Quantum Models",
"url": "https://arxiv.org/abs/quant-ph/0205059"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c386ec17-2da8-452d-901e-d62411b4ddb0",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}