A QAOA-Based Heuristic to Hide Sensitive Itemsets

The benefits of sharing transactional data with upstream supply chain partners has been known for a long time. However, many retailers are still reluctant to share, and there is evidence that the extent of sharing would be greater if information sensitive to retailers is concealed before data are shared. In transactional data, sensitive information are typically frequent itemsets that can be hidden by deleting items belonging to the sensitive itemsets from transactions that support the itemsets. The problem of identifying the smallest set of transactions from which to delete items such that sensitive itemsets will be hidden can be formulated as a generalized set covering problem. Numerous classical approaches have been developed for solving this problem. We propose a new approach to solve this optimization problem using QAOA. In our preliminary experiments, we find optimal solutions for small problems (that use up to 32 qubits) by using simulators and real quantum computers even when we use only one layer of QAOA. Identifying properties of the optimization problem should further help in faster convergence towards the optimal solutions of the optimization problem.