Multiple Query Optimization on the D-Wave 2X Adiabatic Quantum Computer
arXiv:1510.06437
Abstract
The D-Wave adiabatic quantum annealer solves hard combinatorial optimization problems leveraging quantum physics. The newest version features over 1000 qubits and was released in August 2015. We were given access to such a machine, currently hosted at NASA Ames Research Center in California, to explore the potential for hard optimization problems that arise in the context of databases. In this paper, we tackle the problem of multiple query optimization (MQO). We show how an MQO problem instance can be transformed into a mathematical formula that complies with the restrictive input format accepted by the quantum annealer. This formula is translated into weights on and between qubits such that the configuration minimizing the input formula can be found via a process called adiabatic quantum annealing. We analyze the asymptotic growth rate of the number of required qubits in the MQO problem dimensions as the number of qubits is currently the main factor restricting applicability. We experimentally compare the performance of the quantum annealer against other MQO algorithms executed on a traditional computer. While the problem sizes that can be treated are currently limited, we already find a class of problem instances where the quantum annealer is three orders of magnitude faster than other approaches.
References in corpus (7)
- Probing for quantum speedup in spin glass problems with planted solutions
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Quantum Annealing Implementation of Job-Shop Scheduling
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Benchmarking a quantum annealing processor with the time-to-target metric
- Training a Binary Classifier with the Quantum Adiabatic Algorithm
- Performance of a quantum annealer on range-limited constraint satisfaction problems
Cited by in corpus (5)
- Hybrid quantum computing with ancillas
- Finding Maximum Cliques on the D-Wave Quantum Annealer
- Towards Sampling from Nondirected Probabilistic Graphical models using a D-Wave Quantum Annealer
- Comparison of D-Wave Quantum Annealing and Classical Simulated Annealing for Local Minima Determination
- Multiple Query Optimization using a Hybrid Approach of Classical and Quantum Computing