Quantum Optimization Problems
<|reference_start|>Quantum Optimization Problems: 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.<|reference_end|>
@article{yamakami2002quantum,
    title={Quantum Optimization Problems},
    author={Tomoyuki Yamakami},
    journal={arXiv preprint arXiv:quant-ph/0204010},
    year={2002},
    archivePrefix={arXiv},
    eprint={quant-ph/0204010},
    primaryClass={quant-ph cs.CC}
}