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

• URL: http://arxiv.org/abs/2203.12633v1
• Date: Wed, 23 Mar 2022 18:00:03 GMT
• Title: Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization
• Authors: Alp Yurtsever and Tolga Birdal and Vladislav Golyanik
• Abstract summary: We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
• Score: 44.96576908957141
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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.

Related papers

• Quadratic versus Polynomial Unconstrained Binary Models for Quantum Optimization illustrated on Railway Timetabling [0.0]
  We present a generic method to reformulate any problem into a Polynomial Unconstrained Binary Optimization (PUBO) problem. We also provide a generic reformulation into a Quadratic Unconstrained Binary Optimization (QUBO) problem. Our results illustrate that the PUBO reformulation outperforms the QUBO one for the problem at hand.
  arXiv  Detail & Related papers  (2024-11-15T09:23:52Z)
• Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE [0.0]
  Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. This work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC to handle optimization with constraints.
  arXiv  Detail & Related papers  (2023-11-14T19:49:09Z)
• A hybrid algorithm for quadratically constrained quadratic optimization problems [8.90266532129563]
  We propose a variational quantum algorithm for general QCQPs. By encoding the variables on the amplitude of a quantum state, the requirement of the qubit number scales logarithmically with the dimension of the variables. Our numerical experiments on typical QCQP problems, including Max-Cut and optimal power flow problems, demonstrate a better performance of our hybrid algorithm over the classical counterparts.
  arXiv  Detail & Related papers  (2023-09-19T12:19:12Z)
• Quantum-based Distributed Algorithms for Edge Node Placement and Workload Allocation [8.937905773981702]
  We present a mixed-integer linear programming (MILP) model for optimal edge server placement and workload allocation. Existing quantum solvers are limited to solving unconstrained binary programming problems. Our numerical experiments demonstrate the practicality of leveraging quantum supremacy to solve complex optimization problems in edge computing.
  arXiv  Detail & Related papers  (2023-06-01T21:33:08Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  We develop a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate unconstrained binary optimization problems. We showcase the framework's performance on two inverse design problems by optimizing thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering.
  arXiv  Detail & Related papers  (2021-05-06T02:22:23Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Quantum Permutation Synchronization [88.4588059792167]
  We present QuantumSync, the quantum algorithm for solving a quantum vision problem in the context of computer vision. We show how to insert permutation constraints into a QUBO problem and to solve the constrained QUBO problem on the current generation of the abatic quantum DWave computer.
  arXiv  Detail & Related papers  (2021-01-19T17:51:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.