Quantum Optimization Problems

Details Quantum Optimization Problems Quantum Optimization Problems

2002-04-03

arxiv.org/abs/quant-ph/0204010v1

Physics

Quantum Physics

date changed

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Quantum Optimization Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Optimization Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Optimization Problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-340478