Variational Quantum Algorithms for Euclidean Discrepancy and Covariate-Balancing
arXiv:2103.09090
Abstract
Algorithmic discrepancy theory seeks efficient algorithms to find those two-colorings of a set that minimize a given measure of coloring imbalance in the set, its {\it discrepancy}. The {\it Euclidean discrepancy} problem and the problem of balancing covariates in randomized trials have efficient randomized algorithms based on the Gram-Schmidt walk (GSW). We frame these problems as quantum Ising models, for which variational quantum algorithms (VQA) are particularly useful. Simulating an example of covariate-balancing on an IBM quantum simulator, we find that the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) yield results comparable to the GSW algorithm.
13 pages, 6 figures
References in corpus (9)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Ising formulations of many NP problems
- The theory of variational hybrid quantum-classical algorithms
- A Quantum Approximate Optimization Algorithm
- Robust determination of molecular spectra on a quantum processor
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Constructive Algorithms for Discrepancy Minimization
- Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth