Annals of Computer Science and Information Systems, Volume 11

DOI: http://dx.doi.org/10.15439/2017F259

Citation: Proceedings of the 2017 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 11, pages 421–428 (2017)

Full text

Abstract. Quantum Computing is a field of study in computer science based on the laws of quantum physics. Quantum computing is an attractive subject considering that quantum algorithms proved to be more efficient than classical algorithms and the advent of large-scale quantum computation. In particular, Grover's search algorithm is a quantum algorithm that is asymptotically faster than any classical search algorithm and it is relevant for the design of fast optimization algorithms. This article proposes two algorithms based on Grover's adaptative search for biobjective optimization problems where access to the objective functions is given via two different quantum oracles. The proposed algorithms, considering both types of oracles, are compared against NSGA-II, a highly cited multiobjective optimization evolutionary algorithm. Experimental evidence suggests that the quantum optimization methods proposed in this work are at least as effective as NSGA-II in average, considering an equal number of executions. Experimental results showed which oracle required less iterations for similar effectiveness.

References

1. Nielsen, M. A. and Chuang, I. L., Quantum computation and quantum information, Cambridge university press, 2010.
2. Shor, P. W., Algorithms for quantum computation: Discrete logarithms and factoring, In Foundations of Computer Science, 1994 Proceedings, 35th Annual Symposium on (pp. 124-134). IEEE, 1994. http://dx.doi.org/10.1109/SFCS.1994.365700
3. Grover, L. K., A fast quantum mechanical algorithm for database search, In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219), ACM, 1996. http://dx.doi.org/10.1145/237814.237866
4. Dürr, C. and Høyer, P., A quantum algorithm for finding the minimum, arXiv preprint quant-ph/9607014, 1996. doi:10.1.1.57.2796
5. Baritompa, W. P., Bulger, D. W., and Wood, G. R., Grover’s quantum algorithm applied to global optimization, SIAM Journal on Optimization, 15(4), 1170-1184, 2005. http://dx.doi.org/10.1137/040605072
6. Barán, B. and Villagra, M., Multiobjective Optimization in a Quantum Adiabatic Computer. In Proceedings of the 42nd Latin American Conference on Informatics (CLEI), Symposium on Theory of Computation, ENTCS 329, pp.27–38, Valparaiso-Chile, 2016. http://dx.doi.org/10.1016/j.entcs.2016.12.003
7. von Lücken, C., Barán, B. and Brizuela, C., A survey on multi-objective evolutionary algorithms for many-objective problems, Computational Optimization and Applications, 58(3), 707-756, 2014. http://dx.doi.org/10.1007/s10589-014-9644-1
8. Riquelme, N., Baran, B., and von Lücken, C., Performance metrics in multi-objective optimization, Computing Conference (CLEI), 2015 Latin American. IEEE, 2015. http://dx.doi.org/10.1109/CLEI.2015.7360024
9. Lipton, R. J., and Regan, K. W. Quantum Algorithms via Linear Algebra, MIT Press, 2014.
10. Chase, N., et al., A benchmark study of multi-objective optimization methods, BMK-3021, Rev 6, 2009. doi:10.1.1.520.1343
11. E. Zitzler and L. Thiele., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 3(4):257-271, 1999. http://dx.doi.org/10.1109/4235.797969