dorsal/arxiv
View SchemaA Limit on the Speed of Quantum Computation in Determining Parity
| Authors | E. Farhi, J. Goldstone, S. Gutmann, M. Sipser |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9802045 |
| URL | https://arxiv.org/abs/quant-ph/9802045 |
| DOI | 10.1103/PhysRevLett.81.5442 |
| Journal | Phys.Rev.Lett.81:5442-5444,1998 |
Abstract
Consider a function f which is defined on the integers from 1 to N and takes the values -1 and +1. The parity of f is the product over all x from 1 to N of f(x). With no further information about f, to classically determine the parity of f requires N calls of the function f. We show that any quantum algorithm capable of determining the parity of f contains at least N/2 applications of the unitary operator which evaluates f. Thus for this problem, quantum computers cannot outperform classical computers.
{
"annotation_id": "38e691c7-802d-4fd3-9634-0437b4357488",
"date_created": "2026-03-02T18:02:41.302000Z",
"date_modified": "2026-03-02T18:02:41.302000Z",
"file_hash": "1d7422b8c51c1a081c5a2c3a0596b17dc0c8b30ef800f9322ed8968d03b6cbec",
"private": false,
"record": {
"abstract": "Consider a function f which is defined on the integers from 1 to N and takes\nthe values -1 and +1. The parity of f is the product over all x from 1 to N of\nf(x). With no further information about f, to classically determine the parity\nof f requires N calls of the function f. We show that any quantum algorithm\ncapable of determining the parity of f contains at least N/2 applications of\nthe unitary operator which evaluates f. Thus for this problem, quantum\ncomputers cannot outperform classical computers.",
"arxiv_id": "quant-ph/9802045",
"authors": [
"E. Farhi",
"J. Goldstone",
"S. Gutmann",
"M. Sipser"
],
"categories": [
"quant-ph"
],
"doi": "10.1103/PhysRevLett.81.5442",
"journal_ref": "Phys.Rev.Lett.81:5442-5444,1998",
"title": "A Limit on the Speed of Quantum Computation in Determining Parity",
"url": "https://arxiv.org/abs/quant-ph/9802045"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "90954c05-fde5-4656-afa9-02fa79e82ea3",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}