dorsal/arxiv
View SchemaQuantum Computation
| Authors | Dorit Aharonov |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812037 |
| URL | https://arxiv.org/abs/quant-ph/9812037 |
| DOI | 10.1142/9789812815569_0007 |
Abstract
In the last few years, theoretical study of quantum systems serving as computational devices has achieved tremendous progress. We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool. This review is about to tell the story of theoretical quantum computation. I left out the developing topic of experimental realizations of the model, and neglected other closely related topics which are quantum information and quantum communication. As a result of narrowing the scope of this paper, I hope it has gained the benefit of being an almost self contained introduction to the exciting field of quantum computation. The review begins with background on theoretical computer science, Turing machines and Boolean circuits. In light of these models, I define quantum computers, and discuss the issue of universal quantum gates. Quantum algorithms, including Shor's factorization algorithm and Grover's algorithm for searching databases, are explained. I will devote much attention to understanding what the origins of the quantum computational power are, and what the limits of this power are. Finally, I describe the recent theoretical results which show that quantum computers maintain their complexity power even in the presence of noise, inaccuracies and finite precision. I tried to put all results in their context, asking what the implications to other issues in computer science and physics are. In the end of this review I make these connections explicit, discussing the possible implications of quantum computation on fundamental physical questions, such as the transition from quantum to classical physics.
{
"annotation_id": "a87e9418-4c81-4dcb-af8b-5f43491a02ba",
"date_created": "2026-03-02T18:02:44.970000Z",
"date_modified": "2026-03-02T18:02:44.970000Z",
"file_hash": "c0afe5f3133ba51a08d276ef960566d430b66af66bd8a9a1c34336a2e979d80c",
"private": false,
"record": {
"abstract": "In the last few years, theoretical study of quantum systems serving as\ncomputational devices has achieved tremendous progress. We now have strong\ntheoretical evidence that quantum computers, if built, might be used as a\ndramatically powerful computational tool. This review is about to tell the\nstory of theoretical quantum computation. I left out the developing topic of\nexperimental realizations of the model, and neglected other closely related\ntopics which are quantum information and quantum communication. As a result of\nnarrowing the scope of this paper, I hope it has gained the benefit of being an\nalmost self contained introduction to the exciting field of quantum\ncomputation.\n The review begins with background on theoretical computer science, Turing\nmachines and Boolean circuits. In light of these models, I define quantum\ncomputers, and discuss the issue of universal quantum gates. Quantum\nalgorithms, including Shor\u0027s factorization algorithm and Grover\u0027s algorithm for\nsearching databases, are explained. I will devote much attention to\nunderstanding what the origins of the quantum computational power are, and what\nthe limits of this power are. Finally, I describe the recent theoretical\nresults which show that quantum computers maintain their complexity power even\nin the presence of noise, inaccuracies and finite precision. I tried to put all\nresults in their context, asking what the implications to other issues in\ncomputer science and physics are. In the end of this review I make these\nconnections explicit, discussing the possible implications of quantum\ncomputation on fundamental physical questions, such as the transition from\nquantum to classical physics.",
"arxiv_id": "quant-ph/9812037",
"authors": [
"Dorit Aharonov"
],
"categories": [
"quant-ph"
],
"doi": "10.1142/9789812815569_0007",
"title": "Quantum Computation",
"url": "https://arxiv.org/abs/quant-ph/9812037"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "5bbd7795-1e69-4cbe-a61b-03fa190a2c93",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}