Quantum Speedup for the Quadratic Assignment Problem

• URL: http://arxiv.org/abs/2410.12181v1
• Date: Wed, 16 Oct 2024 03:00:37 GMT
• Title: Quantum Speedup for the Quadratic Assignment Problem
• Authors: Taku Mikuriya, Kein Yukiyoshi, Shintaro Fujiwara, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa,
• Abstract summary: We show that the search space of the quadratic assignment problem can be reduced using Grover adaptive search (GAS) with Dicke state operators. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty.
• Score: 6.106029308649016
• License:
• Abstract: We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with Dicke state operators. To that end, we first revise the traditional quadratic formulation of the QAP into a higher-order formulation, introducing a binary encoding method ordered by a descending Hamming weight, such that the number of terms in the objective function is reduced. We also show that the phase gate in the GAS can be replaced by a rotation gate about the Z axis, simplifying the quantum circuit without any penalty. Algebraic analyses in terms of the number of qubits, quantum gates, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Interestingly, it is suggested that the higher-order formulation is effective for problems whose size are powers of two, while the quadratic formulation is more effective for other sizes, indicating that switching between the two formulations can enhance the feasibility of the GAS-solved QAP.

Related papers

• Grover Adaptive Search with Spin Variables [3.190355298836875]
  We introduce a novel quantum dictionary subroutine that is designed for this spin-based algorithm. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit.
  arXiv  Detail & Related papers  (2024-10-15T14:24:27Z)
• Quantum Speedup of the Dispersion and Codebook Design Problems [6.735173690339397]
  Dispersion problems are optimization problems classified as NP-hard. We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm.
  arXiv  Detail & Related papers  (2024-06-11T12:00:50Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  We propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz. This ansatz applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence.
  arXiv  Detail & Related papers  (2023-12-12T01:36:49Z)
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations [2.9564164925541503]
  Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. We propose higher-order binary formulations that can simultaneously reduce the numbers of qubits and required gates.
  arXiv  Detail & Related papers  (2023-08-03T07:20:24Z)
• 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)
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem [2.840363325289377]
  We propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO) We conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by Grover adaptive search (GAS) Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation.
  arXiv  Detail & Related papers  (2022-08-10T06:59:43Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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.