dorsal/arxiv
View SchemaAn Introduction to Quantum Complexity Theory
| Authors | Richard Cleve |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9906111 |
| URL | https://arxiv.org/abs/quant-ph/9906111 |
| DOI | 10.1142/9789810248185_0004 |
Abstract
We give a basic overview of computational complexity, query complexity, and communication complexity, with quantum information incorporated into each of these scenarios. The aim is to provide simple but clear definitions, and to highlight the interplay between the three scenarios and currently-known quantum algorithms.
{
"annotation_id": "55a1760c-dbcc-4c67-aa17-6a6339ecb0e2",
"date_created": "2026-03-02T18:02:48.057000Z",
"date_modified": "2026-03-02T18:02:48.057000Z",
"file_hash": "38bf0d0afb8b00339716aa0ba979056dc4b6b4f2e2dd85621ab11834d6c5bb53",
"private": false,
"record": {
"abstract": "We give a basic overview of computational complexity, query complexity, and\ncommunication complexity, with quantum information incorporated into each of\nthese scenarios. The aim is to provide simple but clear definitions, and to\nhighlight the interplay between the three scenarios and currently-known quantum\nalgorithms.",
"arxiv_id": "quant-ph/9906111",
"authors": [
"Richard Cleve"
],
"categories": [
"quant-ph"
],
"doi": "10.1142/9789810248185_0004",
"title": "An Introduction to Quantum Complexity Theory",
"url": "https://arxiv.org/abs/quant-ph/9906111"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "9494aad9-6fe9-4979-a4a6-3b783e944410",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}