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

DOI10.1007/S11128-006-0043-0MaRDI QIDQ2384174zbMATH OpenOpenAlexDBLPWikidataFDO

Authors A. Papageorgiou, H. Woźniakowski

Publication date 20 September 2007

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0504194

zbMATH Keywords

approximationComplexityNP complete problemsquantum algorithms

Mathematics Subject Classification ID

Sturm-Liouville theory (34B24) Analysis of algorithms (68W40) Quantum computation (81P68)

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 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.

Recommendations

• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem
• A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer
• On the complexity of the multivariate Sturm-Liouville eigenvalue problem
• Quantum computation and NP-complete problems
• Solving NP-Complete Problems with Quantum Search

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 996050 (Why is no real title available?)
• scientific article; zbMATH DE number 48198 (Why is no real title available?)
• scientific article; zbMATH DE number 3555381 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• scientific article; zbMATH DE number 3274421 (Why is no real title available?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum complexity of integration
• Quantum Complexity Theory
• Quantum integration in Sobolev classes
• Strengths and Weaknesses of Quantum Computing
• The quantum query complexity of approximating the median and related statistics

Cited in

(5)

• On the complexity of the multivariate Sturm-Liouville eigenvalue problem
• On the complexity of searching for a maximum of a function on a quantum computer
• Classical and quantum complexity of the Sturm-Liouville eigenvalue problem
• A lower bound for the Sturm-Liouville eigenvalue problem on a quantum computer
• The quantum query complexity of elliptic PDE

This page was built for publication: The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2384174)