Quantum Speedup of the Dispersion and Codebook Design Problems

• URL: http://arxiv.org/abs/2406.07187v2
• Date: Wed, 11 Sep 2024 04:04:09 GMT
• Title: Quantum Speedup of the Dispersion and Codebook Design Problems
• Authors: Kein Yukiyoshi, Taku Mikuriya, Hyeon Seok Rou, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa,
• Abstract summary: 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.
• Score: 6.735173690339397
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm, offering quadratic speedup. Dispersion problems are combinatorial optimization problems classified as NP-hard, which appear often in coding theory and wireless communications applications involving optimal codebook design. In turn, GAS is a quantum exhaustive search algorithm that can be used to implement full-fledged maximum-likelihood optimal solutions. In conventional naive formulations however, it is typical to rely on a binary vector spaces, resulting in search space sizes prohibitive even for GAS. To circumvent this challenge, we instead formulate the search of optimal dispersion problem over Dicke states, an equal superposition of binary vectors with equal Hamming weights, which significantly reduces the search space leading to a simplification of the quantum circuit via the elimination of penalty terms. Additionally, we propose a method to replace distance coefficients with their ranks, contributing to the reduction of the number of qubits. Our analysis demonstrates that as a result of the proposed techniques a reduction in query complexity compared to the conventional GAS using Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.

Related papers

• Quantum Speedup for the Quadratic Assignment Problem [6.106029308649016]
  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.
  arXiv  Detail & Related papers  (2024-10-16T03:00:37Z)
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization [6.407238428292173]
  We introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space.
  arXiv  Detail & Related papers  (2024-10-08T05:48:46Z)
• Quantum Semidefinite Programming with Thermal Pure Quantum States [0.5639904484784125]
  We show that a quantization'' of the matrix multiplicative-weight algorithm can provide approximate solutions to SDPs quadratically faster than the best classical algorithms. We propose a modification of this quantum algorithm and show that a similar speedup can be obtained by replacing the Gibbs-state sampler with the preparation of thermal pure quantum (TPQ) states.
  arXiv  Detail & Related papers  (2023-10-11T18:00:53Z)
• 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)
• Quantum-inspired optimization for wavelength assignment [51.55491037321065]
  We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem. Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
  arXiv  Detail & Related papers  (2022-11-01T07:52:47Z)
• 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)
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory [61.12008553173672]
  We address the minimization problem of the Bregman divergence between an exponential subfamily and a mixture subfamily in a Bregman divergence system. We apply this algorithm to rate distortion and its variants including the quantum setting.
  arXiv  Detail & Related papers  (2022-01-07T13:33:28Z)
• 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)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• 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.