dorsal/arxiv
View SchemaOne Complexity Theorist's View of Quantum Computing
| Authors | Lance Fortnow |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0003035 |
| URL | https://arxiv.org/abs/quant-ph/0003035 |
Abstract
The complexity of quantum computation remains poorly understood. While physicists attempt to find ways to create quantum computers, we still do not have much evidence one way or the other as to how useful these machines will be. The tools of computational complexity theory should come to bear on these important questions. Quantum computing often scares away many potential researchers from computer science because of the apparent background need in quantum mechanics and the alien looking notation used in papers on the topic. This paper will give an overview of quantum computation from the point of view of a complexity theorist. We will see that one can think of BQP as yet another complexity class and study its power without focusing on the physical aspects behind it.
{
"annotation_id": "26abc68f-c008-4366-b69a-01f61467ca68",
"date_created": "2026-03-02T18:01:38.850000Z",
"date_modified": "2026-03-02T18:01:38.850000Z",
"file_hash": "ca7b9007c03ae0127d52de500f95cadcacfe2346f0a679fc5f1ad8e21ef9e0ca",
"private": false,
"record": {
"abstract": "The complexity of quantum computation remains poorly understood. While\nphysicists attempt to find ways to create quantum computers, we still do not\nhave much evidence one way or the other as to how useful these machines will\nbe. The tools of computational complexity theory should come to bear on these\nimportant questions. Quantum computing often scares away many potential\nresearchers from computer science because of the apparent background need in\nquantum mechanics and the alien looking notation used in papers on the topic.\nThis paper will give an overview of quantum computation from the point of view\nof a complexity theorist. We will see that one can think of BQP as yet another\ncomplexity class and study its power without focusing on the physical aspects\nbehind it.",
"arxiv_id": "quant-ph/0003035",
"authors": [
"Lance Fortnow"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "One Complexity Theorist\u0027s View of Quantum Computing",
"url": "https://arxiv.org/abs/quant-ph/0003035"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4d9f7d73-2e31-4383-8ddb-1bdf42d3608f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}