  Quantum computing promises to solve difficult optimization problems in
chemistry, physics and mathematics more efficiently than classical computers,
but requires fault-tolerant quantum computers with millions of qubits. To
overcome errors introduced by today's quantum computers, hybrid algorithms
combining classical and quantum computers are used. In this paper we tackle the
multiple query optimization problem (MQO) which is an important NP-hard problem
in the area of data-intensive problems. We propose a novel hybrid
classical-quantum algorithm to solve the MQO on a gate-based quantum computer.
We perform a detailed experimental evaluation of our algorithm and compare its
performance against a competing approach that employs a quantum annealer --
another type of quantum computer. Our experimental results demonstrate that our
algorithm currently can only handle small problem sizes due to the limited
number of qubits available on a gate-based quantum computer compared to a
quantum computer based on quantum annealing. However, our algorithm shows a
qubit efficiency of close to 99% which is almost a factor of 2 higher compared
to the state of the art implementation. Finally, we analyze how our algorithm
scales with larger problem sizes and conclude that our approach shows promising
results for near-term quantum computers.
