dorsal/arxiv
View SchemaQuantum Computers, Factoring, and Decoherence
| Authors | I. Chuang, Raymond Laflamme, P. Shor, W. Zurek |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9503007 |
| URL | https://arxiv.org/abs/quant-ph/9503007 |
| DOI | 10.1126/science.270.5242.1633 |
Abstract
In a quantum computer any superposition of inputs evolves unitarily into the corresponding superposition of outputs. It has been recently demonstrated that such computers can dramatically speed up the task of finding factors of large numbers -- a problem of great practical significance because of its cryptographic applications. Instead of the nearly exponential ($\sim \exp L^{1/3}$, for a number with $L$ digits) time required by the fastest classical algorithm, the quantum algorithm gives factors in a time polynomial in $L$ ($\sim L^2$). This enormous speed-up is possible in principle because quantum computation can simultaneously follow all of the paths corresponding to the distinct classical inputs, obtaining the solution as a result of coherent quantum interference between the alternatives. Hence, a quantum computer is sophisticated interference device, and it is essential for its quantum state to remain coherent in the course of the operation. In this report we investigate the effect of decoherence on the quantum factorization algorithm and establish an upper bound on a ``quantum factorizable'' $L$ based on the decoherence suffered per operational step.
{
"annotation_id": "93e82925-b5dd-40c2-a904-1bf782cbc7ef",
"date_created": "2026-03-02T18:02:38.138000Z",
"date_modified": "2026-03-02T18:02:38.138000Z",
"file_hash": "3bcf714351d4225779cec4a517f39cd04ce7d6ccc99bae307acc91a5b06f0a19",
"private": false,
"record": {
"abstract": "In a quantum computer any superposition of inputs evolves unitarily into the\ncorresponding superposition of outputs. It has been recently demonstrated that\nsuch computers can dramatically speed up the task of finding factors of large\nnumbers -- a problem of great practical significance because of its\ncryptographic applications. Instead of the nearly exponential ($\\sim \\exp\nL^{1/3}$, for a number with $L$ digits) time required by the fastest classical\nalgorithm, the quantum algorithm gives factors in a time polynomial in $L$\n($\\sim L^2$). This enormous speed-up is possible in principle because quantum\ncomputation can simultaneously follow all of the paths corresponding to the\ndistinct classical inputs, obtaining the solution as a result of coherent\nquantum interference between the alternatives. Hence, a quantum computer is\nsophisticated interference device, and it is essential for its quantum state to\nremain coherent in the course of the operation. In this report we investigate\nthe effect of decoherence on the quantum factorization algorithm and establish\nan upper bound on a ``quantum factorizable\u0027\u0027 $L$ based on the decoherence\nsuffered per operational step.",
"arxiv_id": "quant-ph/9503007",
"authors": [
"I. Chuang",
"Raymond Laflamme",
"P. Shor",
"W. Zurek"
],
"categories": [
"quant-ph"
],
"doi": "10.1126/science.270.5242.1633",
"title": "Quantum Computers, Factoring, and Decoherence",
"url": "https://arxiv.org/abs/quant-ph/9503007"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "604b9b33-0e2f-47ad-b7d0-7df8f54b8e21",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}