  Given a large dataset of many tuples, it is hard for users to pick out their
preferred tuples. Thus, the preference query problem, which is to find the most
preferred tuples from a dataset, is widely discussed in the database area. In
this problem, a utility function is given by the user to evaluate to what
extent the user prefers a tuple. However, considering a dataset consisting of N
tuples, the existing algorithms need O(N) time to answer a query, or need O(N)
time for a cold start to answer a query. The reason is that in a classical
computer, a linear time is needed to evaluate the utilities by the utility
function for N tuples. In this paper, we discuss the Quantum Preference Query
(QPQ) problem, where the dataset is given in a quantum memory, and we use a
quantum computer to return the answers. Due to quantum parallelism, the quantum
algorithm can theoretically perform better than their classical competitors. We
discuss this problem in different kinds of input and output. In the QPQ
problem, the input can be a number k or a threshold theta. Given k, the problem
is to return k tuples with the highest utilities. Given theta, the problem is
to return all the tuples with utilities higher than theta. Also, in QPQ
problem, the output can be classical (i.e., a list of tuples) or quantum (i.e.,
a superposition in quantum bits). We proposed four quantum algorithms to solve
the problems in the above four scenarios. We analyze the number of memory
accesses needed for each quantum algorithm, which shows that the proposed
quantum algorithms are at least quadratically faster than their classical
competitors. In our experiments, we show that to answer a QPQ problem, the
quantum algorithms achieve up to 1000x improvement in number of memory accesses
than their classical competitors, which proved that QPQ problem could be a
future direction of the study of preference query problems.
