Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
arXiv:2308.01572 · doi:10.1109/TQE.2024.3393437
Abstract
Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this paper, we propose higher-order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher-order formulations improve the convergence performance of GAS by both reducing the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.
11 pages, 8 figures
References in corpus (18)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- Halving the cost of quantum addition
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- Addition on a Quantum Computer
- Grover Adaptive Search for Constrained Polynomial Binary Optimization
- Resource-efficient digital quantum simulation of -level systems for photonic, vibrational, and spin- Hamiltonians
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
- Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding
- Short-Depth Circuits for Dicke State Preparation
- Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
- Quadratic and Higher-Order Unconstrained Binary Optimization of Railway Rescheduling for Quantum Computing
- Grover search under localized dephasing
- Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
- A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
- Quantum Search Algorithm for Binary Constant Weight Codes
Cited by in corpus (5)
- Quantum Software Engineering: Roadmap and Challenges Ahead
- Quantum Speedup of the Dispersion and Codebook Design Problems
- Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
- A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
- Grover Adaptive Search with Spin Variables