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

arXiv:quant-ph/0506137

A fast quantum search algorithm by controlled measurement and qubit comparison implying the complexity class inclusion NP in BQP

Andreas de Vries

Published Jun 16, 2005• 1 citation
arXivHTMLPDF

Abstract

This paper has been withdrawn by the author due to an apparent misunderstanding of quantum feedback control.
DOI
10.48550/arxiv.quant-ph/0506137

Related papers

An Exponentially Fast Quantum Search Algorithm

Goong Chen, Zijian Diao

This paper has been withdrawn by the authors.

arXiv:quant-ph/0011109•Nov 27, 2000•13 citations

On Interpolating between Quantum and Classical Complexity Classes

Joseph Maurice Rojas

We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while (*) is doable in quantum randomized polynomial time when m=2 (and no classical randomized polynomial time algorithm is known), (*) is nearly NP-hard for general m: Under a plausible hypothesis involving primes in arithmetic progression (implied by the Generalized Riemann Hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for (*) would imply the widely disbelieved inclusion NP \\subseteq BPP. This type of quantum/classical interpolation phenomenon appears to new.

Chapman & Hall/CRC applied mathematics and nonlinear science series•Sep 19, 2007•1 citation

An Algorithm to Speed Up Quantum Search

Martinelli, Giuseppe, Massimo Panella

The paper has been withdrawn because the research work is still in progress.

arXiv:quant-ph/0609176•Sep 22, 2006•0 citations

A Number Theoretic Interpolation Between Quantum and Classical Complexity Classes

Joseph Maurice Rojas

We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while (*) is doable in quantum randomized polynomial time when m=2 (and no classical randomized polynomial time algorithm is known), (*) is nearly NP-hard for general m: Under a plausible hypothesis involving primes in arithmetic progression (implied by the Generalized Riemann Hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for (*) would imply the widely disbelieved inclusion NP \subseteq BPP. This type of quantum/classical interpolation phenomenon appears to new.

arXiv:quant-ph/0604089•Apr 12, 2006•0 citations

Near-optimal measurement-based feedback control for a single qubit

Ashkan Balouchi, Kurt A. Jacobs

Bulletin of the American Physical Society•Mar 4, 2014•0 citations

On Interpolating between Quantum and Classical Complexity Classes

Joseph Maurice Rojas

Abstract We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while () is doable in quantum randomized polynomial time when m=2, () is nearly NP-complete for general m. In particular, () is in NP for most inputs and, under a plausible hypothesis involving primes in arithmetic progression (implied by the generalized Riemann hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for () would imply the widely disbelieved inclusion NP⊆BPP. This type of quantum/classical interpolation phenomenon appears to be new. As a consequence we can also address recent questions on the complexity of polynomial factorization posed by Cox, and by Karpinski and Shparlinski.

Chapman & Hall/CRC eBooks•Sep 19, 2007•0 citations
We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while (*) is doable in quantum randomized polynomial time when m=2 (and no classical randomized polynomial time algorithm is known), (*) is nearly NP-hard for general m: Under a plausible hypothesis involving primes in arithmetic progression (implied by the Generalized Riemann Hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for (*) would imply the widely disbelieved inclusion NP \\subseteq BPP. This type of quantum/classical interpolation phenomenon appears to new.
We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: (*) Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while (*) is doable in quantum randomized polynomial time when m=2 (and no classical randomized polynomial time algorithm is known), (*) is nearly NP-hard for general m: Under a plausible hypothesis involving primes in arithmetic progression (implied by the Generalized Riemann Hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for (*) would imply the widely disbelieved inclusion NP \subseteq BPP. This type of quantum/classical interpolation phenomenon appears to new.
Abstract We reveal a natural algebraic problem whose complexity appears to interpolate between the well-known complexity classes BQP and NP: Decide whether a univariate polynomial with exactly m monomial terms has a p-adic rational root. In particular, we show that while () is doable in quantum randomized polynomial time when m=2, () is nearly NP-complete for general m. In particular, () is in NP for most inputs and, under a plausible hypothesis involving primes in arithmetic progression (implied by the generalized Riemann hypothesis for certain cyclotomic fields), a randomized polynomial time algorithm for () would imply the widely disbelieved inclusion NP⊆BPP. This type of quantum/classical interpolation phenomenon appears to be new. As a consequence we can also address recent questions on the complexity of polynomial factorization posed by Cox, and by Karpinski and Shparlinski.