dorsal/arxiv
View SchemaRobust Polynomials and Quantum Algorithms
| Authors | Harry Buhrman, Ilan Newman, Hein Roehrig, Ronald de Wolf |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0309220 |
| URL | https://arxiv.org/abs/quant-ph/0309220 |
Abstract
We define and study the complexity of robust polynomials for Boolean functions and the related fault-tolerant quantum decision trees, where input bits are perturbed by noise. We compare several different possible definitions. Our main results are * For every n-bit Boolean function f there is an n-variate polynomial p of degree O(n) that robustly approximates it, in the sense that p(x) remains close to f(x) if we slightly vary each of the n inputs of the polynomial. * There is an O(n)-query quantum algorithm that robustly recovers n noisy input bits. Hence every n-bit function can be quantum computed with O(n) queries in the presence of noise. This contrasts with the classical model of Feige et al., where functions such as parity need Theta(n*log n) queries. We give several extensions and applications of these results.
{
"annotation_id": "cf66ffe3-e0cb-4eef-bae2-421b444790fc",
"date_created": "2026-03-02T18:02:03.355000Z",
"date_modified": "2026-03-02T18:02:03.355000Z",
"file_hash": "edd6b64d5b97f76be095a8a41e45ab64fdc7ef8e04a9e764e14abcfad21aa136",
"private": false,
"record": {
"abstract": "We define and study the complexity of robust polynomials for Boolean\nfunctions and the related fault-tolerant quantum decision trees, where input\nbits are perturbed by noise. We compare several different possible definitions.\nOur main results are\n * For every n-bit Boolean function f there is an n-variate polynomial p of\ndegree O(n) that robustly approximates it, in the sense that p(x) remains close\nto f(x) if we slightly vary each of the n inputs of the polynomial.\n * There is an O(n)-query quantum algorithm that robustly recovers n noisy\ninput bits. Hence every n-bit function can be quantum computed with O(n)\nqueries in the presence of noise. This contrasts with the classical model of\nFeige et al., where functions such as parity need Theta(n*log n) queries.\n We give several extensions and applications of these results.",
"arxiv_id": "quant-ph/0309220",
"authors": [
"Harry Buhrman",
"Ilan Newman",
"Hein Roehrig",
"Ronald de Wolf"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Robust Polynomials and Quantum Algorithms",
"url": "https://arxiv.org/abs/quant-ph/0309220"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "a6aa3acb-a0f4-4f25-8826-e5de0746221a",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}