Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
arXiv:2208.05181 · doi:10.1109/TQE.2023.3293452
Abstract
In this paper, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search (GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, 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 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. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.
arXiv comment11 pages, 9 figures
References in corpus (14)
- Tight bounds on quantum searching
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
- Grover search revisited; application to image pattern matching
- Noise Threshold of Quantum Supremacy
- Optimizing Quantum Search Using a Generalized Version of Grover's Algorithm
- Graph Coloring with Quantum Annealing
- Quantum Search Algorithm for Binary Constant Weight Codes
Cited by in corpus (5)
- Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
- Quantum Speedup of the Dispersion and Codebook Design Problems
- Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
- A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
- Grover Adaptive Search with Spin Variables