Published: 2021-02-10

Improving Quantum Annealing Performance on Embedded Problems

Michael R. Zielewski, Mulya Agung, Ryusuke Egawa, Hiroyuki Takizawa

Abstract


Recently, many researchers are investigating quantum annealing as a solver for real-world combinatorial optimization problems. However, due to the format of problems that quantum annealing solves and the structure of the physical annealer, these problems often require additional setup prior to solving. We study how these setup steps affect performance and provide insight into the interplay among them using the job-shop scheduling problem for our evaluation. We show that the empirical probability of success is highly sensitive to problem setup and that excess variables and large embeddings reduce performance. We then show that certain problem instances are unable to be solved without the use of additional post-processing methods. Finally, we investigate the effect of pausing during the anneal. Our results show that pausing within a certain time window can improve the probability of success, which is consistent with other work. However, we also show that the performance improvement due to pausing can be masked depending on properties of the embedding, and thus, special care must be taken for embedded problems.

Full Text:

PDF

References


Abbott, A.A., Calude, C.S., Dinneen, M.J., et al.: A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing. International Journal of Quantum Information 17(05), 1950042 (2019), DOI: 10.1142/S0219749919500424

Albash, T., Lidar, D.A.: Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Phys. Rev. X 8(3), 031016 (2018), DOI: 10.1103/PhysRevX.8.031016

Amin, M.H.: Searching for quantum speedup in quasistatic quantum annealers. Phys. Rev. A 92(5), 052323 (2015), DOI: 10.1103/PhysRevA.92.052323

Applegate, D.L., Cook, W.J.: A computational study of the job-shop scheduling problem. INFORMS J. Comput. 3(2), 149–156 (1991), DOI: 10.1287/ijoc.3.2.149

Boothby, K., Bunyk, P., Raymond, J., et al.: 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 (2019), accessed: 2020-11-18

Bowman, E.H.: The schedule-sequencing problem. Operations Research 7(5), 621–624 (1959), DOI: 10.1287/opre.7.5.621

Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. https://arxiv.org/abs/1406.2741 (2014), accessed: 2020-11-18

D-Wave Systems: D-Wave Binary CSP. https://github.com/dwavesystems/dwavebinarycsp, accessed: 2020-07-10

D-Wave Systems: dimod. https://github.com/dwavesystems/dimod, accessed: 2020-07-10

D-Wave Systems: dwave-system. https://github.com/dwavesystems/dwave-system, accessed: 2020-07-10

Date, P., Patton, R.M., Schuman, C.D., et al.: Efficiently embedding QUBO problems on adiabatic quantum computers. Quantum Inf. Process. 18(4), 117 (2019), DOI: 10.1007/s11128-019-2236-3

Denchev, V.S., Boixo, S., Isakov, S.V., et al.: What is the computational value of finite-range tunneling? Phys. Rev. X 6(3), 031015 (2016), DOI: 10.1103/PhysRevX.6.031015

Farhi, E., Goldstone, J., Gutmann, S., et al.: Quantum computation by adiabatic evolution. https://arxiv.org/abs/quant-ph/0001106 (2000), accessed: 2020-11-18

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 22-24 May 1996, Philadelphia, Pennsylvania, USA. pp. 212–219. ACM (1996), DOI: 10.1145/237814.237866

Hen, I., Job, J., Albash, T., et al.: Probing for quantum speedup in spin-glass problems with planted solutions. Phys. Rev. A 92(4), 042325 (2015), DOI: 10.1103/PhysRevA.92.042325

Ikeda, K., Nakamura, Y., Humble, T.S.: Application of quantum annealing to nurse scheduling problem. Scientific Reports 9(1), 12837 (2019), DOI: 10.1038/s41598-019-49172-3

Izquierdo, Z.G., Grabbe, S., Hadfield, S., et al.: Ferromagnetically shifting the power of pausing. https://arxiv.org/abs/2006.08526 (2020), accessed: 2020-11-18

Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5), 5355–5363 (1998), DOI: 10.1103/PhysRevE.58.5355

Karimi, H., Rosenberg, G.: Boosting quantum annealer performance via sample persistence. Quantum Inf. Process. 16(7), 166 (2017), DOI: 10.1007/s11128-017-1615-x

Katzgraber, H.G., Hamze, F., Zhu, Z., et al.: Seeking quantum speedup through spin glasses: The good, the bad, and the ugly. Phys. Rev. X 5(3), 031026 (2015), DOI: 10.1103/PhysRevX.5.031026

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983), DOI: 10.1126/science.220.4598.671

