Quantum-accelerated constraint programming

• URL: http://arxiv.org/abs/2103.04502v2
• Date: Tue, 21 Sep 2021 00:22:25 GMT
• Title: Quantum-accelerated constraint programming
• Authors: Kyle E. C. Booth, Bryan O'Gorman, Jeffrey Marshall, Stuart Hadfield, Eleanor Rieffel
• Abstract summary: Constraint (CP) is a paradigm used to model and solve constraint satisfaction and programming optimization problems. We show how quantum algorithms can accelerate CP, at both the levels of inference and search.
• Score: 0.377986002491873
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constraint programming (CP) is a paradigm used to model and solve constraint satisfaction and combinatorial optimization problems. In CP, problems are modeled with constraints that describe acceptable solutions and solved with backtracking tree search augmented with logical inference. In this paper, we show how quantum algorithms can accelerate CP, at both the levels of inference and search. Leveraging existing quantum algorithms, we introduce a quantum-accelerated filtering algorithm for the $\texttt{alldifferent}$ global constraint and discuss its applicability to a broader family of global constraints with similar structure. We propose frameworks for the integration of quantum filtering algorithms within both classical and quantum backtracking search schemes, including a novel hybrid classical-quantum backtracking search method. This work suggests that CP is a promising candidate application for early fault-tolerant quantum computers and beyond.

Related papers

• Quantum Optimization Algorithms [1.5571090040924025]
  We motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers.<n>An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem.<n>We outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.
  arXiv  Detail & Related papers  (2025-11-15T22:53:57Z)
• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms [0.0]
  We explore a class of hybrid quantum algorithms that are closely related to classical greedy or local search algorithms.<n>We develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems.
  arXiv  Detail & Related papers  (2025-09-02T18:00:05Z)
• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  We propose a new approach to utilize quantum computers for binary linear programming (BLP) Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP. In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework.
  arXiv  Detail & Related papers  (2025-03-27T07:24:33Z)
• Quantum Approximate Optimisation Applied to Graph Similarity [0.0]
  We introduce a novel quantum optimisation simulation package facilitating investigation of all constituent components of the QAOA. We investigate eight classical optimisation methods each at six levels of decomposition. An encoding for permutation based problems such as graph similarity through edge overlap to the QAOA allows for significant quantum memory savings.
  arXiv  Detail & Related papers  (2024-12-23T06:04:08Z)
• Scaling Up the Quantum Divide and Conquer Algorithm for Combinatorial Optimization [0.8121127831316319]
  We propose a method for constructing quantum circuits which greatly reduces inter-device communication costs. We show that we can construct tractable circuits nearly three times the size of previous QDCA methods while retaining a similar or greater level of quality.
  arXiv  Detail & Related papers  (2024-05-01T20:49:50Z)
• A quantum annealing approach to the minimum distance problem of quantum codes [0.0]
  We introduce an approach to compute the minimum distance of quantum stabilizer codes by reformulating the problem as a Quadratic Unconstrained Binary Optimization problem. We demonstrate practical viability of our method by comparing the performance of purely classical algorithms with the D-Wave Advantage 4.1 quantum annealer.
  arXiv  Detail & Related papers  (2024-04-26T21:29:42Z)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Quantum computing has been used to attempt to solve these problems using a range of algorithms. This work presents a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach.
  arXiv  Detail & Related papers  (2024-03-05T17:46:04Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• 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)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• 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)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.