Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf

Published Jan 1, 2005• 17 citations
Publisher
DOI
10.1007/978-3-540-31856-9_49

Related papers

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

Theory of Computing Systems•Jun 1, 2007•50 citations

Robust Quantum Algorithms and Polynomials

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

We study the complexity of robust quantum algorithms. These still work with high probability if the n input bits are noisy. We exhibit a robust quantum algorithm that recovers the complete input with high probability using O(n) queries. This implies that every n-bit function can be quantum computed robustly with O(n) queries, which contrasts with Feige et al.’s Ω(n log n) classical bound for PARITY. We also give similar bounds on the degrees of multilinear polynomials that robustly approximate Boolean functions. 1

•Jan 1, 2005•18 citations

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

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.

arXiv:quant-ph/0309220•Journal of Computer and System Sciences•Sep 30, 2003•3 citations

Quantum Algorithms for Network Signal Coordination

Vinayak Dixit, Richard Pech

There has been increasing interest in developing efficient quantum algorithms for hard classical problems. The Network Signal Coordination (NSC) problem is one such problem known to be NP complete. We implement Grover's search algorithm to solve the NSC problem to provide quadratic speedup. We further extend the algorithm to a Robust NSC formulation and analyse its complexity under both constant and polynomial-precision robustness parameters. The Robust NSC problem determines whether there exists a fraction (alpha) of solutions space that will lead to system delays less than a maximum threshold (K). The key contributions of this work are (1) development of a quantum algorithm for the NSC problem, and (2) a quantum algorithm for the Robust NSC problem whose iteration count is O(1/sqrt(alpha)), independent of the search space size, and (3) an extension to polynomial-precision robustness where alpha = alpha_o/p(N) decays polynomially with network size, retaining a quadratic quantum speedup. We demonstrate its implementation through simulation and on an actual quantum computer.

quant-pharXiv:2603.04758•Mar 6, 2026•0 citations

On quantum algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Complexity•Sep 1, 1998•30 citations

On quantum algorithms

CleveRichard, EkertArtur, HendersonLea +2 more

Complexity•Sep 1, 1998•0 citations
We study the complexity of robust quantum algorithms. These still work with high probability if the n input bits are noisy. We exhibit a robust quantum algorithm that recovers the complete input with high probability using O(n) queries. This implies that every n-bit function can be quantum computed robustly with O(n) queries, which contrasts with Feige et al.’s Ω(n log n) classical bound for PARITY. We also give similar bounds on the degrees of multilinear polynomials that robustly approximate Boolean functions. 1
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.
There has been increasing interest in developing efficient quantum algorithms for hard classical problems. The Network Signal Coordination (NSC) problem is one such problem known to be NP complete. We implement Grover's search algorithm to solve the NSC problem to provide quadratic speedup. We further extend the algorithm to a Robust NSC formulation and analyse its complexity under both constant and polynomial-precision robustness parameters. The Robust NSC problem determines whether there exists a fraction (alpha) of solutions space that will lead to system delays less than a maximum threshold (K). The key contributions of this work are (1) development of a quantum algorithm for the NSC problem, and (2) a quantum algorithm for the Robust NSC problem whose iteration count is O(1/sqrt(alpha)), independent of the search space size, and (3) an extension to polynomial-precision robustness where alpha = alpha_o/p(N) decays polynomially with network size, retaining a quadratic quantum speedup. We demonstrate its implementation through simulation and on an actual quantum computer.