Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization | SpringerLink
Skip to main content
Springer Nature Link
Log in

Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization

  • Conference paper
  • First Online:
Computer Vision – ECCV 2022 (ECCV 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13683))

Included in the following conference series:

  • 2623 Accesses

Abstract

We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linearly-constrained, binary optimization problems on quantum annealers (QA). The computational premise of quantum computers has cultivated the re-design of various existing vision problems into quantum-friendly forms. Experimental QA realisations can solve a particular non-convex problem known as the quadratic unconstrained binary optimization (QUBO). Yet a naive-QUBO cannot take into account the restrictions on the parameters. To introduce additional structure in the parameter space, researchers have crafted ad-hoc solutions incorporating (linear) constraints in the form of regularizers. However, this comes at the expense of a hyper-parameter, balancing the impact of regularization. To date, a true constrained solver of quadratic binary optimization (QBO) problems has lacked. Q-FW first reformulates constrained-QBO as a copositive program (CP), then employs Frank-Wolfe iterations to solve CP while satisfying linear (in)equality constraints. This procedure unrolls the original constrained-QBO into a set of unconstrained QUBOs all of which are solved, in a sequel, on a QA. We use D-Wave Advantage QA to conduct synthetic and real experiments on two important computer vision problems, graph matching and permutation synchronization, which demonstrate that our approach is effective in alleviating the need for an explicit regularization coefficient.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Quantum computers are still in early stages. However, a diverse set of CV experiments present optimistic predictions regarding the future.

  2. 2.

    Throughout the paper we concentrate on the equality constraints and provide a simple modification to satisfy inequality constraints in our supplementary material.

  3. 3.

    Strong duality is a standard assumption for primal-dual methods in optimization.

  4. 4.

    This amounts to computing the top singular vector of \(\hat{\textbf{X}}\) [54].

  5. 5.

    A binary relation P(x, y), is in \(\textrm{FP}^{\textrm{NP}}\) if and only if there is a deterministic polynomial time algorithm that can determine whether P(x, y) holds given both x and y.

  6. 6.

    While still providing a way to handle inequalities in our supplementary material, we leave it as a future work to study problems with inequality constraints.

  7. 7.

    The difference between the lowest and second-lowest energy state/eigen-value.

  8. 8.

    Such sets are easy to obtain by keypoint detection or sampling either on images or on shapes, e.g. by detecting N landmarks per image, in a M-view image collection.

  9. 9.

    Requires solving a combinatorial optimization problem with heuristics.

