{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:30:25Z","timestamp":1762522225779,"version":"build-2065373602"},"reference-count":63,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T00:00:00Z","timestamp":1539302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["Fronteras de la Ciencia 1007 and SNI number 41594"],"award-info":[{"award-number":["Fronteras de la Ciencia 1007 and SNI number 41594"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>In this paper, we propose a methodology to solve the stereo matching problem through quantum annealing optimization. Our proposal takes advantage of the existing Min-Cut\/Max-Flow network formulation of computer vision problems. Based on this network formulation, we construct a quadratic pseudo-Boolean function and then optimize it through the use of the D-Wave quantum annealing technology. Experimental validation using two kinds of stereo pair of images, random dot stereograms and gray-scale, shows that our methodology is effective.<\/jats:p>","DOI":"10.3390\/e20100786","type":"journal-article","created":{"date-parts":[[2018,10,12]],"date-time":"2018-10-12T10:54:03Z","timestamp":1539341643000},"page":"786","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["A QUBO Formulation of the Stereo Matching Problem for D-Wave Quantum Annealers"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9892-1913","authenticated-orcid":false,"given":"William","family":"Cruz-Santos","sequence":"first","affiliation":[{"name":"CU-UAEM Valle de Chalco, Hermenegildo Galeana 3, Valle de Chalco 56615, Estado de M\u00e9xico, Mexico"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7444-4534","authenticated-orcid":false,"given":"Salvador E.","family":"Venegas-Andraca","sequence":"additional","affiliation":[{"name":"Tecnologico de Monterrey, Escuela de Ingenieria y Ciencias. Ave., Eugenio Garza Sada 2501, Monterrey 64849, NL, Mexico"}]},{"given":"Marco","family":"Lanzagorta","sequence":"additional","affiliation":[{"name":"US Naval Research Laboratory, 4555 Overlook Ave., SW Washington, DC 20375, USA"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Klette, R. (2014). Concise Computer Vision: An Introduction into Theory and Algorithms, Springer Publishing Company.","DOI":"10.1007\/978-1-4471-6320-6"},{"key":"ref_2","unstructured":"Stockman, G., and Shapiro, L.G. (2001). Computer Vision, Prentice Hall PTR. [1st ed.]."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Szeliski, R. (2010). Computer Vision: Algorithms and Applications, Springer. [1st ed.].","DOI":"10.1007\/978-1-84882-935-0"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1109\/TPAMI.2003.1217603","article-title":"Advances in Computational Stereo","volume":"25","author":"Brown","year":"2003","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Hartley, R., and Zisserman, A. (2003). Multiple View Geometry in Computer Vision, Cambridge University Press. [2nd ed.].","DOI":"10.1017\/CBO9780511811685"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Triggs, B., McLauchlan, P.F., Hartley, R.I., and Fitzgibbon, A.W. (2000, January 21\u201322). Bundle Adjustment\u2014A Modern Synthesis. Proceedings of the International Workshop on Vision Algorithms: Theory and Practice, Corfu, Greece.","DOI":"10.1007\/3-540-44480-7_21"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1023\/A:1008103604354","article-title":"Integrated Person Tracking Using Stereo, Color, and Pattern Detection","volume":"37","author":"Darrell","year":"2000","journal-title":"Int. J. Comput. Vis."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1109\/CVPR.2006.19","article-title":"A Comparison and Evaluation of Multi-View Stereo Reconstruction Algorithms","volume":"Volume 1","author":"Seitz","year":"2006","journal-title":"Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1109\/MCG.2004.1297011","article-title":"Image-Based Interactive Exploration of Real-World Environments","volume":"24","author":"Uyttendaele","year":"2004","journal-title":"IEEE Comput. Graph. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Konolige, K., and Bolles, R.C. (2007, January 21\u201322). Localization and Mapping for Autonomous Navigation in Outdoor Terrains: A Stereo Vision Approach. Proceedings of the 2007 IEEE Workshop on Applications of Computer Vision (WACV \u201907), Austin, TX, USA.","DOI":"10.1109\/WACV.2007.40"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1080\/00107514.2014.964942","article-title":"An introduction to quantum machine learning","volume":"56","author":"Schuld","year":"2014","journal-title":"Contemp. Phys."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1038\/nature23474","article-title":"Quantum machine learning","volume":"549","author":"Biamonte","year":"2017","journal-title":"Nature"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/nphys3029","article-title":"Quantum principal component analysis","volume":"10","author":"Lloyd","year":"2014","journal-title":"Nat. Phys."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"130503","DOI":"10.1103\/PhysRevLett.113.130503","article-title":"Quantum Support Vector Machine for Big Data Classification","volume":"113","author":"Rebentrost","year":"2014","journal-title":"Phys. Rev. Lett."},{"key":"ref_15","unstructured":"Adachi, S.H., and Henderson, M.P. (arXiv, 2015). Application of Quantum Annealing to Training of Deep Neural Networks, arXiv."},{"key":"ref_16","unstructured":"Kulchytskyy, B., Andriyash, E., Amin, M., and Melko, R. (arXiv, 2016). Quantum Boltzmann Machine, arXiv."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"022308","DOI":"10.1103\/PhysRevA.94.022308","article-title":"Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning","volume":"94","author":"Benedetti","year":"2016","journal-title":"Phys. Rev. A"},{"key":"ref_18","first-page":"130503","article-title":"Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models","volume":"7","author":"Benedetti","year":"2017","journal-title":"Phys. Rev. X"},{"key":"ref_19","unstructured":"(2018, January 07). IBM Quantum Experience. Available online: http:\/\/research.ibm.com\/ibm-q\/."},{"key":"ref_20","unstructured":"(2018, January 07). D-Wave systems. Available online: http:\/\/www.dwavesys.com\/."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1038\/srep00571","article-title":"Finding low-energy conformations of lattice protein models by quantum annealing","volume":"2","author":"Dickson","year":"2012","journal-title":"Sci. Rep."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1140\/epjst\/e2015-02347-y","article-title":"A quantum annealing approach for fault detection and diagnosis of graph-based systems","volume":"224","author":"Fluegemann","year":"2015","journal-title":"Eur. Phys. J. Spec. Top."},{"key":"ref_23","unstructured":"King, J., Yarkoni, S., Nevisi, M.M., Hilton, J.P., and McGeoch, C.C. (arXiv, 2015). Benchmarking a quantum annealing processor with the time-to-target metric, arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"14","DOI":"10.3389\/fict.2016.00014","article-title":"Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis","volume":"3","author":"Bian","year":"2016","journal-title":"Front. ICT"},{"key":"ref_25","first-page":"8","article-title":"An Accelerator Architecture for Combinatorial Optimization Problems","volume":"53","author":"Tsukamoto","year":"2017","journal-title":"Fujitsu Sci. Tech. J."},{"key":"ref_26","first-page":"78","article-title":"Ising Computer","volume":"65","author":"Yamaoka","year":"2016","journal-title":"Hitachi Rev."},{"key":"ref_27","first-page":"174","article-title":"A cross-disciplinary introduction to quantum annealing-based algorithms","volume":"5982","author":"McGeoch","year":"2018","journal-title":"Contemp. Phys."},{"key":"ref_28","unstructured":"Apolloni, B., Cesa-Bianchi, N., and de Falco, D. (1988, January 4\u20139). A numerical implementation of Quantum Annealing. Proceedings of the Stochastic Processes, Physics and Geometry, Ascona, Switzerland."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0304-4149(89)90040-9","article-title":"Quantum stochastic optimization","volume":"33","author":"Apolloni","year":"1989","journal-title":"Stoch. Process. Appl."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"4141","DOI":"10.1021\/j100163a045","article-title":"Novel approach for computing the global minimum of proteins. 1. General concepts, methods, and approximations","volume":"95","author":"Somorjai","year":"1991","journal-title":"J. Phys. Chem."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"6715","DOI":"10.1021\/j100127a023","article-title":"Global energy minimum searches using an approximate solution of the imaginary time Schroedinger equation","volume":"97","author":"Amara","year":"1993","journal-title":"J. Phys. Chem."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0009-2614(94)00117-0","article-title":"Quantum annealing: A new method for minimizing multidimensional functions","volume":"219","author":"Finnila","year":"1994","journal-title":"Chem. Phys. Lett."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"5355","DOI":"10.1103\/PhysRevE.58.5355","article-title":"Quantum annealing in the transverse Ising model","volume":"58","author":"Kadowaki","year":"1998","journal-title":"Phys. Rev. E"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"R393","DOI":"10.1088\/0305-4470\/39\/36\/R01","article-title":"Optimization using quantum mechanics: quantum annealing through adiabatic evolution","volume":"39","author":"Santoro","year":"2006","journal-title":"J. Phys. A Math. Gen."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","article-title":"On the computational complexity of Ising spin glass models","volume":"15","author":"Barahona","year":"1982","journal-title":"J. Phys. A Math. Gen."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","article-title":"Pseudo-boolean Optimization","volume":"123","author":"Boros","year":"2002","journal-title":"Discret. Appl. Math."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1126\/science.1057726","article-title":"A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem","volume":"292","author":"Farhi","year":"2001","journal-title":"Science"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"102111","DOI":"10.1063\/1.2798382","article-title":"Bounds for the adiabatic approximation with applications to quantum computation","volume":"48","author":"Jansen","year":"2007","journal-title":"J. Math. Phys"},{"key":"ref_40","unstructured":"Forsyth, D.A., and Ponce, J. (2002). Computer Vision: A Modern Approach, Pearson."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/TPAMI.1985.4767639","article-title":"Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming","volume":"PAMI-7","author":"Ohta","year":"1985","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1109\/TPAMI.2003.1206509","article-title":"Stereo matching using belief propagation","volume":"25","author":"Sun","year":"2003","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1109\/34.969114","article-title":"Fast Approximate Energy Minimization via Graph Cuts","volume":"23","author":"Boykov","year":"2001","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An Experimental Comparison of Min-Cut\/Max-Flow Algorithms for Energy Minimization in Vision","volume":"26","author":"Boykov","year":"2004","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Veksler, O. (2006, January 4\u20137). Reducing Search Space for Stereo Correspondence with Graph Cuts. Proceedings of the British Machine Vision Conference 2006, Edinburgh, UK.","DOI":"10.5244\/C.20.73"},{"key":"ref_46","unstructured":"Papadimitriou, C.H., and Steiglitz, K. (1982). Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","article-title":"The Complexity of Multiterminal Cuts","volume":"23","author":"Dahlhaus","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02523685","article-title":"Primal-dual approximation algorithms for integral flow and multicut in trees","volume":"18","author":"Garg","year":"1997","journal-title":"Algorithmica"},{"key":"ref_49","unstructured":"Boros, E., and Gruber, A. (arXiv, 2014). On Quadratization of Pseudo-Boolean Functions, arXiv."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2016.01.001","article-title":"Quadratization of symmetric pseudo-Boolean functions","volume":"203","author":"Anthony","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_51","unstructured":"Freedman, D., and Drineas, P. (2005, January 20\u201326). Energy Minimization via Graph Cuts: Settling What is Possible. Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), San Diego, CA, USA."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","article-title":"Transformation of General Binary MRF Minimization to the First-Order Case","volume":"33","author":"Ishikawa","year":"2011","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_53","unstructured":"Tanburn, R., and Dattani, N.S. (2018, September 17). Quadratization in Pseudo-Boolean Optimization and Adiabatic Quantum Computing. Available online: https:\/\/github.com\/ndattani\/quadratizationReview."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Zureiki, A., Devy, M., and Chatila, R. (October, January 16). Stereo Matching using Reduced-Graph Cuts. Proceedings of the 2007 IEEE International Conference on Image Processing, San Antonio, TX, USA.","DOI":"10.1109\/ICIP.2007.4378935"},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Hartley, R.I., and Wang, L. (2010, January 5\u201311). Fast Multi-labelling for Stereo Matching. Proceedings of the 11th European Conference on Computer Vision (ECCV 2010), Heraklion, Crete, Greece.","DOI":"10.1007\/978-3-642-15558-1_38"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s11128-008-0082-9","article-title":"Minor-embedding in adiabatic quantum computation: I. The parameter setting problem","volume":"7","author":"Choi","year":"2008","journal-title":"Quantum Inf. Process."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s11128-010-0200-3","article-title":"Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design","volume":"10","author":"Choi","year":"2011","journal-title":"Quantum Inf. Process."},{"key":"ref_58","unstructured":"Booth, M., Reinhardt, S.P., and Roy, A. (2017). Partitioning Optimization Problems for Hybrid Classical\/Quantum Execution, D-Wave the Quantum Computing Company. Technical Report."},{"key":"ref_59","unstructured":"(2018, September 14). IBM ILOG CPLEX Optimizer. Available online: http:\/\/www-01.ibm.com\/software\/integration\/optimization\/cplex-optimizer."},{"key":"ref_60","unstructured":"(2018, September 14). METSlib An Open Source Tabu Search Metaheuristic framework in modern C++. Available online: http:\/\/projects.coin-or.org\/metslib."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/s10589-016-9844-y","article-title":"Building an iterative heuristic solver for a quantum annealer","volume":"65","author":"Rosenberg","year":"2016","journal-title":"Comput. Optim. Appl."},{"key":"ref_62","unstructured":"(2018, September 14). Qbsolv Software, Version 2000Q. Available online: https:\/\/www.dwavesys.com\/software."},{"key":"ref_63","unstructured":"(2018, September 14). D-Wave sOurce Code and Documentation. Available online: https:\/\/github.com\/dwavesystems\/qbsolv."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/10\/786\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:25:23Z","timestamp":1760196323000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/20\/10\/786"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,12]]},"references-count":63,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["e20100786"],"URL":"https:\/\/doi.org\/10.3390\/e20100786","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2018,10,12]]}}}