arXiv:quant-ph/0105005

Quantum Period Query Proves NP in BQP

Philippe Jorrand, Mehdi Mhalla

Published May 2, 2001• 0 citations

Abstract

Withdrawn by the authors. Since the elements within each period of function hA are not distinct, period finding cannot operate properly. Thanks to all for the comments and sorry for the inconvenience.

DOI: 10.48550/arxiv.quant-ph/0105005

Related papers

Solving in the quantum computer every classical NP problem in polynomial time

Fernando Maroto

This paper has been withdrawn by the author due to a crucial error in eq.59. I apologize for the inconveniences.

arXiv:quant-ph/9801036Jan 16, 19980 citations

A Quantum NP Solver: NP in QP

Clarke, Thomas L.

A attempt at a quantum algorithm for solving NP problems is presented. Now withdrawn because some crucial operators were not unitary.

arXiv:quant-ph/9908080Aug 27, 19990 citations

A family of unitaries for the quantum period finding algorithm

John George Francis, Anil Shaji

Quantum Information ProcessingAug 26, 20230 citations

NP Problem in Quantum Algorithm

Masanori Ohya, Natsuki Masuda

WORLD SCIENTIFIC eBooksFeb 1, 20087 citations

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

Andreas de Vries

This paper has been withdrawn by the author due to an apparent misunderstanding of quantum feedback control.

arXiv:quant-ph/0506137Jun 16, 20050 citations

Open Problems Related to Quantum Query Complexity

Scott Aaronson

I offer a case that quantum query complexity still has loads of enticing and fundamental open problems—from relativized QMA versus QCMA and BQP versus IP , to time/space tradeoffs for collision and element distinctness, to polynomial degree versus quantum query complexity for partial functions, to the Unitary Synthesis Problem and more.

arXiv:2109.06917ACM Transactions on Quantum ComputingDec 21, 202127 citations