References

  1. Albash, T., Lidar, D.A.: Adiabatic quantum computation. Rev. Mod. Phys. 90(1), 015002 (2018)

    Article  MathSciNet  Google Scholar 

  2. Arrigoni, F., Ricci, E., Pajdla, T.: Multi-frame motion segmentation by combining two-frame results. Int. J. Comput. Vision 130, 1–33 (2022)

    Article  Google Scholar 

  3. Arthur, D., Pusey-Nazzaro, L., et al.: Qubo formulations for training machine learning models. Sci. Rep. 11(1), 1–10 (2021)

    Google Scholar 

  4. Arute, F., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)

    Article  Google Scholar 

  5. Benkner, M.S., Lähner, Z., Golyanik, V., Wunderlich, C., Theobalt, C., Moeller, M.: Q-match: iterative shape matching via quantum annealing. In: Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 7586–7596 (2021)

    Google Scholar 

  6. Bernard, F., Theobalt, C., Moeller, M.: DS*: tighter lifting-free convex relaxations for quadratic matching problems. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2018

    Google Scholar 

  7. Birdal, T., Golyanik, V., Theobalt, C., Guibas, L.J.: Quantum permutation synchronization. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 13122–13133 (2021)

    Google Scholar 

  8. Birdal, T., Simsekli, U.: Probabilistic permutation synchronization using the riemannian structure of the birkhoff polytope. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11105–11116 (2019)

    Google Scholar 

  9. Birdal, T., Simsekli, U., Eken, M.O., Ilic, S.: Bayesian pose graph optimization via bingham distributions and tempered geodesic MCMC. In: Advances in Neural Information Processing Systems, vol. 31 (2018)

    Google Scholar 

  10. Bomze, I.M., Dür, M., De Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Global Optim. 18(4), 301–320 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bomze, I.M., Rinaldi, F., Zeffiro, D.: Frank-wolfe and friends: a journey into projection-free first-order optimization methods. 4OR 19(3), 313–345 (2021)

    Google Scholar 

  12. Born, M., Fock, V.: Beweis des adiabatensatzes. Zeitschrift für Physik 51(3), 165–180 (1928)

    Article  MATH  Google Scholar 

  13. Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120(2), 479–495 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  14. Caetano, T.S., McAuley, J.J., Cheng, L., Le, Q.V., Smola, A.J.: Learning graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1048–1058 (2009)

    Article  Google Scholar 

  15. Cai, J., Macready, W.G., Roy, A.: A practical heuristic for finding graph minors. arXiv e-prints (2014)

    Google Scholar 

  16. Cavallaro, G., Willsch, D., Willsch, M., Michielsen, K., Riedel, M.: Approaching remote sensing image classification with ensembles of support vector machines on the d-wave quantum annealer. In: IEEE International Geoscience and Remote Sensing Symposium (IGARSS) (2020)

    Google Scholar 

  17. Chin, T.J., Suter, D., Chng, S.F., Quach, J.: Quantum robust fitting. arXiv preprint arXiv:2006.06986 (2020)

  18. Cho, M., Alahari, K., Ponce, J.: Learning graphs to match. In: International Conference on Computer Vision (ICCV), pp. 25–32 (2013)

    Google Scholar 

  19. Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. ACM Trans. Algorithms (TALG) 6(4), 1–30 (2010)

    Google Scholar 

  20. D-Wave Systems Inc: dwave-system documentation (2022). https://docs.ocean.dwavesys.com/_/downloads/system/en/latest/pdf/. Accessed 05 Mar 2022

  21. Dai, A., Nießner, M., Zollhöfer, M., Izadi, S., Theobalt, C.: Bundlefusion: real-time globally consistent 3D reconstruction using on-the-fly surface reintegration. ACM Trans. Graph. (TOG) 36(4), 76a (2017)

    Article  Google Scholar 

  22. Dattani, N., Szalay, S., Chancellor, N.: Pegasus: the second connectivity graph for large-scale quantum annealing hardware. arXiv e-prints (2019)

    Google Scholar 

  23. De Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12(4), 875–892 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  24. Deng, H., Birdal, T., Ilic, S.: PPF-FoldNet: unsupervised learning of rotation invariant 3D local descriptors. In: Proceedings of the European Conference on Computer Vision (ECCV), pp. 602–618 (2018)

    Google Scholar 

  25. Doan, A.D., Sasdelli, M., Chin, T.J., Suter, D.: A hybrid quantum-classical algorithm for robust fitting. arXiv preprint arXiv:2201.10110 (2022)

  26. Dukanovic, I., Rendl, F.: Copositive programming motivated bounds on the stability and the chromatic numbers. Math. Program. 121(2), 249–268 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  27. Dür, M.: Copositive programming-a survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering, pp. 3–20. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12598-0_1

    Chapter  Google Scholar 

  28. Dür, M., Rendl, F.: Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems. EURO J. Comput. Optim. 9, 100021 (2021)

    Article  MathSciNet  Google Scholar 

  29. Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science 292(5516), 472–475 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  30. Frank, M., Wolfe, P., et al.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1–2), 95–110 (1956)

    Article  MathSciNet  Google Scholar 

  31. Gao, M., Lahner, Z., Thunberg, J., Cremers, D., Bernard, F.: Isometric multi-shape matching. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14183–14193 (2021)

    Google Scholar 

  32. Golyanik, V., Theobalt, C.: A quantum computational approach to correspondence problems on point sets. In: Computer Vision and Pattern Recognition (CVPR) (2020)

    Google Scholar 

  33. Govindu, V.M.: Lie-algebraic averaging for globally consistent motion estimation. In: Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2004, vol. 1, p. I. IEEE (2004)

    Google Scholar 

  34. 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 (1996)

    Google Scholar 

  35. Hazan, E.: Sparse approximate solutions to semidefinite programs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol. 4957, pp. 306–316. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78773-0_27

    Chapter  Google Scholar 

  36. Hu, F., Wang, B.N., Wang, N., Wang, C.: Quantum machine learning with d-wave quantum computer. Quantum Eng. 1(2), e12 (2019)

    Article  Google Scholar 

  37. Huang, J., Birdal, T., Gojcic, Z., Guibas, L.J., Hu, S.M.: Multiway non-rigid point cloud registration via learned functional map synchronization. arXiv preprint arXiv:2111.12878 (2021)

  38. Huang, J., et al.: Multibodysync: multi-body segmentation and motion estimation via 3D scan synchronization. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7108–7118 (2021)

    Google Scholar 

  39. Huang, Q.X., Guibas, L.: Consistent shape maps via semidefinite programming. In: Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (SGP). Eurographics Association (2013)

    Google Scholar 

  40. Huber, D.F., Hebert, M.: Fully automatic registration of multiple 3D data sets. Image Vis. Comput. 21(7), 637–650 (2003)

    Article  Google Scholar 

  41. Jaggi, M.: Revisiting frank-wolfe: projection-free sparse convex optimization. In: International Conference on Machine Learning, pp. 427–435. PMLR (2013)

    Google Scholar 

  42. Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse ising model. Phys. Rev. E 58, 5355–5363 (1998)

    Article  Google Scholar 

  43. Kezurer, I., Kovalsky, S.Z., Basri, R., Lipman, Y.: Tight relaxation of quadratic matching. In: Computer Graphics Forum, vol. 34, pp. 115–128. Wiley Online Library (2015)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  45. Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: Advances in Neural Information Processing Systems (NeurIPS), pp. 1097–1105 (2012)

    Google Scholar 

  46. Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2(1–2), 83–97 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  47. Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of frank-wolfe optimization variants. In: Advances in Neural Information Processing Systems, vol. 28 (2015)

    Google Scholar 

  48. Lan, G.: The complexity of large-scale convex programming under a linear optimization oracle. arXiv preprint arXiv:1309.5550

  49. Levitin, E., Polyak, B.: Constrained minimization methods. USSR Comput. Math. Math. Phys. 6(5), 1–50 (1966)

    Article  MATH  Google Scholar 

  50. Li, J., Ghosh, S.: Quantum-soft QUBO suppression for accurate object detection. In: Vedaldi, A., Bischof, H., Brox, T., Frahm, J.-M. (eds.) ECCV 2020. LNCS, vol. 12374, pp. 158–173. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-58526-6_10

    Chapter  Google Scholar 

  51. Li, X., Larson, M., Hanjalic, A.: Pairwise geometric matching for large-scale object retrieval. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5153–5161 (2015)

    Google Scholar 

  52. Maset, E., Arrigoni, F., Fusiello, A.: Practical and efficient multi-view matching. In: International Conference on Computer Vision (ICCV) (2017)

    Google Scholar 

  53. McGeoch, C., Farré, P.: The advantage system: performance update. Technical report, Technical Report 14-1054A-A, D-Wave Systems Inc., Burnaby, Canada (2021)

    Google Scholar 

  54. Mirsky, L.: Symmetric gauge functions and unitarily invariant norms. Q. J. Math. 11(1), 50–59 (1960)

    Article  MathSciNet  MATH  Google Scholar 

  55. Munkres, J.: Algorithms for the assignment and transportation problems. J. Soc. Ind. Appl. Math. 5(1), 32–38 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  56. Mur-Artal, R., Tardós, J.D.: ORB-SLAM2: an open-source SLAM system for monocular, stereo and RGB-D cameras. IEEE Trans. Rob. 33(5), 1255–1262 (2017). https://doi.org/10.1109/TRO.2017.2705103

    Article  Google Scholar 

  57. Neven, H., Denchev, V.S., Rose, G., Macready, W.G.: Qboost: large scale classifier training with adiabatic quantum optimization. In: Asian Conference on Machine Learning (ACML) (2012)

    Google Scholar 

  58. Neven, H., Rose, G., Macready, W.G.: Image recognition with an adiabatic quantum computer I. Mapping to quadratic unconstrained binary optimization. arXiv e-prints (2008)

    Google Scholar 

  59. Nguyen, N.T.T., Kenyon, G.T.: Image classification using quantum inference on the d-wave 2x. arXiv e-prints (2019)

    Google Scholar 

  60. Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)

    Google Scholar 

  61. Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discret. Optim. 6(3), 231–241 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  62. Technical description of the d-wave quantum processing unit. https://docs.dwavesys.com/docs/latest/doc_qpu.html. Accessed 05 Mar 2022

  63. Quist, A.J., de Klerk, E., Roos, C., Terlaky, T.: Copositive realxation for general quadratic programming. Optim. Methods Softw. 9(1–3), 185–208 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  64. Sahiner, A., Ergen, T., Pauly, J.M., Pilanci, M.: Vector-output relu neural network problems are copositive programs: convex analysis of two layer networks and polynomial-time algorithms. In: International Conference on Learning Representations (2020)

    Google Scholar 

  65. Sattler, T., Weyand, T., Leibe, B., Kobbelt, L.: Image retrieval for image-based localization revisited (2012)

    Google Scholar 

  66. Schonberger, J.L., Frahm, J.M.: Structure-from-motion revisited. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 4104–4113 (2016)

    Google Scholar 

  67. Seelbach Benkner, M., Golyanik, V., Theobalt, C., Moeller, M.: Adiabatic quantum graph matching with permutation matrix constraints. In: International Conference on 3D Vision (3DV) (2020)

    Google Scholar 

  68. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Annual Symposium on Foundations of Computer Science (1994)

    Google Scholar 

  69. Systems, D.: D-wave details product expansion & cross platform roadmap (2021). https://tinyurl.com/yeyknn7y

  70. Xiang, R., Lai, R., Zhao, H.: Efficient and robust shape correspondence via sparsity-enforced quadratic assignment. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9513–9522 (2020)

    Google Scholar 

  71. Yasuoka, H.: Computational complexity of quadratic unconstrained binary optimization. arXiv preprint arXiv:2109.10048 (2021)

  72. Yurtsever, A., Fercoq, O., Cevher, V.: A conditional-gradient-based augmented lagrangian framework. In: International Conference on Machine Learning, pp. 7272–7281. PMLR (2019)

    Google Scholar 

  73. Yurtsever, A., Fercoq, O., Locatello, F., Cevher, V.: A conditional gradient framework for composite convex minimization with applications to semidefinite programming. In: International Conference on Machine Learning, pp. 5727–5736. PMLR (2018)

    Google Scholar 

  74. Yurtsever, A., Tropp, J.A., Fercoq, O., Udell, M., Cevher, V.: Scalable semidefinite programming. SIAM J. Math. Data Sci. 3(1), 171–200 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  75. Zaech, J.N., Liniger, A., Danelljan, M., Dai, D., Van Gool, L.: Adiabatic quantum computing for multi object tracking. arXiv preprint arXiv:2202.08837 (2022)

  76. Zhou, X., Zhu, M., Daniilidis, K.: Multi-image matching via fast alternating minimization. In: International Conference on Computer Vision (ICCV), pp. 4032–4040 (2015)

    Google Scholar 

