The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries

Simple item page
dc.creatorPapageorgiou, A.
dc.creatorWozniakowski, H.
dc.date2005-04-26
dc.date.accessioned2026-07-07T06:12:41Z
dc.date.available2026-07-07T06:12:41Z
dc.descriptionWe 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 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.
dc.description18 pages
dc.identifierhttps://arxiv.org/abs/quant-ph/0504194
dc.identifierhttp://arxiv.org/abs/quant-ph/0504194
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/92857
dc.subjectQuantum Physics
dc.titleThe Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
dc.typetext

Files

Collections

arXiv