Lanting, T., King, A.D., Evert, B., et al.: Experimental demonstration of perturbative anticrossing mitigation using nonuniform driver hamiltonians. Phys. Rev. A 96(4), 042322 (2017), DOI: 10.1103/PhysRevA.96.042322

Lucas, A.: Ising formulations of many NP problems. Frontiers in Physics 2, 5 (2014), DOI: 10.3389/fphy.2014.00005

Mandrà, S., Zhu, Z., Wang, W., et al.: Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics versus quantum approaches. Phys. Rev. A 94(2), 022337 (2016), DOI: 10.1103/PhysRevA.94.022337

Marshall, J., Venturelli, D., Hen, I., et al.: Power of pausing: Advancing understanding of thermalization in experimental quantum annealers. Phys. Rev. Applied 11(4), 044083 (2019), DOI: 10.1103/PhysRevApplied.11.044083

Okada, S., Ohzeki, M., Taguchi, S.: Efficient partition of integer optimization problems with one-hot encoding. Scientific Reports 9(1), 13036 (2019), DOI: 10.1038/s41598-019-49539-6

Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nature Communications 5(1), 3243 (2014), DOI: 10.1038/ncomms4243

Recruit Communications: PyQUBO. https://github.com/recruit-communications/pyqubo, accessed: 2020-07-10

Rieffel, E.G., Venturelli, D., OGorman, B., et al.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing 14(1), 1–36 (2015), DOI: 10.1007/s11128-014-0892-x

Rosenberg, G., Vazifeh, M., Woods, B., et al.: Building an iterative heuristic solver for a quantum annealer. Comput. Optim. Appl. 65(3), 845–869 (2016), DOI: 10.1007/s10589-016-9844-y

Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303–332 (1999), DOI: 10.1137/S0036144598347011

Stollenwerk, T., OGorman, B., Venturelli, D., et al.: Quantum annealing applied to deconflicting optimal trajectories for air traffic management. IEEE Transactions on Intelligent Transportation Systems 21(1), 285–297 (2020), DOI: 10.1109/TITS.2019.2891235

Tanahashi, K., Takayanagi, S., Motohashi, T., et al.: Application of Ising machines and a software development for Ising machines. Journal of the Physical Society of Japan 88(6), 061010 (2019), DOI: 10.7566/JPSJ.88.061010

Tran, T.T., Do, M., Rieffel, E.G., et al.: A hybrid quantum-classical approach to solving scheduling problems. In: Proceedings of the Ninth Annual Symposium on Combinatorial Search, SOCS 2016, 6-8 July 2016, Tarrytown, NY, USA. pp. 98–106. AAAI Press (2016), http://aaai.org/ocs/index.php/SOCS/SOCS16/paper/view/13958

Tran, T.T., Wang, Z., Do, M., et al.: Explorations of quantum-classical approaches to scheduling a Mars lander activity problem. In: Planning for Hybrid Systems, Papers from the 2016 AAAI Workshop, 13 February 2016, Phoenix, Arizona, USA. AAAI Workshops, vol. WS-16-12. AAAI Press (2016), http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/view/12664

Venturelli, D., Marchand, D.J.J., Rojo, G.: Quantum annealing implementation of job-shop scheduling. In: Proceedings of the EleventhWorkshop on Constraint Satisfaction Techniques for Planning and Scheduling, COPLAS 2016, 13-14 June 2016, London, UK. pp. 25–34 (2016)

Yarkoni, S., Plaat, A., Bäck, T.: First results solving arbitrarily structured maximum independent set problems using quantum annealing. In: 2018 IEEE Congress on Evolutionary Computation, CEC 2018, 8-13 July 2018, Rio de Janeiro, Brazil. pp. 1–6. IEEE (2018), DOI: 10.1109/CEC.2018.8477865

Yarkoni, S., Wang, H., Plaat, A., et al.: Boosting quantum annealing performance using evolution strategies for annealing offsets tuning. In: Feld, S., Linnhoff-Popien, C. (eds.) Quantum Technology and Optimization Problems - First InternationalWorkshop, QTOP@NetSys 2019, 18 March 2019, Munich, Germany, Proceedings. Lecture Notes in Computer Science, vol. 11413, pp. 157–168. Springer (2017), DOI: 10.1007/978-3-030-14082-3_14




Publishing Center of South Ural State University (454080, Lenin prospekt, 76, Chelyabinsk, Russia)