dorsal/arxiv
View SchemaMultilinear Formulas and Skepticism of Quantum Computing
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0311039 |
| URL | https://arxiv.org/abs/quant-ph/0311039 |
Abstract
Several researchers, including Leonid Levin, Gerard 't Hooft, and Stephen Wolfram, have argued that quantum mechanics will break down before the factoring of large numbers becomes possible. If this is true, then there should be a natural set of quantum states that can account for all experiments performed to date, but not for Shor's factoring algorithm. We investigate as a candidate the set of states expressible by a polynomial number of additions and tensor products. Using a recent lower bound on multilinear formula size due to Raz, we then show that states arising in quantum error-correction require n^{Omega(log n)} additions and tensor products even to approximate, which incidentally yields the first superpolynomial gap between general and multilinear formula size of functions. More broadly, we introduce a complexity classification of pure quantum states, and prove many basic facts about this classification. Our goal is to refine vague ideas about a breakdown of quantum mechanics into specific hypotheses that might be experimentally testable in the near future.
{
"annotation_id": "667cbfe1-d363-48d6-bbed-1520151f5176",
"date_created": "2026-03-02T18:02:03.637000Z",
"date_modified": "2026-03-02T18:02:03.637000Z",
"file_hash": "d0fead59531c798de2b5f1c3b4da6185fee2b61b6163c349b916b9c9dcff99dc",
"private": false,
"record": {
"abstract": "Several researchers, including Leonid Levin, Gerard \u0027t Hooft, and Stephen\nWolfram, have argued that quantum mechanics will break down before the\nfactoring of large numbers becomes possible. If this is true, then there should\nbe a natural set of quantum states that can account for all experiments\nperformed to date, but not for Shor\u0027s factoring algorithm. We investigate as a\ncandidate the set of states expressible by a polynomial number of additions and\ntensor products. Using a recent lower bound on multilinear formula size due to\nRaz, we then show that states arising in quantum error-correction require\nn^{Omega(log n)} additions and tensor products even to approximate, which\nincidentally yields the first superpolynomial gap between general and\nmultilinear formula size of functions. More broadly, we introduce a complexity\nclassification of pure quantum states, and prove many basic facts about this\nclassification. Our goal is to refine vague ideas about a breakdown of quantum\nmechanics into specific hypotheses that might be experimentally testable in the\nnear future.",
"arxiv_id": "quant-ph/0311039",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Multilinear Formulas and Skepticism of Quantum Computing",
"url": "https://arxiv.org/abs/quant-ph/0311039"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "874cce95-01af-42f6-b8bf-f846a17c95fb",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}