2017/09/21 by Mark Lewis, Lewis, Mark, Gary Kochenberger +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Optimization and Search Problems #Quantum Computing Algorithms and Architecture
paper · pdf · doi:10.48550/arxiv.1709.07511
openalex publication_date 2017/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we focus on the unconstrained binary quadratic optimization model, maximize xt Qx, x binary, and consider the problem of identifying optimal solutions that are robust with respect to perturbations in the Q matrix.. We are motivated to find robust, or stable, solutions because of the uncertainty inherent in the big data origins of Q and limitations in computer numerical precision, particularly in a new class of quantum annealing computers. Experimental design techniques are used to generate a diverse subset of possible scenarios, from which robust solutions are identified. An illustrative example with practical application to business decision making is examined. The approach presented also generates a surface response equation which is used to estimate upper bounds in constant time for Q instantiations within the scenario extremes. In addition, a theoretical framework for the robustness of individual xi variables is considered by examining the range of Q values over which the xi are predetermined.