Quantum Optimization Problems

Simple item page
dc.creatorYamakami, Tomoyuki
dc.date2002-04-03
dc.date.accessioned2026-07-07T06:03:54Z
dc.date.available2026-07-07T06:03:54Z
dc.descriptionKrentel [J. Comput. System. Sci., 36, pp.490--509] presented a framework for an NP optimization problem that searches an optimal value among exponentially-many outcomes of polynomial-time computations. This paper expands his framework to a quantum optimization problem using polynomial-time quantum computations and introduces the notion of an ``universal'' quantum optimization problem similar to a classical ``complete'' optimization problem. We exhibit a canonical quantum optimization problem that is universal for the class of polynomial-time quantum optimization problems. We show in a certain relativized world that all quantum optimization problems cannot be approximated closely by quantum polynomial-time computations. We also study the complexity of quantum optimization problems in connection to well-known complexity classes.
dc.descriptiondate changed
dc.identifierhttps://arxiv.org/abs/quant-ph/0204010
dc.identifierhttp://arxiv.org/abs/quant-ph/0204010
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/90117
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleQuantum Optimization Problems
dc.typetext

Files

Collections

arXiv