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

arXiv: https://arxiv.org/abs/2203.12633 · HTML: https://mlsanity.com/paper/2203.12633/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 83 references that are in the map.
- First posted on arXiv 23 Mar 2022.

## Builds on (most cited first, 30 of 34)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [ORB-SLAM2: an Open-Source SLAM System for Monocular, Stereo and RGB-D Cameras](https://mlsanity.com/paper/1610.06475/) (2016)
- [PPF-FoldNet: Unsupervised Learning of Rotation Invariant 3D Local Descriptors](https://mlsanity.com/paper/1808.10322/) (2018)
- [Learning multiview 3D point cloud registration](https://mlsanity.com/paper/2001.05119/) (2020)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [MultiBodySync: Multi-Body Segmentation and Motion Estimation via 3D Scan Synchronization](https://mlsanity.com/paper/2101.06605/) (2021)
- [Scalable Semidefinite Programming](https://mlsanity.com/paper/1912.02949/) (2019)
- [Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms](https://mlsanity.com/paper/2012.13329/) (2020)
- [Multi-Image Matching via Fast Alternating Minimization](https://mlsanity.com/paper/1505.04845/) (2015)
- [QUBO Formulations for Training Machine Learning Models](https://mlsanity.com/paper/2008.02369/) (2020)
- [Isometric Multi-Shape Matching](https://mlsanity.com/paper/2012.02689/) (2020)
- [Quantum Permutation Synchronization](https://mlsanity.com/paper/2101.07755/) (2021)
- [Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronization](https://mlsanity.com/paper/2111.12878/) (2021)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [Learning Transformation Synchronization](https://mlsanity.com/paper/1901.09458/) (2019)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [A practical heuristic for finding graph minors](https://mlsanity.com/paper/1406.2741/) (2014)
- [Probabilistic Permutation Synchronization using the Riemannian Structure of the Birkhoff Polytope](https://mlsanity.com/paper/1904.05814/) (2019)
- [A Quantum Computational Approach to Correspondence Problems on Point Sets](https://mlsanity.com/paper/1912.12296/) (2019)
- [Adiabatic Quantum Computing for Multi Object Tracking](https://mlsanity.com/paper/2202.08837/) (2022)
- [DS*: Tighter Lifting-Free Convex Relaxations for Quadratic Matching Problems](https://mlsanity.com/paper/1711.10733/) (2017)
- [Adiabatic Quantum Graph Matching with Permutation Matrix Constraints](https://mlsanity.com/paper/2107.04032/) (2021)
- [Bayesian Pose Graph Optimization via Bingham Distributions and Tempered Geodesic MCMC](https://mlsanity.com/paper/1805.12279/) (2018)
- [Synchronizing Probability Measures on Rotations via Optimal Transport](https://mlsanity.com/paper/2004.00663/) (2020)
- [Quantum-soft QUBO Suppression for Accurate Object Detection](https://mlsanity.com/paper/2007.13992/) (2020)
- [A Hybrid Quantum-Classical Algorithm for Robust Fitting](https://mlsanity.com/paper/2201.10110/) (2022)
- [Image classification using quantum inference on the D-Wave 2X](https://mlsanity.com/paper/1905.13215/) (2019)
- [Quantum Robust Fitting](https://mlsanity.com/paper/2006.06986/) (2020)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)

## Built on by (most cited first, 8 of 8)

- [Quantum Multi-Model Fitting](https://mlsanity.com/paper/2303.15444/) (2023)
- [3D-QAE: Fully Quantum Auto-Encoding of 3D Point Clouds](https://mlsanity.com/paper/2311.05604/) (2023)
- [Robust Fitting on a Gate Quantum Computer](https://mlsanity.com/paper/2409.02006/) (2024)
- [Quantum-enhanced Computer Vision: Going Beyond Classical Algorithms](https://mlsanity.com/paper/2510.07317/) (2025)
- [QuAnt: Quantum Annealing with Learnt Couplings](https://mlsanity.com/paper/2210.08114/) (2022)
- [Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradients](https://mlsanity.com/paper/2310.15128/) (2023)
- [Quantum Annealing for Computer Vision Minimization Problems](https://mlsanity.com/paper/2312.12848/) (2023)
- [Spherical and Hyperbolic Toric Topology-Based Codes On Graph Embedding for Ising MRF Models: Classical and Quantum Topology Machine Learning](https://mlsanity.com/paper/2307.15778/) (2023)

## Abstract (arXiv)

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 realizations 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.