Grover Adaptive Search with Spin Variables

Abstract

This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables $\{0,1\}$, we reformulate the problem using spin variables $\{+1,-1\}$ to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations.

13 pages, 9 figures

References in corpus (13)

• Ising formulations of many NP problems
• Validating quantum computers using randomized model circuits
• Efficient Z-Gates for Quantum Computing
• Quantum Computing for Finance: State of the Art and Future Prospects
• Optimization under Uncertainty in the Era of Big Data and Deep Learning: When Machine Learning Meets Mathematical Programming
• Grover Adaptive Search for Constrained Polynomial Binary Optimization
• Deterministic Preparation of Dicke States
• Linear-depth quantum circuits for multiqubit controlled gates
• Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
• Quantum Speedup of the Dispersion and Codebook Design Problems
• Linear decomposition of approximate multi-controlled single qubit gates