The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries |
| |
Authors: | A. Papageorgiou H. Woźniakowski |
| |
Affiliation: | (1) Department of Computer Science, Columbia University, Columbia, NY, USA;(2) Institute of Applied Mathematics and Mechanics, University of Warsaw, Warsaw, 00-927, Poland |
| |
Abstract: | We show how a number of NP-complete as well as NP-hard problems can be reduced to the Sturm-Liouville eigenvalue problem in the quantum setting with queries. We consider power queries which are derived from the propagator of a system evolving with a Hamiltonian obtained from the discretization of the Sturm-Liouville operator. We use results of our earlier paper concering the complexity of the Sturm-Liouville eigenvalue problem. We show that the number of power queries as well the number of qubits needed to solve the problems studied in this paper is a low degree polynomial. The implementation of power queries by a polynomial number of elementary quantum gates is an open issue. If this problem is solved positively for the power queries used for the Sturm-Liouville eigenvalue problem then a quantum computer would be a very powerful computation device allowing us to solve NP-complete problems in polynomial time. |
| |
Keywords: | Complexity quantum algorithms appoximation NP complete problems |
本文献已被 SpringerLink 等数据库收录! |