Variational quantum algorithm for unconstrained black box binary optimization: Application to feature selection
arXiv:2205.03045 · doi:10.22331/q-2023-01-26-909
Abstract
We introduce a variational quantum algorithm to solve unconstrained black box binary optimization problems, i.e., problems in which the objective function is given as black box. This is in contrast to the typical setting of quantum algorithms for optimization where a classical objective function is provided as a given Quadratic Unconstrained Binary Optimization problem and mapped to a sum of Pauli operators. Furthermore, we provide theoretical justification for our method based on convergence guarantees of quantum imaginary time evolution. To investigate the performance of our algorithm and its potential advantages, we tackle a challenging real-world optimization problem: feature selection. This refers to the problem of selecting a subset of relevant features to use for constructing a predictive model such as fraud detection. Optimal feature selection -- when formulated in terms of a generic loss function -- offers little structure on which to build classical heuristics, thus resulting primarily in 'greedy methods'. This leaves room for (near-term) quantum algorithms to be competitive to classical state-of-the-art approaches. We apply our quantum-optimization-based feature selection algorithm, termed VarQFS, to build a predictive model for a credit risk data set with 20 and 59 input features (qubits) and train the model using quantum hardware and tensor-network-based numerical simulations, respectively. We show that the quantum method produces competitive and in certain aspects even better performance compared to traditional feature selection techniques used in today's industry.
References in corpus (38)
- Scikit-learn: Machine Learning in Python
- A variational eigenvalue solver on a quantum processor
- Efficient classical simulation of slightly entangled quantum computations
- Barren plateaus in quantum neural network training landscapes
- A Quantum Approximate Optimization Algorithm
- Error mitigation for short-depth quantum circuits
- Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
- Noise-Induced Barren Plateaus in Variational Quantum Algorithms
- Quantum optimization using variational algorithms on near-term quantum devices
- Variational ansatz-based quantum simulation of imaginary time evolution
- Quantum Natural Gradient
- An initialization strategy for addressing barren plateaus in parametrized quantum circuits
- Towards Quantum Machine Learning with Tensor Networks
- Warm-starting quantum optimization
- Unsupervised Generative Modeling Using Matrix Product States
- Improving Variational Quantum Optimization using CVaR
- What limits the simulation of quantum computers?
- Trainability of Dissipative Perceptron-Based Quantum Neural Networks
- Estimating the gradient and higher-order derivatives on quantum hardware
- Entanglement Devised Barren Plateau Mitigation
- Barren plateaus preclude learning scramblers
- Filtering variational quantum algorithms for combinatorial optimization
- Fisher Information in Noisy Intermediate-Scale Quantum Applications
- Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
- Supervised Learning with Quantum-Inspired Tensor Networks
- Holographic quantum algorithms for simulating correlated spin systems
- The Variational Power of Quantum Circuit Tensor Networks
- A case study of variational quantum algorithms for a job shop scheduling problem
- Error mitigation for universal gates on encoded qubits
- Reexamination of optimal quantum state estimation of pure states
- Characterizing the loss landscape of variational quantum circuits
- Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealers
- On the natural gradient for variational quantum eigensolver
- Quantum-Enhanced Simulation-Based Optimization
- Quantum Circuits For Two-Dimensional Isometric Tensor Networks
- Quantum statistical learning via Quantum Wasserstein natural gradient
- Simulating Large PEPs Tensor Networks on Small Quantum Devices
- Quantum Speedup of Natural Gradient for Variational Bayes