Quantum solutions for densest k-subgraph problems
Tóm tắt
In this paper, we present, for the first time, quantum annealing solutions for densest k-subgraph problems which have many applications in computational biology. Our solutions are formulated as solutions for quadratic unconstrained binary optimization (QUBO) and integer programming problems, proved to be equivalent with the densest k-subgraph problems and then tested on an D-Wave 2X machine. The QUBO formulations are optimal in terms of the number of logical qubits, but require the highest number of physical qubits after embedding. Experimental work reported here suggests that the D-Wave 2X model cannot handle problems of this difficulty. The next generation of D-wave hardware architecture—the Pegasus architecture—is much denser than the current one, so dense QUBOs will be easier to embed. The experimental work also suggests that the current built-in post-processing optimization method does not work very well for some problems and the default setting (post-processing optimization on) should be avoided (or at least tested before being turned on).
Tài liệu tham khảo
Abbott, A. A., Calude, C. S., Dinneen, M. J., & Hua, R. (2018). A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing. CDMTCS Report Series 520.
Billionnet, A. (2005). Different formulations for solving the heaviest k-subgraph problem. INFOR: Information Systems and Operational Research, 43(3), 171–186.
Bollobás, B. (1981). Degree sequences of random graphs. Discrete Mathematics, 33(1), 1–19.
Bomze, I. M., Budinich, M., Pardalos, P., & Pelillo, M. (1999). Handbook of combinatorial optimization. In D.-Z. Du & P. M. Pardalos (Eds.), chap. The maximum clique problem (pp. 1–74). Dordrecht: Kluwer Academic Publishers.
Boothby, T., King, A. D., & Roy, A. (2016). Fast clique minor generation in Chimera quit connectivity graphs. Quantum Information Processing, 15(1), 495–508.
Calude, C. S., Calude, E., & Dinneen, M. J. (2015). Adiabatic quantum computing challenges. ACM SIGACT News, 46(1), 40–61. https://doi.org/10.1145/2744447.2744459.
Calude, C. S., Dinneen, M. J., & Hua, R. (2017). QUBO formulations for the graph isomorphism problem and related problems. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2017.04.016.
Calude, C. S., Dinneen, M. J., & Hua, R. (2019). Quantum solutions for densest \(k\)-subgraph problems. Report CDMTCS-540, Centre for Discrete Mathematics and Theoretical Computer Science, University of Auckland, Auckland, New Zealand. https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports. Accessed Dec 2019.
Canzar, S., Andreotti, S., Weese, D., Reinert, K., & Klau, G. W. (2016). CIDANE: Comprehensive isoform discovery and abundance estimation. Genome Biology, 17, 16.
Corneil, D. G., & Perl, Y. (1984). Clustering and domination in perfect graphs. Discrete Applied Mathematics, 9(1), 27–39.
D-Wave Systems. (2018). D-Wave Problem-Solving Handbook. User Manual. https://docs.dwavesys.com/docs/latest/doc_handbook.html. Accessed Dec 2019.
D-Wave Systems. (2018). D-Wave Solver Properties and Parameters Reference. User Manual. https://docs.dwavesys.com/docs/latest/doc_solver_ref.html. Accessed Dec 2019.
D-Wave Systems. (2018). Postprocessing Methods on D-Wave Systems. User Manual. https://docs.dwavesys.com/docs/latest/doc_post-processing.html. Accessed Dec 2019.
D-Wave Systems. (2019). Next-Generation Topology of D-Wave Quantum Processors. https://www.dwavesys.com/sites/default/files/14-1026A- C_Next-Generation-Topology-of-DW-Quantum-Processors.pdf. Accessed Dec 2019.
D-Wave Systems, Inc. (2018). Developer guide for Python. Technical Report Release 2.4 09-1024A-K.
Dinneen, M. J., & Hua, R. (2017). Formulating graph covering problems for adiabatic quantum computers. In: Proceedings of the Australasian Computer Science Week Multiconference, ACSW ’17 (pp. 18:1–18:10). New York, NY, USA: ACM. https://doi.org/10.1145/3014812.3014830.
Fratkin, E., Naughton, B. T., Brutlag, D. L., & Batzoglou, S. (2006). Motifcut: Regulatory motifs finding with maximum density subgraphs. Bioinformatics, 22(14), e150–1e57.
Hagberg, A., Schult, D., & Swart, P. (2019). NetworkX. Software for Complex Networks
Hamerly, R., Inagaki, T., McMahon, P. L., Venturelli, D., Marandi, A., Onodera, T., et al. (2019). Experimental investigation of performance differences between coherent ising machines and a quantum annealer. Science Advances, 5(5), eaau0823.
Hua, R., & Dinneen, M. J. (2020). Improved QUBO formulation of the graph isomorphism problem. SN Computer Science, 1(1), 19.
Jensen, F. V., Lauritzen, S. L., & Olesen, K. G. (1990). Bayesian updating incausal probabilistic networks by local computations. Computational Statistics Quarterly, 4, 269–282.
Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse ising model. Physical Review E, 58(5), 5355.
Keil, J. M., & Brecht, T. B. (1991). The complexity of clustering in planar graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 9, 155–159.
Khuller, S., Saha, B. (2009) On finding dense subgraphs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming: Part I, ICALP ’09 (pp. 597–608). Berlin: Springer. https://doi.org/10.1007/978-3-642-02927-1_50.
Markowitz, H. M. (1957). The elimination form of the inverse and its application to linear programming. Management Science, 3(3), 255–269.
McGeoch, C. C. (2014). Adiabatic quantum computation and quantum annealing. Theory and practice. San Rafael: Morgan & Claypool Publishers.
McGeoch, C. C., Harris, R., Reinhardt, S. P., & Bunyk, P. I. (2019). Practical annealing-based quantum computing. Computer, 52, 38–46.
Paun, G., Rozenberg, G., & Salomaa, A. (2010). The oxford handbook of membrane computing. New York: Oxford University Press Inc.
Pudenz, K. L., Albash, T., & Lidar, D. A. (2014). Error-corrected quantum annealing with hundreds of qubits. Nature Communications, 5, 3243.
Saha, B., Hoch, A., Khuller, S., Raschid, L., & Zhang, X. N. (2010). Dense subgraphs with restrictions and applications to gene annotation graphs. In B. Berger (Ed.), Research in computational molecular biology (pp. 456–472). Berlin: Springer.
Stein, W., et al. (2016). Sage mathematics software (version 7.0).