Grover Adaptive Search for Constrained Polynomial Binary Optimization

Abstract

In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.

arXiv comment11 pages, 15 figures

References in corpus (29)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• A Quantum Approximate Optimization Algorithm
• Towards Quantum Chemistry on a Quantum Computer
• Tight bounds on quantum searching
• Validating quantum computers using randomized model circuits
• Quantum computing for finance: overview and prospects
• Robustness of adiabatic quantum computation
• Quantum Computing for Finance: State of the Art and Future Prospects
• A Quantum Algorithm for Finding the Minimum
• A new quantum ripple-carry addition circuit
• Quantum Risk Analysis
• Warm-starting quantum optimization
• Halving the cost of quantum addition
• Quantum computational finance: Monte Carlo pricing of financial derivatives
• Amplitude estimation without phase estimation
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Improving Variational Quantum Optimization using CVaR
• Option Pricing using Quantum Computers
• Variational Quantum Linear Solver
• Addition on a Quantum Computer
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Characterization of a two-transmon processor with individual single-shot qubit readout
• Quantum Approximate Counting, Simplified
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Quantum computational finance: quantum algorithm for portfolio optimization
• Foundational Patterns for Efficient Quantum Computing

Cited by in corpus (45)

• Quantum computing for finance
• Challenges and Opportunities in Quantum Optimization
• Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
• Quantum Computing: Towards Industry Reference Problems
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• Constrained Optimization via Quantum Zeno Dynamics
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Grover search revisited; application to image pattern matching
• Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection
• A Grover search-based algorithm for the list coloring problem
• Muzzle the Shuttle: Efficient Compilation for Multi-Trap Trapped-Ion Quantum Computers
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Fermionic Quantum Approximate Optimization Algorithm
• Optimizing Quantum Search Using a Generalized Version of Grover's Algorithm
• Quantum Optimization for Training Quantum Neural Networks
• 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
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• A QUBO model of the RNA folding problem optimized by variational hybrid quantum annealing
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Quantum Algorithm for Smoothed Particle Hydrodynamics
• Coherence Fraction in Grover Search Algorithm
• A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
• Canonical Construction of Quantum Oracles
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Quantum Circuit Design for Decoded Quantum Interferometry
• Classification and transformations of quantum circuit decompositions for permutation operations
• A Quantum Approach for Optimal Transient Control in Network-Based Epidemic Models
• Quantum Global Minimum Finder based on Variational Quantum Search
• Approximate Phase Search and Eigen Estimation using Modified Grover's Algorithm
• Optimizing Quantum Search with a Binomial Version of Grover's Algorithm
• Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing
• Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application
• Grover Adaptive Search with Spin Variables
• The Quantum Ensemble Variational Optimization Algorithm: Applications to Molecular Inverse Design
• Gate Efficient Composition of Hamiltonian Simulation and Block-Encoding with its Application on HUBO, Chemistry and Finite Difference Method