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• 16 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

arXiv:quant-ph/0309220•Theory of Computing Systems•Jun 1, 2007•67 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

On quantum algorithms

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

Complexity•Sep 1, 1998•28 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•1 citation

Implementation of a noise-robust quantum algorithm for multivariate polynomial factorization

Iñigo Perez Delgado, Lian-Ao Wu

We implement in an IBM quantum computer a quantum algorithm for multivariate polynomial factoring and propose a noise-avoiding protocol to distill the experimental results in the presence of noise. This algorithm uses single-qubit quantum state tomography (QST) processes to factor a specific type of multivariate polynomials. In one-to-one correspondence, it encodes each multivariate polynomial to one quantum state. While the validity of the algorithm is experimentally verified, the quality of the final results is subjected to the decoherence levels of the preparation of the quantum states. In this paper we propose a protocol to ensure the validity of factors found by our algorithm in the presence of such decoherence and noise. This method might be, in fact, part of a larger class of methods based on that same premise and useful outside the implementation of this specific algorithm. In combination with the noise robustness of the single-qubit QST, our factorization algorithm performs perfectly, even reversing the effects of weak noise, for the second- to fifth-order polynomial cases for which it has been implemented.

Physical Review A•Jul 18, 2022•1 citation

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
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.
We implement in an IBM quantum computer a quantum algorithm for multivariate polynomial factoring and propose a noise-avoiding protocol to distill the experimental results in the presence of noise. This algorithm uses single-qubit quantum state tomography (QST) processes to factor a specific type of multivariate polynomials. In one-to-one correspondence, it encodes each multivariate polynomial to one quantum state. While the validity of the algorithm is experimentally verified, the quality of the final results is subjected to the decoherence levels of the preparation of the quantum states. In this paper we propose a protocol to ensure the validity of factors found by our algorithm in the presence of such decoherence and noise. This method might be, in fact, part of a larger class of methods based on that same premise and useful outside the implementation of this specific algorithm. In combination with the noise robustness of the single-qubit QST, our factorization algorithm performs perfectly, even reversing the effects of weak noise, for the second- to fifth-order polynomial cases for which it has been implemented.