Journal of Advances in Applied Mathematics

Download PDF (465.7 KB) PP. 82 - 90 Pub. Date: July 1, 2018

DOI: 10.22606/jaam.2018.33002

• Richard H. Warren^*
  Lockheed Martin Corporation-Retired

This paper describes the logic and creativity needed in order to have high probability of solving discrete optimization problems on a quantum annealing computer. Current features of quantum computing via annealing are discussed. We illustrate the logic at the forefront of this new era of computing, describe some of the work done in this field, and indicate the distinct mindset that is used when programming this type of machine. The traveling salesman problem is formulated for solving on a quantum annealing computer, which illustrates the methods for this computer.

Quantum annealing, Ising objective function, Boolean logic, penalty functions, traveling salesman problem

[1] S. H. Adachi and M. P. Henderson. 2015. Application of quantum annealing to training of deep neural networks. arXiv:1510.06356, 18 pages.

[2] M. Benedetti, J. Realpe-Gomez, R. Biswas, and A. Perdomo-Ortiz. 2016. Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning. Phys. Rev. A 94, 022308.

[3] Z. Bian, F. Chudak, W. G. Macready, G. Rose. 2010. The Ising model: teaching an old problem new tricks. DWave Systems. http://www.dwavesys.com/sites/default/files/weightedmaxsat_v2.pdf

[4] Z. Bian, F. Chudak, W. G. Macready, L. Clark, F. Gaitan. 2013. Experimental determination of Ramsey numbers. Phys. Rev. Lett. 111, 130505.

[5] Z. Bian, F. Chudak, R. Israel, B. Lackey, W. G. Macready, A. Roy. 2014. Discrete optimization using quantum annealing on sparse Ising models. Front. Phys. 2 Article 56.

[6] E. Boros and P. L. Hammer. 2001. Pseudo-Boolean Optimization. http://rutcor.rutgers.edu/~boros/Papers/2002-DAM-BH.pdf

[7] S. Boixo, T. F. R?nnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, M. Troyer. 2014. Evidence for quantum annealing with more than one hundred qubits. Nature Physics 10, 218-224. DOI: 10.1038/nphys2900

[8] S. Boixo, G. Ortiz, R. Somma. 2015. Fast quantum methods for optimization. Eur. Phys. J. Special Topics 224, 35-49.

[9] M. Henderson, J. Novak, T. Cook. 2018. Leveraging adiabatic quantum computation for election forecasting. arXiv:1802.00069

[10] V. Horan, S. Adachi, S. Bak. 2016. A comparison of approaches for finding minimum identifying codes on graphs. Quantum Inf. Process. 15, 1827-1848.

[11] Z. Jiang and E. G. Rieffel. 2017. Non-commuting two-local Hamiltonians for quantum error suppression. Quantum Inf. Process. 16, Article 89. https://doi.org/10.1007/s11128-017-1527-9

[12] M. W. Johnson et al. 2011. Quantum annealing with manufactured spins. Nature 473, 194-198. DOI: 10.1038/nature10012

[13] K. Karimi, N. G. Dickson, F. Hamze, M. H. S. Amin, M. Drew-Brook, F. A. Chudak, P. I. Bunyk, W. G. Macready, G. Rose. 2012. Investigating the performance of an adiabatic quantum optimization processor. Quantum Inf. Process. 11, 77-88.

[14] H. G. Katzgraber, F. Hamze, R. S. Andrist. 2014. Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Phys. Review X 4, 021008.

[15] J. King, S. Yarkoni, M. M. Nevisi, J. P. Hilton, C. C. McGeoch. 2015. Benchmarking a quantum annealing processor with the time-to-target metric. arXiv:1508.05087

[16] D. Korenkevych, Y. Xue, Z. Bian, F. Chudak, W. G. Macready, J. Rolfe, E. Andriyash. 2016. Benchmarking quantum hardware for training of fully visible Boltzmann machines. arXiv:1611.04528

[17] T. Lanting et al. 2014. Entanglement in a quantum annealing processor. Phys. Rev. X 4, 021041. DOI: 10.1103/PhysRevX.4.021041

[18] A. Lucas. 2014. Ising formulations of many NP problems. Front. Phys. 2 Article 5, 15 pages. DOI:10.3389/fphy.2014.00005

[19] V. Martin-Mayor and I. Hen. 2015. Unraveling quantum annealers using classical hardness. Scientific Reports 5, 15324.

[20] C. C. McGeoch and C. Wang. 2013. Experimental evaluation of an adiabatic quantum system for combinatorial optimization, Proceedings of the ACM International Conference on Computing Frontiers, Article No. 23, ACM Press. DOI:10.1145/2482767.2482797

[21] C. C. McGeoch. 2014. Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice, Morgan & Claypool.

[22] F. Neukart, D. Von Dollen, C. Seidel, G. Compostella. 2018. Quantum-enhanced reinforcement learning for finite-episode games with discrete state spaces. Front. Phys. 5, Article 71. DOI:10.3389/fphy.2017.00071

[23] Programming with QUBOs. 2016. Release 2.4, D-Wave Systems. Available upon request at inquiry@dwavesys.com.

[24] K. L. Pudenz, T. Albash, D. A. Lidar. 2014. Error-corrected quantum annealing with hundreds of qubits. Nature Communications 5, Article No. 3243.

[25] E. G. Rieffel, D. Venturelli, B. O’Gorman, M. B. Do, E. M. Prystay, V. N. Smelyanskiy. 2015. A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14, 1-36.

[26] T. F. R?nnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, M. Troyer. 2014. Defining and detecting quantum speedup. Nature 345, 420-424.

[27] G. E. Santoro and E. Tosatti. 2006. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. J. Phys. A 39, R393-R431. DOI:10.1088/0305-4470/39/36/R01

[28] P. Shor. 1997. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484-1509.

[29] S. Suzuki, J. Inoue, B. K. Chakrabarti. 2013. Quantum Ising Phases and Transitions in Transverse Ising Models, 2nd edition, Springer-Verlag.

[30] R. H. Warren. 2013. Adapting the traveling salesman problem to an adiabatic quantum computer, Quantum Inf. Process. 12, 1781-1785. DOI:10.1007/s11128-012-0490-8

[31] J. D. Whitfield, M. Faccin, J. D. Biamonte. 2012. Ground-state spin logic. Europhysics Letters 99, 57004. DOI:10.1209/0295-5075/99/57004

[32] T. Albash and D. A. Lidar. 2018. Adiabatic quantum computing, Rev. Mod. Phys. 90, 015002. DOI:10.1103/RevModPhys.90.015002