Download references

Acknowledgment

A.Y. received support from the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.

Author information

Authors and Affiliations

  1. Umeå University, Umeå, Sweden

    Alp Yurtsever

  2. Imperial College London, London, UK

    Tolga Birdal

  3. MPI Saarbrücken, Saarbrücken, Germany

    Vladislav Golyanik

Authors
  1. Alp Yurtsever
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tolga Birdal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vladislav Golyanik
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Vladislav Golyanik .

Editor information

Editors and Affiliations

  1. Tel Aviv University, Tel Aviv, Israel

    Shai Avidan

  2. University College London, London, UK

    Gabriel Brostow

  3. Google AI, Accra, Ghana

    Moustapha Cissé

  4. University of Catania, Catania, Italy

    Giovanni Maria Farinella

  5. Facebook (United States), Menlo Park, CA, USA

    Tal Hassner

1 Electronic supplementary material

Below is the link to the electronic supplementary material.

Supplementary material 1 (pdf 1861 KB)

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Yurtsever, A., Birdal, T., Golyanik, V. (2022). Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization. In: Avidan, S., Brostow, G., Cissé, M., Farinella, G.M., Hassner, T. (eds) Computer Vision – ECCV 2022. ECCV 2022. Lecture Notes in Computer Science, vol 13683. Springer, Cham. https://doi.org/10.1007/978-3-031-20050-2_21

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-20050-2_21

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-20049-6

  • Online ISBN: 978-3-031-20050-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics