dorsal/arxiv
View SchemaAn Introduction to Quantum Computing for Non-Physicists
| Authors | Eleanor G. Rieffel, Wolfgang Polak |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9809016 |
| URL | https://arxiv.org/abs/quant-ph/9809016 |
| Journal | ACM Comput.Surveys 32:300-335,2000 |
Abstract
Richard Feynman's observation that quantum mechanical effects could not be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used quantum effects. This speculation appeared justified when Peter Shor described a polynomial time quantum algorithm for factoring integers. In quantum systems, the computational space increases exponentially with the size of the system which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new non-traditional programming techniques. The aim of this paper is to guide computer scientists and other non-physicists through the conceptual and notational barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to harnessing the power of quantum parallelism are explained, including Shor's algorithm, Grover's algorithm, and Hogg's algorithms. We conclude with a discussion of quantum error correction.
{
"annotation_id": "f92c4be5-da79-4111-9085-71c06d7b2c8e",
"date_created": "2026-03-02T18:02:45.040000Z",
"date_modified": "2026-03-02T18:02:45.040000Z",
"file_hash": "cd0b96820a528df9efe9afca0a2b1dde7d0b45e65add1dc1ab25406e7f202cae",
"private": false,
"record": {
"abstract": "Richard Feynman\u0027s observation that quantum mechanical effects could not be\nsimulated efficiently on a computer led to speculation that computation in\ngeneral could be done more efficiently if it used quantum effects. This\nspeculation appeared justified when Peter Shor described a polynomial time\nquantum algorithm for factoring integers.\n In quantum systems, the computational space increases exponentially with the\nsize of the system which enables exponential parallelism. This parallelism\ncould lead to exponentially faster quantum algorithms than possible\nclassically. The catch is that accessing the results, which requires\nmeasurement, proves tricky and requires new non-traditional programming\ntechniques.\n The aim of this paper is to guide computer scientists and other\nnon-physicists through the conceptual and notational barriers that separate\nquantum computing from conventional computing. We introduce basic principles of\nquantum mechanics to explain where the power of quantum computers comes from\nand why it is difficult to harness. We describe quantum cryptography,\nteleportation, and dense coding. Various approaches to harnessing the power of\nquantum parallelism are explained, including Shor\u0027s algorithm, Grover\u0027s\nalgorithm, and Hogg\u0027s algorithms. We conclude with a discussion of quantum\nerror correction.",
"arxiv_id": "quant-ph/9809016",
"authors": [
"Eleanor G. Rieffel",
"Wolfgang Polak"
],
"categories": [
"quant-ph",
"cs.GL"
],
"journal_ref": "ACM Comput.Surveys 32:300-335,2000",
"title": "An Introduction to Quantum Computing for Non-Physicists",
"url": "https://arxiv.org/abs/quant-ph/9809016"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6acb4f57-842a-4287-aa68-03b4daf6c3ee",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}